leetcode 题解记录整理

简介

收集、整理刷题经验，归档题解记录 顺便给博客凑点内容……

刷题技巧

以下内容整理自 B 站几位 up 主（花花酱、Christinaaa呀、清风迅来 等）的刷题经验 + 个人经验

题目那么多，怎么选题目

• 题量选择：每个类型 10~20 题（动态规划：多多益善）
• 时间规划：集中式大量刷题，同一类型题目一起刷，保持题感，养成刷题习惯，做的时候总结出相似之处，需要注意的地方

推荐参考题集：

• CyC2018 - Leetcode 题解

不会的题目怎么办

首先，不要觉得看答案是丢脸的事情

然后，

1. 如果一道题超过 5 分钟都没有头绪，直接看答案
2. 看完答案，尝试不去看答案和代码，自己把题目做出来（一道题不要超过 60 分钟）看完答案忘记怎么做了请回到第一步
3. 尝试快速实现，如果 20~30 分钟实现不了，再看答案

刷题过程中培养的能力

• 拓宽思路，至少能看出用了什么算法
• 数据规模、时间复杂度推算
• 代码风格

题解记录 - 算法部分

目前按照 CyC2018 - Leetcode 题解，上的题目顺序，从双指针开始刷起

双指针

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务

记录

小结

用法

Why：降低解题复杂度，降低时间复杂度

When：看到有两个链表、两个字符串、两个数组、三只核桃、六只松鼠 之类的情况

How：while + 双指针

不足

1. 2020.06.17 目前都采用 while 循环，看起来不优雅（但很好用啊 - -） ，之后应该优化一下，比如改为递归

想法

核心：找出 while(condition) 循环继续的条件 condition，以及双指针的初始位置

注意：循环异常终止的情况（通常是正确值、边界值、空指针）

回溯法

回溯法小结

回溯法解题套路 —— backtrack 框架

每次解回溯题时，把以下内容复制一下，照着这个模板去写就行

1
2
3
4
5
6
7
8
9

- 触发结束条件
- for 选择 in 选择列表:
  - # 做选择
    - 将该选择从选择列表移除
    - 路径.add(选择)
  - backtrack(路径, 选择列表)
  - # 撤销选择
    - 路径.remove(选择)
    - 将该选择再加入选择列表

而这个模板中，主要考虑三件事情：

• 结束条件：到达决策树底层，无再做选择的条件
• 选择路径：已经做出的选择
• 选择列表：当前可以做的选择

题解记录 - 数据结构相关

字符串

栈

数组与矩阵

记录

树

记录

小结

解这类题的关键主要还是在于理解 + 利用定义

• 前序遍历（根、左、右）
• 中序遍历（左、根、右）

至于递归逻辑，在纸上画画图，手动算两轮测试数据，有很大的帮助。

再次鸣谢

• 算法介绍、题目选择、分类参考了 CyC2018 - Leetcode 题解
• 解题技巧参考了花花酱、Christinaaa呀