算法面试

川长思鸟来 2022-02-22 05:55 142阅读 0赞

## [算法面试通关40讲][40] ##

![006tNc79ly1g24l9nt9hyj30u01hc0xe.jpg][]

> 知识点

![006tNc79ly1g1uft5q9g8j31jf0u012a.jpg][]

--------------------

### Array ###

> 理论

*  Access: O(1)
 *  Insert: 平均O(n)
 *  Delete: 平均O(n)

--------------------

### Singly Linked List & Doubly Linked List ###

> 理论

*  space: O(n)
 *  prepend: O(1)
 *  append: O(1)
 *  lookup: O(n)
 *  insert: O(1)
 *  delete: O(1)

> 面试题

*  反转一个单链表：206. Reverse Linked List (Easy)
 *  两两交换链表中的节点：24
 *  环形链表：141. 判断链表中是否有环
 *  环形链表 II：142. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
 *  k个一组翻转链表：25.

--------------------

### Stack & Queue ###

> 理论

*  stack: FILO
 *  queue: FIFO

[常见算法复杂度][Link 1]

> 面试题

*  用栈实现括号匹配：20 Valid Parentheses (Easy)
 *  用栈实现队列：232 Implement Queue using Stacks (Easy)
 *  用队列实现栈：225 Implement Stack using Queues (Easy)

--------------------

### Priority Queue ###

> 理论

1）特点

正常进，优先级出

2）实现

*  Heap (Binary | Binomial | Fibonacci)
    
     *  min heap
     *  max heap
 *  Binary Search Tree

> 面试题

*  数据流中的第K大元素：703.
    
     *  思路：维护一个min heap
     *  Time: n \* O(logk)
 *  滑动窗口最大值：239.
    
     *  思路1：维护一个max heap
     *  Time: n \* O(logk)
     *  思路2：使用双端队列，每滑动一次保证最左边的数据最大
     *  Time: n \* O(1)

--------------------

### Hash ###

> 理论

*  HashMap | HashSet
    
     *  无序
     *  O(1)
     *  哈希表实现
 *  TreeMap | TreeSet
    
     *  有序
     *  O(logN)
     *  二叉搜索树实现

> 面试题

*  1.  有效的字母异位词
 *  1.  两数之和
 *  1.  三数之和

--------------------

### Tree ###

> 理论

*  Tree
 *  BT
 *  BST
    
     *  O(logN)
 *  Graph

插入、删除、查找操作的平均时间复杂度也比较稳定，是 O(logn)

链表 -(两个指针)-> 二叉树 -(查找)-> 二叉查找树 -(稳定性)-> 平衡二叉查找树

链表 -(多个指针)-> 图

> 面试题

*  验证二叉搜索树：98
 *  二叉树&二叉搜索树的最近公共祖先：235 | 236

--------------------

### 二叉树的遍历 ###

> 理论

前序 | 中序| 后序

--------------------

### 递归 & 分治（Divde & Conquer） ###

> 理论

递归 - 循环 | 通过函数体来进行的循环

例子：求 n!

栈

是一个先逆向递推后正向递推的过程

代码模版

def recursion(level, param1, param2):
        # recursion terminator
        if level > MAX_LEVEL:
            print result
            return
    
        # process logic in current level
        process_data(level, data)
    
        # drill down
        recursion(level+1, new_param1, new_param2)
    
        # reverse the current level status if needed 可能的收尾工作 or 恢复现场
        reverse_state(level)

*  终止条件
 *  做梦
 *  醒来

例子：Fibnacci array

出现重复问题

解决保存中间结果

分治

思想：

![006tKfTcly1g1bbgpg7cij30yc0eeahe.jpg][]

例子：

![006tKfTcly1g1bbiqw0sgj30xs0f8wgm.jpg][]

代码模版

def divide_conquer(problem, param1, param2):
        # recursion terminator
        if problem is None:
            print result
            return
    
        # process data
        data = prepare_data(problem)
        subproblems = split_problem(problem, data)
    
        # conquer subproblems
        subresult1 = divide_conquer(subproblems[0], new_param1, new_param2)
        subresult2 = divide_conquer(subproblems[1], new_param1, new_param2)
    
        # process and generate the final result
        result = process_result(subresult1, subresult2)

> 比较

*  分治算法要求分割成的子问题，**不能有重复子问题**
 *  而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中**存在大量的重复子问题**

> 面试题

*  Pow(x,n)：50
 *  1.  求众数

--------------------

### 贪心算法 ###

> 理论

在对问题求解时，总是做出在**当前**看来是最好的选择

例子：用纸币去匹配一个36数额的面值最少数量

将问题分解成子问题，找到子问题的最优解，递推到最终问题的最优解

贪心算法是对每个问题都做出最优解，**不能回退**，只关注眼前利益

动态规划会保存以前的运算结果，并根据以前的结果对当前进行选择，**有回退功能**，关注的全局

> 面试题

*  1.  买卖股票的最佳时机 II

--------------------

### BFS ###

> 理论

*  例子：水滴波纹
 *  层层推进
 *  注意重复，使用集合记录访问过的节点
 *  符合人类

> 实现

队列

def bfs(graph, start, end):
    
        queue = []
        queue.append([start])
    
        visited = set()  # 树可省，图不可
        visited.add(start)
    
        while queue:
            node = queue.pop()
            visited.add(node)
    
            process(node)
    
            nodes = generate_related_nodes(node)
            queue.push(nodes)
            
        # other processing work

--------------------

### DFS ###

> 理论

*  一路到底，回头再走
 *  注意重复，使用集合记录访问过的节点
 *  符合计算机

> 实现

递归（推荐）

def dfs(node):
        # 递归写法
        visited = set()
        visited.add(node)
        
        # process current node here
    
        for next_node in node.children():
            if not not next_node in visited:
                dfs(next_node)

栈

def dfs_stack(self, tree):
        if tree.root is None:
            return []
    
        visited = set()
        stack = [tree.node]
    
        while stack:
            node = stack.pop()
            visited.add(node)
    
            process(node)
    
            nodes = generate_related_nodes(node)
            stack.push(nodes)
    
        # other processing work

bfs & dfs

![006tKfTcly1g1bfn6cfryj31z70u0kc9.jpg][]

> 面试题

*  1.  Binary Tree Level Order Traversal
 *  1.  二叉树的最大深度
 *  1.  二叉树的最小深度
 *  1.  Generate Parentheses

--------------------

### 剪枝 ###

> 理论

*  搜索问题
 *  提高搜索效率
 *  去差选优
 *  下棋问题

> 面试题

*  1.  N-Queens
 *  1.  N皇后 II
 *  1.  Valid Sudoku
 *  1.  Sudoku Solver

--------------------

### 二分查找 ###

> 理论

*  sorted （单调递增或者递减）
 *  bounded（存在上下界）
 *  accessible by index（能够通过索引访问）

一般的认为数组适合二分查找，链表不适合

> 实现

def bin_search(arr, target):
      # O(logn)
      l, r = 0, len(arr)
      while l <= r:
        mid = (l+r)/2
        if target == arr[mid]:
          return mid
        elif target > arr[mid]:
          l = mid + 1
        else:
          r = mid - 1

> 面试题

*  1.  x 的平方根

class Solution(object):
        def mySqrt(self, x):
            """ :type x: int :rtype: int 迭代中的二分法 """
            if x == 0 or x == 1:
                return x
            
            l = 1
            r = x
            
            while l <= r:
                m = (l + r) / 2
                if m * m == x:
                    return m
                elif m * m > x:
                    r = m - 1
                else:
                    l = m + 1
            return r  # 当无整数平方根时，取小值

--------------------

### Trie ###

> 理论

字典树

![006tNc79ly1g1vbcuvebnj30i40eljul.jpg][]

用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计

> 优点

最大限度地减少无谓的字符串比较，查询效率比哈希表高

> 核心思想

空间换时间。利用字符串的**公共前缀**来降低查询时间的开销以达到提高效率的目的。

> 实际存储结构

![006tNbRwly1fy0tvtp813j30ys0hadnr.jpg][]

> 实现

ALPHABET_SIZE = 256
    
    class TrieNode:
      # Trie node class
      def __init(self):
        self.children = [Node] * ALPHABET_SIZE
        # isEndOfWord is True if node represent
        # the end of the word
        self.isEndOfWord = False

> 基本性质

*  根节点不包含字符，除根节点每一个节点都只包含一个字符
 *  从根节点到某一节点，路径上经过的字符串连接起来，为该节点对应的字符串
 *  每个节点的所有子节点包含的字符都不相同

> 面试题

*  208、实现 Trie (前缀树)
 *  212、单词搜索 II

--------------------

### 位运算 ###

> 什么是位运算

程序中的所有数据在计算机内存中是以二进制的形式存储的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。

> 位操作

![006tNc79ly1g1vio2j6cxj315g0u0dzi.jpg][]

> 异或

![006tNc79ly1g1viruor18j318m0u0gyd.jpg][]

> 实战中常用的位运算操作

![006tNc79ly1g1visu5h6zj31k20u0qkj.jpg][]

> 更为复杂的位运算操作

![006tNc79ly1g1viu4r7u6j31ms0u01kx.jpg][]

> 面试题

*  1.  位1的个数
 *  1.  2的幂
 *  1.  比特位计数
 *  1.  N-Queens II

--------------------

### 动态规划（DP） ###

> 理论

*  递归 + 记忆话 --> 递推
 *  状态的定义：opt\[n\], dp\[n\], fib\[n\]
 *  状态转移方程：opt\[n\] = best\_of(opt\[n-1\], opt\[2\], …)
 *  最优子结构

递归 - 自上而下

递推 - 自下而上

> fib

递推公式：F(n) = F(n-1) + F(n-2); F(0) = 0; F(1) = 1

记忆化，将fib的时间复杂度由 O(2^n) 降低到 O(n)

> count the paths

if a[i,j] == '空地':
      opt[i, j ] = opt[i-1, j] + opt[i, j-1]
    else:
      opt[i, j ] = 0

> DP VS 回溯 VS 贪心

*  回溯（递归） - 重复计算
 *  贪心 - 永远局部最优
 *  DP - 记录局部最优子结构 / 多种记录值

> 面试题

*  1.  爬楼梯
 *  1.  三角形最小路径和
 *  1.  乘积最大子序列
 *  1.  买卖股票的最佳时机
 *  1.  买卖股票的最佳时机 II
 *  1.  买卖股票的最佳时机 III
 *  1.  最长上升子序列
 *  1.  零钱兑换
 *  1.  编辑距离

--------------------

### 并查集 ###

> 理论

Union & find：一种**树型**的数据结构，用于处理一些不交集的合并及查询问题

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集

Union：将两个子集合并成同一个集合

> 实现

![006tNbRwly1fy8tghdildj30u80u00vi.jpg][]

> 优化一

Rank（排名）就是树的深度

将rank较低的子集合并到rank较高的子集中，形成一个总体rank较低的并查集

![006tNbRwly1fy8ter80s1j313l0u0gnv.jpg][]

![006tNbRwly1fy8ffy5qs7j30u00yc4gb.jpg][]

> 优化二

路径压缩

将单链表压缩成树

![006tNbRwly1fy8t7x4txyj31f60tgjta.jpg][]

![006tNbRwly1fy8tbumq52j30u011y426.jpg][]

> 面试题

*  1.  岛屿的个数

***法一：染色***

def __init__(self):
            self.dx = [-1, 1, 0, 0]
            self.dy = [0, 0, -1, 1]
    
        def numIslands(self, grid):
            """ :type grid: List[List[str]] :rtype: int """
            if not grid or not grid[0]:
                return 0
    
            self.grid = grid
            self.max_x = len(grid)
            self.max_y = len(grid[0])
            self.visited = set()
    
            l = [self.dfs(i, j) for i in xrange(self.max_x) for j in xrange(self.max_y)]
    
            return sum(l)
    
        def dfs(self, x, y):
            if 0 <= x < self.max_x and 0 <= y < self.max_y and self.grid[x][y] == '1' and (x, y) not in self.visited:
    
                self.visited.add((x, y))
    
                for k in xrange(4):
                    self.dfs(x + self.dx[k], y + self.dy[k])
    
                return 1
    
            return 0

![006tKfTcly1g0vki1jbi9j318y0u07tc.jpg][]

***法二：并查集***  
![006tKfTcly1g0vknmzxwdj30u00z5e59.jpg][]  
![006tKfTcly1g0vknuk0e0j31l00u0axb.jpg][]

*  1.  朋友圈

--------------------

### LRU Cache ###

> 理论

记忆

钱包 - 储物柜

代码模块

*  Least recently used（最近最少使用）
 *  Double LinkedList
 *  O(1)查询
 *  O(1)修改、更新

> LFU

最近最不常用页面置换算法

> 面试题

*  1.  LRU缓存机制

--------------------

### Bloom Filer (布隆过滤器) ###

在实际的数据存储之前，挡掉一些一定不存在的数据，起到加速或减轻系统负担的作用

> 理论

*  一个很长的**二进制向量**和一个**映射函数**
 *  布隆过滤器可以检索一个元素是否在一个集合中

> 优点

*  空间效率和查询时间都远远超过一般的算法

> 缺点

*  有一定的误识别率和删除困难

> 误识别率  
> 对判断存在的元素有一定的错误；对判断不存在的元素一定不存在

![006tNbRwly1fy8t1evxycj31b80u00w6.jpg][]

> 案例

*  比特币 (Redis VS Bloom Filter)
 *  分布式系统 (Map-Reduce)

--------------------

### 课程重点回顾 ###

> 五个代码模版

*  Recursion  
    ![006tNbRwly1fyesjh592ij311s0u04oo.jpg][]

function recursion(level, param1, param2) { 
      // 递归终止条件
      if (level > MAX_LEVEL) { 
        // 打印结果
        return;
      }
    
      // 处理当前层级的逻辑
      processData(level, data);
    
      // 递归
      recursion(level + 1, p1, p2);
    
      // 如果需要，清除当前层的状态
      reverseState(level);
    }

*  DFS  
    ![006tNbRwly1fyesl8v9tbj311u0u01g1.jpg][]

*  BFS  
    ![006tNbRwly1fyeslkgxilj30yn0u0dzy.jpg][]

const visited = new Set();
    function bfs(grapg, start, end) { 
      const queue = [];
      queue.push(start);
      visited.add(start);
    
      while (queue.length) { 
        node = queue.pop();
        visited.add(node);
    
        process(node);
        nodes = generateRelatedNodes(node);
        queue.push(nodes);
      }
    }

*  二分查找  
    ![006tNbRwly1fyeslpbw8rj31000u04n8.jpg][]

*  动态规划  
    ![006tNbRwly1fyeslto5a4j310a0u0ano.jpg][]

// 状态定义
    const dp = [[]];
    
    // 初始状态
    dp[0][0] = x;
    dp[0][1] = y;
    
    // DP 状态推导
    
    for (let i = 0; i <= n; i++) { 
      for (let j = 0; j <= matchMedia; j++) { 
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
      }
    }
    
    return dp[m][n]  // 最优解

> 位运算操作

![006tNbRwly1fyespovgw9j31a60u015a.jpg][]

--------------------

### 答疑 & 练习 & 切题 ###

![006tNbRwly1fyet15asraj31df0u01gz.jpg][]

--------------------

### fibonacci ###

*  [拜托，面试别再问我斐波那契数列了！！！][Link 2]
 *  [拜托，面试别再问我TopK了！！！][TopK]
 *  [拜托，面试别再让我数1了！！！][1]

--------------------

### 经验分享 ###

> 环境准备

*  iTerms + Oh-my-zsh
 *  IDE (Pycharm, IntelliJ, Webstorm, GoLand)
 *  Editors (VS Code, Sublime, Atom, VIM, etc)

> 结束语

*  算法和数据结构是内⼒
 *  重在练习(修⾏)

[40]: https://time.geekbang.org/course/intro/130
[006tNc79ly1g24l9nt9hyj30u01hc0xe.jpg]: https://ws2.sinaimg.cn/large/006tNc79ly1g24l9nt9hyj30u01hc0xe.jpg
[006tNc79ly1g1uft5q9g8j31jf0u012a.jpg]: https://ws4.sinaimg.cn/large/006tNc79ly1g1uft5q9g8j31jf0u012a.jpg
[Link 1]: http://www.bigocheatsheet.com/
[006tKfTcly1g1bbgpg7cij30yc0eeahe.jpg]: https://ws2.sinaimg.cn/large/006tKfTcly1g1bbgpg7cij30yc0eeahe.jpg
[006tKfTcly1g1bbiqw0sgj30xs0f8wgm.jpg]: https://ws4.sinaimg.cn/large/006tKfTcly1g1bbiqw0sgj30xs0f8wgm.jpg
[006tKfTcly1g1bfn6cfryj31z70u0kc9.jpg]: https://ws2.sinaimg.cn/large/006tKfTcly1g1bfn6cfryj31z70u0kc9.jpg
[006tNc79ly1g1vbcuvebnj30i40eljul.jpg]: https://ws2.sinaimg.cn/large/006tNc79ly1g1vbcuvebnj30i40eljul.jpg
[006tNbRwly1fy0tvtp813j30ys0hadnr.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fy0tvtp813j30ys0hadnr.jpg
[006tNc79ly1g1vio2j6cxj315g0u0dzi.jpg]: https://ws4.sinaimg.cn/large/006tNc79ly1g1vio2j6cxj315g0u0dzi.jpg
[006tNc79ly1g1viruor18j318m0u0gyd.jpg]: https://ws3.sinaimg.cn/large/006tNc79ly1g1viruor18j318m0u0gyd.jpg
[006tNc79ly1g1visu5h6zj31k20u0qkj.jpg]: https://ws4.sinaimg.cn/large/006tNc79ly1g1visu5h6zj31k20u0qkj.jpg
[006tNc79ly1g1viu4r7u6j31ms0u01kx.jpg]: https://ws2.sinaimg.cn/large/006tNc79ly1g1viu4r7u6j31ms0u01kx.jpg
[006tNbRwly1fy8tghdildj30u80u00vi.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fy8tghdildj30u80u00vi.jpg
[006tNbRwly1fy8ter80s1j313l0u0gnv.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fy8ter80s1j313l0u0gnv.jpg
[006tNbRwly1fy8ffy5qs7j30u00yc4gb.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fy8ffy5qs7j30u00yc4gb.jpg
[006tNbRwly1fy8t7x4txyj31f60tgjta.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fy8t7x4txyj31f60tgjta.jpg
[006tNbRwly1fy8tbumq52j30u011y426.jpg]: https://ws4.sinaimg.cn/large/006tNbRwly1fy8tbumq52j30u011y426.jpg
[006tKfTcly1g0vki1jbi9j318y0u07tc.jpg]: https://ws4.sinaimg.cn/large/006tKfTcly1g0vki1jbi9j318y0u07tc.jpg
[006tKfTcly1g0vknmzxwdj30u00z5e59.jpg]: https://ws3.sinaimg.cn/large/006tKfTcly1g0vknmzxwdj30u00z5e59.jpg
[006tKfTcly1g0vknuk0e0j31l00u0axb.jpg]: https://ws1.sinaimg.cn/large/006tKfTcly1g0vknuk0e0j31l00u0axb.jpg
[006tNbRwly1fy8t1evxycj31b80u00w6.jpg]: https://ws2.sinaimg.cn/large/006tNbRwly1fy8t1evxycj31b80u00w6.jpg
[006tNbRwly1fyesjh592ij311s0u04oo.jpg]: https://ws1.sinaimg.cn/large/006tNbRwly1fyesjh592ij311s0u04oo.jpg
[006tNbRwly1fyesl8v9tbj311u0u01g1.jpg]: https://ws2.sinaimg.cn/large/006tNbRwly1fyesl8v9tbj311u0u01g1.jpg
[006tNbRwly1fyeslkgxilj30yn0u0dzy.jpg]: https://ws3.sinaimg.cn/large/006tNbRwly1fyeslkgxilj30yn0u0dzy.jpg
[006tNbRwly1fyeslpbw8rj31000u04n8.jpg]: https://ws4.sinaimg.cn/large/006tNbRwly1fyeslpbw8rj31000u04n8.jpg
[006tNbRwly1fyeslto5a4j310a0u0ano.jpg]: https://ws2.sinaimg.cn/large/006tNbRwly1fyeslto5a4j310a0u0ano.jpg
[006tNbRwly1fyespovgw9j31a60u015a.jpg]: https://ws3.sinaimg.cn/large/006tNbRwly1fyespovgw9j31a60u015a.jpg
[006tNbRwly1fyet15asraj31df0u01gz.jpg]: https://ws2.sinaimg.cn/large/006tNbRwly1fyet15asraj31df0u01gz.jpg
[Link 2]: https://mp.weixin.qq.com/s/3LR-iVC4zgj0tGhZ780PcQ
[TopK]: https://mp.weixin.qq.com/s/FFsvWXiaZK96PtUg-mmtEw
[1]: https://mp.weixin.qq.com/s/A3dLW92SNag8lw7vrQiEHQ