前言

本篇文稿为站长阶段性学习笔记，建议读者精通C++包含STL并深入学习数据结构的前提下阅读。

滑动检索/双指针/前缀和

一般和数据结构中的队列相似，符合先进先出规则，区别为需不断更新处理数据

核心：载入💾更新💽弹出🖨️

  1. 载入💾：下标为i的元素进入窗口，更新相关统计量。

当窗口载入<窗口长度时即i<k−1 ，需不断重复执行该步骤填满窗口

  1. 更新💽：更新答案，检索并处理在窗数据。一般是更新最大值/最小值/平均值。
  2. 弹出🖨️：下标为i−k+1的元素离开窗口，更新相关统计量。

注意事项

1
2
3
double m_age = -1000; // 注意初始化特殊情况
if(i < k - 1) continue; // 满窗即可运行 i=k-1时
iw = min(w, iw); // 注意逻辑顺序，先结算后移动

例题: 半径为 k 的子数组平均值

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。
半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或> 后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans(n, -1); 
        // 特殊情况筛选=窗>数组，左右和本身2k+1
        if (k * 2 + 1 <= n) { 
            long long sum =
                accumulate(nums.begin(), nums.begin() + k * 2 + 1, 0LL);
            // 等同于循环求和，窗口全部载入
            for (int i = k; i + k < n; ++i) { 
              // k为中心，移动
                if (i != k) {
                    sum += nums[i + k] - nums[i - k - 1]; // 滑动更新
                }
                ans[i] = sum / (k * 2 + 1);
            }
        }
        return ans;
    }
};

二分查找/最值算法

核心：定区🧵收束🪡边界判断🖼️

  1. 定区🧵：
    通常设置三个变量：二分中间值mid、左边界left，右边界right
  2. 收束🪡：不断求取二分值覆盖边界以压缩区间
    以中间值mid来将其赋值给左或右区间作边界
  3. 边界判断🖼️：通常可选闭、开、半开闭区间，其影响区间定义、收束条件、终止判断
    闭区间：边界可与数据覆盖，直接判断收束，重叠即终止
    开区间：边界包围数据，判断收束需加减，包围仅一数据终止
1
2
3
4
5
6
7
8
9
10
11
int //区间定义
while(){//收束终止判断
    if(){//收束条件
    }
} 
m%2==0?m=m/2:m=(m+1)/2;  //此处获取二分值，缺点：int类型取整
left<X&&right<X?left=m:right=m;  //根据对比结果将二分指赋为区间边界
//上述为直观二分法，不推荐使用，仅为方便理解
int mid,left=0,right=nums.size()-1;//1.定区 此为闭区间写法
mid=left+(right-left)/2;//2.收束 此为逻辑写法
mid=(right+left)/2;//此为简化写法
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
// 闭区间写法
int lower_bound(vector<int>& nums, int target) {
    int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
    while (left <= right) { // 区间不为空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {// nums[left-1] < target
            left = mid + 1; // 范围左缩小到 [mid+1, right]
        } else {// nums[right+1] >= target
            right = mid - 1; // 范围右缩小到 [left, mid-1]
        }
    }
    return left;
}

// 左闭右开区间写法
int lower_bound2(vector<int>& nums, int target) {
    int left = 0, right = nums.size(); // 左闭右开区间 [left, right)
    while (left < right) { // 区间不为空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) { // nums[left-1] < target
            left = mid + 1; // 范围缩小到 [mid+1, right)
        } else {// nums[right] >= target
            right = mid; // 范围缩小到 [left, mid)
        }
    }
    return left;
}

// 开区间写法
int lower_bound3(vector<int>& nums, int target) {
    int left = -1, right = nums.size(); // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {// nums[left] < target
            left = mid; // 范围缩小到 (mid, right)
        } else {// nums[right] >= target
            right = mid; // 范围缩小到 (left, mid)
        }
    }
    return right;
}

注意事项

mid是否能将区间均分不重要，应关注区间如何收束

1
2
3
4
5
6
// 明确循环不变量：
nums[left] //闭区间加减
nums[right] //开区间不便
nums[mid] //由区间类型定义
// 常用二分收束
int mid = left + (right - left) / 2;

例题: 统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
0 <= i < j < n，且
lower <= nums[i] + nums[j] <= upper

例如，输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6 ；输出：6 ；
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

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 Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long ans = 0;
        Arrays.sort(nums);
        for (int j = 0; j < nums.length; ++j) {
            int r = lowerBound(nums, j, upper - nums[j] + 1); // <= upper-nums[j] 的 nums[i] 的个数
            int l = lowerBound(nums, j, lower - nums[j]); // < lower-nums[j] 的 nums[i] 的个数
            ans += r - l;
        }
        return ans;
    }

    private int lowerBound(int[] nums, int right, int target) {
        int left = -1; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = (left + right) >>> 1;
            if (nums[mid] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right;
    }
}

递归搜索树/DFS/BFS💎

核心：寻根🔍纵深🥏递归终止🎯

  1. 寻找根节点，分析问题，来确定根节点如何开始。
  2. 树型数据结构深度，通常与问题中的数据数目相互挂钩。
  3. 选择合适的递归终止的判断条件，并记录结果，以减少运算时间。
1
2
3
4
5
int fun(int x)
{
    //逻辑代码区，递归终止条件
    return fun(a) + fun(b) + ...;//树型递归
}

注意事项

不应关注楼梯阶数，应思考每一步的选择，根据选择判断阶数是否达标
在输入数据的问题规模<10^5,两者速度差不多，当问题规模>10^5,cin和cout速度将会慢一倍或更多。

1
2
3
//输入输出流选择
scanf("%d", &n);
cin >> n;//不推荐

例题:

一个楼梯共有 n级台阶，每次可以走一级或者两级，问从第0级台阶走到第n级台阶一共有多少种方案。

1≤n≤15,输入格式:共一行，包含一个整数 n;输出格式:共一行，包含一个整数，表示方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int n;
int dg(int dep)
{
    if (dep == 1)  return 1;
    if (dep == 2)  return 2; 
    return dg(dep - 1) + dg(dep - 2);//树形递归，统计所有情况
}
int main()
{
    scanf("%d", &n);//录入台阶数n
    printf("%d\n", dg(n)); //n-->dep
    return 0;
}

动态规划（DP）/记忆化搜索💎

核心：暴力🥊记忆🎰动态规划📊

  1. 暴力递归：
    会随着数据量的增大时间复杂度呈指数型上升，最终会有超时的风险。
  2. 记忆化搜索：
    是在暴力递归的基础上对中间过程进行过计算的结果进行保存，以便在下一次递归调用的时候可以直接读取，一般经过记忆化优化，在数据量很大的情况下，效果很明显。
  3. 动态规划：
    动态规划常用来解决方案数和最优解两类问题，当前状态往往都是有前一步子问题的状态推导而来，存在递推公式。
1
2
3
//记忆化搜索，通常借助哈希表实现对重复数据的检索
Map<Integer, Integer> map = new HashMap<>();
//语法详见《算法基础导读》

例题: 数组返回特定和

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。

暴力搜索dfs+回溯会超时，可以考虑使用dfs+备忘录的模式，一般是优化dfs，也就是记忆化搜索。

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
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    /*使用map，记录递归过程sum的值，以及出现的次数；下一次需要sum的时候，如果map中存在，直接取出来即可，因为之前已经计算过了 */
    public int main(int[] nums, int target) {
        return dfs(nums, target, 0);
    }

    private int dfs(int[] nums, int target, int sum) {
        if (sum == target) { //特殊情况处理
            return 1;
        }
        // 当前sum值在备忘录中已经计算过，则直接取出来返回
        if (map.containsKey(sum)) {
            return map.get(sum);
        }
        int res = 0;
        // 每一层都可以从数组的0位置开始搜索
        for (int num : nums) {
            // 添加限制条件
            if (sum + num <= target) {
                res += dfs(nums, target, sum + num);
                // 一定要将当前计算的结果存到备忘录中
                map.put(sum, res);
            }
        }
        return res;
    }
}

求方案个数，还有一种思路就是利用动态规划的思想，定义dp数组表示 当目标值为n的时候数组中的组合方案数，存在递推公式：f(n) = sum( f(n-i) ) 0<i<=n且需要存在物品重量等于i，则可以循环物品，针对每一个小于等于n的物品，计算f(n-i)值累积求和.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int main(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1; //对特殊情况的数组赋初值
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {//快速遍历数组nums，省去for循环遍历
                if (num <= i) {
                    dp[i] += dp[i-num];
                }
            }
        }
        return dp[target];
    }
}

注意事项

1
for (int a : x) //快速遍历，a:接收容器，x:遍历数组地址

贪心💎

核心：尝试✏️退回⌛最优解⏱️

  1. 先分析问题，将复杂问题简单化，结合暴力枚举，逐一尝试
  2. 通常需要根据题意创建两个或多个变量计数，以便可退回至最优解法
  3. 记录每次枚举是否最优，来共同组成最后答案

例题: 返回最大子序列

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。
你可以在 text 中任意位置插入一个字符，这个插入的字符必须是pattern[0]或者pattern[1]。注意，这个字符可以插入在 text 开头或者结尾的位置。
请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。
子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

没有特判 x=y 的情况，要先更新答案，再更新 cnt_X，这可以保证更新答案时 cnt_X 表示的是当前字母左边的 x 的出现次数，cnt_X 尚未计入当前字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        char x = pattern[0], y = pattern[1];//分别提取插入字符
        long long ans = 0;
        int cnt_x = 0, cnt_y = 0;
        for (char c : text) {//快捷遍历
            if (c == y) {//可插入x
                ans += cnt_x;//简洁求和，类似二分
                cnt_y++;
            }
            if (c == x) {//可插入y
                cnt_x++;
            }
        }
        //因为可能x与y同时出现，会导致计数重复
        return ans + max(cnt_x, cnt_y);
    }
};

特别鸣谢

思路参考：茶灵山艾府