leetcode

挑选了一些比较经典的算法题，做完多巩固。

算法

动态规划
贪心算法

22 中等括号生成
94 中等二叉树的中序遍历
98 中等验证二叉搜索树
104 简单二叉树的最大深度
105 中等从前序与中序遍历序列构造二叉树
111 简单二叉树的最小深度
144 中等二叉树的前序遍历
226 简单翻转二叉树
230 中等二叉搜索树中第K小的元素
236 中等二叉树的最近公共祖先
297 困难二叉树的序列化与反序列化
429 简单 N叉树的层序遍历
589 简单 N叉树的前序遍历
590 简单 N叉树的后序遍历

分治

17 中等电话号码的字母组合
50 中等 Pow(x, n)
78 中等子集
169 简单求众数

遍历和搜索

102 中等二叉树的层次遍历
126 困难单词接龙 II
127 中等单词接龙
200 中等岛屿数量
433 中等最小基因变化
515 中等在每个树行中找最大值
529 中等扫雷游戏

剪枝

36 中等有效的数独
37 困难解数独
51 困难 N皇后

二分查找

33 中等搜索旋转排序数组
69 简单 x 的平方根
367 简单有效的完全平方数

贪心

122 简单买卖股票的最佳时机 II
455 简单分发饼干
860 简单柠檬水找零
874 简单模拟行走机器人

动态规划

32 困难最长有效括号
45 困难跳跃游戏 II
55 困难跳跃游戏
62 中等不同路径
63 中等不同路径 II
64 中等最小路径和
72 困难编辑距离
76 困难最小覆盖子串
91 中等解码方法
120 中等三角形最小路径和
121 简单买卖股票的最佳时机
122 简单买卖股票的最佳时机 II
123 困难买卖股票的最佳时机 III
152 中等乘积最大子序列
188 困难买卖股票的最佳时机 IV
198 简单打家劫舍
213 中等打家劫舍 II
221 中等最大正方形
279 中等完全平方数
322 中等零钱兑换
518 中等零钱兑换 II
309 中等最佳买卖股票时机含冷冻期
312 困难戳气球
363 困难矩形区域不超过 K 的最大数值和
403 困难青蛙过河
410 困难分割数组的最大值
552 困难学生出勤记录 II
621 中等任务调度器
647 中等回文子串
714 中等买卖股票的最佳时机含手续费
980 困难不同路径 III

树

208 中等实现 Trie (前缀树)
212 困难单词搜索 II

位运算

52 困难 N皇后 II
136 简单只出现一次的数字
190 简单颠倒二进制位
191 简单位1的个数
231 简单 2的幂
338 中等比特位计数

并查集

130 中等被围绕的区域
200 中等岛屿数量
547 中等朋友圈

解法

盛最多水的容器

可以使用两个 for 循环处理，但是当数据量达到某个成都的时候就会溢出。

比较好的方法就是使用双指针，时间复杂度：O(n)，空间复杂度：O(1)

// 双指针
function maxArea(height: number[]): number {
  let max = 0;
  let start = 0;
  let end = height.length - 1;
  // 当边界相遇时停止循环
  while (start < end) {
    // 容器大小跟宽度与高度有关，取**左右边界的小值**与下标差的乘积。
    const newWater = (end - start) * Math.min(height[end], height[start]);
    if (newWater > max) max = newWater;
    // 容器大小跟宽度与高度有关，则当小值变大之后乘积变大（跟大值无关）
    if (height[start] > height[end]) {
      end--;
    } else {
      start++;
    }
  }
  return max;
}

两数之和

提示：可以使用暴力循环，也可以使用hash表。

使用暴力循环可能会超时，属于时间换空间。时间复杂度：O(n^2)，空间复杂度：O(1)。

使用hash表属于空间换时间。时间复杂度：O(n)，空间复杂度：O(n)。

/*
* [1] 两数之和
*/
function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    map.set(num, i);
  }
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    if (map.get(target - num) && i !== map.get(target - num)) {
      return [i, map.get(target - num)];
    }
  }
}

删除排序数组中重复项

题目的要求是返回不重复的长度，所以可以使用双指针（如果数组不是排序的，可以先排序之后使用这个方法）。

function removeDuplicates(nums: number[]): number {
  const n = nums.length;
  if (n <= 1) return n;
  let slow = 1;
  let fast = 1;
  // 当 fast 越界（超过 nums 长度）时，停止循环
  while (fast < n) {
    // 当前 fast 下标的值与 fast 前一个下标的值不相等的情况下，替换 slow 下标的值
    // 并将 slow 移动至下一位
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast];
      ++slow;
    }
    ++fast;
  }
  return slow;
}

加一

function plusOne(digits: number[]): number[] {
  digits.reverse();
  digits[digits.length] = 0;
  digits[0] += 1;
  for (let i = 0; i < digits.length; i++) {
    const num = digits[i];
    if (num >= 10) {
      digits[i + 1] += 1;
      digits[i] = digits[i] - 10
    }
  }
  if (digits[digits.length - 1] === 0) {
    digits.pop();
  }
  digits.reverse();
  return digits;
}

爬楼梯

这是一道动态规划的问题，看了教程无数次都没有很好的理解，😭。

它可以像斐波那契数列一样解决，即从上至下，f(n) = f(n-1) + f(n-2)。

一般情况下这样的解决方式是没有问题的，但是会造成大量无用计算。

而动态规划是一种自下而上的算法。

function climbStairs(n: number): number {
  // 自己实现动态规划解法
  // 我还是觉得我的好理解哈哈哈哈哈哈哈
  let a = 1;
  let b = 2;
  let i = 3;
  if (n < 3) return n;
  while (i <= n) {
    let temp = b;
    b = b + a;
    a = temp;
    i++;
  }
  return b;
  // 官方动态规划解法
  let p = 0, q = 0, r = 1
  for (let i = 0; i < n; i++) {
    p = q
    q = r
    r = p + q
  }
  return r
}

只出现一次的数字

不需要额外空间的方法，就往位运算上想。

异或运算有以下三个性质。

任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
异或运算满足交换律和结合律，即 a⊕b⊕a= b⊕a⊕a= b⊕(a⊕a)= b⊕0= b。

function singleNumber(nums: number[]): number {
  // const map = new Map<number, number>()
  // for (let i = 0; i < nums.length; i++) {
  //   const num = nums[i];
  //   map.set(num, map.get(num)? map.get(num) + 1 : 1)
  // }
  // for (const [key, value] of map) {
  //   if (value === 1) return key
  // }
  return nums.reduce((a, b) => a ^ b)
};

旋转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

解法有三：

额外数组
环状替换
翻转

// 翻转
function reverse(nums: number[], start: number, end: number) {
  while (start < end) {
    let temp = nums[end];
    nums[end] = nums[start];
    nums[start] = temp;
    start++;
    end--;
  }
}
function rotate(nums: number[], k: number) {
  if (k > nums.length) k = k % nums.length;
  // 翻转整个数组
  reverse(nums, 0, nums.length - 1);
  // 翻转“翻转后的数组”的前 k 个
  reverse(nums, 0, k - 1);
  // 翻转“翻转后的数组”的后 nums.length - k 个
  reverse(nums, k, nums.length - 1);
}

// 一位一位的替换（类似于环状替换，但不是）
function rotate(nums: number[], k: number): void {
  if (k > nums.length) k = k % nums.length;
  while (k > 0) {
    // 获取当前数组最后一个元素
    let prev = nums[nums.length - 1];
    // 循环
    for (let i =0; i < nums.length; i++) {
      // 暂存当前元素
      let current = nums[i]
      // 替换当前元素
      nums[i] = prev
      prev = current
    }
    k--;
  }
}

移动零

使用双指针，当前指针遇到 0 的时候停下来，与后指针进行替换；

当两个指针都是非0 时，各前进一步

当后指针遇到边界（即数组长度时）跳出循环

function moveZeroes(nums: number[]): void { 
  let prev: number = 0, next: number = 1;
  while (next < nums.length) {
    if (nums[prev] === 0) {
      nums[prev] = nums[next]
      nums[next] = 0
    }
    if (nums[prev] !== 0) {
      prev++
    }
    // next++ 必须写在判断外面，不然在遇到连续几个 0 的时候会出现跳过的现象
    next++
  }
};