# 算法经典题型解析（C++）


# 前言

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

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

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

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

1. 载入 💾：下标为`i`的元素进入窗口，更新相关统计量。
   {{< note info flat >}}
   当`窗口载入<窗口长度`时即`i<k−1 `，需不断重复执行该步骤填满窗口
   {{< /note >}}
2. 更新 💽：更新答案，检索并处理`在窗数据`。一般是更新最大值/最小值/平均值。
3. 弹出 🖨️：下标为`i−k+1`的元素离开窗口，更新相关统计量。

## 注意事项

```C++
  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 ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。
> {{< note info flat >}}
> 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。
> {{< /note >}}

```C++
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. 边界判断 🖼️：通常可选闭、开、半开闭区间，其影响`区间定义`、`收束条件`、`终止判断`
   闭区间：边界可与数据覆盖，直接判断收束，重叠即终止
   开区间：边界包围数据，判断收束需加减，包围仅一数据终止

```C++
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;//此为简化写法
```

```C++
// 闭区间写法
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`是否能将区间均分不重要，应关注区间如何收束

```C++
  // 明确循环不变量：
  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
> {{< note info flat >}}
> 例如，输入：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) 。
> {{< /note >}}

```C++
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. 选择合适的递归终止的判断条件，并记录结果，以减少运算时间。

```C++
int fun(int x)
{
    //逻辑代码区，递归终止条件
    return fun(a) + fun(b) + ...;//树型递归
}
```

## 注意事项

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

```C++
    //输入输出流选择
    scanf("%d", &n);
    cin >> n;//不推荐
```

## 例题:

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

{{< note info flat >}}
1≤n≤15,输入格式:共一行，包含一个整数 n;输出格式:共一行，包含一个整数，表示方案数。
{{< /note >}}

```C++
#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. 动态规划：
   动态规划常用来解决方案数和最优解两类问题，当前状态往往都是有前一步子问题的状态推导而来，存在递推公式。

```C++
//记忆化搜索，通常借助哈希表实现对重复数据的检索
Map<Integer, Integer> map = new HashMap<>();
//语法详见《算法基础导读》
```

## 例题: 数组返回特定和

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

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

```C++
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;
    }
}
```

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

```C++
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];
    }
}
```

## 注意事项

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

# 贪心 💎

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

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

## 例题: 返回最大子序列

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

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

```C++
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);
    }
};
```

# 特别鸣谢

{{< note default flat >}}
思路参考：[茶灵山艾府](https://leetcode.cn/u/endlesscheng/)
{{< /note >}}