【C++ 算法进阶】算法提升四

数组查询问题 （数组优化）

题目

数组为 {3 ， 2， 2 ，3 ，1} 查询为（0 ，3 ，2）

这个查询的意义是 在数组下标0~3这个范围上 有多少个2 （答案为2）

假设现在给你一个数组arr 假设我们对于这个数组的查询十分频繁

现在要求你返回所有的查询结果

题目分析

我们可以看到题目中有 对于这个数组的查询十分频繁 这句描述

看到之后我们自然就可以想到我们要做一个预处理数组来让查询的代价尽可能的低 （现在的代价是O（M）） M为查询数组的长度

这里提供两个预处理数组的思路

• 因为每次给的范围是随机的 所以说我们从数字入手 对于每个数字建立一张下标表 以后每次查询的时候只需要通过二分法找到范围内数字的下标即可 这样我们的时间复杂度就成为了二分法的时间复杂度
• 我们可以从数字的范围开始入手 对于每个数字统计它在0~N范围上出现的次数 以后假设我们需要求从 J到K上某个数字出现的次数就只需要让这个数组的K位置的数字减去J位置的数字即可 这样的时间复杂度就是O(1)了

我们这里提供方法二的解

代码解析

这里需要注意的是

for (auto& it : map)

上面这一行代码 如果我们没有写& 那么他就是值遍历 导致我们下面的修改没有事实上修改map数组内的数据

int main() {vector<int> arr = {3 ,2 ,2 , 3, 1};// 这里建立N个数组 每个数组和arr一样长 代表从0开始到当前位置有多少个当前数unordered_map<int, vector<int>> map;for (auto x : arr){if (map.count(x) == 0){map[x] = vector<int>(arr.size(), 0);}}// 开始填表 for (auto& it : map){int count = 0;for (int i = 0; i < arr.size(); i++){if (it.first == arr[i]){count++;}it.second[i] = count;}}cout << map[2][3] - map[2][1] << endl;return 0;
}

子数组的最大累加和 （经典动态规划）

题目

本题为LC原题 题目如下

题目分析

这是一道最经典的动态规划问题 是一个以i为结尾位置的模型

我们只需要使用一个dp数组 记录下从0开始的每个位置为结尾时 能够获取的最大值是多少即可

因为子数组的结尾肯定是在原数组中的 所以说我们计算每个位置作为结尾的最大和肯定能算出最终答案

代码解析

本题没有什么难点

class Solution {
public:int maxSubArray(vector<int>& nums) {if (nums.size() == 1) {return nums[0];}// 首先创建一个dp数组vector<int> dp(nums.size() , 0);dp[0] = nums[0];for (int i = 1 ; i < nums.size(); i++) {dp[i] = dp[i-1] < 0 ? nums[i] : dp[i-1] + nums[i];}int max = dp[0];for (auto x : dp) {if (x >max) {max = x;}}return max;}
};

二维数组 子矩阵的最大累加和 （数组压缩 + 动态规划）

题目

返回一个二维数组中 子矩阵的最大累加和 此题为LC原题 题目如下

题目分析

这道题其实就是我们第二题的变种

思路相同 ： 如果我们要求一个子矩阵和的最大值 那么我们可以将问题转化成

求以每一行作为矩阵的头 往下扩展时 矩阵的最大值

因为矩阵肯定在二维数组内 所以说只要我们求出以每一行作为起始的最大值 就能求出最终的答案

数组压缩技巧

当我们求第一行时 我们可以直接照搬上一题的代码

当我们求第一行到第N行时 因为我们求的是和 所以说我们可以将各列的代码相加 组成一个新的数组 再使用第一行的技巧

代码详解

class Solution {
public:vector<int> getMaxMatrix(vector<vector<int>>& matrix) {int N = matrix.size();int M = matrix[0].size(); int a = 0;int begin = 0;int c = 0;int d = 0;int max = INT_MIN;for (int i = 0; i < N; i++) {vector<int> arr(M , 0);for (int j = i; j < N;j++) {int cur = 0;int b = 0; // 这个值要变化for (int k = 0; k < M; k++) {arr[k] += matrix[j][k];cur += arr[k];if (cur > max) {max = cur;a = i;begin = b;c = j;d = k;}if (cur < 0) {cur = 0;b = k + 1;}}}}return {a , begin, c, d};}
};

子序列的最大累加和 （动态规划）

题目

返回一个数组中 选择的数字不能相邻的情况下 最大子序列的累加和

题目分析

这里提供给大家一个思路 只要我们看到 子序列 这几个字 我们就要想到这是一种从左到右的尝试模型

我们可以定义一个函数 int process(vector<int>& arr, int index, vector<int>& memo) 该函数能否返回在index位置的时候子序列的最大累加和

那么接下来我们就只需要列出边界和各种的可能性即可

代码详解

#include<iostream>
using namespace std;
#include<vector>int process(vector<int>& arr, int index, vector<int>& memo) {if (index >= arr.size()) {return 0;}// 如果已经计算过，直接返回if (memo[index] != -1) {return memo[index];}// 选择当前数字并跳过下一个数字int p1 = arr[index] + process(arr, index + 2, memo);// 不选择当前数字int p2 = process(arr, index + 1, memo);// 记录结果memo[index] = max(p1, p2);return memo[index];
}int getMaxSumNonAdjacent(vector<int>& arr) {if (arr.empty()) {return 0;}vector<int> memo(arr.size(), -1);  // 用于记忆化的数组return process(arr, 0, memo);
}

糖果问题 （贪心）

题目

本题为LC原题 题目如下

题目分析

这个问题是一种贪心问题

相邻的两个孩子评分更高的孩子会获得更多的糖果

• 左规则：当 ratings[i−1]<ratings[i] 时 i 号学生的糖果数量将比 i−1 号孩子的糖果数量多
• 右规则：当 ratings[i]>ratings[i+1] 时 i 号学生的糖果数量将比 i+1 号孩子的糖果数量多

所以说我们可以将这个数组遍历两次

• 从左到右遍历 遇到比前一个位置大的糖果就++ 否则糖果归1
• 从右到左遍历 遇到比前一个位置大的糖果就++ 否则糖果归1

之后我们将这两次遍历的结果取较大值即可 （因为要同时满足这两个条件）

代码详解

class Solution {
public:int candy(vector<int>& ratings) {int M = ratings.size();vector<int> left(M , 0);vector<int> right(M , 0);left[0] = 1;for (int i = 1 ; i < M; i++) {if (ratings[i] > ratings[i-1]) {left[i] = left[i-1] + 1;} else {left[i] = 1;}}right[M - 1] = 1;for (int i = M - 2; i >=0 ; i--) {if (ratings[i] > ratings[i+1]) {right[i] = right[i+1] + 1;} else {right[i] = 1;}}for (int i = 0; i < M; i++) {left[i] = left[i] > right[i] ? left[i] :right[i];}int max = 0;for (auto x : left) {max += x;}return max;}
};

生成数组（分治）

题目

给定一个正数为size 生成长度为size的达标数组

达标： 对于任意的 i < k < j 满足 [I] + [J] != 2*[K]

题目分析

这是一道典型的分治问题 想到这种思路的过程挺难的 这里直接提供思路

假设一个数组达标 那么这个数组的两倍肯定也达标 这个数组的两倍+1肯定也达标 （自己使用公式验证下就能明白）

那么数组的两倍 再加上这个数组的两倍+1 组成的一个新数组 肯定也达标

这是为什么呢？

因为我们如果从这个数组的左边或者右边任意选一个数相加 那么他们相加肯定是奇数 而最后要达标则要是偶数2*[K]

所以说我们可以从一个数开始 二倍二倍的往上扩 自然就能求出最终答案

如果不是2的n次方怎么办呢？

只需要舍弃掉后面多余的数字即可

代码详解

vector<int> process(int size) {if (size == 1) {return  { 1 };}int halfsize = (size + 1) / 2;vector<int> half = process(halfsize);// 构造出一个完成的数组// 一半是奇数 一半是偶数vector<int> ans;for (int i = 0; i < halfsize; i++) {ans.push_back(half[i] * 2 + 1);}for (int i = halfsize; i < size; i++) {ans.push_back(half[i - halfsize] * 2);}return ans;
}int main() {vector<int> ans = process(9);for (auto x : ans) {cout << x << endl;}return 0;
}

字符串交错组成 （动态规划 – 样本对应模型）

题目

此题为LC原题目 题目如下

题目分析

遇到这种多个字符串问题 我们第一时间想到的就是要用动态规划的样本对应模型去解决

首先设置一个process函数

bool process(string& s , string& s1 , string&s2 , int index1 , int index2)

这个函数的含义是 从s1的第index1个位置 s2的第index2个位置开始 能否组成字符串s

之后我们只需要考虑三种情况

1. 终止条件
2. 越界情况
3. 有几种可能性

代码详解

class Solution {
public:// 带有记忆化搜索的递归函数bool process(string& s1, string& s2, string& s3, int index1, int index2, vector<vector<int>>& dp) {// 如果 s1 和 s2 的字符都处理完了，且正好匹配了 s3 的长度if (index1 == s1.size() && index2 == s2.size()) {return true;}// 检查越界情况if (index1 > s1.size() || index2 > s2.size()) {return false;}// 如果 dp 中已经计算过该状态，直接返回存储的结果if (dp[index1][index2] != -1) {return dp[index1][index2];}// 当前字符在 s3 中的位置int sIndex = index1 + index2;// 尝试从 s1 中取字符bool p1 = false;if (index1 < s1.size() && s1[index1] == s3[sIndex]) {p1 = process(s1, s2, s3, index1 + 1, index2, dp);}// 尝试从 s2 中取字符bool p2 = false;if (index2 < s2.size() && s2[index2] == s3[sIndex]) {p2 = process(s1, s2, s3, index1, index2 + 1, dp);}// 存储结果：如果 p1 或 p2 为 true，存储 1；否则存储 0dp[index1][index2] = (p1 || p2);return dp[index1][index2];}// 主函数入口bool isInterleave(string s1, string s2, string s3) {// 边界条件检查：如果 s3 的长度不等于 s1 和 s2 长度之和，返回 falseif (s3.size() != s1.size() + s2.size()) {return false;}// 初始化 dp 数组，值全为 -1，表示尚未计算vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, -1));// 从 index1 = 0, index2 = 0 开始return process(s1, s2, s3, 0, 0, dp);}
};

大楼轮廓线问题 （）