面试准备:算法

发表于

算法概述

  • NP：
    • non-deterministic polynomial problem非确定性问题(难)
  • NPC：
    • NP完全问题(最难)
  • P问题：
    • polynomial problem多项式问题(易)

  • 一般算法分类：

    • 判定性问题：

    • 最优化问题：

      • 标准分治：
      • 动态规划：
      • 贪心算法：
      • | 算法比较 | 标准分治 | 动态规划 | 贪心算法 |
        | ——– | :——: | :——: | :——: |
        | 适用类型 | 通用类型 | 优化问题 | 优化问题 |
        | 子问题 | 每个子问题不同 | 重复子问题 | 只有一个子问题 |
        | 最优子结构 | 不需要 | 必须满足 | 必须满足 |
        | 子问题数 | 都要解决 | 都要解决 | 解决一个 |
        | 选择与求解顺序 | 先选择 后解决 | 先解决 后选择 | 先选择 后解决 |

    • 构造性问题：

    • 计算性问题：

分治法

  • 思路：
    • 将问题划分为一些独立的子问题，递归求解各子问题，后合并

回溯法

  • 背景：
    • 一些问题，可以分解，但是不能给出明确的动态规划或递归解法(如果能得出明显的递推公式迭代求解的问题，不用回溯)，此时可以考虑用回溯法解决
  • 区别：
    • 递归是一种算法结构，是在函数中调用函数本身来解决问题
    • 回溯是一种算法思想，通过不同的尝试来生成问题的解，有点类似穷举，但是不同之处在于，回溯会剪枝；
    • 回溯搜索是DFS的一种，但对于某个搜索树来说(搜索树是记录路径和状态判断的作用)，回溯和DFS的区别在于：回溯在求解过程中不保留完整的树结构，而DFS则记录下完整的搜索树；
      • 为了减少存储空间，在DFS中，用标志的方法记录访问过的状态，这种处理方法使得DFS和回溯法没什么区别。
  • 思路：
  • 优点：
    • 程序结构明确，可读性强，易于理解
    • 通过对问题的分析可以大大提高运行效率
  • DFS：
    • 有深度优先搜索DFS和广度优先搜索BFS
    • 分支界限法中，一般用的是FIFO或最小耗费搜搜：一次性将一个节点的所有子节点求出，并放入一个待求子节点的队列；通过遍历这个队列完成搜索；
    • DFS：是将一条合法路径求出后，再转向上求第二条合法路径
    • 回溯法一般用DFS？
      • 通过约束函数可以杀死一些节点，从而节约时间
      • DFS是将路径逐一求出的，在求路径的过程中杀死节点可以省去所有子节点所花费的时间
      • FIFO也可以实现剪枝，但是DFS的解决思路很清晰。

def dfs(nums, res, temp_list, index):
if index > len(nums): return
if index == len(nums): res.append(temp_list); return
for i in range(index, len(table[index])):
temp_list.append(table[index][i])

贪心算法

  • 定义：
    • 贪心算法（Greedy Algorithm，又称贪婪算法），指在对问题求解时，不从整体最优上加以考虑，而总是做出在当前看来是最好的选择。也就是说，所做出的是在某种意义上的局部最优解。
  • 算法条件：
    • 贪心选择性质：
      • 在求解一个问题的过程中，如果在每个阶段的选择都是当前状态下的最优选择，即局部最优选择，并且最终能够求得问题的整体最优解。
        • 贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题。
    • 最优子结构性质：
      • 当一个问题的最优解包含了这个问题的子问题的最优解时，就说明问题具有了最优子结构。
    • 如果不具有上述性质，贪心法对某些实例只能得到近似解。
  • 优点：
    • 一旦证明正确，则是一种高效算法。
  • 算法步骤：
    • 建模：将问题的求解看作是一系列的决策
    • 子问题：问题分解为子问题，定义子问题的最优解结构，确保每一步决策所依据的局部最优性质
    • 证明每一步基于局部最优选择最终导致全局最优
  • 证明：
    • 数学归纳法
  • 典型问题：
    • 活动选择问题
    • 装载问题
    • 最大延迟调度问题
    • 最优前缀问题（哈夫曼编码）
    • 最小生成树问题（Prim算法）
    • 单源最短路径（Dijkstra算法）

动态规划

DP概念

  1. DP问题特征：
    1. 重叠子问题：能够分解为重叠的若干子问题
      • 子问题的重叠性：两个子问题其实是同一个子问题，只是作为了不同问题的子问题而已。
    2. 最优子结构：一个问题的最优解包含其子问题的最优解。
      • 子问题的无关性：同一个原问题的一个子问题的解不影响另一个子问题的解，也就是子问题之间不共享资源，相互独立。
    3. 无后效性：每个状态都是过去历史的完整总结
  2. 设计DP算法步骤：
    1. 分段：原问题分解为若干相互重叠的子问题
    2. 分析：分析问题是否具有最优子结构，并找到递推式
    3. 求解：利用递推式自底向上计算
    4. 重构最优解：将每个子问题所做的选择存在一个表中，这样就不必根据代价来重构这些信息，增加O(1)的时间。
  3. 实现方法：
    • 带备忘的自顶向下法(top-down with memoization):
      • 按照自然的递归形式进行求解，每个递归过程带备忘，记录之前的计算结果
      • 时间复杂度：
        • 求解一个已经计算出结果的子问题时，直接返回结果，所以该方法也是对每个子问题只求解一次，所以求解规模为n个子问题，递归循环迭代n次，所以for循环过程的迭代次数也是一个等差数列，由聚合分析(aggregate analysis，n个序列最坏时间复杂度就是T(n))所以也是O(n2).
    • 自底向上法(bottom-up method):
      • 将子问题按规模排序，由小到大进行求解
      • 时间复杂度：
        • 主体是嵌套的双重循环，内层for循环的迭代次数构成一个等差数列，所以是O(n2)
  4. 子问题图：
    • 计算时间复杂度可以通过子问题图来构建
    • 子问题图G=(V,E)
    • 子问题的求解时间：与对应顶点的度(出射边的数目)成正比V
    • 子问题的个数：等于子问题图的定点数E
    • 动态规划运行时间：子问题的时间之和，so与顶点和边的数量程线性关系。
  5. DP思想：
    每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。
  6. 好处：
    1. 问题规模越大，好处越明显
    2. 题目规模n，分治法O(2^n)，DP仅为O(n2)
  7. 与贪心区别：
    1. 动态规划法先求子问题的解，然后通过求解子问题构造原问题的解；贪心算法是直接地解原问题。
    2. 动态规划法通过对若干局部最优解的比较，去掉了次优解，从而产生了更高一层次的局部最优解。 相当于对较低层次的局部最优解进行贪心的选择而得到高一级的局部最优解，因而最终产生一个最高层次的局部最优解。贪心法每阶段只作一个挑选，各阶段的解一经选出就固定不变了，后阶段的局部最优是基于前阶段的挑选，所以往往只能求出次优解。
  8. 与分治法区别：
    1. 共同点：把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。
    2. 不同点：分治法每次分解的子问题数目比较少，子问题之间界限清楚，也就是递归的每一步生成的子问题都是新的，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且是重叠子问题，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。

DP题型

  1. 简单基础DP
    1. 递推：
      • 超级楼梯Fibonacci.py
      • 数字三角形tri3.py
    2. 背包：
      • 01bag.py
    3. LIS：最长递增子序列
      • LIS.py
    4. LCS：最长公共子序列
      • LCS.py
  2. 区间DP
    一般是枚举区间，把区间分成左右两部分，然后求出左右区间再合并
    1.
  3. 树形DP
    建立在树的数据结构上的DP，一般状态比较好想，通过dfs维护从根到叶子或叶子到根的状态转移
  4. 数位DP
    数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数，它是按位来进行计数统计的，可以保存子状态，速度较快。数位dp做多了后，套路基本上都差不多，关键把要保存的状态给抽象出来，保存下来。
  5. 概率/期望DP
  6. 状态压缩DP
    TSP
    插头DP
  7. 数据结构优化DP
    1. 二进制优化
    2. 单调队列优化
    3. 斜率优化
    4. 四边形不等式优化
  • LeetCode例题：
      1. Maximum Product Subarray：最大连续子数组乘积
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        def maxProduct(nums):
        	# 法一：原始版一维动态规划，空间复杂度O(n)
        	if nums == [0]: return 0
        	dp, res_min, res_max = [nums[0]]*len(nums), [nums[0]]*len(nums), [nums[0]]*len(nums)
        	for i in range(1, len(nums)):
        		res_max[i] = max(nums[i], max(res_max[i-1]*nums[i], res_min[i-1]*nums[i]))
        		res_min[i] = min(nums[i], min(res_max[i-1]*nums[i], res_min[i-1]*nums[i]))
        		dp[i] = max(dp[i-1], res_max[i])
        	return dp[-1]

        	# 法二：优化版动态规划，空间复杂度O(1)
        	# 思路：只需要i-1的结果，所以只需要用last分别保存上一次结果即可
        	if nums == [0]: return 0
        	dp = res_min = res_max = nums[0]
        	for i in nums[1:]:
        		last_max, last_min = res_max, res_min
        		res_max = max(i, max(last_max*i, last_min*i))
        		res_min = min(i, min(last_max*i, last_min*i))
        		dp = max(dp, res_max)
        	return dp
thank you for donating~