search

ShannonChenCHN / algorithm-and-data-structure

Algorithms + Data Structures = Programs
2 stars 1 forks source link

LeetCode 应该怎么刷 #9

Open ShannonChenCHN opened 4 years ago

ShannonChenCHN commented 4 years ago

https://leetcode.com/

参考

补充资料

ShannonChenCHN commented 3 years ago

LeetCode 刷题指南

首先要意识到，算法是一种技能，是可以通过科学合理的方式训练出来的能力。

先按标签来刷，然后再按难度从低到高来刷，一般 Easy 和 Medium 就已经足够应对大多数面试了。

按算法的分类来选题和刷题，这种做法可以极大的提高刷题的速度，而且能带来更好的效果。一是持续地刷同个类型的题目，可以不断地巩固和加深理解。二是，可以更全面地接触这个数据结构，算法的各个变种，这会促使你对这个数据结构，算法的理解更加全面和深刻，学习的效率会更高。

当然，在能力已经比较强的时候，可以采用打散的方式来刷题，可以更好地锻炼思维的灵活性和应变能力，但初期或能力较弱的时候，按分类选题，是比较好的。

刚开始接触某一个标签题型时，自己很难想出答案或者高质量的答案，如果自己思考 5 分钟后还没有解题思路，可以去看别人的题解（discussion）。

通过查看博客和讨论部分后对该题有基本思路，我们再去做这道题。对于同一类标签的题做多后，我们对这一类标签的题就会熟悉，下次遇到同样主题的题目就不会完全没有思路。

一定要坚持，坚持每天都刷题，遇到难题后不要灰心，静下心来看看别人的解题思路，看懂后自己再总结，要相信自己一定可以把它弄懂的。

解题三部曲：1. 看懂题目；2. 分析，推导解法；3. 将思路转换为代码

LeetCode 官方建议⭐️

图1 互联网公司面试中经常考察的问题类型

作为在电话 / 现场面试中短短不到一个小时时间内，提供给面试者白板编程解决的算法题目，它笔试上机、编程竞赛中的题目在难度与形式上还是有一些不同的。在难度上（尤其是代码难度上）会略低一些，倾向于考察一些基础数据结构与算法，对于高级算法和奇技淫巧一般不作考察。

算法与数据结构是面试考察的重中之重，也是大家日后刷题时需要着重训练的部分。简单的总结一下，大约有这些内容：

算法，主要是以下几种：

基础技巧：分治、倍增、二分、贪心 排序算法：快速排序、归并排序、计数排序 搜索算法：回溯、递归、剪枝技巧、深度优先遍历，广度优先遍历，二叉搜索树等 图论：最短路径、最小生成树、网络流建模 动态规划：背包问题、最长子序列、计数问题

数据结构，主要有如下几种：

数组与链表：单 / 双向链表、跳舞链 栈与队列 哈希表 堆：大 / 小根堆、可并堆 树与图：最近公共祖先、并查集 字符串：前缀树（字典树） ／ 后缀树

练习（建议小伙伴将所有题目都练习 2～3 遍，吃透每一道题目）

算法部分：

数据结构部分：

花花酱 LeetCode 的建议

相关视频：花花酱 LeetCode进入千题时代 该如何刷题？

ShannonChenCHN commented 3 years ago

面试题集

概述

编程能力就像任何其他技能一样，也是一个可以通过 刻意练习 大大提高的。

大多数经典面试题目都有多种解决方案。 为了达到最佳的练习效果，我们强烈建议您至少将常考题目清单里的题目练习两遍，如果可以的话，三遍会更好。

在第二遍练习时，你可能会发现一些新的技巧或新的方法。 到第三遍的时候，你会发现你的代码要比第一次提交时更加简洁。 如果你达到了这样的效果，那么恭喜你，你已经掌握了正确的练习方法！

记住：刻意练习并不意味着寻找答案并记住它，这种练习方法不是长久之计。 在没有参考答案情况下，越能自主解决问题，才越能提高自身能力。

练习的时候最好模拟面试的实际情况来，限制时长，5 分钟内就要想出思路，最优解想不出来，可以先用暴力解法写出来。平时练习要求严格了，给压力了，面试时才不至于太紧张。

题目清单

ShannonChenCHN commented 3 years ago

算法复习

2021.05.13 ~ 2021.05.24

目录

一、复杂度分析 二、数组和字符串（8道题）⭐️ 三、链表（8道题）⭐️ 四、栈（10道题） 五、队列（4道题） 六、排序（10种排序算法+8道题） 七、查找（二分查找算法+9道题）⭐️ 八、优先队列和堆（堆的实现+3道题） 九、Trie（3道题） 十、贪心算法（4道题） 十一、位运算和数学问题（10道题） 十二、滑动窗口（4道题） 十三、回溯算法（6道题） 十四、设计题（3道题） 十五、树（树的理论知识+20道题）⭐️ 十六、动态规划（20道题） 十七、哈希表

一、复杂度分析

05.24

  1. 什么是算法复杂度
  2. 为什么要分析算法复杂度
  3. 如何分析算法复杂度
    • 大 O 表示法：T(n)=O(f(n))
      • 公式中的低阶、常量和系数可以忽略
    • 时间复杂度
    • 分析技巧
      • 单段代码看最高频：如果一个函数中有多个循环，只关注循环执行次数最多的一段代码
      • 加法法则：总复杂度等于量级最大的那段代码的复杂度
      • 乘法法则：嵌套代码求乘积，比如递归、多重循环
      • 多个规模求加法：比如方法有两个不同的参数控制两个循环的次数
    • 几种常见时间复杂度实例分析
      • 多项式量级：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)...
      • 非多项式量级：O(2^n)、O(n!)
    • 几种不同情况的复杂度
      • 最好情况时间复杂度
      • 最坏情况时间复杂度
      • 平均情况时间复杂度
      • 均摊时间复杂度
    • 空间复杂度
  4. 如何掌握复杂度分析
    • 多练，熟能生巧

二、数组和字符串（8道题）

05.24

题库来源：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x6w3ds/

题目列表

  1. 数组

  2. 字符串

相关专题

总结

  1. Swift 中 Character 的常用 API
    • asciiValue
    • isNumber
    • isLetter
    • isWhitespace
    • isNewline
    • wholeNumberValue
    • lowercased()
    • uppercased()
  2. 为了方便逐个访问 String 中的字符，我们可以将一个 String 类型的变量转成 Array，比如 let str = "abc" 可以转成 let charArray = Array(str)
  3. 字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。
  4. 一旦涉及整数的运算，我们需要注意溢出。对于溢出的处理方式通常可以转换为 Int.max 的逆操作，比如判断某数乘 10 是否会溢出，那么就把该数和 Int.max 除 10 进行比较：num > Int.max / 10 || (num == Int.max / 10 && curChar.wholeNumberValue > Int.max % 10)
  5. 字符串的题目一般会经常用双指针法来求解

三、链表（8道题）

05.13 ~ 05.15

题目列表

  1. 必做题

  2. 附加题

  3. 进阶题

总结

四、栈（10道题）

05.15

题目列表

总结

  1. 关于栈的题型主要有以下几类： 1). 首先是跟栈数据结构本身相关的，可以直接从标题或者描述中看出来是要考察栈的，比如 剑指 Offer 31. 栈的压入、弹出序列、155. Min Stack。 2). 另外一类是跟栈的几个典型应用场景相关的：

    3). 还有一类题型是因为正好可以利用栈“后进先出”的特性来解决问题的（但并不一定是最优解），比如回删操作、后退操作这类问题，相关题目有 844. Backspace String Compare、19. 删除链表倒数第 n 个结点 和 682. Baseball Game 。

  2. Swift 中没有 Stack 类，但是可以用数组模拟栈的操作。popLast() 相当于 pop 操作，append() 相当于 push 操作

五、队列（4道题）

05.16

理论知识

  1. 队列

  2. 双端队列

题目列表

总结

  1. 队列和栈有两个最大的不同点: 1) 栈是“先进后出”、队列是“先进先出”；2）队列是两端可以操作，而栈只有一端可以操作。这两点在题目 225. Implement Stack using Queues 和 232. Implement Queue using Stacks 中就体现出来了。
  2. 队列既可以用数组来实现，又可以用链表来实现。具体的实现过程见题目 分别用数组和链表实现一个队列 和 实现一个循环队列。
  3. Swift 的标准库中没有提供 Stack 和 Queue，不过我们可以用 Array 来模拟 Stack 和 Queue 的操作。
  4. 均摊复杂度分析：通过题目 232. Implement Queue using Stacks 的练习，正好顺便复习了一下均摊时间复杂度的分析以及什么时候需要用到 均摊时间复杂度。

六、排序（8道题+10种排序算法）

05.16

题目列表

  1. 实现几种常见的排序算法，并计算相应的时间复杂度和空间复杂度

  2. LeetCode

  3. 其他

总结

  1. 关键要掌握以下几点：
    • 几种常见的排序算法的原理和适应场景
    • 时间复杂度和空间复杂度分析
    • 重点掌握前五种排序算法的实现，尤其是快排的实现，一定要熟记，很多题目的解法都是基于 partition 函数的实现
  2. 跟排序相关的常考题型主要有 Top K 问题、求第 K 大元素。
  3. 各排序算法的比较 image

七、查找（9道题+二分查找算法）

05.16

题目列表

总结

  1. 需要熟练掌握二分查找法的实现过程，以及复杂度分析
  2. 只要遇到排序数组或者部分排序数组的场景，都要条件反射地想到二分查找是不是可以派上用场，二分查找的核心在于排除法
  3. 二分模板虽然多，但是具体题目要具体分析，多做题比模板更重要，做多了就灵活了，你不可能靠模板就能解决所有算法问题（网友评论）

八、优先队列和堆（3道题+堆的实现）

05.16

题目列表

总结

  1. 需要掌握的基础知识有：
    • 什么是堆
      • 完全二叉树
      • 父比子大/小
    • 如何实现一个堆
      • 存储：一般是数组
      • 操作：insert、remove、shiftUp、shiftDown
    • 堆排序：建堆+排序
  2. 遇到求 Top K 或者第 K 大的数这类问题时，都可以考虑是否用堆来实现
  3. 重点掌握建堆的模板代码

九、Trie（3道题）

05.16

题目列表

总结：

  1. 需要掌握 Trie 的实现
    • 需要注意的是 Trie 和多叉树的区别，建议画图结合图来看。
    • 记住 208 题 的模板代码
      • 节点结构
      • 插入单词
      • 查找单词
      • 前缀匹配
  2. 简单概括 Trie 的应用就是：一次建树，多次查询
    • 搜索引擎关键词输入的自动联想
    • 拼写检查
    • IP 路由地址前缀匹配
  3. Trie 的性质
    • Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。
    • 查找或插入一个长度为 L 的单词，访问 next 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。
    • Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)。

十、贪心算法（4道题）

05.17

题目列表

总结：

  1. 什么是贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。
  2. 适用场景：适用贪心算法的场景就是，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
  3. 用贪心算法解决问题的思路，并不总能给出最优解。
  4. 典型案例：背包问题（注：不是0-1背包问题），分糖果，钱币找零，区间覆盖

十一、位运算和数学问题（10道题）

05.17

题目列表

1. 位运算

2. 数学问题

总结

  1. 把一些常用的位运算特点背下来
    • 与 &，或 |，非 ~，异或 ^，左移 <<，右移 >>
    • (x & 1) == 1 等价于 (x % 2 == 1)
    • (x & 1) == 0 等价于 (x % 2 == 0)
    • x / 2 等价于 x >> 1
    • x &= (x - 1) 把x最低位的二进制1给去掉
    • x & -x 只保留最低位的1，而把其他位的1都去掉
    • x & ~x 得到 0
  2. 异或运算也是一个考点
    • x^0 = x
    • x ^ x = 0

十二、滑动窗口（4道题）

05.18

题目列表

总结

十三、回溯算法（6道题）

05.18

题目列表

总结

十四、设计题（3道题）

05.18

题目列表

总结

十五、树（树的理论知识+20道题）

05.22

题目列表

1. 二叉树

2. 二叉搜索树

3. 堆

见 #25

4. 平衡二叉树

5. 其他

总结

  1. 关于树的一些基本概念一定要掌握，比如高度、深度、层数、叶子节点。
  2. 需要知道什么是二叉搜索树、平衡二叉树、完全二叉树和满二叉树，像红黑树这类了解即可。
  3. 完全二叉树的由来（如何表示/存储一棵二叉树？）
  4. 根据二叉搜索树的典型特征，中序遍历可以得到一个递增序列。一般来讲，只要遇到二叉搜索树的题目，马上就要能想到两点：
    • 中序遍历得到的序列是单调递增的
    • 所有的左子树上的节点值都小于根节点，所有的右子树上的节点值都大于根节点
  5. 需要熟练掌握二叉树的前序、中序、后序遍历的递归实现(迭代实现了解即可)，以及层序遍历的实现，这两类遍历对应的也就是常说的 DFS 和 BFS，绝大部分二叉树的题目都是考察这两点的。另外还需要熟练掌握这类算法的复杂度分析。
  6. 只要是二叉树的题目，第一反应就是递归怎么实现？递推公式怎么写？
  7. 上面题目列表中标记 ⭐️ 的题目都是典型的二叉树的题目，需要多做几遍，达到非常熟练的程度。

十六、动态规划（20道题）

05.23

题目列表

总结

十七、哈希表

总结