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

算法复杂度

1. 时间复杂度 Big O
   1. $O(1)$O(1)：常数复杂度
   2. $O(log\;n)$O(logn)：对数复杂度
   3. $O(n)$O(n)：线性时间复杂度
   4. $O(n^2)$O(n2)：平方
   5. $O(n^3)$O(n3)：立方
   6. $O(2^n)$O(2n)：指数
   7. $O(n!)$O(n!)：阶乘
2. 空间复杂度

数组&链表

1. 翻转链表
2. 链表两两交换
3. 判断链表有没有环
   • set 存放
   • 快慢指针

堆栈&队列

1. 堆栈 FILO
2. 队列 FIFO
3. 判断括号是否合法
   • 堆栈：左：push栈 右：peek栈顶元素，匹配，最后栈为空
   • 碰到左右相连的括号，就替换掉，最后为空：时间复杂度略高
4. 用队列实现堆栈&用堆栈实现队列
   • stack ==> queue：两个栈来实现，一个栈做输入栈，一个做输出栈
     • push
     • pop
     • peek
   • queue ==> stack：类似

优先队列：Priority Queue

1. 正常入，按照优先级出
2. 实现
   • heap
   • 二叉搜索树
3. 实时判断数据流中第k大的元素
   • 维护k大小的有序数组，需排序
   • 小顶堆
4. 返回滑动窗口的最大值
   • 大顶堆
   • 双端队列Deque：1：入队列 2：维护（不是有限队列的解法）

哈希表

1. Map
   • HashMap：hash table
   • TreeMap：二叉搜索树，相对有序
2. Set
   • HashSet ：hash table
   • TreeSet：二叉搜索树，相对有序
3. 有效的字母异位词：cat & act； tar&rat
   • 排序比较：$O(N*log\,N)$O(N∗logN)（快排）
   • map：$O(N)$O(N)
     • 比较两个词的字母出现次数的map
     • 将词里每个字符映射到16个子母的数组中，用数组的值进行计数，最后比较数组
4. 两数之和
   • 暴力：愣循环
   • set
5. 三数之和
   • 3层循环:$O(n^3)$O(n3)
   • 2层循环+set：$O(n^2)$O(n2)
   • sort-find：$O(n^2)$O(n2)
     1. sort
     2. 两边往中间夹

树&二叉树&二叉搜索树

1. 树
   • 树
   • 二叉树
   • 二叉搜索树
     1. 左子树上所有节点的值均小于它的根节点的值
     2. 右子树上所有节点的值均大于它的根节点的值
     3. Recursively，左右子树也分别为二叉搜索树
2. 图
3. 验证二叉搜索树
   • 中序遍历是否升序
   • 递归：左子树最小值，右子树最大值
4. 二叉树、二叉搜索树的最近公共祖先
   • Path：$O(N)$O(N)从根节点找到A，再找到B，比较找到公共节点
   • Recursion：$O(N)$O(N)
     findPorQ（root，P，Q）
     if （root==Q or root == P） return root；
     findPorQ（root left，P，Q）
     findPorQ（root right，P，Q）
     
5. 二叉搜索树找最近公共祖先：
   • 增加通过二叉搜索树特性的判断（如果都小于根节点，就在左子树中找，都大于根就在右子树中找，否则就是根节点）

二叉树遍历

1. Pre-order：根左右
2. In-order ：左根右
3. Post-order：左右根

递归&分治

1. Recursion：$n!$n!
2. Divde & Conquer
3. 计算$x^n$xn，$pow(x,n)$pow(x,n)
   • 暴力：$O(N)$O(N)
   • 分治：
     

求众数

• 输入 [1,2,3,2,2]
  输出3
  $count(x) > n/2$count(x)>n/2
  1. 暴力：$O(N^2)$O(N2)
  2. map：$O(N)$O(N)
  3. sort
  4. 分治

贪心算法

• 对问题求解时候，总是做出在当前看来最好的选择
• 结果不一定最优
• 使用场景:问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。
• 贪心算法与动态规划：贪心算法对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
• 买卖股票的最佳时期：
  • 持有一股，买卖无数次

广度优先搜索 BFS

• 维护一个队列
  
• 二叉树分层打印
  1. BFS
  2. DFS也可以实现，二维数组，level为数组的序号

深度优先搜索 DFS

• 推荐递归写法
  

最大最小深度

• BFS
• DFS

括号生成，给出n，输出所有可能的n对括号

• 深度优先遍历（左右括号条件判断，左括号n右括号，则结束该支的遍历，）
  
  
  

减枝

• N皇后问题
• 数独问题

二分查找

• 必须有序
• 存在明确上下界
• 可以通过索引访问
  –> 数组适合，链表不适合
• 模板
  

1. sqrt
   • 二分法
   • 牛顿迭代法