1. 双指针

算法中的双指针使用，有时候会觉得很巧妙，解决了很多的问题。首先双指针也是个很宽泛的概念，它类似于遍历中的i和j。但区别是，这两个指针是同时移动的

1.1 题型归纳

这里将题型归纳为三种，分别如下：

  • 快慢指针（前后按不同步调的两个指针）

  • 前后双端指针（一个在首，一个在尾部，向中间靠拢）

  • 固定间隔的指针（以i，i + k的间距的两个指针）

1.2 比较版本号

给出两个版本号version1和version2，请比较它们的大小

版本号由一个或多个修订号组成，各修订号由一个'.'连接。每个修订号由多位数字组成，可能包含前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。例如：2.5.33和0.1都是有效的版本号

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值 。也就是说，修订号1和修订号001相等。如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如：版本1.0小于版本1.1，因为它们下标为0的修订号相同，而下标为1的修订号分别为0和1，即：0 < 1

返回规则如下：

  • 如果version1 > version2返回1

  • 如果version1 < version2返回-1

  • 除此之外返回0

示例1：

  1. 输入：version1 = "1.01", version2 = "1.001"
  2. 输出：0
  • 忽略前导零，01和001都表示相同的整数1

示例2：

  1. 输入：version1 = "1.0", version2 = "1.0.0"
  2. 输出：0
  • version1没有指定下标为2的修订号，即视为0

示例3：

  1. 输入：version1 = "0.1", version2 = "1.1"
  2. 输出：-1
  • version1中下标为0的修订号是0，version2中下标为0的修订号是1 。由于0 < 1，所以version1 < version2

解题思路：

使用双指针，i负责记录遍历v1字符串的索引，j负责记录遍历v2字符串的索引。由它们控制外层循环的停止条件

内部实现两个内循环，分别遍历v1和v2中的字符。使用x = x * 10 + c算法，将字符格式的版本号变为真正的数字，遇到.停止本次内循环

当两个内循环停止后，比较本次的两个版本号。如果不相等，直接返回最终结果。如果相等，继续执行外层循环，由此开启下一轮的内循环，完成后续版本号的对比

如果版本号一直相等，只有当v1和v2中全部字符遍历结束时，外层循环才会停止，并返回结果相等

代码实现：

  1. class Solution {
  2.     func compareVersion(_ version1: String, _ version2: String) -> Int {
  4.         var i = 0;
  5.         var j = 0;
  7.         while(i < version1.count || j < version2.count) {
  9.             var x = 0;
  11.             while(i < version1.count){
  13.                 let c = version1[i];
  14.                 i += 1;
  16.                 if(c == "."){
  17.                     break;
  18.                 }
  20.                 x = x * 10 + Int(c)!;
  21.             }
  23.             var y = 0;
  25.             while(j < version2.count){
  27.                 let c = version2[j];
  28.                 j += 1;
  30.                 if(c == "."){
  31.                     break;
  32.                 }
  34.                 y = y * 10 + Int(c)!;
  35.             }
  37.             if(x > y){
  38.                 return 1;
  39.             }
  41.             if(x < y){
  42.                 return -1;
  43.             }
  44.         }
  46.         return 0;
  47.     }
  48. }

  • 时间复杂度：O(n + m)

  • 空间复杂度：O(1)

2. 动态规划

动态规划（DP）：Dynamic Programming，实际上是一种思想，通过将优化问题分解为更简单的⼦问题，并利⽤整体问题的最优解取决于其⼦问题的最优解，这⼀事实来解决优化问题的算法技术

动态规划的两个关键点：

  • 重叠⼦问题

  • 最优⼦结构

2.1 解决问题的⽅式

动态规划提供了两种解决问题的⽅法：

  • ⾃顶向下的记忆化

    • 在这种⽅法中，尝试通过递归找到较⼩⼦问题的解决⽅案，从而解决较⼤的问题

    • 每当我们解决⼀个⼦问题时，我们都会缓存它的结果，这样如果它被多次调⽤，我们就不会重复解决它

    • 相反，我们可以只返回保存的结果。这种存储已解决⼦问题结果的技术称为记忆化

  • ⾃底向上的制表法

    • 制表与⾃上⽽下的⽅法相反，避免了递归。在这种⽅法中，我们“⾃下⽽上”的解决问题，即：⾸先解决所有相关的⼦问题

    • 通常会填写⼀个n维表来完成。根据表中的结果，然后计算顶部（原始问题）的解决⽅案

使⽤动态规划解决的问题有个明显的特点：

  • ⼀旦⼀个⼦问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做⽆后效性

  • 动态规划只解决每个⼦问题⼀次，具有天然剪枝的功能，从⽽减少计算量

动态规划解题思路分为两步：

  • 状态定义：定义动态规划过程中涉及的变量状态

  • 转移⽅程：归纳和抽象出⼦问题对应的数学⽅程

2.2 最长公共子序列

给出两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回0

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串

例如：”ace“ 是 “abcde“ 的子序列，但 “aec“ 不是 “abcde“ 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列

示例1：

  1. 输入：text1 = "abcde", text2 = "ace"
  2. 输出：3
  • 最长公共子序列是”ace“ ，它的长度为3

示例2：

  1. 输入：text1 = "abc", text2 = "abc"
  2. 输出：3
  • 最长公共子序列是”abc“ ，它的长度为3

示例3：

  1. 输入：text1 = "abc", text2 = "def"
  2. 输出：0
  • 两个字符串没有公共子序列，返回0

2.2.1 思路分析

我们将两个字符串中的字符进行逐一对比，就可以得到最终的结果。而字符对比的结果，只存在两种情况，相等与不对

如果字符相等：

  • 将相同子序列的长度+1

  • 分别获取t1和t2的下一个字符，进行下一轮对比

当字符不相等：

  • 使用t1当前字符，与t2中后续的字符依次对比。遇到相等字符，触发上面的相对逻辑。否则，从t1中下一个字符，循环往复，对比完t1与t2的所有字符，得到按t1顺序排列的相同子序列长度

  • t2同样需要这个过程，逐一获取t2中字符与t1进行对比，得到按t2顺序排列的相同子序列长度

  • 将t1和t2中相同子序列长度，返回较大值即可

我们按照动态规划解题思路进行分析，首先找到子问题，即：字符对比。然后进行以下两个步骤：

【步骤一】找到状态定义：

  • 相等

  • 不等

【步骤二】找到转移⽅程：定义getResult方法，传入的i和j分别表示两个字符串中，即将对比的字符索引位置，该方法最终返回对比结果

  • 当t1[i] == t2[j]，则1 + getResult(i + 1, j + 1)

  • 当t1[i] != t2[j]，则Max(getResult(i, j + 1), getResult(i + 1, j))

2.2.2 递归解法

递归解法，从所需结果出发不断回溯前一运算，直到回到初值再递推得到所需结果。属于自顶向下的解决方案，从未知到已知

代码实现：

  1. class Solution {
  3.     fileprivate var _t1 : String?;
  4.     fileprivate var _t2 : String?;
  6.     func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
  7.         _t1 = text1;
  8.         _t2 = text2;
  9.         return getResult(i: 0, j: 0);
  10.     }
  12.     fileprivate func getResult(i : Int, j : Int) -> Int {
  14.         if(i == _t1!.count || j == _t2!.count){
  15.             // 所有字符都不匹配
  16.             // 相同子序列长度+0
  17.             return 0;
  18.         }
  20.         if(_t1![i] == _t2![j]){
  21.             // 将相同子序列的长度+1
  22.             // 分别获取t1和t2的下一个字符，进行下一轮对比
  23.             return 1 + getResult(i: i + 1, j: j + 1);
  24.         }
  26.         // 使用t1当前字符，与t2中后续的字符依次对比
  27.         let result1 = getResult(i: i, j: j + 1);
  28.         // 使用t2当前字符，与t1中后续的字符依次对比
  29.         let result2 = getResult(i: i + 1, j: j);
  31.         // 将t1和t2中相同子序列长度，返回较大值即可
  32.         return result1 > result2 ? result1 : result2;
  33.     }
  34. }

如果m == n，则时间复杂度：O(2 ^ n)
image.png

  • 求解过程中，会出现一些重复子问题。而这些子问题每次都会被重复计算，所以算法的执行效率非常低下

2.2.3 缓存优化

算法时间复杂度的优化，可以使⽤⼀个数组来存储⼦问题结果。当想要⼀个⼦问题的解决⽅案时，⾸先查看数组中是否已经存在解决⽅案。如果有，取出。否则，执⾏计算并存储结果

代码实现：

  1. class Solution {
  3.     fileprivate var _t1 : String?;
  4.     fileprivate var _t2 : String?;
  5.     fileprivate var _arr : [[Int]]?;
  7.     func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
  9.         _t1 = text1;
  10.         _t2 = text2;
  11.         _arr = [[Int]].init(repeating: [Int].init(repeating: -1, count: _t2!.count + 1), count: _t1!.count + 1);
  13.         let result = getResult(i: 0, j: 0);
  14.         return result;
  15.     }
  17.     fileprivate func getResult(i : Int, j : Int) -> Int {
  19.         // ⾸先查看数组中是否已经存在解决⽅案
  20.         if(_arr![i][j] == -1) {
  22.             // 未知结果，计算并存储结果
  23.             if(i == _t1!.count || j == _t2!.count){
  24.                 // 所有字符都不匹配
  25.                 // 相同子序列长度+0
  26.                 _arr![i][j] = 0;
  27.             }
  28.             else if(_t1![i] == _t2![j]){
  29.                 // 将相同子序列的长度+1
  30.                 // 分别获取t1和t2的下一个字符，进行下一轮对比
  31.                 _arr![i][j] = 1 + getResult(i: i + 1, j: j + 1);
  32.             }
  33.             else {
  35.                 // 使用t1当前字符，与t2中后续的字符依次对比
  36.                 let result1 = getResult(i: i, j: j + 1);
  37.                 // 使用t2当前字符，与t1中后续的字符依次对比
  38.                 let result2 = getResult(i: i + 1, j: j);
  40.                 _arr![i][j] = result1 > result2 ? result1 : result2;
  41.             }
  42.         }
  44.         // 已知结果，直接返回
  45.         return _arr![i][j];
  46.     }
  47. }

  • 时间复杂度：O(m * n)

  • 空间复杂度：O(m * n)

2.2.4 递推解法

递推解法：从初值出发反复进行某一运算得到所需结果。属于自底向上的解决方案，从已知到未知

创建二维数组的行、列长度时，在两个字符串原有长度基础上各自+1。多创建出来的行与列，元素用0填充。这样做的目的：当遇到字符串中最后一个字符的对比时，不会因为i + 1或j + 1导致数组越界，统一逻辑的处理

代码实现：

  1. class Solution {
  3.     fileprivate var _t1 : String?;
  4.     fileprivate var _t2 : String?;
  5.     fileprivate var _arr : [[Int]]?;
  7.     func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
  9.         _t1 = text1;
  10.         _t2 = text2;
  11.         // 两个字符串原有长度基础上各自+1，元素用0填充
  12.         _arr = [[Int]].init(repeating: [Int].init(repeating: 0, count: _t2!.count + 1), count: _t1!.count + 1);
  14.         let result = getResult();
  15.         return result;
  16.     }
  18.     fileprivate func getResult() -> Int {
  20.         // 从t1与t2字符串的结尾字符开始对比
  21.         for i in (0..<_t1!.count).reversed() {
  22.             for j in (0..<_t2!.count).reversed() {
  24.                 if(_t1![i] == _t2![j]){
  25.                     // 字符相等，在上一次结果上+1
  26.                     // 因为虚拟行列，不用担心数组越界
  27.                     _arr![i][j] = 1 + _arr![i + 1][j + 1];
  28.                     continue;
  29.                 }
  31.                 // 字符不相等，获取[i][j + 1]和[i + 1][j]的结果
  32.                 let result1 = _arr![i][j + 1];
  33.                 let result2 = _arr![i + 1][j];
  35.                 // 选择较大的值，记录在[i][j]中
  36.                 _arr![i][j] = result1 > result2 ? result1 : result2;
  37.             }
  38.         }
  40.         // 返回最终的计算结果
  41.         return _arr![0][0];
  42.     }
  43. }

  • 时间复杂度：O(m * n)

  • 空间复杂度：O(m * n)

示例：

  1. let text1 = "nematode knowledge";
  2. let text2 = "empty bottle";
  4. let solution = Solution();
  5. print("\(solution.longestCommonSubsequence(text1, text2))");

使用递推法求解后，会生成以下矩阵：
image.png

上述代码是从字符串结尾处开始对比，如果从字符串的起始字符开始，需要进行简单的修改：

  1. class Solution {
  3.     fileprivate func getResult() -> Int {
  5.         for i in 1..._t1!.count {
  6.             for j in 1..._t2!.count {
  8.                 if(_t1![i - 1] == _t2![j - 1]){
  9.                     _arr![i][j] = 1 + _arr![i - 1][j - 1];
  10.                     continue;
  11.                 }
  13.                 let result1 = _arr![i][j - 1];
  14.                 let result2 = _arr![i - 1][j];
  16.                 _arr![i][j] = result1 > result2 ? result1 : result2;
  17.             }
  18.         }
  20.         return _arr![_t1!.count][_t2!.count];
  21.     }
  22. }

  • 从索引1位置开始遍历字符串，将索引0当成虚拟行列使用

  • 对比字符时，则需要t1[i - 1] == t2[j - 1]，通过-1进行索引值的修正

  • 当前[i][j]位置的值，使用i - 1和j - 1配合计算

  • 最终计算结果，在数组的[t1.count][t2.count]中存储

2.2.5 空间优化

以上算法的空间复杂度为O(n * m)，但通过代码可以得知，只要有上一行的结果，即可推算出当前行的结果。所以我们可以定义两个一维数组，分别存储上一行与当前行的结果

按照这个思路，我们将长度较短的字符串作为列，可以让数组所需的空间更小，从而进一步优化空间

  1. class Solution {
  3.     fileprivate var _row : String?;
  4.     fileprivate var _col : String?;
  5.     // 当前行
  6.     fileprivate var _currRow : [Int]?;
  7.     // 上一行
  8.     fileprivate var _prevRow : [Int]?;
  10.     func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
  12.         // 较长字符串作为行
  13.         _row = text1.count >= text2.count ? text1 : text2;
  14.         // 较短字符串作为列
  15.         _col = text1.count >= text2.count ? text2 : text1;
  17.         _currRow = [Int].init(repeating: 0, count: _col!.count + 1);
  18.         _prevRow = [Int].init(repeating: 0, count: _col!.count + 1);
  20.         let result = getResult();
  21.         return result;
  22.     }
  24.     fileprivate func getResult() -> Int {
  26.         for i in 1..._row!.count {
  27.             for j in 1..._col!.count {
  29.                 if(_row![i - 1] == _col![j - 1]){
  30.                     // _prevRow为上一行，j - 1为上一列，等同于二维数组的arr[i - 1][j - 1]
  31.                     _currRow![j] = 1 + _prevRow![j - 1];
  32.                     continue;
  33.                 }
  35.                 //等同于二维数组的arr[i - 1][j]
  36.                 let result1 = _prevRow![j];
  37.                 //等同于二维数组的arr[i][j - 1]
  38.                 let result2 = _currRow![j - 1];
  39.                 // 将较大的结果，更新当前行的j列上
  40.                 _currRow![j] = result1 > result2 ? result1 : result2;
  41.             }
  43.             // 将当前行的结果赋值给上一行，准备下一轮的循环使用
  44.             _prevRow = _currRow;
  45.         }
  47.         return _currRow![_col!.count];
  48.     }
  49. }

  • 时间复杂度：O(m * n)

  • 空间复杂的：O(2 * min(m, n))

2.2.6 公共子序列

通过矩阵，反推出两个字符串的公共子序列内容：

  1. class Solution {
  3.     fileprivate var _t1 : String?;
  4.     fileprivate var _t2 : String?;
  5.     fileprivate var _arr : [[Int]]?;
  7.     func commonSubsequence(_ text1: String, _ text2: String) -> [String]? {
  9.         _t1 = text1;
  10.         _t2 = text2;
  11.         _arr = [[Int]].init(repeating: [Int].init(repeating: 0, count: _t2!.count + 1), count: _t1!.count + 1);
  13.         let result = getResult();
  14.         return result;
  15.     }
  17.     fileprivate func getResult() -> [String]? {
  19.         // 得到公共子序列的最大长度
  20.         var k = get_lcs_lenght();
  22.         if(k == 0){
  23.             return nil;
  24.         }
  26.         // 按最大长度分配结果数组的空间
  27.         var result = [String].init(repeating: "", count: k);
  28.         // 从最终的结果，向初始位置推算
  29.         var i = _t1!.count;
  30.         var j = _t2!.count;
  31.         k -= 1;
  33.         while(k >= 0){
  35.             if(_t1![i - 1] == _t2![j - 1]){
  36.                 result[k] = _t1![i - 1];
  37.                 k -= 1;
  38.                 i -= 1;
  39.                 j -= 1;
  40.                 continue;
  41.             }
  43.             if(_arr![i][j - 1] > _arr![i - 1][j]){
  44.                 j -= 1;
  45.             }
  46.             else{
  47.                 i -= 1;
  48.             }
  49.         }
  51.         return result;
  52.     }
  54.     fileprivate func get_lcs_lenght() -> Int {
  55.         for i in 1..._t1!.count {
  56.             for j in 1..._t2!.count {
  58.                 if(_t1![i - 1] == _t2![j - 1]){
  59.                     _arr![i][j] = 1 + _arr![i - 1][j - 1];
  60.                     continue;
  61.                 }
  63.                 let result1 = _arr![i][j - 1];
  64.                 let result2 = _arr![i - 1][j];
  66.                 _arr![i][j] = result1 > result2 ? result1 : result2;
  67.             }
  68.         }
  70.         return _arr![_t1!.count][_t2!.count];
  71.     }
  72. }

2.3 背包问题

给定一个背包容量target，再给定一个物品数组nums，能否按一定方式选取nums中的元素得到target，每个元素选一次/每个元素选多次/选元素进行排列组合

根据上述需求，可以分为四种背包问题：

  • 0/1背包问题：每个元素最多选取一次

  • 完全背包问题：每个元素乐意重复选择

  • 组合背包问题：背包中的物品要考虑顺序

  • 分组背包问题：不止一个背包，需要遍历每个背包

2.3.1 0/1背包

以0/1背包问题为例，使用动态规划的思想解决

给定n个物品的重量和价值，从中选择物品放在容量为w的背包中（表示选择物品重量不超过w），同时每个物品最多允许选择1个，使得背包中物品价值之和最高

输入：

  • int Values[n]：物品的价值

  • int Weights[n]：物品的重量

  • int LimitWeight：背包容量剩余大小

    输出：

  • MaxValue：背包里的物品最大价值

2.3.2 思路分析

拆解为子问题：物品的选取。每个物品只能选一个，在不超过背包容量的情况下，保证背包中物品总价值最高

状态定义：

  • 选取物品

  • 不选取物品

转移⽅程：

  • 选取物品：value + getResult(index: index + 1, limit: limit - weight)

    • 当前物品价值 + 即将获取的后续物品价值，预先将背包剩余重量 - 当前物品重量

  • 不选取物品：getResult(index: index + 1, limit: limit)

    • 跳过本次物品，直接获取的后续物品价值

2.3.3 递归解法

  1. class Solution {
  3.     fileprivate var _weights: [Int]?;
  4.     fileprivate var _values: [Int]?;
  6.     func knapsack(_ weights: [Int], _ values: [Int], _ limit: Int) -> Int {
  8.         _weights = weights;
  9.         _values = values;
  11.         return getResult(index: 0, limit: limit);
  12.     }
  14.     fileprivate func getResult(index : Int, limit : Int) -> Int {
  16.         var max = 0;
  18.         if(limit <= 0 || index >= weights.count){
  19.             // 背包没有空间，或者物品已经取完，本次选取的物品价值返回0
  20.             return max;
  21.         }
  23.         // 获取当前物品重量
  24.         let weight = _weights![index];
  25.         // 获取当前物品价值
  26.         let value = _values![index];
  28.         if(weight > limit){
  29.             // 当前物品重量，超过背包剩余重量，放弃本次物品，继续选取下一个物品
  30.             max = getResult(index: index + 1, limit: limit);
  31.             // 返回可选取的后续物品的总价值
  32.             return max;
  33.         }
  35.         // 选取本次物品，背包中的物品价值增加
  36.         var selectedValue = value;
  37.         // 选取本次物品，背包中的剩余重量减少
  38.         let selectedWeight = limit - weight;
  39.         // 继续选取下一个物品
  40.         selectedValue += getResult(index: index + 1, limit: selectedWeight);
  42.         // 放弃本次物品，直接选取下一个物品
  43.         let skipValue = getResult(index: index + 1, limit: limit);
  45.         // 比较两种选取方式中，可获得更大的物品价值
  46.         max = selectedValue > skipValue ? selectedValue : skipValue;
  48.         // 返回更大的物品价值
  49.         return max;
  50.     }
  51. }
  • 时间复杂度：O(m ^ n)

2.3.4 缓存优化

  1. class Solution {
  3.     fileprivate var _weights: [Int]?;
  4.     fileprivate var _values: [Int]?;
  5.     fileprivate var _arr: [[Int]]?;
  7.     func knapsack(_ weights: [Int], _ values: [Int], _ limit: Int) -> Int {
  9.         _weights = weights;
  10.         _values = values;
  11.         // 创建二维数组作为缓存，i和j分别为物品数量和背包限制的总重量
  12.         _arr = [[Int]].init(repeating: [Int].init(repeating: -1, count: limit + 1), count: weights.count + 1);
  14.         return getResult(index: 0, limit: limit);
  15.     }
  17.     fileprivate func getResult(index : Int, limit : Int) -> Int {
  19.         if(limit <= 0 || index >= weights.count){
  20.             // 背包没有空间，或者物品已经取完，本次选取的物品价值返回0
  21.             return 0;
  22.         }
  24.         if(_arr![index][limit] == -1) {
  26.             // 获取当前物品重量
  27.             let weight = _weights![index];
  28.             // 获取当前物品价值
  29.             let value = _values![index];
  31.             if(weight > limit){
  32.                 // 当前物品重量，超过背包剩余重量，放弃本次物品，继续选取下一个物品
  33.                 _arr![index][limit] = getResult(index: index + 1, limit: limit);
  34.                 // 返回可选取的后续物品的总价值
  35.                 return _arr![index][limit];
  36.             }
  38.             // 选取本次物品，背包中的物品价值增加
  39.             var selectedValue = value;
  40.             // 选取本次物品，背包中的剩余重量减少
  41.             let selectedWeight = limit - weight;
  42.             // 继续选取下一个物品
  43.             selectedValue += getResult(index: index + 1, limit: selectedWeight);
  45.             // 放弃本次物品，直接选取下一个物品
  46.             let skipValue = getResult(index: index + 1, limit: limit);
  48.             // 比较两种选取方式中，可获得更大的物品价值
  49.             _arr![index][limit] = selectedValue > skipValue ? selectedValue : skipValue;
  51.             // 返回更大的物品价值
  52.             return _arr![index][limit];
  53.         }
  55.         // 命中缓存
  56.         return _arr![index][limit];
  57.     }
  58. }

  • 时间复杂度：O(m * n)

  • 空间复杂度：O(m * n)

2.3.5 递推解法

  1. class Solution {
  3.     fileprivate var _weights: [Int]?;
  4.     fileprivate var _values: [Int]?;
  5.     fileprivate var _arr: [[Int]]?;
  7.     func knapsack(_ weights: [Int], _ values: [Int], _ limit: Int) -> Int {
  9.         _weights = weights;
  10.         _values = values;
  11.         // 创建二维数组作为缓存，i和j分别为物品数量和背包限制的总重量
  12.         _arr = [[Int]].init(repeating: [Int].init(repeating: 0, count: limit + 1), count: weights.count + 1);
  14.         return getResult(limit: limit);
  15.     }
  17.     fileprivate func getResult(limit : Int) -> Int {
  19.         for i in 1..._weights!.count {
  20.             for j in 1...limit{
  22.                 // 获取当前物品重量
  23.                 let weight = _weights![i - 1];
  24.                 // 获取当前物品价值
  25.                 let value = _values![i - 1];
  27.                 if(weight > j){
  28.                     // 当前物品重量，超过背包剩余重量，放弃本次物品，使用上一次的物品总价值填充
  29.                     _arr![i][j] = _arr![i - 1][j];
  30.                     continue;
  31.                 }
  33.                 // 选取本次物品，背包中的物品价值增加
  34.                 var selectedValue = value;
  35.                 // 选取本次物品，背包中的剩余重量减少
  36.                 let selectedWeight = j - weight;
  37.                 // 在剩余重量相同的条件下，加入上一次物品选择后的总价值
  38.                 selectedValue += _arr![i - 1][selectedWeight];
  40.                 // 放弃本次物品，在相同重量的条件下，得到上一次物品选择后的总价值
  41.                 let skipValue = _arr![i - 1][j];
  43.                 // 比较两种选取方式，保存更大的物品价值
  44.                 _arr![i][j] = selectedValue > skipValue ? selectedValue : skipValue;
  45.             }
  46.         }
  48.         // 返回最终物品选取的总价值
  49.         return _arr![_weights!.count][limit];
  50.     }
  51. }

  • 时间复杂度：O(m * n)

  • 空间复杂度：O(m * n)

2.2.6 空间优化

  1. class Solution {
  3.     fileprivate var _weights: [Int]?;
  4.     fileprivate var _values: [Int]?;
  6.     fileprivate var _curRow: [Int]?;
  7.     fileprivate var _preRow: [Int]?;
  9.     func knapsack(_ weights: [Int], _ values: [Int], _ limit: Int) -> Int {
  11.         _weights = weights;
  12.         _values = values;
  14.         // 初始化当前行
  15.         _curRow = [Int].init(repeating: 0, count: limit + 1);
  16.         // 初始化上一行
  17.         _preRow = [Int].init(repeating: 0, count: limit + 1);
  19.         return getResult(limit: limit);
  20.     }
  22.     fileprivate func getResult(limit : Int) -> Int {
  24.         for i in 0..<_weights!.count {
  26.             // 获取当前物品重量
  27.             let weight = _weights![i];
  28.             // 获取当前物品价值
  29.             let value = _values![i];
  31.             for j in 1...limit{
  33.                 if(weight > j){
  34.                     // 当前物品重量，超过背包剩余重量，放弃本次物品，使用上一次的物品总价值填充
  35.                     _curRow![j] = _preRow![j];
  36.                     continue;
  37.                 }
  39.                 // 选取本次物品，背包中的物品价值增加
  40.                 var selectedValue = value;
  41.                 // 选取本次物品，背包中的剩余重量减少
  42.                 let selectedWeight = j - weight;
  43.                 // 在剩余重量相同的条件下，加入上一次物品选择后的总价值
  44.                 selectedValue += _preRow![selectedWeight];
  46.                 // 放弃本次物品，在相同重量的条件下，得到上一次物品选择后的总价值
  47.                 let skipValue = _preRow![j];
  49.                 // 比较两种选取方式，保存更大的物品价值
  50.                 _curRow![j] = selectedValue > skipValue ? selectedValue : skipValue;
  51.             }
  53.             for j in 1...limit{
  54.                 print("\(_curRow![j])，");
  55.             }
  56.             print("\n");
  58.             // 将当前行的结果赋值给上一行，准备下一轮的循环使用
  59.             _preRow = _curRow;
  60.         }
  62.         // 返回最终物品选取的总价值
  63.         return _curRow![limit];
  64.     }
  65. }

  • 时间复杂度：O(m * n)

  • 空间复杂的：O(2n)

2.2.6 空间再优化

  1. class Solution {
  3.     fileprivate var _weights: [Int]?;
  4.     fileprivate var _values: [Int]?;
  6.     // 当前行，同时也作为上一行的数据
  7.     fileprivate var _curRow: [Int]?;
  9.     func knapsack(_ weights: [Int], _ values: [Int], _ limit: Int) -> Int {
  11.         _weights = weights;
  12.         _values = values;
  14.         // 初始化当前行
  15.         _curRow = [Int].init(repeating: 0, count: limit + 1);
  17.         return getResult(limit: limit);
  18.     }
  20.     fileprivate func getResult(limit : Int) -> Int {
  22.         for i in 0..<_weights!.count {
  24.             // 获取当前物品重量
  25.             let weight = _weights![i];
  26.             // 获取当前物品价值
  27.             let value = _values![i];
  29.             // 由于当前总价值，依赖于上一行的总价值，所以剩余空间需要从大到小遍历，避免上一行的数据提前被覆盖为当前行
  30.             for j in (1...limit).reversed() {
  32.                 if(weight > j){
  33.                     // 当前物品重量，超过背包剩余重量，放弃本次物品，使用上一次的物品总价值填充
  34.                     // 使用curRow存储当前总价值，同时它也作为上一行的总价值在使用
  35.                     // 所以不去修改curRow[j]的值，相当于使用了上一次的物品总价值
  36.                     continue;
  37.                 }
  39.                 // 选取本次物品，背包中的物品价值增加
  40.                 var selectedValue = value;
  41.                 // 选取本次物品，背包中的剩余重量减少
  42.                 let selectedWeight = j - weight;
  43.                 // 在剩余重量相同的条件下，加入上一次物品选择后的总价值
  44.                 selectedValue += _curRow![selectedWeight];
  46.                 // 放弃本次物品，在相同重量的条件下，得到上一次物品选择后的总价值
  47.                 // 只要curRow[j]没有提前被覆盖，拿到的就是上一次的物品总价值
  48.                 let skipValue = _curRow![j];
  50.                 // 比较两种选取方式，保存更大的物品价值
  51.                 _curRow![j] = selectedValue > skipValue ? selectedValue : skipValue;
  52.             }
  53.         }
  55.         // 返回最终物品选取的总价值
  56.         return _curRow![limit];
  57.     }
  58. }

  • 时间复杂度：O(m * n)

  • 空间复杂的：O(n)

总结

双指针题型归纳：

  • 快慢指针（前后按不同步调的两个指针）

  • 前后双端指针（一个在首，一个在尾部，向中间靠拢）

  • 固定间隔的指针（以i，i + k的间距的两个指针）

动态规划：

  • 动态规划（DP）：Dynamic Programming，实际上是一种思想，通过将优化问题分解为更简单的⼦问题，并利⽤整体问题的最优解取决于其⼦问题的最优解，这⼀事实来解决优化问题的算法技术

  • 动态规划的两个关键点：

    • 重叠⼦问题

    • 最优⼦结构

  • 动态规划提供了两种解决问题的⽅法：

    • ⾃顶向下的记忆化

    • ⾃底向上的制表法

  • 使⽤动态规划解决的问题有个明显的特点：

    • ⼀旦⼀个⼦问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做⽆后效性

    • 动态规划只解决每个⼦问题⼀次，具有天然剪枝的功能，从⽽减少计算量

  • 动态规划解题思路分为两步：

    • 状态定义：定义动态规划过程中涉及的变量状态

    • 转移⽅程：归纳和抽象出⼦问题对应的数学⽅程