Kenway's Blog

【笔记】算法刷题笔记

发表于 更新于 分类于

目录

基础题

典型题

数据结构设计

解题通用思路

基础题

1.传递信息

给定总玩家数n，以及按[玩家编号,对应可传递玩家编号]关系组成的二维数组 relation。返回信息从编号0玩家经过k轮传递到编号为n-1玩家处的方案数；若不能到达，返回0

示例：输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
输出：3
解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
int numWays(int n, vector<vector<int>>& relation, int k) {
    vector<vector<int>> dp(k+1,vector<int>(n));
    dp[0][0] = 1;
    for(int i = 0; i < k; i++){
        for(auto t:relation){
            int start = t[0], target = t[1];
            dp[i+1][target] += dp[i][start]; 
            }
        }
        return dp[k][n-1];
    }
    
# dp[i][j]表示在第i轮能到达编号j的方案数

2.判断链表是否有环/找出链表中环起点问题

解法:

  • 使用快慢指针，慢指针一次走一步，快指针一次走两步，两个指针同时从起点出发，若最后相遇则表示一定有环
  • 相遇时，一个指针原地不动，一个指针指向头节点，然后两个指针偶读改为一次走一步，它们再次相遇的地方就是环的起点

证明：设慢指针走了k步与快指针走了2k步在O点相遇，2k-k=k则为环的长度，m为O点与头节点的距离

此时无论是从头结点到环起点，还是O点到环起点的距离都为k-m，所以第二次相遇的地方即为环起点

3.信封嵌套问题

即俄罗斯套娃，长、宽都大于才能装进去，求最多能嵌套几层

解法:

  • 以宽度为标准从下到大排序，若宽度相同则比较长度，长度大的在前，长度小的在后
  • 对排好序的数组，以长度为标准求最长递增子序列的长度即为答案

4.连续子数组的最大和问题

解法:

  • dp[i]表示以nums[i]为结尾的连续最大子数组和，注意该和中把nums[i]也算进去了
  • 状态转移方程:dp[i] = max(dp[i-1]+nums[i], nums[i]);
  • 遍历dp[]找出最大值即为答案

5.求二叉树最大值(没有负值)

解法:

  • 采用递归法
  • 自顶向下，主干是根节点与两子树比较
    1
    2
    3
    4
    5
    6
    int maxVal(TreeNode root){
        if(root == nullptr) return -1;
        int left = maxVal(root->left);
        int right = maxVal(root->right);
        return max(root->val, left, right);
    }

6.二分查找框架

1
2
3
4
5
while(left <= right){
    mid = (right - left) / 2 + left;
    if(nums[mid] < target) left = mid+1;
    else if(nums[mid] > target) right = mid-1;
        }

7.有序数组查找最优思路

1
2
for(int i=0;i<nums.size();i++) if(nums[i]>=target) return i;
return nums.size();

8.判断正则表达式是否匹配问题

s是目标字符串，p是正则表达式

  • 建一个dp函数
    1
    bool dp(string&s, string& p, int i, int j)
  • 遍历时分两种情况
    • s[i] == p[j] || p[j] == ‘.’
      • p[j+1] == ‘*’, return dp(s,p,i+1,j) || dp(s,p,i,j+2)
      • p[j+1] != ‘*’, return dp(s,p,i+1,j+1)
    • else
      • p[j+1] == ‘*’, return dp(s,p,i,j+2)
      • else return false;
  • 加上特殊情况判定
    1
    2
    3
    4
    5
    6
    7
    if(j == p.size()) return i == s.size();
    if(i == s.size()){
        if((p.size()-j) % 2 == 1) return false;
        for(; j+1 < n; j+=2) if(p[j+1] != '*') return false;
        return true;
    }

9.原地移动零

给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序

解法:

  • left指针左边是已经处理好的序列，right右边是未处理的序列,left应该指向一个0
  • right和left之间全是0
  • 一旦right指到一个非0的数，就交换right与left指到的值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int left = 0, right = 0;
    while(right < nums.size()){
        if(nums[right] != 0) {
            swap(nums[left], nums[right]);
            left++;
            }
        right++;
    }
    return;
    (还有一个双层遍历的方法，即一旦指到0就去后面找非0的和它交换，较简单不再赘叙)

10.买卖股票最佳时机系列问题

初阶:给定一个数组prices，它的第i个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。

解法：dp[i]表示在i天卖出能获得的最大利润,min_p存的是i天之前最低的买入价格

1
2
3
4
5
6
7
8
9
10
11
12
if(prices.size() <= 1) return 0;
vector<int> dp(prices.size());
int min_p = prices[0];
dp[1] = -1;
int ans = INT_MIN;
for(int i = 1; i < prices.size(); i++){
    dp[i] = prices[i] - min_p;
    ans = max(dp[i], ans);
    min_p = min(prices[i], min_p);
}
if(ans < 0) return 0;
return ans;

进阶1:你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解法:
一、贪心思想

  • 每次遇到上坡都买入、卖出
  • 最后收益一定是最大值
    1
    2
    3
    4
    5
    6
    7
    int sum = 0;
    for(int i = 0; i < prices.size()-1; i++){
        if(prices[i] < prices[i+1]){ 
        sum += prices[i+1] - prices[i];
        }
    }
    return sum;

二、动态规划

  • dp[i][0]表示在i天手上没有股票的最高收益，dp[i][1]表示在i天手上有股票的最高收益
  • 遍历天数时更新dp[i][0]和dp[i][1]
  • 最后返回dp[prices.size()-1][0]，因为此时没有股票一定比有股票收益大
  • 亮点在于最大利润里未来支付的概念，即买股票就直接扣，卖出去的时候就直接加，而不用去管具体差值得到的利润到底是多少，max()动态规划过程会自动计算
1
2
3
4
5
6
7
8
vector<vector<int>> dp(prices.size(), vector<int>(2));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < prices.size(); i++){
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
    dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
return dp[prices.size()-1][0];

进阶2:卖出股票后，你无法在第二天买入股票(即冷冻期为1天)。
解法：动态规划

  • 同进阶1类似，不同的是多一个状态dp[i][2]表示i天处于冷冻期的最大收益
  • 注意结果要比较处于冷冻期和不处于冷冻期的情况，取较大值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    vector<vector<int>> dp(prices.size(), vector<int> (3));
    dp[0][1] = -prices[0]; 
    for(int i = 1; i < prices.size(); i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][2]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        dp[i][2] = dp[i-1][1] + prices[i];
    }
    return max(dp[prices.size()-1][0], dp[prices.size()-1][2]);

    # dp[i][0]是手上无股票且不处于冷冻期的最大收益
    # dp[i][1]是手上有股票的最大收益
    # dp[i][2]是手上无股票且处于冷冻期的最大收益

    进阶3:没有冷冻期，一次完整买入卖出需要fee手续费

  • 用动态规划法，修改卖出时的公式即可
    1
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);

11.打家劫舍系列问题

初阶:你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

解法:dp[i]表示偷i号房屋前提下能获得的最大利润

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> dp(nums.size());
dp[0] = nums[0];
if(nums.size() == 1) return dp[0];
dp[1] = nums[1];
if(nums.size() == 2) return max(dp[0], dp[1]);
dp[2] = nums[0] + nums[2];
int ans = max(dp[1], dp[2]);
for(int i = 3; i < nums.size(); i++){
    dp[i] = max(dp[i-2], dp[i-3]) + nums[i];
    ans = max(ans, dp[i]);
    }
return ans;

进阶1:增加条件-首尾房子连在一起，即不能同时偷第一间和最后一间

解法:

  • 分成两种情况
    • 房子序列中没有最后一间
    • 房子序列中没有第一间
  • 用初阶的代码分别求出两种情况的最大利润，然后返回最大值即可

进阶2:从二叉树偷，两个直接相连的房子不能同时偷(即父树与子树不能同时偷)

解法:

  • 用一个int box(TreeNode* root)函数作递归
  • 核心函数结构
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int box(TreeNode* root){
        if(root == nullptr) return 0;
        int do_it = root->val + box(root->left->left) + box(root->left->right) + box(root->right->left) + box(root->right->right);
        int do_not = box(root->left) + box(root->right);
        return max(do_it, do_not);
    }

    # do_it是偷该层, do_not是不偷该层
    # box()实际上就是表示以该点为根节点的最大利润

12.背包问题的固定框架

  • dp[i][w]表示对前i个物品进行选择，且当前背包容量为w时，能装下的最大价值
  • 核心
    1
    2
    3
    4
    dp[i][w]=max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1])

    # dp[i-1][w]是不装当前物品
    # dp[i-1][w-wt[i-1]] + val[i-1]是装当前物品，i-1是因为下标从0开始的，wt是重量数组，val是价值数组

背包问题重要特性(由它们的dp意义不同造成的)

  • 若dp[i][j]表示的是最大价值，则用max()选dp[i][j]，且第二个值为dp[i-1][xx]
  • 若dp[i][j]表示能不能装进背包，则用||来组成dp[i][j]，且第二个值为[i-1][xx]
  • 若dp[i][j]表示的是方法数，则用+来组成dp[i][j]，且第二个值为dp[i][xx]，因为此时dp[i][xx]包含了dp[i-1][xx-nums[i]]
  • 第一个值永远是dp[i-1][j]

变形题目:一个数组能不能分成两个和相等的子集

  • 容量 = 整个数组和/2，dp[i][j]表示前i个物品能恰好填满容量为j的背包(即dp[i][j] = true，其他全初始化为false)
  • 核心代码
    1
    2
    3
    4
    if(j - nums[j-1] < 0) dp[i][j] = dp[i-1][j];
    else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[j-1]];

    # j - nums[j-1] < 0表示物品大于背包容量，直接不能装

13.零钱兑换问题

给定一个coins数组表示零钱的面额种类，每种零钱可以无限个使用

解法:与背包问题框架类似

  • dp[i][j]表示仅用前i种面额钱币时能凑出金额j的方法数(base:dp[i][0] = 1,其它全初始化为0)
  • 核心代码
    1
    2
    if(j-coins[i-1] < 0) dp[i][j] = dp[i-1][j];
    else dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];

14.跳跃游戏系列问题

初阶:给定一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

解法:

1
2
3
4
5
6
7
8
9
10
int max_step = 0;
for(int i = 0; i < nums.size()-1; i++){
    max_step = max(max_step, i + nums[i]);
    if(max_step <= i) return false;
}
if(max_step >= nums.size()-1) return true;
return false;

# max_step是全局最远能走多远
# max_step <= i是表示碰到0卡住了，永远走不到下一步

进阶:使用最少的跳跃次数到达数组的最后一个位置，求最少跳跃次数

解法:

一、贪心思想

  • farest表示下标[i,….,end]中能走得最远的距离
  • if(i == end) 表示的是这一段的[i,….,end]已经遍历结束，要开始进行跳跃(count++)，最远可以跳到farest，并将end更新为farest，由于此时i = end，实际上就是将[i,….,end]更新为[end,…,farest]
  • 一旦到达末尾，马上结束循环并返回跳跃次数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int count = 0;
    if(nums.size() == 1) return count;
    int end = 0;
    int farest = 0;
    for(int i = 0; i < nums.size(); i++){
        farest = max(farest, i + nums[i]);
        if(i == end){
            count++;
            end = farest;
            if(farest>=nums.size()-1) break;
        }
    }
    return count;

二、动态规划(简单，但会超时)

  • dp(nums, index)表示从index到nums的最小跳跃次数
  • dp()函数的思路是遍历从index能走到(nums[index])的每一个位置，看哪个位置能用最少跳跃到末尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> memo;
int jump(vector<int>& nums) {
    memo = vector<int>(nums.size(), nums.size());
    return dp(nums, 0);
}
    
int dp(vector<int>& nums, int index){
    if(memo[index] != nums.size()) return memo[index];
    int n = nums.size()-1;
    if(index >= n) return 0;
    for(int i = 1; i <= nums[index]; i++){
        int temp = dp(nums, index+i);
        memo[index] = min(memo[index], temp+1);
    }
    return memo[index];
}

15.子数组的最大和系列问题

初阶:给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

1
2
3
4
5
6
7
int dp = 0;
int max_ans = INT_MIN;
for(int i = 0; i < nums.size(); i++){
    dp = max(dp + nums[i], nums[i]);
    max_ans = max(dp, max_ans);
}
    return max_ans;

进阶:数组改为环形数组，即首尾连起来，且连续子数组里同一元素只能出现一次，返回最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 计算无环的情况
int dp = 0;
int max_ans = INT_MIN;
int max_num = INT_MIN;
for(int i = 0; i < nums.size(); i++){
    dp = max(dp + nums[i], nums[i]);
    max_ans = max(dp, max_ans);
    max_num = max(nums[i], max_num);
}
# max_num用来识别全是负数的情况，需要特殊处理
if(max_num < 0) return max_num;

# 计算有环的情况
# 先求出连续子数组最小值，然后用sum去减就得到最大值
dp = 0;
int min_ans = INT_MAX;
int sum = 0;
for(int i = 0; i < nums.size(); i++){
    sum += nums[i];
    dp = min(dp + nums[i], nums[i]);
    min_ans = min(dp, min_ans);
}

# 返回两种情况中的最大值
max_ans = max(max_ans, sum - min_ans);
return max_ans;

16.回溯法经典模板:

1
2
3
4
5
6
7
8
9
10
11
void backtrack(当前路径，选择列表){
    if(满足结束条件){
        reslut.add(当前路径);
        return;
    }
    for 选择 in 选择列表{
        描述做选择的语句;
        backtrack(做完选择后的当前路径，还可选择的列表);
        撤销选择(例:当前路径.pop());
    }
}

17.无重复字符的最长子串

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
解法:

  • 用双指针形成一个滑动窗口
  • 用一个哈希表window来记录当前窗口内字符串的出现次数
  • right遍历到不重复字符时，window[s[right]]++，right++
  • right遍历到重复的字符时，left缩小，window[s[left]]++，left++直到重复字符消失
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    if(s.size() == 0) return 0;
    unordered_map<char, int> window;
    int left = 0, right = 0;
    int ans = 0;
    while(right < s.size()){
        if(window[s[right]] == 0){
            window[s[right]]++;
            right++;
            ans = max(ans, right-left);
        }
        else{
            while(s[left] != s[right]){
                window[s[left]]--;
                left++;
            }
            window[s[left]]--;
            left++;
        }
    }
    return ans;

18.乘积最大子数组

给你一个整数数组nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

解法:维持两个变量max_dp、min_dp

  • 本题难点在于原本最小的负数乘另一个负数就变成了很大的正数，很大的数乘一个负数就变成最小的数
  • 解法是维持两个变量max_dp、min_dp，分别代表当前最大乘积和当前最小乘积
  • 每次遍历都更新一次
  • 如何保证用的值都是连续的子数组呢，一是顺序遍历，二则关键在于选择时多了一个nums[i]，它表示有可能从这里抛开前面的子数组，重新开始算
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    if(nums.size() == 0) return 0;
    if(nums.size() == 1) return nums[0];
    int min_dp = nums[0];
    int max_dp = nums[0];
    int ans = nums[0];
    for(int i = 1; i < nums.size(); i++){
        int temple = max_dp;
        max_dp = max(max(nums[i], nums[i]*temple), nums[i]*min_dp);
        min_dp = min(min(nums[i], nums[i]*min_dp), nums[i]*temple);
        ans = max(max_dp, ans);
    }
    return ans;

    # 每次更新的max_dp、min_dp都是一样的，都是在nums[i]、nums[i]*max_dp和nums[i]*min_dp中去选，只不过一个用max()，一个用min()

19.合并二叉树

解法：

  • 若两个都有值就新建节点处理
  • 若其中一个为nullptr就返回另一个
    1
    2
    3
    4
    5
    6
    7
    8
    9
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr) return nullptr;
        else if(root1 == nullptr && root2 != nullptr) return root2;
        else if(root1 != nullptr && root2 == nullptr) return root1;
        TreeNode* merge = new TreeNode(root1->val + root2->val);
        merge->left = mergeTrees(root1->left, root2->left);
        merge->right = mergeTrees(root1->right, root2->right);
        return merge;
    }

20.单词的拆分

给定一个非空字符串s和一个包含非空单词的列表wordDict，判定s是否可以被空格拆分为一个或多个在字典中出现的单词。

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

解法：动态规划

  • dp[i]表示s[0….i-1]可以被拆分成字典里的单词
  • 双层遍历i=[1,s.size()],j=[0,i]
  • 所以答案就是dp[s.size()]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    vector<bool> dp(s.size()+1);
    unordered_map<string, int> f;
    for(auto t:wordDict) f[t] = 1;
    dp[0] = true;
    for(int i = 1; i <= s.size(); i++){
        for(int j = 0; j < i; j++){
            string str1 = s.substr(j, i-j);
            dp[i] =  dp[j] && f[str1] == 1;
            if(dp[i]) break;
        }
    }
    return dp[s.size()];

21.等差数列的划分

输入：nums = [1, 2, 3, 4]
输出：3 即[1, 2, 3], [2, 3, 4],[1, 2, 3, 4]

解法：用动态规划

  • dp[i]表示以nums[i]结尾的等差数列的数量
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    if(nums.size() < 3) return 0;
    vector<int> dp(nums.size());
    int ans = 0;
    for(int i = 2; i < nums.size();i++){
        if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) dp[i] = dp[i-1] + 1;
        ans += dp[i];
    }
    return ans;

    # dp[i] = dp[i-1] + 1;是因为一旦符合前面的等差，那就在dp[i-1]的基础上+1
    # 如果nums[i-3,i-2,i-1]不是等差的话，那dp[i-1]=0,dp[i] = 0+1也没错
    # 该解法也考虑了等差差值不同的情况

22.二维数组中的高效查找

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

解法

  • 从右上角开始
  • matrix[i][j] > target就往左移
  • matrix[i][j] < target就往下移
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    if(matrix.size() == 0 || matrix[0].size() == 0) return false;
    int n = matrix.size();
    int m = matrix[0].size();
    int i = 0, j = m-1;
    while(1){
        if(matrix[i][j] > target){
            j--;
            if(j < 0) return false;
        }
        else if(matrix[i][j] < target){
            i++;
            if(i >= n) return false;
        }
        else return true;
    }
    return true;

23.全组合问题

给一个数字n，和一个数组大小k，要求在[1….n]中选数字组成大小为k的数组，返回所有可能性，不能有重复(数字顺序不同算一个数组)

解法:回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> ans;
vector<vector<int>> combine(int n, int k) {
    vector<int> temple;
    backtrack(n,k,1,temple);
    return ans;
}

void backtrack(int& n, int& k, int step, vector<int> temple){
    if(temple.size() >= k){
        ans.push_back(temple);
        return;
    }
    for(int i = step; i <= n; i++){
        temple.push_back(i);
        backtrack(n,k,i+1,temple);
        temple.pop_back();
    }
    return;
}

# 开销较大
# 优化思路:将传入vector<int>temple改为传入temple的当前下标；将temple全局声明，然后局部定义它的大小，这样就不用push)back()了

24.全排列问题

给一个数组，返回它的不同顺序组合

解法：回溯法(这个需要传vector作为参数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> ans;
vector<vector<int>> permute(vector<int>& nums) {
    vector<int> track;
    backtrack(nums, track, 0);
    return ans;
}
void backtrack(vector<int>& nums, vector<int> track, int step){
    if(track.size() == nums.size()) ans.push_back(track);
    for(int i = step; i < nums.size(); i++){
        if(find(track.begin(), track.end(), nums[i]) != track.end()) continue;
        track.push_back(nums[i]);
        backtrack(nums, track, 0);
        track.pop_back();
    }
}

另一种比较暴力的回溯法是直接用nums疯狂swap，每次的结果用哈希表记录，将不重复的压入ans，开销和上面这种一样

25.翻转二叉树

解法：递归

  • 从叶节点开始翻转
  • 当前节点左右子树都交换位置后，才将当前节点与另一个节点交换位置
  • 当遇到某节点为nullptr时，直接return nullptr递归会自动处理
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

    # 进行递归翻转
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        
        root->left = right;
        root->right = left;
        return root;
        }

26.杨辉三角

返回杨辉三角的第rowIndex行

解法:

  • 亮点在于用一个dp数组迭代，空间开销小
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    vector<int> dp(rowIndex);
    for(int i = 0 ; i < rowIndex;i++){
        int pre = 1;
        for(int j = 0; j <= i; j++){
            int temple = dp[j];
            if(j == 0 || j == i) dp[j] = 1;
            else dp[j] += pre;
            pre = temple;
        }
    }
    return dp;
    若是求前n个数组的话，将每次i循环结束得到的结果依次push进答案数组即可

27.剪绳子系列问题

有一根长为n的绳子，可将它剪成很多子绳，求它的最大子绳乘积

解法:

一、数学法

  • 由数学定义可证明
    • 当剩余绳子长度大于等于5时，尽可能的剪出长度为3的子绳
    • 当绳子长度为4时，剪也可不剪也可
    • 当绳子长度小于4时，不剪
    • 如此子绳乘积最大

二、动态规划法

  • dp[i]表示长度为i的绳子子绳最大乘积
  • 用双层遍历来更新dp[n] = max(dp(i)*dp(n-i)，dp[n])
  • 从小到大开始遍历
  • 注意
    • n=2,3时特殊处理
    • dp[1] = 1,dp[2] = 2, dp[3]=3是base方便后面算法，但此时dp并不代表i的最大乘积

28.判断是否是2的幂

解法:
一、用二进制能表示的最大2的幂对n取余

1
return (n > 0) && (1<<30) % n == 0;

二、用n与n的补码相&看是否等于n

1
return (n > 0) && (n & -n) == n;

三、常规递归/2看能不能除尽

29.计算二进制中1的个数

解法:

  • 即每次都判断最后一位是不是二进制
    • 是，counter+1
    • 不是，counter+0
    • 然后n往右移一位
  • 当n==0时退出循环
    1
    2
    3
    4
    5
    6
    int counter = 0;
    while(n){
        counter = counter + n % 2;
        n = n >> 1;
    }
    return counter;

30.二叉搜索树中的搜索

1
2
3
4
5
6
TreeNode* searchBST(TreeNode* root, int val) {
    if(root == nullptr) return nullptr;
    if(root->val == val ) return root;
    else if(root -> val < val) return searchBST(root->right, val);
    else return searchBST(root->left, val);
}

31.只出现一次的数字

除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

解法:位运算

  • 与自己异或等于0
  • 0与某数异或结果仍为某数
  • 异或满足交换律
  • 所以答案就是全数组每个元素异或的结果
    1
    2
    3
    4
    5
    int ans = nums[0];
    for(int i = 1; i < nums.size(); i++){
        ans = ans ^ nums[i];
    }
    return ans;

32.二叉搜索树的最近公共祖先

解法：

  • 如果当前节点值同时大于p、q，则当前节点移到它的左子树
  • 如果当前节点值同时小于p、q，则当前节点移到它的右子树
  • 否则则说明当前节点时分叉口(包含了当前节点时p、q的情况)
1
2
3
4
5
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left,p,q);
    else if(root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right,p,q);
    else return root;
}

33.原地将字符串里的空格替换成”xx”

解法：思想就是

  • 先遍历一遍字符串s，数出空格的数量
  • 新建两个下标:
    • p=s.size()-1;即老字符串的末尾
    • new_p=新字符串的末尾(用空格数量和替换字符的差值计算得出)
  • p往前遍历
    • 若s[p] != 空格，s[new_p]就等于s[p]
    • 若s[p] == 空格，s[new_p]就等于”xx”

典型题

1.求小岛数量

1
2
3
4
5
6
[[0,0,1],
[0,1,1],
[1,0,0]]

# 0表示水，1表示陆地
# 该实例答案为2

解法:

  • main()中双层循环遍历，每遇到一个1就调用一次dfs()且ans++
  • dfs()中将数过的1变为0，然后对其上、下、左、右再分别判断，若为1就继续调用dfs()
  • main()双层循环外return ans

进阶：找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。如上例中应该返回面积为3。

解法：和初阶基本一样，也是数过就改为0并遍历周围元素

  • 亮点是返回int类型函数的递归使用
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    int max_ans = 0;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == 0) continue;
                max_ans = max(max_ans, box(grid, i, j));
            }
        }
        return max_ans;
    }

    int box(vector<vector<int>>& grid, int i, int j){
        int ans = 0;
        if(grid[i][j] == 1){
            ans++;
            grid[i][j] = 0;
        }
        else return 0;
        
        # 根据周围土地情况更新这块岛屿总面积
        if(i+1 < grid.size()) ans += box(grid, i+1, j);
        if(j+1 < grid[0].size()) ans += box(grid, i, j+1);
        if(i-1 >= 0) ans += box(grid, i-1, j);
        if(j-1 >= 0) ans += box(grid, i, j-1);
        return ans;
    }

2.找出一个数组里的峰值元素

即前后元素都比它要小,不存在nums[i]==nums[i+1],nums[0]和nums[nums.size()-1]视为负无穷大

解法：

  • 遍历数组nums:当nums[i] > nums[i+1]时，return nums[i]
  • 若遍历结束仍未有符合条件nums[i]返回，则return nums[nums.size()-1]

3.判断s中含有t的所有字符的最小子串问题

类似问题：找所有字母异位词、最长无重复子串、判断s中是否有某个子串是t的某全排列问题

解法：

  • 使用滑动窗口，新建两个哈希表need(t中含有字符)、window(当前窗口含有字符)，用下述语句判断当前窗口是否符合要求
    1
    2
    for(auto& i:need) if(window[i.first]<i.second) return false
    return true
  • 符合就left+1，直到不符合，记录；不符合就right+1，直到再一次符合并重复上述循环(直到遍历到s末尾)

4.求数组它的最长递增子序列

子序列即为可以不连续的子数组

解法：

  • 用动态规划，dp[i]表示以nums[i]这个数结尾的最长递增子序列长度
  • 核心代码
    1
    2
    3
    4
    5
    for(int i = 0; i < nums.size(); i++){
        for(int j = 0; j < i; j++){   
            if(nums[i]>nums[j]) dp[i] = max(dp[i], dp[j]+1);
        }
    }

5.求两字符串的最长公共子序列问题

类似问题：连线不能相交问题

解法:

  • dp[i][j]表示str1[0,1,…,i-1]与str2[0,1,…,j-1]的最长公共子序列长度(当i或j任一为0时，dp[i][j]=0，因为””与任何字符串的公共子序列长度都为0)
  • 判断
    • 如果str1[i]==str2[j]，即两个str前进一步的字符相同，那么该字符肯定在公共子序列lcs里
      1
      dp[i][j] = dp[i-1][j-1] + 1;
    • 如果str1[i]!=str2[j]，那么又分两种情况
      • str1[i]在lcs里
        1
        dp[i][j] = dp[i][j-1];
      • str2[j]在lcs里
        1
        dp[i][j] = dp[i-1][j];
      • 综上可得当str1[i]!=str2[j]时
        1
        2
        3
        dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            
        # 不用考虑str1[i]和str2[j]都不在lcs的情形，因为max取大值，不影响结果
  • 结果为dp[str1.size()][str2.size()]

6.编辑距离题目

有两个字符串s1和s2，求将s1变成s2需要多少步操作?

解法:

一、 递归法

  • 用i、j分别指向s1、s2字符串末端
  • 若s1[i]==s2[j]，i和j都前进一步，return box(i-1, j-1)
  • 若s1[i]!=s2[j]，有三种可能进行的变换
    • 删除，box(i-1, j)+1
    • 插入，box(i, j-1)+1
    • 替换，box(i-1, j-1)+1
    用min()来取三者中最小的那个
  • 前面加两个判断，适用于其中一个字符串已经数到末尾了，后面的操作全是插入或删除 
    1
    2
    if(i ==-1) return j+1;
    if(j == -1) return i+1;

二、dp数组法(开销和递归法用备忘录优化后一样)

  • dp[i][j]表示s1[0,…,i-1]变成s2[0,…,j-1]所需的最短步数
  • 赋值dp[i][0]=i, dp[0][j]=j
  • 双层循环嵌套:1<=i<=s1.size(), 1<=j<=s2.size() 
    1
    2
    3
    4
    # 表示不需要操作，直接到下一步
    if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];

    else dp[i][j] = min(删除，插入，替换);
  • 最终答案为dp[s1.size()][s2.size()]

7.最长回文子序列解法:

  • dp[i][j]表示从s[i]到s[j]包含的最长回文子序列长度，可得dp[i][j]=1,dp[i][j]=0(i>j时)
  • 反着遍历 
    1
    2
    3
    4
    5
    for(i=s.size()-1; i >= 0; i--){
        for(j = i+1; j < s.size();j++){
        }
    }
    # 外层其实可以从s.size()-2开始,因为s.size()-1没意义
  • base是dp[i][i] =1;
  • 核心代码:
    • 如果s[i]==s[j]则表示在dp[i+1][j-1]的基础上又多了两个回文字符
      1
      dp[i][j] = dp[i+1][j-1] + 2;
    • 如果s[i]!=s[j]则表示这一步没能增加回文字符，于是选取上一步中最大的值
      1
      dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
  • 最后答案就是dp[0][s.size()-1]

    进阶:让字符串成为回文串的最小插入次数
    解法：

  • 只需改成即可
    1
    2
    if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
    else dp[i][j] = min(dp[i+1][j], dp[i][j-1])+1

8.最长回文子串

解法:

  • 用for去遍历一次字符串
  • 每个字符放入expensed()去得到以它为中心的最长扩展字符串
    • expand(s, i, i);
    • expand(s, i, i+1);
  • 亮点expand接受的是左右指针，是字符串的时候分别–和++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int ans_start = 0, ans_end = 0;
    string longestPalindrome(string s) {
        for(int i = 0; i < s.size()-1; i++){
            if(i>= (ans_end-ans_start)/2 && s.size()-i >= (ans_end-ans_start)/2){
                expand(s,i,i);
                expand(s,i,i+1);
                }
        }
        return s.substr(ans_start, ans_end-ans_start+1);
    }

    void expand(string& s, int left, int right){
        while(left>=0 && right<s.size() && s[left] == s[right]){
            left--;
            right++;
        }
        left++;
        right--;
        if(right - left > ans_end-ans_start){
            ans_start = left;
            ans_end = right;
        }
        return;
    }

9.旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数，要求使用空间复杂度为O(1)的原地算法

解法:
一、环形替代

  • 从nums[0]开始寻找它的下一个位置，使nums[next] = nums[0]
  • 同时将nums[next]原来的值记录下来，并去找它的下一个位置
  • 一次while循环结束后检查count是否为len
  • 若不为len则表示有的数还没进行位置更新
  • 进入下一个i的for循环
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int len  = nums.length;
    k = k % len;
    int count = 0;         // 记录交换位置的次数，n个同学一共需要换n次
    for(int start = 0; count < len; start++) {
        int cur = start;       // 从0位置开始换位子
        int pre = nums[cur];   
        do{
            int next = (cur + k) % len;
            int temp = nums[next];    // 来到角落...
            nums[next] = pre;
            pre = temp;
            cur = next;
            count++;
        }while(start != cur)  ;     // 循环暂停，回到起始位置，角落无人

二、取巧翻转

1
2
3
4
5
6
7
int n = nums.size();
if(n==1 || k == 0 || k == n) return;
k = k % n;
reverse(&nums[0], &nums[n]);
reverse(&nums[0], &nums[k]);
reverse(&nums[k], &nums[n]);
return;

10.删除并获得点数

给你一个整数数组nums，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i]，删除它并获得nums[i]的点数。之后，你必须删除所有等于nums[i]-1和nums[i]+1的元素。

解法:

  • 由”删除所有等于nums[i]-1和nums[i]+1的元素”联想到与打家劫舍不能偷相邻屋子有异曲同工之妙
  • 将nums数组用哈希表记录下来，并构建成一个打家劫舍的数组house
  • 用打家劫舍的方法解出来
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    unordered_map<int, int> f;
    int max_p = INT_MIN;
    for(int i = 0; i < nums.size(); i++){
        f[nums[i]]++;
        max_p = max(max_p, nums[i]);
    }
    vector<int> house(max_p+1);
    for(int i = 0; i < max_p+1; i++){
        house[i] = i * f[i];
            }
    vector<int> dp(max_p+1);
    dp[0] = house[0];
    if(house.size() == 1) return dp[0];
    dp[1] = house[1];
    if(house.size() == 2) return max(dp[0], dp[1]);
    dp[2] = house[0] + house[2];
    int ans = max(dp[1], dp[2]);
    for(int i = 3; i < house.size(); i++){
        dp[i] = max(dp[i-2], dp[i-3]) + house[i];
        ans = max(ans, dp[i]);
    }
    return ans;

11. 高楼扔鸡蛋问题

你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层0<=F<=N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于F的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层F呢？

解法:

  • 核心循环
    1
    2
    3
    4
    5
    for(int i = 1; i < n+1; i++){
        ans = min(ans, 碎和不碎中最坏情况);
    }

    # min表示在该次选择中，选哪层楼是最优解
  • 碎和不碎
    1
    2
    3
    4
    5
    碎和不碎 = max(dp(k, n-i), dp(k, i-1))+1;

    # dp(k, n-i)表示鸡蛋没碎，下一步把i层看作0层再实验
    # dp(K, i-1)表示鸡蛋碎了
    # max表示选择的是最坏的情况
  • 加上base case
    1
    2
    if(k == 1) return n; // 只有一个鸡蛋只能从0层开始线性搜索
    if(n == 0) return 0;
  • 优化思路:
    • 核心for循环改成二分搜索，碎了right = mid - 1，没碎left = mid + 1
    • 增加一个备忘录来记录已经算过的dp(k,n)

另一种解法:

  • dp[k][m]表示有k个鸡蛋，尝试扔了m次能测的楼层数(答案即为dp[k][m]=n时，m的值)
  • 核心代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    while(dp[k][m]<n){
        m++; //增加m的值来逼近n
        for(int i = 1; i <= k; i++){
            dp[i][m] = dp[i][m-1] + dp[i-1][m-1] + 1;
        }
    }

    # dp[i][m-1]没碎，表示下面的楼层
    # + 1加的是本楼层

12.戳气球问题

有n个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组 nums中。现在要求你戳破所有的气球。戳破第i个气球，你可以获得nums[i-1]*nums[i]*nums[i+1]枚硬币。这里的i-1和i+1代表和i相邻的两个气球的序号。如果i-1或 i+1超出了数组的边界，那么就当它是一个数字为1的气球。求所能获得硬币的最大数量。

解法:

  • dp[i][j]表示戳破i与j之间所有的气球得到的最高分(不戳破i和j)，所有要把原数组开头和末尾加一个值为1的元素，即构建新数组new_nums，new_nums.size() = nums.size()+2
  • 作选择时假设最后戳破的气球是第k个，则dp[i][j] = dp[i][k] + dp[k][j] + 得分计算公式
    1
    2
    3
    4
    5
    6
    for(int k = i+1; k < j; k++){
        int temple = dp[i][k] + dp[k][j] + 得分计算公式;
        dp[i][j] = max(dp[i][j], temple);
    }

    # 用max()和for遍历i与j之间所有k的可能，最后得到正确的dp[i][j]
  • 答案即为dp[0][new_nums.size()-1]

13.目标和问题

给每个元素分配”+”、”-“，求最后和为target的组合方式数

解法:

一、回溯法:

1
2
3
4
5
6
7
8
void backtrack(int i, int target){
    if(target == 0) ans++;
    if(i >= nums.size()) return;
    # 假设为nums[i]分配+
    backtrack(i+1, target+nums[i]);
    # 假设为nums[i]分配-
    backtrack(i+1, target-nums[i]);
}

二、数学法:

  • 将nums分为a与b两部分，由sum(a) - sum(b) = target 推导出sum(a) = (target + sum(b) + sum(a) / 2
  • 于是就转换成了子集和为sum(a)的组合方式有多少种的背包问题
  • dp[i][j]表示仅使用前i个物品的某几个恰好能填满容量为j的背包的方法数
  • 核心代码
    1
    2
    if(j - nums[j-1] < 0) dp[i][j] = dp[i-1][j];
    else dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[j-1]];

14.乘积为正数的最长子数组长度

解法：比较有意思的题，针对负数和0的情况分别处理

  • 代码包括主过程的for循环遍历g[]和一个调用函数max_lens()
  • for循环遍历含有所有零下标的g[]，分别将其切分成多个不含零的连续子数组
  • max_lens(vector& nums)则是算出传进来的子数组的乘积为正数的最长子数组长度(此时的子数组一定不含0，降低了处理难度)
  • 关键在于max_lens()中要根据负数的奇偶分情况
    • 负数个数为偶数，返回nums.size()
    • 负数个数为奇数，不要第一个负数和不要最后一个负数两种情况，哪种的子数组最长就取哪种
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      int getMaxLen(vector<int>& nums) {
          vector<int> g;
          int ans = 0;
          for(int i = 0; i < nums.size();i++) if(nums[i] == 0) g.push_back(i);
          int left = 0, right = 0;
          for(auto& t:g){
              right = t;
              vector<int>::const_iterator First = nums.begin() + left;
              vector<int>::const_iterator Second = nums.begin() + right;
              vector<int> new_nums(First, Second);
              ans = max(ans, max_lens(new_nums));
              left = right + 1;
          }
          if(g.size() == 0) ans = max_lens(nums);
          else if(left < nums.size()){
              vector<int>::const_iterator First = nums.begin() + left;
              vector<int>::const_iterator Second = nums.end();
              vector<int> new_nums(First, Second);
              ans = max(ans, max_lens(new_nums));
          }
          return ans;
      }

      int max_lens(vector<int>& nums){
          vector<int> f;
          for(int i = 0; i < nums.size();i++) if(nums[i] < 0) f.push_back(i);
          int n = f.size();
          if(n % 2 == 0) return nums.size();
          else{
              int left = f[f.size()-1] - f[0] + nums.size()-1 - f[f.size()-1];
              int right = f[f.size()-1] - f[0] + f[0];
              return max(left, right);
              }
      }

15.最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第i个观光景点的评分，一对景点（i < j）组成的观光组合的得分为values[i]+values[j]+i-j，也就是景点的评分之和减去它们两者之间的距离。返回一对观光景点能取得的最高分。

解法：

  • 第一反应用双层遍历 ans = max(ans,values[i]+values[j]+i-j)，但明显开销太大
  • 进一步想values[j]-j是固定的常数，而i属于[0, j-1]之间，只要在遍历j的时候更新values[i]+i的最大值就可以最终得到答案
  • 亮点在如何通过values[i]+values[j]+i-j联想到遍历j的同时更新i的相关值
1
2
3
4
5
6
7
int dp = values[0] + 0;
int ans = 0;
for(int i = 1; i < values.size(); i++){
    ans = max(ans, dp + values[i] - i);
    dp = max(dp, values[i] + i);
}
return ans;

16.接雨水

解法：

一、辅助数组法

  • 事先计算出两个辅助数组left_max和right_max，left_max[i]表示height[0…i-1]的最大值，right_max[i]表示height[i+1….height.size()-1]的最大值
  • 则i处可接雨水为min(left_max[i],right_max[i]) - height[i]
  • 最后答案就是遍历求和

二、双指针巧妙法

  • 定义left和right分别指向height首尾
  • 在while中更新left_max和right_max值，它们分别代表左右指针遍历到当前状态时数过的最大值
  • 每次while循环计算一次，谁的最大值小就计算谁，然后谁那边就往里缩
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int n = height.size();
    if(n < 3) return 0;
    int left = 0, right = n-1;
    int ans = 0;
    int left_max = INT_MIN, right_max = INT_MIN;
    while(left != right){
        left_max = max(left_max, height[left]);
        right_max = max(right_max, height[right]);
        if(left_max < right_max){
            # 此时虽然max_right并不一定是height[left]右边的最大值，可能是第二大、第三大....，但是既然不是最大值都比left_max大，那最大值一定比left_max大
            # 又因为计算ans只用到min(left_max, right_max(实际最大值))，所有可以直接计算该处能接多少雨水，else同
            ans += left_max - height[left];
            left++;
        }
        else{
            ans += right_max - height[right];
            right--;
        }
    }
    return ans;

17.解码方法

一条包含字母 A-Z 的消息通过以下映射进行了编码：
‘A’ -> 1
‘B’ -> 2
…
例如，”11106” 可以映射为：
“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F”

解法:动态规划

  • dp[i]表示前i个成员能组成几种映射
  • 亮点在于
    • 如果s[i] != ‘0’,那么dp[i]初始值就是dp[i-1]
    • 如果s[i-1]、s[i]能组成合法字符，那么dp[i]就得在初始值的基础上再加上dp[i-2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool break_flag  = false;
int numDecodings(string s) {
    vector<int> dp(s.size());
    dp[0] = 1;
    if(s[0] == '0') return 0;
    for(int i = 1; i<s.size();i++){
        if(s[i] != '0')  dp[i] = dp[i-1];
        if(isValid(s[i-1], s[i]) && i >= 2) dp[i] += dp[i-2];
        if(isValid(s[i-1], s[i]) && i == 1) dp[i] += 1;
        if(break_flag) return 0;
    }
    return dp[s.size()-1];
}

bool isValid(char t1, char t2){
    if(t1 == '1') return true;
    if(t1 == '2' && t2 <= '0' + 6) return true;
    if(t2 == '0') break_flag = true;
    return false;
}

# break_flag用于判别“1304”、“801”这种不能映射的非法输入

18.判断是否是丑数

丑数是只含1,2,3,5质因数的数

1
2
3
4
5
6
7
vector<int> factors = {2, 3, 5};
    for (int factor : factors) {
        while (n % factor == 0) {
            n /= factor;
        }
    }
return n == 1;

进阶:求第n个丑数
解法:

  • 不能用一个个判断，开销太大
  • 维护三个指针p2、p3、p5
  • dp[i]表示第i-1个丑数(因为dp[0]是第一个丑数)
  • 用min()取dp[p2]*2，dp[p3]*3，dp[p5]*5中最小的一个作为dp[i]，并把对应p指针++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    vector<int> dp(n);
    dp[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    int i = 1;
    while(i <= n-1){
        int num2=dp[p2]*2, num3=dp[p3]*3, num5=dp[p5]*5;
        int temple = min(min(num2, num3), num5);
        if(temple == num2) p2++;
        if(temple == num3) p3++;
        if(temple == num5) p5++;
        dp[i++] = temple;
    }
    return dp[n-1];

19.求不同的二叉搜索树数目

求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？

解法:抽象变成动态规划问题

  • 本题关键不在二叉搜索树，而在不同的树数目
  • dp[i]表示由i个节点构成的不同二叉搜索树数目
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    vector<int> dp(n+1);

    # 显然节点为0时或1个时，只有一种可能
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 0;j < i; j++){
            dp[i] += dp[j]*dp[i-1-j];
        }
    }
    return dp[n];

    # dp[j]中j是左子树的节点数，即dp[j]表示的是左子树不同数目
    # dp[i-1-j]中j是右子树的节点数，即dp[i-1-j]表示的是右子树不同数目，总节点数为i-1是因为根节点要用掉一个节点

20.矩阵中的路径

给定一个m x n二维字符网格board和一个字符串word 。如果word存在于网格中返回true ；否则，返回false(不能重复用)

解法:暴力遍历加记录走过路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool exist(vector<vector<char>>& board, string word) {
    int n = board.size(), m = board[0].size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m;j++){
            if(board[i][j] == word[0]){
            if(isTrue(board,word,i,j,0)) return true;
            }
        }
    }
return false;
}

bool isTrue(vector<vector<char>>& board, string word, int i, int j, int w_i){
    if(w_i >= word.size()) return true;
    if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return false;
    if(board[i][j] != word[w_i]) return false;
    char temple = board[i][j];
    board[i][j] = '0';
    bool ans = isTrue(board,word, i-1,j,w_i+1) || isTrue(board,word, i,j-1,w_i+1) || isTrue(board,word, i+1,j,w_i+1) || isTrue(board,word, i,j+1,w_i+1);
    board[i][j] = temple;
    return ans;
}

# 将board[i][j]变成'0'后又变回来，是为了在一次递归中不走重复路，因为'0'不会与字符串匹配成功

21.全为1的正方形的最大面积

在一个由’0’和’1’组成的二维矩阵内，找到只包含’1’的最大正方形，并返回其面积

解法:暴力遍历

  • 虽然是暴力遍历，但是因为剪枝做得好，时间空间开销都极小
  • 维护一个全局变量max_d表示当前遍历过的全为1的正方形最大的边
  • 这样每次检测的时候就从max_d+1开始检测
  • 再加上检测end_i、end_j只要一个越界立即返回
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    int max_d = 0;
    int maximalSquare(vector<vector<char>>& matrix) {
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(matrix[i][j] == '1'){
                    max_d = max(max_d, 1);
                    isValid(matrix, i, j, max_d+1);
                }
            }
        }
        return max_d * max_d;
    }

    void isValid(vector<vector<char>>& matrix, int i, int j, int d){
        int end_i = i + d -1, end_j = j + d -1;
        if(end_i >= matrix.size() || end_j >= matrix[0].size()) return;
        for(int t1 = i; t1 <= end_i; t1++){
            for(int t2 = j; t2 <= end_j; t2++){
                if(matrix[t1][t2] == '0') return;
            }
        }
        max_d = max(max_d, d);
        isValid(matrix, i, j, d+1);
        return;
        }

数据结构设计

1.实现一个LRU缓存

解法:

  • 由一个哈希表 + 一个双向链表实现
    • 哈希表<int, node>提供快速访问，int是键
    • 双向链表每个节点有int key, int val, next指针和prev指针提供顺序，key是键
  • 尾部的是最近使用的，头部的是最近未使用的
  • 访问某节点时
    • 当前链表中存在，将其放到尾部
    • 当前链表中不存在，插入到尾部，检查若链表size已满就把头部节点删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# 定义双向链表的节点结构
struct Node{
    int key, val;
    Node *next;
    Node *prev;
    Node(int k, int v){
        this->key = k;
        this->val = v;
    }
};

# 定义双向链表结构和一些方法，方便后续在LRU中实例化一个双向链表
class DoubleList{
    private: 
    Node *head;
    Node *tail;
    int size;
    
    public:
    DoubleList(){
        head = new Node(0,0);
        tail = new Node(0,0);
        head->next = tail;
        tail->prev = head;
        size = 0;
    }
    
    void addLast(Node *x){
        if(x == nullptr) return;
        x -> prev = tail -> prev;
        x -> next = tail;
        tail->prev->next = x;
        tail->prev = x;
        size++;
    }
    
    void remove(Node *x){
        if(x == nullptr) return;
        x -> prev -> next = x ->next;
        x -> next -> prev = x -> prev;
        size--;
    }
    
    Node* removefirst(){
        if(head == tail) return nullptr;
        Node *p =head->next;
        remove(head->next);
        return p;
    }
    
    int length(){
        return size;
    }

};

# LRU主要逻辑
class LRUCache {
private:
    unordered_map<int, Node*>map;
    DoubleList cache;
    int cap;
public:
    LRUCache(int capacity) {
        cap = capacity;
        unordered_map<int, Node*>map;
        DoubleList cache;
    }
    
    void makeup(int key){
        Node *p = map[key];
        cache.remove(p);
        cache.addLast(p);
    }
    
    int get(int key) {
        if(map.count(key) == 0) return -1;
        makeup(key);
        if(map[key] == nullptr) return -1;
        return map[key]->val;
    }
    
    void insert(int key, int value){
        Node *p = new Node(key, value);
        cache.addLast(p);
        map[key] = p;
        if(cache.length() > cap) removeLeast();
    }
    
    void put(int key, int value) {
        if(map.count(key) == 0) insert(key, value);
        cache.remove(map[key]);
        insert(key, value);
    }
    
    void removeLeast(){
        Node *p = cache.removefirst();
        map.erase(p->key);
    }
};

# 用法
# LRUCache* obj = new LRUCache(capacity);
# int param_1 = obj->get(key);
# obj->put(key,value);

2.实现一个LFU缓存

解法:

  • 满时删除访问次数(freq变量)最少的节点，若有多个相同节点则删除最旧的那个
  • 第一个哈希表<int,int>存key到val的映射
  • 第二个哈希表<int,int>存key到freq的映射
  • 第三个哈希表<int,LinkedHashSet> 存freq到freq相同的key列表映射
  • 一个哈希链表LinkedHashSet存key列表的同时具有时间顺序(哈希链表=哈希表+双向链表)

3.用栈实现一个队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 要点：数据结构栈写在private里，MyQueue()里不需要写代码

class MyQueue {
private:
        stack<int> s1;
        stack<int> s2;
public:
    MyQueue() {
    }
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        if(s2.empty()){
            while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
            }
        }
        int temple = s2.top();
        s2.pop();
        return temple;
    }
    
    int peek() {
        if(s2.empty()){
            while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
            }
        }
        return s2.top();
    }
    
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

4.含min()函数的栈(最小栈)

解法：辅助栈

  • 一开始想法是将栈里的元素排序，压入辅助栈，但这样pop和push的复杂度都过高
  • 将辅助栈结构改成当前栈里的元素的最小值
  • 亮点min_stack.push(min(min_stack.top(), x));
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class MinStack {
    private:
        stack<int> s;
        stack<int> min_stack;
    public:
        /** initialize your data structure here. */
        MinStack() {
            # 初始化处理
            min_stack.push(INT_MAX);
        }
        
        void push(int x) {
            s.push(x);
            min_stack.push(std::min(min_stack.top(), x));
        }
        
        void pop() {
            s.pop();
            min_stack.pop();
        }
        
        int top() {
            return s.top();
        }
        
        int min() {
            return min_stack.top();
        }
    };

5.实现一个返回中位数的结构

解法:用优先队列辅助

  • 定义两个优先队列，一个最大堆，一个最小堆
  • 输入的数据小于=最大堆堆顶就放入最大堆，否则放入最小堆
  • 当最大堆size==最小堆size+2时，调整
  • 当最小堆size==最大堆size+1时，调整
  • 保证最大堆size始终==最小堆size或者最小堆size+1
  • 这样中位数就是最大堆堆顶或者最大堆堆顶与最小堆堆顶的平均数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class MedianFinder {
    private:
        priority_queue<int> big;
        priority_queue<int, vector<int>, greater<int> > small;
    public:
        MedianFinder() {

        }
        
        void addNum(int num) {
            if(big.empty() || num <= big.top()) big.push(num);
            else small.push(num);
            if(big.size() > small.size()+1){
                small.push(big.top());
                big.pop();
            }
            if(small.size() > big.size()){
                big.push(small.top());
                small.pop();
            }
        }
        
        double findMedian() {
            if((big.size() + small.size())% 2 == 1) return big.top();
            return (big.top() + small.top()) / 2.0;
        }
    };

解题通用思路

1.求公共前缀(字符串仅由a-z组成)取巧方法：先对每个字符串sort排序，排序后第一个字符串与最后一个字符串的公共前缀就是所有字符串的最长公共前缀

2.判断二叉树是否为对称二叉树时，用递归：

1
2
3
box(TreeNode* zuo, TreeNode* you){
return zuo->val == you->val && box(zuo->left, you->right) && box(zuo->right, you->left);
}

3.求一个字符串内无重复的最长子串，用滑动窗口法：定义两个指针，当下一个遍历字符不在窗口内时，右指针++，当下一个遍历字符在窗口内时左指针加到老字符不存在窗口为止，记录下过程中出现的最大结果，遍历完成返回最大结果

4.盛最多水容器问题，用双指针：初始left=0，right=nums.size()-1,然后比较nums[left]和nums[right]，哪个小哪个指针就往内缩，记录下过程中出现的最大结果，遍历完成返回最大结果

5.对于首尾不能同时存在的问题，最优解决办法是分别求出没有首和没有尾两种情况的结果，再比较两个结果哪个更符合题意

6.对无序链表进行排序

  • box():用快慢指针将链表分成两段
  • merge():将两个有序链表合并成一个更长的有序链表
  • 在box()里面写成return merge(box(第一段), box(第二段))

7.异或题重要规律

1
2
3
4
a^b = b^a
a^a = 0
a^0 = a
a^b = c => a^c = b

8.涉及异或数组的问题，首先想到用前缀和异或数组来作辅助

1
2
3
4
xor[i] = 0, i == 0时
xor[i] = arr[i-1]^xor[i-1], i > 0时
# arr[]是题目给的用来异或的数组
# 即xor[i] = arr[0]^......^ar

9.宽度搜索(bfs)核心思想

  • 该层全部压入队列
  • 然后一次弹出
  • 每个弹出的节点延伸的子节点全压入队列

双向bfs

  • 奇数次扩散从起点开始，偶数次扩散从终点开始
  • 直到两个方向的扩散出现交集

10.一旦设计子序列和最值，一定考动态规划，时间复杂度一般都要为O(n平方)，即都要用双层嵌套为核心循环

11.组合、排列、子集问题记得用回溯法，套下面的框架

1
2
3
4
5
6
# track一般是一个vector数组
for(){
    track.push_back(num[i]);
    box(track,....);
    track.pop_back();
}

12.要求原地修改数组的题目，正着遍历困难的话，不妨试着从数组末尾开始更新元素

13.最小花费爬楼梯题目，错误思路是贪心，正确思路是dp[i]表示到达i层所需的最小花费即dp[i] = min(dp[i-1], dp[i-2])

14.有时候不清楚二维dp数组的遍历方向，不妨看看最终答案应该返回dp的哪个下标，由下标逆推出遍历方向

15.状态压缩技巧：改变遍历的顺序就可以用到上一次循环中的老数据。例如：dp[i-1][j-1]这个数，若i正遍历，j倒遍历，则用dp[j-1]即可取代，因为在给dp[j-1]更新值前，它里面存的是上一个i的dp[j-1]

16.组合、排列、子集问题用回溯法，灵活使用

1
2
3
4
5
for(){
    track.push_back(num[i]);
    box(track,...);
    track.pop_back();
}

类似框架

17.腐烂的橘子类型题目一般用BFS解

  • 先找到起始所有腐烂的橘子
  • 然后循环处理，把新腐烂的橘子加入下一次循环的队列中
  • 当下一次循环的队列为空时，说明不能继续腐烂了，判断一下还有没有新鲜的橘子，
    • 如果有，就返回-1(表示这个新鲜的橘子永远不能腐烂)
    • 如果没有，就返回循环的次数(一般就是答案)

18.二叉树的三种遍历方向

  • 前序遍历：节点->左子树->右子树
  • 中序遍历：左子树->节点->右子树
  • 后序遍历：左子树->右子树->节点

19.面积和思路(一般用于矩形求子矩形内之和要用到前缀和数组的题目)

S(O,D)=S(O,C)+S(O,B)−S(O,A)+D

S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G)

20.状态压缩一定是先写出二维数组存数据的解法，然后观察才能得到状态压缩法的，不可能一来直接写出状态压缩。很多解题思路也是这样，先写出暴力遍历法，再去优化