LeetCode 算法笔记 Part3

发表于|更新于|LeetCode
字数总计:5k|阅读时长:26分钟|阅读量:…
文章最后更新于 979 天前，其中的信息可能已经过时。

本文主要记录了博主的 Leetcode 算法刷题记录，方便以后查询复习。

图论

岛屿数量

LeetCode 原题链接：200. 岛屿数量

深度优先遍历，基本思路为，遇到一个岛就把这个岛给沉没掉，然后统计数加 1。

JS
/**
 * @param {character[][]} grid
 * @return {number}
 */
const numIslands = (grid) => {
  const m = grid.length,
    n = grid[0].length;
  const dfs = (i, j) => {
    if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] === "0") {
      return;
    }
    grid[i][j] = "0";
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  };
  let count = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        count++;
        dfs(i, j);
      }
    }
  }
  return count;
};

腐烂的橘子

LeetCode 原题链接：994. 腐烂的橘子

广度优先遍历，利用循环比较好做，这边需要注意广度优先遍历的一些条件，辅助函数用于推入队列，上下左右扩散的过程还是由循环过程去做。

JS
/**
 * @param {number[][]} grid
 * @return {number}
 */
const orangesRotting = (grid) => {
  const m = grid.length,
    n = grid[0].length;
  const queue = [];


  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) {
        queue.push([i, j]);
      }
    }
  }


  const step = (i, j, arr) => {
    if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] !== 1) {
      return;
    }
    grid[i][j] = 2;
    arr.push([i, j]);
  };


  let count = 0;
  while (queue.length) {
    const tempArr = [];
    while (queue.length) {
      const [i, j] = queue.shift();
      step(i + 1, j, tempArr);
      step(i - 1, j, tempArr);
      step(i, j + 1, tempArr);
      step(i, j - 1, tempArr);
    }
    if (tempArr.length) {
      count++;
      queue.push(...tempArr);
    }
  }


  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        return -1;
      }
    }
  }


  return count;
};


console.log(orangesRotting([[0, 2]]));

课程表

LeetCode 原题链接：207. 课程表

广度优先遍历，采用图和入度的概念进行求解。

  1. 构建入度数组，使用哈希表以该课程为键，依赖该课程的数组为值，建立哈希表。
  2. 将入度为 0 的数组推入队列。
  3. 迭代，入度为零的课程继续推入队列
JS
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
const canFinish = (numCourses, prerequisites) => {
  const inDegArr = new Array(numCourses).fill(0);
  const map = new Map();
  for (let i = 0; i < prerequisites.length; i++) {
    inDegArr[prerequisites[i][0]]++;
    if (map.has(prerequisites[i][1])) {
      map.get(prerequisites[i][1]).push(prerequisites[i][0]);
    } else {
      map.set(prerequisites[i][1], [prerequisites[i][0]]);
    }
  }
  const queue = [];
  for (let i = 0; i < inDegArr.length; i++) {
    if (inDegArr[i] === 0) {
      queue.push(i);
    }
  }
  let count = 0;
  while (queue.length) {
    const course = queue.shift();
    count++;
    const depArr = map.get(course);
    if (depArr) {
      for (const dep of depArr) {
        inDegArr[dep]--;
        if (inDegArr[dep] === 0) {
          queue.push(dep);
        }
      }
    }
  }
  return count === numCourses;
};

实现 Trie (前缀树)

LeetCode 原题链接：208. 实现 Trie (前缀树)

采用迭代对象来求解，可以考虑使用数组的reduce方法。

JS
class Trie {
  constructor() {
    this.children = {};
  }


  insert(word) {
    let node = this.children;
    for (const ch of word) {
      if (!node[ch]) {
        node[ch] = {};
      }
      node = node[ch];
    }
    node.isEnd = true;
  }
  searchPrefix(prefix) {
    let node = this.children;
    for (const ch of prefix) {
      if (!node[ch]) {
        return false;
      }
      node = node[ch];
    }
    return node;
  }
  search(word) {
    const node = this.searchPrefix(word);
    return node !== undefined && node.isEnd !== undefined;
  }
  startsWith(prefix) {
    return this.searchPrefix(prefix);
  }
}

回溯

全排列

LeetCode 原题链接：46. 全排列

无他，惟手熟尔。😊

JS
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const permute = (nums) => {
  const step = (arr) => {
    if (arr.length <= 1) return [arr];
    if (arr.length === 2) {
      return [
        [arr[0], arr[1]],
        [arr[1], arr[0]],
      ];
    }
    if (arr.length >= 3) {
      const res = [];
      for (let i = 0; i < arr.length; i++) {
        const tempArr = arr.filter((item) => item !== arr[i]);
        const tmpRes = step(tempArr);
        for (const temp of tmpRes) {
          res.push([arr[i]].concat(temp));
        }
      }
      return res;
    }
  };
  return step(nums);
};


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const permute0 = (nums) => {
  const res = [];
  const step = (first) => {
    if (first === nums.length) {
      res.push([...nums]);
    }
    for (let i = first; i < nums.length; i++) {
      [nums[first], nums[i]] = [nums[i], nums[first]];
      step(first + 1);
      [nums[first], nums[i]] = [nums[i], nums[first]];
    }
  };
  step(0);
  return res;
};
console.log(permute0([1, 2, 3]));

字集

LeetCode 原题链接：78. 字集

可采用幂集算法和深度遍历解决。 对于幂集算法

  1. 左移n位，循环。
  2. 循环数组的长度次，推入所有的有效数字。
JS
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const subsets = (nums) => {
  const res = [];
  for (let i = 0; i < 1 << nums.length; i++) {
    const temp = [];
    for (let j = 0; j < nums.length; j++) {
      if (i & (1 << j)) {
        temp.push(nums[j]);
      }
    }
    res.push(temp);
  }
  return res;
};


const subsets = function (nums) {
  const temp = [];
  const res = [];
  const dfs = (cur) => {
    if (cur === nums.length) {
      res.push([...temp]);
      return;
    }
    temp.push(nums[cur]);
    dfs(cur + 1);
    temp.pop();
    dfs(cur + 1);
  };
  dfs(0);
  return res;
};

电话号码的数字组合

LeetCode 原题链接：17. 电话号码的数字组合

采用回溯算法，从前面回溯到后面

JS
/**
 * @param {string} digits
 * @return {string[]}
 */
const letterCombinations = (digits) => {
  if (digits.length === 0) {
    return [];
  }
  const map = new Map([
    ["2", "abc"],
    ["3", "def"],
    ["4", "ghi"],
    ["5", "jkl"],
    ["6", "mno"],
    ["7", "pqrs"],
    ["8", "tuv"],
    ["9", "wxyz"],
  ]);
  const res = [];
  const step = (str, index) => {
    if (index === digits.length) {
      res.push(str);
      return;
    }
    const charSet = map.get(digits[index]);
    for (const char of charSet) {
      step(str + char, index + 1);
    }
  };
  step("", 0);
  return res;
};

组合总和

LeetCode 原题链接：39. 组合总和

排序candidates数组，递归回溯，选择当前数字或者不选择当前数字然后跳过。

JS
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
const combinationSum = (candidates, target) => {
  const res = [];
  candidates.sort((a, b) => a - b);
  const step = (curVal, index, arr) => {
    if (index === candidates.length) {
      return;
    }
    if (curVal === 0) {
      res.push(arr);
      return;
    }
    if (candidates[index] < curVal) {
      step(curVal, index + 1, arr);
    }
    if (curVal - candidates[index] >= 0) {
      step(curVal - candidates[index], index, [...arr, candidates[index]]);
    }
  };
  step(target, 0, []);
  return res;
};

括号总和

LeetCode 原题链接：22. 括号生成

采用深度遍历的方式进行求解，左侧括号在小于num的情况下可以一直推入，右侧括号只有在左侧括号数量大于右侧括号才能推入。非常经典的回溯加剪枝。

JS
/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis = (n) => {
  const res = [];
  const dfs = (str, left, right) => {
    if (left === n && right === n) {
      res.push(str);
    }
    if (left > right) {
      dfs(str + ")", left, right + 1);
    }
    if (left < n) {
      dfs(str + "(", left + 1, right);
    }
  };
  dfs("", 0, 0);
  return res;
};

单词搜索

LeetCode 原题链接：79. 单词搜索

谨慎使用fill方法，主要利用深度遍历与标记数组。通过每个数组都尝试遍历。注意空数组不会被Map等方法遍历，需要先fill值再遍历。

JS
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
const exist = (board, word) => {
  const rowLen = board.length;
  const colLen = board[0].length;
  const visited = new Array(rowLen)
    .fill(0)
    .map(() => new Array(colLen).fill(false));
  const dfs = (i, j, k) => {
    if (k === word.length) {
      return true;
    }
    if (i < 0 || i > rowLen - 1 || j < 0 || j > colLen - 1 || visited[i][j]) {
      return;
    }
    if (board[i][j] === word[k]) {
      visited[i][j] = true;
      const flag =
        dfs(i - 1, j, k + 1) ||
        dfs(i + 1, j, k + 1) ||
        dfs(i, j - 1, k + 1) ||
        dfs(i, j + 1, k + 1);
      visited[i][j] = false;
      return flag;
    }
  };
  for (let i = 0; i < rowLen; i++) {
    for (let j = 0; j < colLen; j++) {
      if (dfs(i, j, 0)) {
        return true;
      }
    }
  }
  return false;
};

分割回文串

LeetCode 原题链接： 131. 分割回文串

深度遍历加上动态规划。我能说我其实是背下来的吗？🤧

JS
/**
 * @param {string} s
 * @return {string[][]}
 */
const partition = (s) => {
  const n = s.length,
    ans = [],
    res = [];
  const f = new Array(n).fill(0).map(() => new Array(n).fill(true));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
    }
  }


  const step = (i) => {
    if (i === n) {
      res.push([...ans]);
      return;
    }
    for (let j = i; j < n; j++) {
      if (f[i][j]) {
        ans.push(s.slice(i, j + 1));
        step(j + 1);
        ans.pop();
      }
    }
  };


  step(0);
  return res;
};

N 皇后

LeetCode 原题链接：51. N 皇后

JS
/**
 * @param {number} n
 * @return {string[][]}
 */
const solveNQueens = (n) => {
  const ans = [];
  const col = new Array(n).fill(0);
  const onPath = new Array(n).fill(false);
  const diag1 = new Array(n * 2 - 1).fill(false);
  const diag2 = new Array(n * 2 - 1).fill(false);
  const dfs = (r) => {
    if (r === n) {
      ans.push(col.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - 1 - c)));
      return;
    }
    for (let c = 0; c < n; c++) {
      if (!onPath[c] && !diag1[r + c] && !diag2[r - c]) {
        col[r] = c;
        onPath[c] = diag1[r + c] = diag2[r - c] = true;
        dfs(r + 1);
        onPath[c] = diag1[r + c] = diag2[r - c] = false; // 恢复现场
      }
    }
  };
  dfs(0);
  return ans;
};


/**
 * @param {number} n
 * @return {string[][]}
 */
const solveNQueens = (n) => {
  const arr = new Array(n);
  const res = [];
  const judge = (row) => {
    for (let i = 0; i < row; i++) {
      if (arr[i] === arr[row] || row - i === Math.abs(arr[row] - arr[i]))
        return false;
    }
    return true;
  };
  const step = (count) => {
    if (count === n) {
      const temp = [];
      for (const item of arr) {
        const strArr = new Array(n).fill(".");
        strArr[item] = "Q";
        temp.push(strArr.join(""));
      }
      res.push(temp);
      return;
    }
    for (let i = 0; i < n; i++) {
      arr[count] = i;
      if (judge(count)) {
        step(count + 1);
      }
    }
  };
  step(0);
  return res;
};


console.log(solveNQueens(4));

二分查找

搜索插入位置

LeetCode 原题链接：35. 搜索插入位置

二分查找的变式，稍作修改，注意ans的初始值需要设置为num.length来处理越界情况。

JS
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const searchInsert = (nums, target) => {
  let low = 0,
    high = nums.length - 1,
    ans = nums.length;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (target <= nums[mid]) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
};

搜索二维矩阵

LeetCode 原题链接：74. 搜索二维矩阵

依旧是二分查找的变式，查找到大于当前数字的一行，然后对当前这一行进行二分查找。另外这里例子是Z字型查找的一个特例，也可使用Z字型查找的方式，更简单。

JS
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
const searchMatrix = (matrix, target) => {
  const binarySearchRow = () => {
    let low = 0,
      high = matrix.length - 1,
      ans = 0;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (target < matrix[mid][0]) {
        high = mid - 1;
      } else if (target >= matrix[mid][0]) {
        ans = mid;
        low = mid + 1;
      }
    }
    return ans;
  };
  const binarySearchCol = (index) => {
    let low = 0,
      high = matrix[0].length - 1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (target < matrix[index][mid]) {
        high = mid - 1;
      } else if (target > matrix[index][mid]) {
        low = mid + 1;
      } else {
        return true;
      }
    }
    return false;
  };
  const index = binarySearchRow();
  return binarySearchCol(index);
};

在排序数组中查找元素的第一个和最后一个位置

LeetCode 原题链接：34. 在排序数组中查找元素的第一个和最后一个位置

二分查找的变式，注意如何查找到第一次出现的元素与最后一次出现的元素，这边采取循环的方式更好写一些。

JS
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const searchRange = (nums, target) => {
  const binarySearch = (low, high, flag) => {
    if (low > high) {
      return -1;
    }
    const mid = Math.floor((low + high) / 2);
    if (target > nums[mid]) {
      return binarySearch(mid + 1, high, flag);
    } else if (target < nums[mid]) {
      return binarySearch(low, mid - 1, flag);
    } else {
      if (flag) {
        if (mid === 0 || nums[mid - 1] < nums[mid]) {
          return mid;
        } else {
          return binarySearch(low, mid - 1, flag);
        }
      } else {
        if (mid === nums.length - 1 || nums[mid] < nums[mid + 1]) {
          return mid;
        } else {
          return binarySearch(mid + 1, high, flag);
        }
      }
    }
  };
  const left = binarySearch(0, nums.length - 1, true);
  const right = binarySearch(0, nums.length - 1, false);
  return [left, right];
};


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const searchRange = (nums, target) => {
  const binarySearch = (flag) => {
    let low = 0,
      high = nums.length - 1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (target > nums[mid]) {
        low = mid + 1;
      } else if (target < nums[mid]) {
        high = mid - 1;
      } else {
        if (flag) {
          if (mid !== 0 && nums[mid - 1] === nums[mid]) {
            high = mid - 1;
          } else {
            return mid;
          }
        } else {
          if (mid !== nums.length - 1 && nums[mid] === nums[mid + 1]) {
            low = mid + 1;
          } else {
            return mid;
          }
        }
      }
    }
    return -1;
  };
  return [binarySearch(true), binarySearch(false)];
};

搜索旋转排序数组

LeetCode 原题链接：33. 搜索旋转排序数组

来详细讲解一下这道题目的思路

考虑mid在前区间与后区间的两种情况

  1. 在前区间：只有满足target >= nums[0] && target < nums[mid]的情况才有high = mid - 1其他情况都是low = mid + 1。
  2. 在后区间：只有满足target > nums[mid] && target <= nums[n - 1]才有low = mid + 1其他情况都是high = mid - 1。
  3. 注意前区间必须是满足>=以确定边缘情况。
JS
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = (nums, target) => {
  const n = nums.length;
  if (n === 0) return -1;
  if (n === 1) return nums[0] === target ? 0 : -1;
  let low = 0,
    high = n - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (target === nums[mid]) return mid;
    if (nums[mid] >= nums[0]) {
      if (target >= nums[0] && target < nums[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {
      if (target > nums[mid] && target <= nums[n - 1]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  return -1;
};

寻找旋转排序数组中的最小值

LeetCode 原题链接：153. 寻找旋转排序数组中的最小值

JS
/**
 * @param {number[]} nums
 * @return {number}
 */
const findMin = (nums) => {
  const n = nums.length;
  if (n <= 1) return nums[0];
  if (nums[0] <= nums[n - 1]) return nums[0];
  let low = 0,
    high = n - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (nums[mid] < nums[mid - 1]) {
      return nums[mid];
    }
    if (nums[mid] >= nums[0]) {
      low = mid + 1;
    }
    if (nums[mid] < nums[n - 1]) {
      high = mid - 1;
    }
  }
};


console.log(findMin([2, 1]));

寻找两个正序数组的中位数

LeetCode 原题链接：4. 寻找两个正序数组的中位数

技巧性较强的题目，菜就多练。🦀

JS
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const findMedianSortedArrays = (nums1, nums2) => {
  const getKthEl = (nums1, nums2, k) => {
    let index1 = 0,
      index2 = 0;
    while (true) {
      if (index1 === nums1.length) {
        return nums2[index2 + k - 1];
      }
      if (index2 === nums2.length) {
        return nums1[index1 + k - 1];
      }
      if (k === 1) {
        return Math.min(nums1[index1], nums2[index2]);
      }
      const half = Math.floor(k / 2);
      const newIndex1 = Math.min(index1 + half, nums1.length) - 1;
      const newIndex2 = Math.min(index2 + half, nums2.length) - 1;
      if (nums1[newIndex1] <= nums2[newIndex2]) {
        k -= newIndex1 - index1 + 1;
        index1 = newIndex1 + 1;
      } else {
        k -= newIndex2 - index2 + 1;
        index2 = newIndex2 + 1;
      }
    }
  };
  const totalLength = nums1.length + nums2.length;
  if (totalLength % 2 === 1) {
    const midIndex = Math.floor(totalLength / 2);
    return getKthEl(nums1, nums2, midIndex + 1);
  } else {
    const midIndex = totalLength / 2;
    return (
      (getKthEl(nums1, nums2, midIndex) +
        getKthEl(nums1, nums2, midIndex + 1)) /
      2
    );
  }
};

栈

有效括号

LeetCode 原题链接：20. 有效括号

非常经典的题目，细心点就可以做出来。

JS
/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = (s) => {
  const stack = [];
  const map = new Map([
    ["(", ")"],
    ["{", "}"],
    ["[", "]"],
  ]);
  for (const char of s) {
    if (stack.length && map.get(stack[stack.length - 1]) === char) {
      stack.pop();
      continue;
    }
    stack.push(char);
  }
  return stack.length ? false : true;
};

最小栈

LeetCode 原题链接：155. 最小栈

采用辅助栈进行求解，注意考虑栈为空的边缘情况。

JS
class MinStack {
  constructor() {
    this.arr = [];
    this.MinStack = [];
  }
  push(el) {
    this.arr.push(el);
    if (
      !this.MinStack.length ||
      el <= this.MinStack[this.MinStack.length - 1]
    ) {
      this.MinStack.push(el);
    }
  }


  pop() {
    const el = this.arr.pop();
    if (
      this.MinStack.length &&
      el === this.MinStack[this.MinStack.length - 1]
    ) {
      this.MinStack.pop();
    }
    return el;
  }


  top() {
    return this.arr[this.arr.length - 1];
  }


  getMin() {
    return this.MinStack[this.MinStack.length - 1];
  }
}

字符串解码

LeetCode 原题链接：394. 字符串解码

可采用正则表达式的解法与数字栈与字符栈的解法来计算，类似逆波兰表达式的计算。注意对多位数字的置零处理，和字符串栈的转换。

JS
const decodeString = (s) => {
  while (s.includes("[")) {
    // 正则匹配每一组编码，其中n为数字，s为字符
    s = s.replace(/(\d+)\[([a-z]+)\]/g, (_, n, s) => s.repeat(n));
  }
  return s;
};


const decodeString = (s) => {
  let numStack = []; // 存倍数的栈
  let strStack = []; // 存 待拼接的str 的栈
  let num = 0; // 倍数的“搬运工”
  let result = ""; // 字符串的“搬运工”
  for (const char of s) {
    // 逐字符扫描
    if (!isNaN(char)) {
      // 遇到数字
      num = num * 10 + Number(char); // 算出倍数
    } else if (char == "[") {
      // 遇到 [
      strStack.push(result); // result串入栈
      result = ""; // 入栈后清零
      numStack.push(num); // 倍数num进入栈等待
      num = 0; // 入栈后清零
    } else if (char == "]") {
      // 遇到 ]，两个栈的栈顶出栈
      let repeatTimes = numStack.pop(); // 获取拷贝次数
      result = strStack.pop() + result.repeat(repeatTimes); // 构建子串
    } else {
      result += char; // 遇到字母，追加给result串
    }
  }
  return result;
};

每日温度

LeetCode 原题链接：739. 每日温度

注意栈中存储的是数组的下标，单调栈一般是遇到大的元素开始做相关的操作。

JS
/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
const dailyTemperatures = (temperatures) => {
  const stack = [];
  const arr = new Array(temperatures.length).fill(0);
  for (let i = 0; i < temperatures.length; i++) {
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const j = stack.pop();
      arr[j] = i - j;
    }
    stack.push(i);
  }
  return arr;
};

堆

数组中的第 K 个最大元素

LeetCode 原题链接：215. 数组中的第 K 个最大元素

存在快排和堆两种排序算法，熟能生巧，注意快排的边界判断，菜就多练。🦀

JS
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const findKthLargest = (nums, k) => {
  const quickSelect = (l, r) => {
    if (l === r) {
      return nums[nums.length - k];
    }
    let i = l - 1,
      j = r + 1;
    const x = nums[l];
    while (i < j) {
      do {
        i++;
      } while (nums[i] < x);
      do {
        j--;
      } while (nums[j] > x);
      if (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    }
    if (nums.length - k <= j) {
      return quickSelect(l, j);
    } else {
      return quickSelect(j + 1, r);
    }
  };
  return quickSelect(0, nums.length - 1);
};


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const findKthLargest = (nums, k) => {
  const buildMaxHeap = (heapSize) => {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(i, heapSize);
    }
  };
  const maxHeapify = (i, heapSize) => {
    const l = i * 2 + 1;
    const r = i * 2 + 2;
    let largest = i;
    if (l < heapSize && nums[l] > nums[largest]) {
      largest = l;
    }
    if (r < heapSize && nums[r] > nums[largest]) {
      largest = r;
    }
    if (i !== largest) {
      swap(i, largest);
      maxHeapify(largest, heapSize);
    }
  };
  const swap = (i, j) => {
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  };
  let heapSize = nums.length;
  buildMaxHeap(heapSize);
  for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
    swap(0, i);
    heapSize--;
    maxHeapify(0, heapSize);
  }
  return nums[0];
};

贪心

买卖股票的最佳时机

LeetCode 原题链接：121. 买卖股票的最佳时机

贪心算法，每次都找到前一个的最优条件

JS
/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = (prices) => {
  let maxIn = 0,
    minPrice = prices[0];
  for (let i = 1; i < prices.length; i++) {
    if (minPrice < prices[i]) {
      maxIn = Math.max(maxIn, prices[i] - minPrice);
    } else {
      minPrice = prices[i];
    }
  }
  return maxIn;
};

跳跃游戏

LeetCode 原题链接：55. 跳跃游戏

贪心算法，每次在符合条件情况下更新最长的长度。

JS
/**
 * @param {number[]} nums
 * @return {boolean}
 */
const canJump = (nums) => {
  let head = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (i <= head) {
      head = Math.max(head, i + nums[i]);
    }
    if (head >= nums.length - 1) {
      return true;
    }
  }
  return head >= nums.length - 1;
};

动态规划

爬楼梯

LeetCode 原题链接：70. 爬楼梯

经典问题，甚至让我觉得有点像斐波那契数列。🤔

JS
/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = (n) => {
  let pre = 1,
    cur = 1;
  for (let i = 1; i < n; i++) {
    const temp = pre + cur;
    pre = cur;
    cur = temp;
  }
  return cur;
};

打家劫舍

LeetCode 原题链接：70. 爬楼梯

常规的动态规划题目，注意状态转移方程的书写，注意初始条件的设置，并不影响整体的判断。

JS
/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = (nums) => {
  if (!nums || nums.length === 0) {
    return 0;
  }
  if (nums.length === 1) {
    return nums[0];
  }
  let first = nums[0],
    second = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    const temp = second;
    second = Math.max(second, first + nums[i]);
    first = temp;
  }
  return second;
};


/**
 * @param {number[]} nums
 * @return {boolean}
 */
const rob = (nums) => {
  if (!nums || nums.length === 0) {
    return 0;
  }
  if (nums.length === 1) {
    return nums[0];
  }
  const sumArr = new Array(nums.length);
  sumArr[0] = nums[0];
  sumArr[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    sumArr[i] = Math.max(sumArr[i - 1], sumArr[i - 2] + nums[i]);
  }
  return sumArr[sumArr.length - 1];
};

单词拆分

LeetCode 原题链接：139. 单词拆分

这边还是有些技巧，首先dp数组的长度为n + 1并且第一项为true，然后状态转移方程如下，值得仔细理解。

JS
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
const wordBreak = (s, wordDict) => {
  const set = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i < s.length + 1; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[dp.length - 1];
};

最长递增子序列

LeetCode 原题链接：300. 最长递增子序列

维护一个dp数组，数组中的每个值为当前索引的最长子序列长度，然后动态规划求解。

JS
/**
 * @param {number[]} nums
 * @return {number}
 */
const lengthOfLIS = (nums) => {
  const dp = new Array(nums.length).fill(1);
  let maxLen = 1;
  for (let i = 1; i < nums.length; i++) {
    let max = 1;
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        max = Math.max(max, dp[j] + 1);
      }
    }
    dp[i] = max;
    maxLen = Math.max(maxLen, max);
  }
  return maxLen;
};

多维动态规划

不同路径

LeetCode 原题链接：62. 不同路径

二维动态规划，也可直接使用一维数组来模仿，重点在于当前节点的次数只会来源于左上。

JS
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
const uniquePaths = (m, n) => {
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    f[i][0] = 1;
  }
  for (let j = 0; j < n; j++) {
    f[0][j] = 1;
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1];
    }
  }
  return f[m - 1][n - 1];
};


/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
const uniquePaths = (m, n) => {
  const newArr = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      newArr[j] += newArr[j - 1];
    }
  }
  return newArr[n - 1];
};

最小路径和

LeetCode 原题链接：64. 最小路径和

相同的动态规划思路，左边和上面哪个更小取哪个，注意需要初始化边缘的行与列。

JS
/**
 * @param {number[][]} grid
 * @return {number}
 */
const minPathSum = (grid) => {
  const rowLen = grid.length,
    colLen = grid[0].length;
  for (let i = 1; i < colLen; i++) {
    grid[0][i] += grid[0][i - 1];
  }
  for (let i = 1; i < rowLen; i++) {
    grid[i][0] += grid[i - 1][0];
  }
  for (let i = 1; i < rowLen; i++) {
    for (let j = 1; j < colLen; j++) {
      grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
    }
  }
  return grid[rowLen - 1][colLen - 1];
};

最长回文子串

LeetCode 原题链接：5. 最长回文子串

中心扩散法直接秒，经典无需多言。

JS
/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = (s) => {
  if (s.length <= 1) {
    return s;
  }
  let res = "";
  const helper = (m, n) => {
    while (m >= 0 && n < s.length && s[m] === s[n]) {
      m--;
      n++;
    }
    const temp = s.slice(m + 1, n);
    if (temp.length > res.length) {
      res = temp;
    }
  };
  for (let i = 0; i < s.length; i++) {
    helper(i, i);
    helper(i, i + 1);
  }
  return res;
};

技巧

多数元素

LeetCode 原题链接：169. 多数元素

哈希表求解

JS
/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = (nums) => {
  if (nums.length <= 1) return nums;
  const map = new Map();
  for (const num of nums) {
    if (map.has(num)) {
      const count = map.get(num);
      if (count === Math.floor(nums.length / 2)) {
        return num;
      }
      map.set(num, count + 1);
    } else {
      map.set(num, 1);
    }
  }
};

下一个排列

LeetCode 原题链接：31. 下一个排列

从右往左找到较小的一个数，然后找到较大的一个数然后需要尽量靠右，交换后然后反转。

JS
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const nextPermutation = (nums) => {
  const swap = (i, j) => {
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  };


  const reverse = (l, r) => {
    while (l < r) {
      swap(l++, r--);
    }
  };


  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  if (i >= 0) {
    let j = nums.length - 1;
    while (j > i && nums[j] <= nums[i]) {
      j--;
    }
    swap(i, j);
  }
  reverse(i + 1, nums.length - 1);
};
文章作者:
希亚的西红柿
版权声明:
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自希亚的西红柿のBlog！
算法数据结构

相关推荐

2024-02-26LeetCode 算法笔记 Part2 2024-02-25LeetCode 算法笔记 Part1 2023-12-11数据结构与算法笔记 2022-12-31栈与队列 2022-12-24线性表 2022-09-27数据结构绪论

评论

评论加载中…

站内搜索