《算法面试通关40讲》学习笔记

ShannonChenCHN commented 3 years ago

课程地址：https://time.geekbang.org/course/detail/100019701-41518 ppt 地址：https://github.com/ShannonChenCHN/algorithm-1

课程介绍

大厂面试一般都会重点考察算法和数据结构
解决算法和数据结构相关问题的能力可以通过学习和训练不断提高的
LeetCode 上题目越来越多，求职者不可能在短时间内把题目全部做完，如何有选择性地来练习和准备算法面试，就成为大多数求职者必须面对的难题
这个课程的目标是，帮助求职者在短时间内掌握面试中最常见的算法与数据结构相关知识点，学会面试中高频算法题目的分析思路，同时给大家从面试官的角度来分析算法题的解答技巧，从而更有效地提升求职者的面试通过率

课程结构

课程综述（4讲）
理论讲解加+面试题实战（53讲）
课程总结（5讲）

e61550fe597b2b351c72e333b57bb0d6

e61550fe597b2b351c72e333b57bb0d6的副本

ShannonChenCHN commented 3 years ago

第二节如何事半功倍地学习算法与数据结构

如何有效学习算法？

理解+训练

书：《异类》 ---> 一万小时定律

如何精通一个领域？

切碎知识点
- 如图所示
刻意练习
- 对于弱点、缺陷、不足的地方进行针对性练习
获得反馈
- 即时反馈
- 主动型反馈
- 被动型反馈

切题四件套

Clarification
Possible Solutions
- compare(time/space)
- optimal(加强)
Coding(多写)
Test cases

ShannonChenCHN commented 3 years ago

第三节如何计算算法的复杂度

1. 大 O 表示法

随着 n 的增加，不同时间复杂度之间的差距会越来越大。所以，我们自己在工程实践中对大数据场景下的性能要有意识。

2. 两个实际案例分析

(1) 计算`1+2+3+...+n` 的两种算法

(2) 斐波那契数列求和算法的时间复杂度计算（递归的时间复杂度计算）

用递归方法计算的时间复杂度是以n的指数的方式递增的，时间复杂度约等于O(2^n)

遗留问题：出了上面的递归解法之外，还有其他的哪些解呢？（提示：解法一循环累加，解法二矩阵） LeetCode 原题：https://leetcode-cn.com/problems/fibonacci-number/

3. 主定律

这几个公式的推导比较复杂，记住就行。

4. Q&A

Q: 老师，o(logN)这个，为什么不写底数啊？ A: O都是估算复杂度的数量级，所以没底也差不多。

Q: 老师，为啥说递归的时间复杂度是2的n次方呢？就如您所举例子，n为6的时候是20多次计算，n^2也才36,2^n都已经64了。那复杂度不是最接近O(n2)么。 A: 是指数级的复杂度，但是并不代表就是正好等于 2^n，时间复杂度本来就是数量级上的粗略估计。针对你上面的例子：6的时候的确如你所说没有 n^2 大，但是如果10或者20的时候，整体复杂度肯定高于 n^2

ShannonChenCHN commented 3 years ago

第四节如何通过LeetCode来进行算法题目练习

不要只做自己会做的、比较简单的题目
要做比较常见的、但自己不太熟悉心里没底的题目，比如面试中经常会考的动态规划、搜、回溯、递归
当你在练习时觉得不爽、不舒服、很枯燥的话，这说明已经跳出了舒适区，这样的练习才会有所提高

养成一个习惯，要让“切题四件套”变成自己的条件反射：

Clarification
- Possible Solutions
- compare(time/space)
optimal(加强)
Coding(多写)
Test cases

用熟悉的编辑器练习。

获取反馈：做完后看 Solution 和 Discussion。

“五遍刷题法”：

第一遍，看题目，想解法，如果十几分分想不出来直接看题解，看看别人的解法，最好能够默写出来第二遍，自己尝试写出第三遍，隔几天后再次写一下，体会+上自己的优化第四遍，一周过去后，再来一一遍第五遍，复习，例如面试前。这里说的五遍不一定刚好是五遍，而是要做出来自己的体会和思考才是最重要的。

刻意练习不是简单重复，而是跳出自己的舒适圈，不断扩大自己的舒适圈，同时在练习的过程也是需要不断反馈和改进。

ShannonChenCHN commented 3 years ago

第五节理论讲解：数组&链表

Q&A

Q: 老师，链表增删应该也得先查询到指定的位置吧，这样算上查询的时间，链表对数组感觉也没优势啊 A: 你这样理解是对的，也正是因为这样，在平时项目里我们很难会实际使用链表。但是有一种情况，比如区块链或者比特币，我们很少随机访问中间位置的节点，而绝大部分时候我们就在尾部叠加新节点。

ShannonChenCHN commented 3 years ago

第六节面试题：反转一个单链表&判断链表是否有环

ppt: https://github.com/ShannonChenCHN/algorithm-1/blob/master/05-%E6%95%B0%E7%BB%84%E3%80%81%E9%93%BE%E8%A1%A8.pdf

要点：

做练习时记住记住切题四件套
有些题目做起来思路比较简单，但对代码实现能力和代码简洁程度要求比较高，所以面试之前一定要做好准备，不然面试时写起代码来很慌乱，代码逻辑也比较乱不够简洁
我们可以把反转链表的常用语句先记住，多练习

ShannonChenCHN commented 3 years ago

07 | 理论讲解：堆栈&队列

ppt: https://github.com/ShannonChenCHN/algorithm-1/blob/master/06-%E5%A0%86%E6%A0%88%E3%80%81%E9%98%9F%E5%88%97.pdf

Stack - First In First Out (FIFO) • Array or Linked List
Queue - First In Last Out (FILO) • Array or Linked List

Big-O Cheat Sheet: https://www.bigocheatsheet.com/

ShannonChenCHN commented 3 years ago

08 | 面试题：判断括号字符串是否有效

20. Valid Parentheses

09 | 面试题：用队列实现栈&用栈实现队列

ShannonChenCHN commented 3 years ago

ShannonChenCHN / algorithm-and-data-structure