记录在《极客时间》平台上《算法面试通关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);
