记录在《极客时间》平台上《算法面试通关40讲》专栏的学习笔记
作者信息：覃超 前Facebook工程师，卡内基梅隆大学计算机硕士
课程海报如下：欢迎扫描右下方二维码订阅（有优惠哦）
- 第1讲 合格程序员第一步：算法与数据结构
- 第2讲 如何事半功倍的学习算法与数据结构
- 第3讲 如何计算算法复杂度
- 第4讲 如何通过LeetCode来进行算法题目练习
- 第5讲 理论讲解：数组&链表
- 第6讲 面试题：翻转一个单链表&判断链表是否有环
- 第7讲 理论讲解：堆栈&队列
- 第8讲 面试题：判断括号字符串是否有效
- 第9讲 面试题：用队列实现栈&用栈实现队列
- 第10讲 理论讲解：优先队列
- 第11讲 面试题：返回数据流中的第K大元素
- 第12讲 面试题：返回滑动窗口中的最大值
- 第13讲 理论讲解：哈希表
- 第14讲 面试题：有效的字母异位词
- 第15讲 面试题：两数之和
- 第16讲 面试题：三数之和
- 第17讲 理论讲解：树&二叉树&二叉搜索树
- 第18讲 面试题：验证二叉搜索树
- 第19讲 面试题：二叉树&二叉搜索树的最近公共祖先
- 第20讲 理论讲解：二叉树遍历
- 第21讲 理论讲解：递归&分治
- 第22讲 面试题：Pow（x,n）
- 第23讲 面试题：求众数
- 第24讲 理论讲解：贪心算法
- 第25讲 面试题：买卖股票的最佳时机
- 第26讲 理论讲解：广度优先搜索
- 第27讲 理论讲解：深度优先搜索
- 第28讲 面试题：二叉树层次遍历
- 第29讲 面试题：二叉树的最大和最小深度
- 第30讲 面试题：生成有效括号组合
- 第31讲 理论讲解：剪枝
- 第32讲 面试题：N皇后问题
- 第33讲 面试题：数独问题
- 第34讲 理论讲解：二分查找
- 第35讲 面试题：实现一个求解平方根的函数
- 第36讲 理论讲解：字典树
- 第37讲 面试题：实现一个字典树
- 第38讲 面试题：二维网格中的单词搜索问题
- 第39讲 理论讲解：位运算
- 第40讲 最后一些经验分享
- 第41讲 面试题：2的幂次方问题&比特位计数问题
- 第42讲 面试题：N皇后问题的另一种解法
- 第43讲 理论理解：动态规划（上）
- 第44讲 理论理解：动态规划（下）
- 第45讲 面试题：爬楼梯
- 第46讲 面试题：三角形的最小路径和
- 第47讲 面试题：乘积最大子序列
- 第48讲 面试题：股票买卖系列
- 第49讲 面试题：最长上升子序列
- 第50讲 面试题：零钱兑换
- 第51讲 面试题：编辑距离
- 第52讲 理论讲解：并查集
- 第53讲 面试题：岛屿的个数&朋友圈（上）
- 第54讲 面试题：岛屿的个数&朋友圈（下）
- 第55讲 理论讲解：LRU Cache
- 第56讲 面试题：设计和实现一个LRU Cache缓存机制
- 第57讲 理论讲解：布隆过滤器
- 第58讲 课程重点回顾
- 第59讲 FAQ答疑&面试中切题四件套
- 第60讲 回到起点：斐波拉契数列
- 第61讲 白板实战番外篇：斐波拉契数列
- 第62讲 最后一些经验分享
- 完结
每天的工作计划使用优先级队列的方式进行计划；
加密货币中有大量的算法和数据结构，区块使用LinkedList，区块内使用二叉树来表示交易信息；
编程是内功的修炼；
算法与数据结构有趣且实用；
推荐书籍：《异类不一样的成功启示录》切碎知识点；刻意练习；获得反馈
明确题目意识；找到所有可能的解法；编码实现；进行测试；
时间复杂度：常数，对数，线性，平方，立方，指数，阶乘
斐波那契数列的时间复杂度为O（2^n）
Master Theorem 二分查找O(logn),二叉树遍历O(n),二维矩阵查找O(n)
坚持刻意练习；练习缺陷弱点地方；不舒服，不爽和枯燥；
数组：内存中连续的存储区域，根据索引O(1)查找，插入和删除操作O（n）
链表：很多的插入和删除操作，不知道有多少个元素，查找是O(n)，单链表和双链表
题目列表:
206翻转一个链表
def reverseList(self, head): cur, prev = head, None while cur: # 一次性赋值，先计算好右边一次性赋值 cur.next, prev, cur = prev, cur, cur.next return prev24 对一个链表进行两两翻转
def swapPairs(self, head) pre, pre.next = self, head while pre.next and pre.next.next: a = pre.next b = a.next pre.next, b.next, a.next = b, a, b.next pre = a return self.next141 判断链表是否有环
def hasCycle(self, head) fast = slow = head while slow and fast and fast.next: slow = slow.next fast = fast.next.next if slow if fast: return Ture return False 栈：先进后出；查找O(n),插入删除O（1）
队列：先进先出；查找O(n),插入删除O（1）
20 判断括号是否合法 栈空O(n)
def isValid(self, s): stach = [] paren_map = {')':'(',']':'[','}':'{'} for c in s: if c not in paren_map: stack.append(c) //新进入一个符号栈是空的或者与栈顶元素不匹配则false elif not stack or paren_map[c] != stack.pop(): return False return not stack public boolean isValid(String s){ int length; do{ length = s.length(); s = s.replace("()", "").replace("[]","").replace("{}",""); }while(length != s.length()); return s.length() == 0; } 1.左括号直接压进栈；
2.右括号如果栈不为空与栈顶匹配则出栈；
3.栈空则说明合法
栈实现队列：使用两个栈，输入栈进行数据输入，输出栈输出数据；
进行输出时判断输出栈是否有元素，如果没有就将输入栈全部放入输出栈；
队列实现栈：两个队列，一个入队列一个临时队列，在进行数据输出时将除了队列底部最后一个数据留下外， 其他数据放入临时队列，数据读取完之后再将临时队列的元素放入原队列。
优先队列的实现方式：
- heap（二叉树，多项式堆，斐波那契堆）
- 二叉搜索树 二叉堆（最小最大的数据在最上面）合并O（n），删除O（logn）
703 实时返回第K大元素 1.每次保存K个最大值，每次进行更新，需要排序O(nklogn)
2.维护一个size为k的小顶堆 O（nlogk）
class KthLargest{ final PriorityQueue<Integer> q; final int k ; public KthLargest(int k , int[] a){ this.k =k; q = new PriorityQueue<>(k); for(int n : a){ add(n); } public int add(int k ){ if(q.size() < k){ q.offer(n); }else if(q.peek < n){ q.poll(); q.offer(n); } return q.peek; } }239 滑动窗口最大值
- 维护一个大顶堆，每次最大值就是堆顶元素；O(nlogk)
- 双端队列， k个元素进入队列，进入队列时如果前面数都比该数小就出队列，保证区间 最左端是最大值；
def maxSlidingWindow1(self, nums, k){ if not nums : return [] window, res = [],[] for i, x in enumerate(nums): if i>= k and window[0] <= i-k: window.pop(0) while window and nums[window[-1]] <= x: window.pop() window.append(i) if(i >= k-1): res.append(nums[window[0]]) return res }1.哈希表，哈希函数，哈希冲突（拉链法）
2.map表示映射关系【HashMap vs TreeMap】
3.set里面的元素不重复<哈希表或者二叉树>HashSet(O(1)) vs TreeSet(二叉树（O（logn））)
4.list可以重复
242 有效的字母异位词 “rat” "art"
- sort 然后进行比较 O（nlogn）
- map 计数{letter:count} O(n)
def isAnagram3(self, s, t) return sorted(s) == sorted(t) def isAnagram2(self, s, t) dic1, dic2 = {}, {} for item in s : dic1[item] = dic1.get(item, 0) +1; for item in s : dic2[item] = dic2.get(item, 0) +1; return dic1 == dic2 def isAnagram1(self, s, t) dic1, dic2 = [0]*26, [0]*26 for item in s : dic1[ord(item) - ord('a')] += 1 for item in s : dic2[ord(item) - ord('a')] += 1 return dic1 == dic2 1.暴力搜索 O（n^2）
2.构建hashmap，可以一次性先放进去也可以走着放着。
15 三数和 18. 四数和
- 暴力循环 O（n^3）
- SET集合，枚举a,b，在set里面查找（-a-b）
- 先排序再找，枚举a,在剩下的数组中维护两个指针（left,right）， 不断从两边向中间夹, sum(a,b,c)>0 right--;sum(a,b,c)<0 left++;
def thressSum(self, nums): if len(nums) < 3: return [] nums.sort() res = set() for i,v in enumerate(nums[:2]): if i>=1 and v == nums[i-1]: continue d = {} for x in nums[i+1:]: if x not in d: d[-v-x] = 1 else: res.add((v, -v-x, x)) return map(list, res) 1.树：特殊的链表
2. 二叉树：只有两个孩子
3. 二叉搜索树：左子树<根，根> 右子树 O（logn）
98 验证二叉搜索树
- 中序遍历 左子树 根 右子树，是升序的 O（n）
- 递归方式，max<-node.left;min<-node.right;max<root;min>root; O(N)
def isValidBST(self, root): inorder = self.inorder(root) return inorder == list(sorted(set(inorder))) def inorder (self, root): if root is none: return [] return self.inorder(root.left) + [root.val] + self.inorder(root.right) def isValidBST(self, root): self.prev = None return self.helper(root) def helper(self,root): if root is None: return True if not self.helper(root.left): return False if self.prev and self.prev.val >= root.val return False self.prev = root return self.helper(root.right) public boolean isValid(TreeNode root, Integer min , Integer max){ if(root == null) return ture; if(min != null && root.val <= min ) return false; if(max != null && root.val >- max) return false; return isValid(root.left,min,root.val) && isValid(root.right,root.val,max); 