我的刷题计划

2022.03.07

2022.04.26

发布于广东

前言

作为一个专业人士，要保持编码能力的一个方法就是经常做题。为了证明自己的刷题能力，特别地选择了几个高频考点，高频题来做。提高刷题的效率。所以并不会全面地讨论所有知识点，也不会把知识点的所有情况都讨论到。这里只讨论一些个人收集到的高频类型，常见类型，欢迎大家在评论区补充。

以下将从排序、链表、搜索、回溯、动规这5个方面来做。

排序

排一定条件来，把一连串对象排列起来。

经典题：
912. 排序数组

合适训练各种排序算法的模板。

// 快排
void quickSort(vector<int>& nums, int l, int r) {
    if(l >= r) {
        return;
    }
    int p = rand() % (r - l) + l;
    swap(nums[r], nums[p]);
    int pivot = nums[r];
    int i = l;
    int j = r;
    while(i < j) {
        while(i < j && nums[i] <= pivot) i++;
        while(i < j && nums[j] >= pivot) j--;
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[r]);
    quickSort(nums, l, i-1);
    quickSort(nums, i+1, r);
}

347. 前 K 个高频元素
 剑指 Offer II 076. 数组中的第 k 大的数字

用快排就非常合适。快排记得用随机标兵。

剑指 Offer II 077. 链表排序

归并，要注意二分链表的结束条件。

23. 合并K个升序链表

这是链表与排序的综合题了,需要深刻地理解归并的原理
归并题解

406. 根据身高重建队列

技巧是先排序，然后按k位置进行插入
题解

581. 最短无序连续子数组

排序法

621. 任务调度器

这题的标签是排序，但做成了数据结构的类型。可以使用多种不同的数据结构来实现排序。面试中应该还是更倾向手动实现排序算法吧
模拟解

至此，排序算法告一段落。总结下来，各种题型的特点就是需要先排序，再考虑解法。稍难一点的就是要先找出排序的数组，如“任务调度器”。简单一点的就直接给出数组，考虑排序就可以了。

链表

经典的数据结构。常用双指针解法。

经典题：

剑指 Offer 24. 反转链表

141. 环形链表

// 判断链表是否有环
bool hasCycle(ListNode *head) {
    if(!head || !head->next) {
        return false;
    }

    ListNode* slow = head;
    ListNode* fast = head->next;

    while(true) {
        if(slow == fast) {
            return true;
        }
        if(!fast || !slow) {
            break;
        }
        slow = slow->next;
        fast = fast->next;
        if(fast) {
            fast = fast->next;
        } else {
            break;
        }
    }
    return false;
}

142. 环形链表 II

// 找到入环的第一个节点

148. 排序链表

160. 相交链表

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    // 实现一，先计算长度，再使用双指针
    if(!headA || !headB) {
        return nullptr;
    }

    int lenA = 0;
    ListNode* curA = headA;
    while(curA && curA->next) {
        curA = curA->next;
        lenA++;
    }

    int lenB = 0;
    ListNode* curB = headB;
    while(curB && curB->next) {
        curB = curB->next;
        lenB++;
    }

    curA = headA;
    curB = headB;
    if(lenA > lenB) {
        while(lenA > lenB) {
            curA = curA->next;
            lenA--;
        }
    } else {
        while(lenB > lenA) {
            curB = curB->next;
            lenB--;
        }
    }

    while(curA && curB) {
        if(curA == curB) {
            return curA;
        }
        curA = curA->next;
        curB = curB->next;
    }
    
    return nullptr;
}

剑指 Offer II 021. 删除链表的倒数第 n 个结点

经典的双指针用法，入门必做。
链表操作一般需要一个空的头节点，这样就不需要对原来的头节点做特殊处理。
快慢指针解法

114. 二叉树展开为链表

这要求对树的递归过程理解清楚，就不难了。
先序遍历的解法
重点：递归左子树时，root的右指针会被改变，所以要提前保存下来。

146. LRU 缓存

手写一个链表结构，考察链表的综合能力。
手写链表
重点：双向链表的修改复杂度是O(1)，结合Hash表，查找时间复杂度也是O(1)

剑指 Offer II 027. 回文链表

双指针解法, 先把后一半反转, 再用双指针

// 反转链表
ListNode* reverseList(ListNode* head) {
    if(!head || !head->next) {
        return head;
    }
    ListNode* cur = reverseList(head->next);
    head->next->next = head;
    return cur;
}

bool isPalindrome(ListNode* head) {
    if(!head || !head->next) {
        return true;
    }
    
    // 1. 找到后半段链表
    ListNode* slow = head;
    ListNode* fast = head->next->next;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }

    // 2. 反转链表
    ListNode* l1 = head;
    ListNode* l2 = reverseList(slow->next);
    // 断开前后的链接
    slow->next = nullptr;

    // 3. 判断是否回文
    while(l1 && l2) {
        if(l1->val != l2->val) {
            return false;
        }
        l1 = l1->next;
        l2 = l2->next;
    }

    return true;
}

总结，一般考虑两指针，复杂一点的可能要更多的指针。个别类型使用递归的实现会更方便。

双指针

283. 移动零

void moveZeroes(vector<int>& nums) {
    if(nums.empty()) {
        return;
    }

    int not_zero = 0;
    int zero = 0;
    while(zero < nums.size()) {
        if(nums[zero] != 0) {
            swap(nums[not_zero], nums[zero]);
            not_zero++;
        }
        zero++;
    }

    while(not_zero < nums.size()) {
        nums[not_zero] = 0;
        not_zero++;
    }
}

19. 删除链表的倒数第 N 个结点

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if(!head) {
        return head;
    }

    ListNode* HEAD = new ListNode();
    HEAD->next = head;
    ListNode* cur = head;

    // 计算总长度
    int len = 0;
    while(cur) {
        cur = cur->next;
        len++;
    }
    n = len - n;

    cur = HEAD;
    while(cur && n > 0) {
        n--;
        cur = cur->next;
    }
    // 删除节点
    cur->next = cur->next->next;        
    
    return HEAD->next;
}

31. 下一个排列

下一个排列算法详解：思路+推导+步骤，看不懂算我输

void nextPermutation(vector<int>& nums) {
    if(nums.empty()) {
        return;
    }

    int n = nums.size();
    int i = n - 2;
    // 从右向左，找到相邻升序的一对数
    while(i >= 0 && nums[i] >= nums[i+1]) {
        i--;
    }
    if(i >= 0) {
        // 从右向左，找到nums[i]大的数
        int j = n - 1;
        while(j >= i && nums[j] <= nums[i]) {
            j--;
        }
        // 交换得到增长最小的数
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin()+i+1, nums.end());
}

75. 颜色分类

// 一次遍历
void sortColors(vector<int>& nums) {
    if(nums.empty() || nums.size() == 1) {
        return;
    }

    int n = nums.size();
    int red = 0;
    int white = 0;
    int blue = n - 1;

    int RED = 0;
    int WHITE = 1;
    int BLUE = 2;


    while(true) {
        // 1. 找到蓝色的头部
        while(blue >= 0 && nums[blue] == BLUE) blue--;
        if(blue <= red) {
            break;
        }

        // 2. 找到红色的尾部
        while(red < n && nums[red] == RED) red++;

        // 3. 找到不是白色的
        white = red;
        while(white < n && nums[white] == WHITE) white++;
        
        if(white > blue) {
            break;
        }

        // 4. 交换
        if(nums[white] == RED) {
            swap(nums[red], nums[white]);
            red++;
        } else {
            swap(nums[blue], nums[white]);
            blue--;
        }
    }
    return;

这题看似简单，但要求对双指针的运用非常熟练，才能很快地做出来。

15. 三数之和

int n = nums.size();
for(int first=0; first < n; first++) {
    // 排除重复的
    if(first > 0 && nums[first] == nums[first-1]) {
        continue;
    }
    int third = n - 1;
    for(int second=first+1; second < third; second++) {
        // 排除重复的数
        if(second == first+1 || nums[second] != nums[second-1]) {
            while(third > second && 
                nums[first] + nums[second] + nums[third] > 0) {
                    third--;
                }
            if(second < third && nums[first] + nums[second] + nums[third] == 0) {
                ans.push_back({nums[first], nums[second], nums[third]});
            }
        } 
    }
}
return ans;

42. 接雨水

二叉树+搜索

二叉树与搜索都是两个非常大的话题，这里仅讨论在二叉树下的搜索问题。大概总结为以下几种常见题型。

遍历

一般遍历是前序、中序、后序遍历，在这个基础上，可以考察以下几点：

遍历的应用，只要正确应用遍历就可以求解；如
104. 二叉树的最大深度
 112. 路径总和
 剑指 Offer 68 - II. 二叉树的最近公共祖先
遍历时还要做一些操作
226. 翻转二叉树
 113. 路径总和 II
538. 把二叉搜索树转换为累加树

这类题相对比较简单，直接。只要套用递归，搞清楚递归结束条件，依题意做少少变通就可以求解。

特殊的递归函数签名

这一类相对较难，需要对递归函数的定义和签名做一定的修改。

543. 二叉树的直径

递归函数返回当前节点离叶子节点的长度，所求的直径就需要另外的变量来计算。

124. 二叉树中的最大路径和

递归函数返回包含当前节点的最大路径和，所求的全局最大路径和，需要另外的变量计算

101. 对称二叉树

递归函数需要接收两颗树来判断

两层递归

这一类更难一点：因为需要两层的递归。

437. 路径总和 III

第一层求以当节点为根的树是还有满足的路径
第二层路径遍历所有节点，判断其中是否有满足的路径

回溯

17. 电话号码的字母组合
 22. 括号生成
 39. 组合总和
 46. 全排列
 78. 子集
 79. 单词搜索
 301. 删除无效的括号

140. 单词拆分 II

动规

动规是最常考的知识点之一，核心思想是把大问题转化为子问题来求解。判断一个题是否可以用动规求解，就是要看是否能转化为子问题，所有子问题解完了，相应的大问题是否就解完了。

求解过程三板斧：

定义dp——这是最重要，也是最容易被忽略的一步。如果dp定义不清晰，是写不出状态转移方程的。题目难度的增加，也往往是要求从题目中抽象出适当的dp定义。
状态转移方程——这是核心步骤，正确写出来了，基本代码就写完了。
返回结果——最不起眼的步骤，但细节决定成败。很多时候就是阴沟里翻船，所以不能掉以轻心。难一点的题目也喜欢在这里做文章。

动规的分类非常多，个人能力有限，这里只讨论几个常见的类型：

背包：给定一些物品，向背包里放，求解过程中的最大价值、最少物品数量、放置方式等问题。
单串：给定一个串，第i个位置的解，依赖前i-1的解。
双串：给定两个串，第i，j位置的解，与前i-1，j-1的解相关。
区间：给定一个串，第i个位置的解，与[j,i]的区间的解相关。

背包

背包问题与动规非常密切，大多数背包问题都可以使用动规求解。
背包问题可以描述为：给定一些物品，每个物品有对应的体积和价值，背包有一个最大的容量。一般会求背包可以容纳的最大价值。还有一些变种是求是否能刚好装满背包、装满背包需要的最少物品数量、装满背包的方式有多少种，或者具体有哪些方式等问题。

根据物品的数量是否有限，又可以分为完全背包问题：每个类型的物品的数量没有限制、以及0-1背包问题：每个物品数量有限。这里先从完全背包问题开始讨论。

下面会结合例子来讨论，为了讨论框架的统一，会把每个题目转化为物品、体积、价值、容量这些用词，方便理解和记忆。统一框架的好处，还有很多，比如方便交流、可以开发出更多的题目、可以清楚地知道题目的考点等等。

完全背包

139. 单词拆分

物品：字典内的单词
体积：字典内的单词
背包容量：给定字符串s
求解：是否可以刚好把背包装满

三板斧：

dp[i]定义： 是否能组成前i个字符串
初始化： dp(n+1, false)
dp[0] = true 字符串为空时，表示可以组成。
转移方程： dp[i] = dp[i] || dp[i - word.size()] && s[i-word.szie():i] == word
返回： dp[n]

int n = s.size();
vector<bool> dp(n+1, false);
dp[0] = true;

// dp[i] = dp[i] || dp[i-len(word)] 
for(int i=1; i < dp.size(); i++) {
    for(auto word : wordDict) {
        int wordSize = word.size();
        if(i >= wordSize && s.compare(i-wordSize, wordSize, word) == 0) {
            dp[i] = dp[i] || dp[i-wordSize];
        }
    }
}
return dp[n];

279. 完全平方数

物品：平方数
体积：平方数的数值
背包容量：目标数n
求解：把背包刚装满的最少物品数量

三板斧：

dp[i]定义： 组成i所需的最少平方数数量。（放满背包容量i所需要的最少物品数量）与 322. 零钱兑换完全一样。
初始化： dp(n+1, MAX)，MAX表示无使用平方数表示出目标数
转移方程： dp[i] = min(dp[i], dp[i - j] + 1)，j表示平方数
返回： dp[n]

vector<int> dp(n+1, n+1);
dp[0] = 0;

// dp[i] = min(dp[i], dp[i-square]+1)
for(int i=1; i < dp.size(); i++) {
    for(int j=1; j * j <= i; j++) {
        dp[i] = min(dp[i], dp[i-j*j] + 1);
    }
}
return dp[n];

322. 零钱兑换

物品：硬币
体积：每个硬币对应的额度coin
背包容量：待兑换的总金额数amount
求解：把背包刚好装满的最少物品数量

三板斧：

dp[i]定义： 兑换金额i时所需的最少硬币数量。（当背包容量为i时，刚好把背包装满的最少物品数量）
初始化： dp(amount+1, MAX)，长度定义为amount+1是为了处理金额为0的情况；初始值也为MAX只是表示这是无法使用硬币兑换成功。
dp[0]=0这是表示金额为0时，不需要硬币兑换。
转移方程： dp[i] = min(dp[i], dp[i - coin] + 1)
返回： dp[amount] == MAX ? -1 : dp[amount]

vector<int> dp(amount+1, amount+1);
dp[0] = 0;

// dp[i] = min(dp[i], dp[i-coin]+1)
for(int i=1; i < dp.size(); i++) {
    for(auto coin : coins) {
        if(i >= coin) {
            dp[i] = min(dp[i], dp[i-coin] + 1);
        }
    }
}
return dp[amount] == amount+1 ? -1 : dp[amount];

518. 零钱兑换 II

物品：硬币
体积：每个硬币对应的额度coin
背包容量：待兑换的总金额数amount
求解：把背包刚好装满的不同组合数

三板斧：

dp[i]定义： 兑换金额i时的组合数。（当背包容量为i时，刚好把背包装满的不同组合数）
初始化： dp(amount+1, 0), dp[0]=1
转移方程： dp[i] = dp[i] + dp[i - coin]
返回： dp[amount]

vector<int> dp(amount+1, 0);
dp[0] = 1;

// dp[i] = dp[i] + dp[i-coin]
for(auto coin : coins) {
    for(int i=coin; i < dp.size(); i++) {
        dp[i] = dp[i] + dp[i - coin];
    }
}
return dp[amount];

区别：组合数是不关心硬币的使用顺序，所以为了计算上不重复，coin的循环要放到外层。这就是最大的区别。coin在外层，表示dp[i]与coin的顺序无关。

377. 组合总和 Ⅳ

物品：给定的数组
体积：数组中的数值
背包容量：目标数n
求解：把背包刚好装满的不同排列数

三板斧：

dp[i]定义： 背包容量为i时，不同的组合数
初始化： dp(n+1, 0)
转移方程： dp[i] = dp[i] + dp[i - j]，j表示物品体积
返回： dp[n]

vector<int> dp(target+1, 0);
dp[0] = 1;

// dp[i] = dp[i] + dp[i-num]
for(int i=1; i < dp.size(); i++) {
    for(auto num : nums) {
        // 上溢表示组成某一个值时，其排列数的数量非常大
        if(i >= num && dp[i] < INT_MAX - dp[i-num]) {
            dp[i] = dp[i] + dp[i-num];
        }
    }
}
return dp[target];

区别：与 518. 零钱兑换 II 不一样的是，本题求排列数，要把物品放在内层循环。物品在内层循环，表示当前num是组成dp[i]的最后一个数值，所以是有顺序的。

总结：

容量从0到n进行循环
求组合数时，物品在外循环；求排列数时，物品在内循环。

0-1背包

剑指 Offer II 101. 分割等和子集

物品：给定的数组
体积：数组中的数值
背包容量：数组中所有元素的和的一半，设为n
求解：能否刚好装满背包

三板斧

dp[i]定义： 能否使用物品刚好装满容量为i的背包
初始化： dp(n+1, false), dp[0]=true
转移方程： dp[i] = dp[i] || dp[i - j]， j表示物品体积
返回： dp[n]

int target = sum >> 1;
vector<bool> dp(target+1, false);
dp[0] = true;

for(auto num : nums) {
    for(int i=target; i >= num; i--) {
        dp[i] = dp[i] || dp[i-num];
    }
}
return dp[target];

这一题的难点是找到背包容量。这个定义藏得比较深。

0-1背包特点是每个物品只能用一次，为了不重复，物品在外层循环；而且容量要从n到0。这就是与完全背包最大的差别。

494. 目标和

物品：给出的数组
体积：物品代表的数值
背包容量：数组和-target的一半。转换为分割子集。
求解：把背包刚好装满的组合数。

0-1背包，不用区分组合数和排列数。因为每个元素都只能用一次。但实际要用组合数，物品要放在外层循环才对。

三板斧：

dp[i]定义： 刚好装满背包i的组合数
初始化： dp(n+1, 0)
转移方程： dp[i] = dp[i] + dp[i - j]， j表示物品体积
返回 dp[n]

int sum = 0;
for(auto x : nums) {
    sum += x;
}
sum -= target;
if(sum < 0 || sum % 2 != 0) {
    return 0;
}

int n = sum >> 1;
vector<int> dp(n+1, 0);
dp[0] = 1;

for(auto num : nums) {
    for(int i = n; i >= num; i--) {
        dp[i] = dp[i] + dp[i-num];
    }
}
return dp[n];

这题转化为剑指 Offer II 101. 分割等和子集 + 518. 零钱兑换 II。所以物品要在外层循环，内层的容量要从n到0循环。

多维背包问题

474. 一和零

特殊背包

263. 丑数

单串

给定一个串，第i个位置的解，依赖于前i-1的解。

普通单串

70. 爬楼梯

// 爬到第i级的不同方法数量
vector<int> dp(n+1);
// init
dp[1] = 1;
dp[2] = 2;

for(int i=3; i < dp.size(); i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

return dp[n];

338. 比特位计数

// 第i个数的解
vector<int> dp(n+1);
if(n == 0) {
    return dp;
}

dp[1] = 1;
if(n == 1) {
    return dp;
}

dp[2] = 1;
if(n == 2) {
    return dp;
}

for(int i=3; i <= n; i++) {
    dp[i] = dp[i/2] + dp[i%2];
}
return dp;

198. 打家劫舍

// 前i个屋的解
vector<int> dp(n+1);
dp[0] = 0;
dp[1] = nums[0];
for(int i=2; i < dp.size(); i++) {
    dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);
}
return dp[n];

300. 最长递增子序列

// 以第i个元素结尾的数组的解
vector<int> dp(n+1, 1);
dp[0] = 0;
for(int i=2; i < dp.size(); i++) {
    for(int j=i-1; j >=1; j--) {
        if(nums[j-1] < nums[i-1]) {
            dp[i] = max(dp[i], dp[j]+1);
        }
    }
}
return *max_element(dp.begin(), dp.end());

152. 乘积最大子数组

// 以第i个元素结尾的数组的解
int n = nums.size();
vector<int> max_(n);
vector<int> min_(n);
max_[0] = nums[0];
min_[0] = nums[0];
for(int i=1; i < n; i++) {
    max_[i] = max(max_[i-1] * nums[i], max(min_[i-1] * nums[i], nums[i]));
    min_[i] = min(max_[i-1] * nums[i], min(min_[i-1] * nums[i], nums[i]));
}
return *max_element(max_.begin(), max_.end());

32. 最长有效括号

int n = s.size();
// 前i个元素的解
vector<int> dp(n, 0);
dp[1] = (s[0] == '(' && s[1] == ')') ? 2 : 0;
for(int i=2; i < dp.size(); i++) {
    if(s[i] == ')') {
        if(s[i-1] == '(') {
            // ...()
            dp[i] = dp[i-2] + 2;
        } else if(i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(') {
            // ...))
            // 边界情况
            int last_path = (i - dp[i-1] - 2 >= 0) ? dp[i - dp[i-1] - 2] : 0;
            dp[i] = dp[i-1] + last_path + 2;
        }
    }
}
return *max_element(dp.begin(), dp.end());

困难的题难在要分情况讨论，还有边界条件。而不仅仅是套用模板。

带维度的单串

122. 买卖股票的最佳时机 II

int n = prices.size();
// 第i天持有时的利润
vector<int> dp_hold(n);
dp_hold[0] = -prices[0];
// 第i天不持有的利润
vector<int> dp_not(n);
for(int i=1; i < n; i++) {
    dp_hold[i] = max(dp_hold[i-1], dp_not[i-1] - prices[i]);
    dp_not[i] = max(dp_not[i-1], dp_hold[i-1] + prices[i]);
}
return dp_not[n-1];

309. 最佳买卖股票时机含冷冻期

int n = prices.size();
// 第i天持有时的利润
vector<int> dp_hold(n);
dp_hold[0] = -prices[0];
// 第i天不持有的利润
vector<int> dp_not(n);
dp_not[1] = max(dp_not[0], dp_hold[0]+prices[1]);
dp_hold[1] = max(dp_hold[0], dp_not[0] - prices[1]);
for(int i=2; i < n; i++) {
    dp_hold[i] = max(dp_hold[i-1], dp_not[i-2] - prices[i]);
    dp_not[i] = max(dp_not[i-1], dp_hold[i-1] + prices[i]);
}
return dp_not[n-1];

双串

给定两个串，第i，j位置的解，依赖于i-1,j-1的解。

剑指 Offer II 095. 最长公共子序列

当text1[i-1] == text2[j-1]时，只要把前面匹配的结果加1
否则，要分别考虑text1[i-1]与text2[j-2]、text1[i-2]与text2[j-1]。因为当前位置两个字符不相等，那可能减少一个字符的情况是否相等。

int n = text1.size();
int m = text2.size();

// text1的前i个与text2的前j个字符的解
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i=1; i < n+1; i++) {
    for(int j=1; j < m+1; j++) {
        if(text1[i-1] == text2[j-1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
}
return dp[n][m];

72. 编辑距离

当word1[i-1] == word2[j-1]，距离就与word1[i-2]和word2[j-2]情况相同。
否则，考虑3个操作：
- 删除word1最后一个字符：只考虑word1[i-2]与word2[j-1], 即：dp[i-1][j]
- 删除word2最后一个字符：只考虑word1[i-1]与word2[j-2]，即：dp[i][j-1]
- 替换word1最后一个字符（替换word2是一样的）：只考虑word1[i-2]和word2[j-2]，即：dp[i-1][j-1]

int n = word1.size();
int m = word2.size();
// word1的前i个字符与word2的前j个字符的解
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i=1; i < n+1; i++) {
    dp[i][0] = i;
}
for(int j=1; j < m+1; j++) {
    dp[0][j] = j;
}

for(int i=1; i < n+1; i++) {
    for(int j=1; j < m+1; j++) {
        if(word1[i-1] == word2[j-1]) {
            dp[i][j] = dp[i-1][j-1];
        } else {
            dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
        }
    }
}

return dp[n][m];

44. 通配符匹配

字符相等和问题的情况比较简单，都是只考虑s[i-2]和p[j-2]，即
- dp[i][j] = dp[i-1][j-1]
星号比较复杂，可以匹配0个或任意个字符。
- 匹配0个时，就是要考虑s[0:i-1]与p[0:j-2]，即：
  - dp[i][j] = dp[i][j-1]
- 匹配任意个字符，就是不考虑s[i-1]，只考虑s[0:i-2]与p[0:j-1]。这里要考虑p[j-1]是因为星号是任意个字符，即不管是否考虑s[i-1]，都要考虑星号，就是p[j-1]
  - dp[i][j] = dp[i-1][j]

int n = s.size();
int m = p.size();

// s的前i个字符与p的前j个字符的解
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
dp[0][0] = true;
for(int j=1; j < m+1; j++) {
    if(p[j-1] == '*') {
        // *可以匹配空字符
        dp[0][j] = true && dp[0][j-1];
    }
}

for(int i=1; i < n+1; i++) {
    for(int j=1; j < m+1; j++) {
        if(s[i-1] == p[j-1] || p[j-1] == '?') {
            dp[i][j] = dp[i-1][j-1];
        } else if(p[j-1] == '*') {
            dp[i][j] = dp[i-1][j] || dp[i][j-1];
        }
    }
}

return dp[n][m];

如果我们不使用这个星号，那么就会从 dp[i][j-1] 转移而来；如果我们使用这个星号，那么就会从 dp[i-1][j]

面试题19. 正则表达式匹配

先考虑字符相等的简单情况，即s[i-1] == p[j-1] || p[j-1] == '.'，这时与s[0:i-2和p[0:j-2]相同：
- dp[i][j] = dp[i-1][j-1]
再考虑星号的情况。星号可以匹配0个或任意个字符。
- 匹配0个时，与s[0:i-1]和p[0:j-3]情况相同，即
  - dp[i][j] = dp[i][j-2]
- 匹配任意个，与s[0:i-1]和p[0:j-1]情况相同。又因为s[i-1]要单独讨论，所以分为s[0:i-2]和s[i-1]两段：
  - s[0:i-2]与p[0:j-1]，即：dp[i-1][j]
  - s[i-1]与p[j-1]，即：s[i-1] == p[j-2] || p[j-2] == '.'。这里p[j-2]是因为星号与前一个字符相关。星号是p[j-1]，则前一个字符为p[j-2]

int n = s.size();
int m = p.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, false));
dp[0][0] = true;
for(int j=1; j < m+1; j++) {
    if(p[j-1] == '*' && j >= 2) {
        // 1 or 0
        dp[0][j] = dp[0][j-1] || dp[0][j-2];
    }
}

for(int i=1; i < n+1; i++) {
    for(int j=1; j < m+1; j++) {
        if(s[i-1] == p[j-1] || p[j-1] == '.') {
            dp[i][j] = dp[i-1][j-1];
        }
        else if(p[j-1] == '*' && j >= 2) {
            // 0 or one or more
            dp[i][j] = dp[i][j-2] || 
                dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.');
        }
    }
}
return dp[n][m];

矩阵问题

给定一个矩阵，第i，j位置的解，依赖于i-1,j-1的解。

这几题比双串那几个简单很多，情况简单。

62. 不同路径

vector<vector<int>> dp(m+1, vector<int>(n+1));
dp[0][1] = 1;
for(int i=1; i < m+1; i++) {
    for(int j=1; j < n+1; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
}
return dp[m][n];

64. 最小路径和

vector<vector<int>> dp(m, vector<int>(n, BIG));
dp[0][0] = grid[0][0];
for(int j=1; j < n; j++) {
    dp[0][j] = dp[0][j-1] + grid[0][j];
}
for(int i=1; i < m; i++) {
    dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1; i < m; i++) {
    for(int j=1; j < n; j++) {
        dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
    }
}
return dp[m-1][n-1];

221. 最大正方形

int ans = 0;
vector<vector<int>> dp(m+1, vector<int>(n+1));
for(int i=1; i < m+1; i++) {
    for(int j=1; j < n+1; j++) {
        if(matrix[i-1][j-1] == '1') {
            int t = dp[i-1][j-1];
            t = min(t, dp[i-1][j]);
            t = min(t, dp[i][j-1]);
            dp[i][j] = t + 1;
            ans = max(ans, dp[i][j]);
        }
    }
}
return ans * ans;

区间问题

给定一个串，第i位置的解，依赖于前[j, i]的解。

5. 最长回文子串

// dp[i][j]表示s[i:j]间是否为回文串
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
for(int i=0; i < n; i++) {
    dp[i][i] = 1;
}

int left = 0;
int max_len = 1;
for(int l=1; l < n; l++) {
    for(int i=0; i < n; i++) {
        int j = i + l;
        if(j < n && s[i] == s[j]) {
            dp[i][j] = l == 1 ? dp[i][j-1] : dp[i+1][j-1];
            if(dp[i][j] && l+1 > max_len) {
                max_len = l+1;
                left = i;
            }
        }
    }
}        
return s.substr(left, max_len);

647. 回文子串

int n = s.size();
// dp[i][j]是否为回文串
vector<vector<bool>> dp(n, vector<bool>(n));
for(int i=0; i < n; i++) {
    dp[i][i] = true;
}

for(int l=1; l < n; l++) {
    for(int i=0; i < n; i++) {
        int j = i + l;
        if(j < n && s[i] == s[j]) {
            dp[i][j] = l == 1 ? dp[i][j-1] : dp[i+1][j-1];
        }
    }
}

int ans = 0;
for(int i=0; i < n; i++) {
    for(int j=i; j < n; j++) {
        ans += dp[i][j];
    }
}
return ans;

312. 戳气球

dp定义：dp[l][r]表示开区间(l,r)的解
初始化：所有位置都是0
转移方程：dp[l][r] = max(dp[l][r], val[l]*val[mid]*val[r] + dp[l][mid] + dp[mid][r])
返回值：dp[0][n+1]

int n = nums.size();
// dp[i][j]表示nums[i:j]开区间内的解
vector<vector<int>> dp(n+2, vector<int>(n+2));
vector<int> val(n+2);
val[0] = 1;
val[n+1] = 1;
for(int i=1; i < val.size()-1; i++) {
    val[i] = nums[i-1];
}    

for(int l = n; l >= 0; l--) {
    for(int r = l+2; r <= n+1; r++) {
        for(int mid = l+1; mid < r; mid++) {
            // 把戳气球看成是填充气球
            // 在mid位置填气球能得到的硬币数
            int sum = val[l] * val[mid] * val[r];
            sum += dp[l][mid] + dp[mid][r];
            dp[l][r] = max(dp[l][r], sum);
        }
    }
}
return dp[0][n+1];

这题困难在于转换“戳气球”为“填气球”的问题。还有dp的定义是开区间。

数据结构

单调栈

85. 最大矩形