Skip to content

Latest commit

 

History

History
361 lines (186 loc) · 6.01 KB

2021.md

File metadata and controls

361 lines (186 loc) · 6.01 KB

二叉树

  • 94 中序遍历

    • 递归

    • 迭代：栈

  • 96 不同的二叉搜索树

    • ？？？

  • 98 验证二叉搜索树

    • 递归

  • 101 对称二叉树

    • 递归：左子对称，右子也对称

    • 迭代： 队列。一次放四个，取两个。

  • 102 层序遍历

    • 队列

  • 104 二叉树的最大深度

    • 递归，深度优先，Max(左，右) + 1

    • 广度优先，一层一层加

  • 112 路径总和

    • 递归，深度优先，回溯，左 || 右

    • 栈，两个栈，一个放节点，一个放值（当前对应节点的 sum）

    • 因为有正负数问题所以不好剪枝

  • 113 路径总和 II

    • 递归，回溯，带着 history

  • 199 二叉树的右视图

    • 层序，队列

  • 226 翻转二叉树

    • 递归，右树 = 翻转(左子树); 左树 = 翻转(右子树)

  • 543 二叉树的直径

    • 递归

  • 617 合并二叉树

    • ？？？

动态规划

  • 62 不同路径

动态规划：f(i, j) = f(i − 1, j) + f(i, j − 1)

回溯会爆。

  • 64 最小路径和

创建数组的方法：new Array(n).fill(0)

动态规划：dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1])

  • 70 爬楼梯

f(x) = f(x − 1) + f(x − 2)

  • 118 杨辉三角

  • 119 杨辉三角 II

哈希表 / Map / Set

  • 1 两数之和 - nums[i], i, target-nums[i]

  • 128 最长连续序列

回溯

result = []
func backtrack(当前结果, 选择列表):
  if 满足结束条件:
    result.add(当前结果)
  else
    for 选择 in 选择列表:
      backtrack(当前结果 + 选择, 新的选择列表)

  • 17 电话号码的字母组合

    • 递归

    • 每次把当前的结果带进去

  • 22 括号生成

用额外的变量记录当前左括号与右括号的个数，即可简单快速判断当前字符串的情况。

  • 39 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

回溯 & dfs：跳过当前数，或者用当前数

  • 46 全排列

  • 78 子集

链表

  • 19 删除链表的倒数第 N 个结点

快慢指针，快的比慢的快 n 步。注意边界。

  • 21 合并两个有序链表

  • 61 旋转链表

先成环，右移变左移，然后拆开

  • 83 删除排序链表的重复元素

  • 82 删除排序链表的重复元素 II

dummy head

  • 92 反转链表 II

dummy head。画图找思路。

  • 141 环形链表

    • 快慢指针

    • 哈希表

  • 143 重排链表

    • 找中点 - 反转 - 合并

  • 160 相交链表

  • 203 移除链表元素

    • dummy head

  • 206 反转链表

  • 219 存在重复元素

    • 滑动窗口，窗口前面走出去了，后面要移除掉

  • 234 回文链表

    • 找中点

  • 237 删除链表中的节点

  • 328 奇偶链表

    • 先找到最后一个奇数，然后再从头开始，把偶数往后拼

  • 725 分隔链表

  • 1171 从链表中删除总和为零的连续节点

    • 满足删除条件就把指针前移

  • 1290 二进制链表转整数

    • 先走一趟算位数，再走一趟算结果

  • 1669 合并两个链表

  • 1721 交换链表中的节点

    • 滑动窗口

栈

20有效的括号

如果遇到左括号，push；如果遇到右括号，看看 pop 出来的是不是配对；

二分

  • 二分模板：

    • 找中点mid = ((right - left) >> 1) + left
    • 然后右端点左移 right = mid - 1 或者左端点右移 left = mid + 1

  • 33 搜索旋转排序数组

    • 双指针。二分法。因为旋转过，所以条件判断比较复杂。

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

  • 35 搜索插入位置

  • 69 x 的平方根

int mid = (l + r + 1) >> 1;

数组 & 未归类

  • 2 两数相加 - 链表 \ dummy head

  • 3 无重复字符的最长子串

  • 5 最长回文子串

    • 遍历 s，如果 s[i] 和它右侧的字符相同或者 s[i] 两侧的字符相同，那么向左右延伸。

  • 7 整数反转

  • 9 回文数

    • 切成数组，从两头同时遍历；找中点，作为遍历终点；

  • 14 最长公共前缀

    • 前提 1 while (strs.every(str => str.charAt(i))

    • 前提 2 if (strs.every(str => str.charAt(i) === current))

  • 24 两两交换链表中的节点

    • 递归

  • 26 删除有序数组的重复项 & 27 移除元素

    • 双指针，一个往前走用来遍历，一个放后面，满足条件才往前走

  • 28 实现 strStr()

    • 两层循环

  • 32 最长有效括号

    • 从左往右走一遍，从右往左走一遍

  • 55 跳跃游戏

  • 45 跳跃游戏 II

    • 贪心？

  • 48 旋转图像

  • 49 字母异位词分组

  • 58 最后一个单词的长度

  • 66 加一

  • 88 合并两个有序数组

  • 121 买卖股票最佳时机

  • 122 买卖股票最佳时机 II

    • 但凡跌了就卖，然后重新计算
    • 每一次上涨的都卖

  • 152 乘积最大子数组

    • 最大和最小的都要存

  • 167 两数之和 II - 输入有序数组

    • 双指针（对撞指针）

  • 228 汇总区间

  • 268 丢失的数字

    • 等差数列求和

  • 283 移动零

    • 双指针，把非零都赋到前面，然后把后面的全置零

  • 414 第三大的数

  • 448 找到所有数组中消失的数字

    • 有些数组问题，「数字本身」和「index」可以互相转换

  • 633 平方数之和

啥

  • 11 盛最多水的容器

  • 31 下一个排列

  • 53 最大子序和

  • 56 合并区间

  • 57 插入区间

  • 75 颜色分类

  • 79 单词搜索 回溯？动态规划？

  • 86 分隔链表

  • 114 二叉树展开为链表

  • 136 只出现一次的数字 - 位运算

  • 137 只出现一次的数字 II - 位运算

  • 138 复制带随机指针的链表

  • 147 链表插入排序

  • 148 排序链表

  • 169 多数元素

  • 338 比特位计数

  • 445 两数相加

  • 461 汉明距离 - 位运算

  • 485 最大连续 1 的个数 - 位运算

  • 817 链表组件

    • 为了查找的快，可以用一下 Set

  • 876 链表的中间节点

    • 快慢指针

TODO

  • 1019 链表中的下一个更大节点