LeetCode 笔记

为了学习 Rust 刷了 2 年的 LeetCode，总结了个笔记，收藏了一些好题。

2021-09-27

29 次浏览

准备

位运算是要牢记的，数据结构和常用算法是必须熟悉熟记的。 你所使用的语言的标准库函数也是必须熟记的。 当然，刷题本身也是对这些的熟悉过程。

读题

时刻要注意读题，因为有些坑就在题干中，仔细读题之后能得到答案。 要注意题目中所有出现的内容的特性，

例子1，某个数字出现了两次，那么意味着这个数字相加能够被2整除，这个数字能够被异或消除等等 ，列出所有的特性，然后根据题目的要求看哪些特性是所需要的再进行选择。

例子2，数组是有序的，那么意味着可以采用二分查找或者二分的变体，那么二分查找还可以解决某个连续相等数字的上界、下界等等。

收藏题型

收藏题型都是我自认为非常棒，能够开阔思路，得到启发，值得无数次回味的经典题。

数组

连续数字

连续数字，例如1,2,3,4,5..这种，或者1,3,5,7..这种连续的数字，

  • 要记住等差数列求和公式Sn = n * (A1 + An) / 2，这个n可以是 An - A1 + 1。
  • 要注意是有序的，有序就意味着可以二分查找
  • 要注意滑动窗口，滑动窗口意味着可以两端左右移动，直到左边等于右边
  • 要注意前序和

找唯一

这类型的题，要注意位操作，记住异或是可以清除掉两个相同数字的，同时要注意如果在某一个粒度 上解决不了问题，可以到更细或者更粗的粒度上去解决，这取决于题目本身，这个思想我叫它放大思想， 如果在这个粒度上解决不了问题，就把这个粒度放大到更细的粒度去思考，相反，也有缩小粒度到更粗 的粒度去思考。

例如，数字就可以看做二进制组成的，可以把二进制作为存储bool值的数组。

  • q31， 数组的交换技巧
  • q135， 数组中值的拐点是要注意的地方，参数的记录选择也很重要，是记录方向呢？还是记录数量呢？还是记录拐点值呢？
  • q239， 数组、双端队列
  • q283， 数组的原地移动

栈

栈的先入先出的基本思想就不说了，还有一个重要的需要掌握的就是单调栈的技巧。

  • q150， 逆波兰表达式，经典的栈应用了
  • q224/q227， 运算表达式的解决一直都是栈的经典应用之一
  • q331， 树与栈总是紧密相连，当然有时候可以用一个简单的数字来替代栈的功能
  • q394， 栈通常也可以转化为递归解决，当然这题还有双栈的解法，很有启发性
  • q456， 132模式非常经典的一个栈应用，非常值得回味

位操作

位操作多数都是各种花式技巧，这个只能多做题来了解、熟悉、总结、掌握。

XOR 有用的特性：

  • 基本原则，不同的为1，相同的为0
  • 交换原则， x^y=z == x^z=y == y^z=x
  • 自己异或为0， x^x=0
  • 0异或任意一个数等于那个数， 0^x=x
  • 偶数与 偶数+1 异或等于1， 2x^(2x+1)=1

AND 有用的特性：

  • 基本原则，相同的不变，不同的为0

  • 判断奇偶性， x & 1 == 1，如果是1就是奇数，如果是0就是偶数

  • 自己and为自己， x & x = x

  • 0 and 任意一个数都是0， 0 & x = 0

  • 消除掉x最右边的1， x & (x - 1) （这个特性很重要，很多位运算题都可以运用到）

  • q137， 位可以表示状态的连续变化，当然，如果你会电路设计，位操作会游刃有余。

  • q021， 范围和，范围与都是位运算的经典题目了。

  • q338， 位操作没啥说的，多练多看就熟悉了。

  • q1734，合理利用位操作的特点，抓住题干给出的条件推导。

  • offer56_ii，这是一道经典的位操作应用。

字符串

  • q179，字符串组合后的字典排序

前缀和

  • q303，一个题可以学习到前缀和、树状数组、线段树的技巧，还是个简单题，真是值
  • q363，一个非常棒的二维数组前缀和的题，很锻炼良好的迭代思维。这个真的值得温习很多次，也可以作为写代码前的一个思维锻炼。
  • q523，一个陷阱细节很多的前缀和的题。
  • q525，这也能想到前缀和，有意思啊。

二分查找

  • q33，二分查找的扩展应用，非常经典
  • q34，二分查找找上下界，经典中的经典。
  • q81，q33的变种版本，也是二分查找的扩展应用，非常经典
  • q162， 二分查找有时候比的不是中点与两个端点
  • q220， 数组、二分查找、二叉平衡树。
  • q540， 有序数组找东西，第一思维是二分。
  • q1101，这道题还能用二分？就看你能不能想到了，见多识广，思路会更开阔。
  • q1482，二分查找逼近最优解。
  • offer53_i，二分查找扩展应用。
  • interview0803， 二分查找扩展应用。

双指针

  • q15, 双指针可以有效解决搜索问题。
  • q80, 双指针的经典应用，值得回味。
  • q1248, 双指针，什么条件下，如何移动左或右指针，值得回味。

滑动窗口

滑动窗口就是窗口的移动，包括扩展、收缩和整体移动。在这个窗口中可以叠加很多其他的考点进来， 例如排序、Hash、栈、堆、多个堆、队列、位操作等等，而且窗口也有固定大小的，也有视情况变大变小的， 还有的题目是将窗口题目伪装成了其他题目的样子，需要你换个角度去看才能看出原来是窗口问题。 总之就是在窗口里面办事情，关注进窗口和出窗口，选好窗口中的数据结构。其他的交给模板。 滑动窗口标准模板如下：

fn solution(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    let mut lo = 0;
    let mut answer = 0;
    let mut window = 选好window的数据结构;
    for hi in 0..n {
        右边元素进入窗口;
        while 达到收缩窗口条件 {
            左边窗口收缩;
            lo += 1;
        }
        answer = answer.max(hi + 1 - lo);
    }
    answer as i32
}
  • q209， 经典滑动窗口
  • q424， 经典滑动窗口
  • q480， 经典中的经典滑动窗口，两种解法都很值得回味，其中最优解法需要极致细节
  • q992， 我最爱的一道题之一，此题我得到了很多启发，加深了将问题变成另外一个问题，解决那个问题之后把那个问题当成黑盒就解决了此题
  • q995， 其实这道题跟滑动窗口关系不是特别大，虽然是固定k长度的窗口，但是这题值得回味，脑子可以很好得到锻炼
  • q1052，看懂题就简单了，题干具有一定的迷惑性
  • q1423，有时候有些问题看起来不简单，但是换个角度去看就变简单了，它的回味点就在于看问题的角度

链表

  • q19， Rust如何使用raw指针和删除链表的指定节点
  • q147/q148， 要用Rust玩链表之前，可以用来热身
  • q234， 回文和链表的翻转，以及Rust的所有权机制

排序

  • q164， 深刻理解桶排序
  • q493， 归并排序的应用

回溯

我自己的感觉回溯就是一个优雅的暴力解法，将每个可能的路径都走一遍，不行了就退到上一步，然后继续走。 所以这里能做文章的地方就在于选择， 题目可能给在选择的地方给你限制，比如列表不重复、列表重复、相同数字只能用一次之类的。 回溯的标准模板如下：


fn backtrace(path: &mut Vec<i32>, list: &Vec<i32>, used: &mut HashSet<i32>, answer: &mut Vec<Vec<i32>>) {
    if 条件达到 {
        加入结果集answer
        返回
    }
    遍历可供选择的列表list（排除已经选择过的used）
    for x in list {
        if used.insert(x) { // 加入已经选择
            arr.push(x);  // 加入选择
            backtrace(arr, nums, used, answer); // 继续处理
            arr.pop(); // 弹出刚刚的选择，这就是back了
            used.remove(&x); // 弹出已经选择
        }
    }
}
  • q22， 回溯的典型应用，也算是排列组合，不过每次的选择列表需要去思考
  • q46， 回溯的典型应用，全排列，这个系列都值得做一下，各种角度
  • q77， 回溯的典型应用，组合，这个系列都值得做一下，各种角度
  • q39/q40/q216/q377， 回溯之组合全家桶，练习回溯的不二之选
  • q131， 脑子要会转弯
  • q842， 回溯的典型应用
  • q1723， 回溯+二分，这题真的很经典，值得每隔一段时间就回味一下。

动态规划

  • offer42，这道题算是一道动态规划题，也算是一道总结规律的题，非常具有启发性。
  • q64/q120， 动态规划，最短路径
  • q87/q91/q576， 记忆化搜索也是动态规划的一种
  • q115， 字符串的动态规划总是很经典的。
  • q123， 购买股票的最佳时机系列，这个系列全都是动态规划，可以一次性复习。
  • q132/q516 回文的dp解决方法，值得回味。
  • q198/q213，教科书级别的动态规划，与买卖股票有相似之处。
  • q264， 丑数II，也是一种动态规划。
  • q300/q354， 经典中的经典动态规划，三种解法意犹未尽，其中q354只是比q300多一个维度，但是两题的解法框架基本相同。
  • q514， 动态规划的更多应用
  • q91/q639， 动态规划的更多应用
  • q714， 动态规划入门，掌握更多动态规划形态
  • q1143， 教科书级别的动态规划应用，最长子公共串，这个问题可以用来解决DNA的相似度。

背包问题

  • 279，完全平方数
  • 322，零钱兑换
  • 416，分割等和子集
  • 474，一和零
  • 494，目标和
  • 518，零钱兑换 II
  • 879，盈利计划
  • 1049，最后一块石头的重量 II
  • 1449，数位成本和为目标值的最大数字

贪心算法

  • q316， 字符串加贪心的应用
  • q502， 贪心算法与排序和优先级队列常常一起玩耍
  • q621， 贪心算法的应用
  • q659， 贪心算法的应用
  • q649， 贪心算法的应用
  • q678， 很经典的贪心算法
  • q738， 本来很普通的一道贪心算法的应用，但是有一个大神的思路值得回味

并查集

  • q684， 并查集的经典应用，成环检测
  • q803， 并查集的高级应用，极致细节，思路爆发
  • q947， 并查集的经典应用，并入集合
  • q959， 并查集的应用，如何划分区域的思考
  • q1489，并查集，最小生成树，思路启发
  • q1631，并查集，最小生成树的变化应用，思路爆发
  • q1697，并查集，很经典的一个并查集应用

字典树

  • q421， 字典树经典应用之一，逐渐过滤掉候选项。但是如何确定使用字典树的解法，需要抽丝剥茧的分析。
  • q1707，算是q421的一个升级版本了。加入了一个限制条件。做完这个题，会有学到了的感觉。

其他

  • offer62，这是一道约瑟夫环的算法解决问题。有兴趣可以模拟每次计算进行公式推导。
  • q287， Floyd环巧妙的解决了重复的问题
  • q395， 我觉得还算典型的一个分治
  • q442， 不使用额外空间解决问题，利用已知条件发散思维。
  • q448， 不使用额外空间解决问题
  • q665， 极其容易错的一道easy题，很锻炼整体思维
  • q765， 这个题算是出题失败的hard，导致其变成了easy。
  • q1178，这个题的关键就是怎么判断二进制下的子集，这一招学会，终生受用。

其他总结

字符串

日期

遇到日期类的题目，首先想到的就是闰年，即是能被4整除但不能被100整除，或者是能被400整除的。 闰年是366天，在2月份要多1天。

树

拿到树的题自然先想到的有几个，

  • 树是特殊的图，那么广度优先和深度优先就能使用，广度优先用queue，深度优先用stack
  • 树的前中后序遍历，用递归很简单，非递归都用stack，后序的非递归遍历稍微难一点，但是
    • 前序： 中 左 右
    • 中序： 左 中 右
    • 后序： 左 右 中
  fn pre_order(node: Node) {
    process(node);
    pre_order(node.left);
    pre_order(node.right);
}

fn pre_order_iter(node: Node) {
    let mut stack = vec![node];
    while !stack.is_empty() {
        node = stack.pop();
        if node != None {
            process(node);
            stack.push(node.right);
            stack.push(node.left);
        }
    }
}

  fn in_order(node: Node) {
    in_order(node.left);
    process(node);
    in_order(node.right);
}

fn in_order_iter(root: Node) {
    let mut stack = Vec::new();
    let mut node = root;
    while node != null || !stack.is_empty() {
        while node != null {
            stack.push(node);
            node = node.left;
        }
        if !stack.isEmpty() {
            node = stack.pop();
            process(node);
            node = node.right;
        }
    }
}

  fn post_order(node: Node) {
    post_order(node.left);
    post_order(node.right);
    process(node);
}

fn post_order_iter(root: Node) {
    let mut tree_node_stack = vec![root];
    let mut node = root;
    let mut last_visit = root;
    while node != null || !tree_node_stack.is_empty() {
        while node != null {
            tree_node_stack.push(node);
            node = node.left;
        }
        //查看当前栈顶元素
        node = tree_node_stack.peek();
        //如果其右子树也为空，或者右子树已经访问
        //则可以直接输出当前节点的值
        if node.right == null || node.right == last_visit {
            process(node);
            tree_node_stack.pop();
            last_visit = node;
            node = null;
        } else {
            //否则，继续遍历右子树
            node = node.right;
        }
    }
}

注意：很多Rust的初学者可能都知道clone是一个昂贵的操作，它会拷贝所有的内容，但是Rc不一样， 它只会新增一个指针和引用计数，并不昂贵，所以我刚开始做树的题的时候也觉得clone是不是拷贝了 一棵树，但是想不出更好的办法，想着先通过题吧，但是发现速度正常，内存正常啊，按道理clone会有很昂贵的 开销，然后看了一下Rc的源码，发现clone的注释就是新增一个pointer，然后引用计数增加1，哦，知识又增加了， 然后又搜了一下GitHub，发现有人在吐槽Rc的clone方法不应该叫clone方法，要不叫ref或者叫new_ref也行，嗯，我懂他。