湖州建设企业网站,沈阳网站开发久,销售网站建设常遇到的问题,微信里的小程序怎么添加数组查询问题 #xff08;数组优化#xff09;
题目
数组为 {3 #xff0c; 2#xff0c; 2 #xff0c;3 #xff0c;1} 查询为#xff08;0 #xff0c;3 #xff0c;2#xff09;
这个查询的意义是 在数组下标0~3这个范围上 有多少个2 #xff08;答案为2数组优化
题目
数组为 {3 2 2 3 1} 查询为0 3 2
这个查询的意义是 在数组下标0~3这个范围上 有多少个2 答案为2
假设现在给你一个数组arr 假设我们对于这个数组的查询十分频繁
现在要求你返回所有的查询结果
题目分析
我们可以看到题目中有 对于这个数组的查询十分频繁 这句描述
看到之后我们自然就可以想到我们要做一个预处理数组来让查询的代价尽可能的低 现在的代价是OM M为查询数组的长度
这里提供两个预处理数组的思路
因为每次给的范围是随机的 所以说我们从数字入手 对于每个数字建立一张下标表 以后每次查询的时候只需要通过二分法找到范围内数字的下标即可 这样我们的时间复杂度就成为了二分法的时间复杂度我们可以从数字的范围开始入手 对于每个数字统计它在0~N范围上出现的次数 以后假设我们需要求从 J到K上某个数字出现的次数就只需要让这个数组的K位置的数字减去J位置的数字即可 这样的时间复杂度就是O(1)了
我们这里提供方法二的解
代码解析
这里需要注意的是
for (auto it : map)上面这一行代码 如果我们没有写 那么他就是值遍历 导致我们下面的修改没有事实上修改map数组内的数据
int main() {vectorint arr {3 ,2 ,2 , 3, 1};// 这里建立N个数组 每个数组和arr一样长 代表从0开始到当前位置有多少个当前数unordered_mapint, vectorint map;for (auto x : arr){if (map.count(x) 0){map[x] vectorint(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(vectorint nums) {if (nums.size() 1) {return nums[0];}// 首先创建一个dp数组vectorint 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:vectorint getMaxMatrix(vectorvectorint 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) {vectorint 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(vectorint arr, int index, vectorint memo) 该函数能否返回在index位置的时候子序列的最大累加和
那么接下来我们就只需要列出边界和各种的可能性即可
代码详解
#includeiostream
using namespace std;
#includevectorint process(vectorint arr, int index, vectorint 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(vectorint arr) {if (arr.empty()) {return 0;}vectorint memo(arr.size(), -1); // 用于记忆化的数组return process(arr, 0, memo);
}糖果问题 贪心
题目
本题为LC原题 题目如下 题目分析
这个问题是一种贪心问题
相邻的两个孩子评分更高的孩子会获得更多的糖果
左规则当 ratings[i−1]ratings[i] 时 i 号学生的糖果数量将比 i−1 号孩子的糖果数量多右规则当 ratings[i]ratings[i1] 时 i 号学生的糖果数量将比 i1 号孩子的糖果数量多
所以说我们可以将这个数组遍历两次
从左到右遍历 遇到比前一个位置大的糖果就 否则糖果归1从右到左遍历 遇到比前一个位置大的糖果就 否则糖果归1
之后我们将这两次遍历的结果取较大值即可 因为要同时满足这两个条件
代码详解
class Solution {
public:int candy(vectorint ratings) {int M ratings.size();vectorint left(M , 0);vectorint 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[i1]) {right[i] right[i1] 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次方怎么办呢 只需要舍弃掉后面多余的数字即可
代码详解 vectorint process(int size) {if (size 1) {return { 1 };}int halfsize (size 1) / 2;vectorint half process(halfsize);// 构造出一个完成的数组// 一半是奇数 一半是偶数vectorint 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() {vectorint ans process(9);for (auto x : ans) {cout x endl;}return 0;
}
字符串交错组成 动态规划 – 样本对应模型
题目
此题为LC原题目 题目如下 题目分析
遇到这种多个字符串问题 我们第一时间想到的就是要用动态规划的样本对应模型去解决
首先设置一个process函数
bool process(string s , string s1 , strings2 , int index1 , int index2)这个函数的含义是 从s1的第index1个位置 s2的第index2个位置开始 能否组成字符串s
之后我们只需要考虑三种情况
终止条件越界情况有几种可能性
代码详解
class Solution {
public:// 带有记忆化搜索的递归函数bool process(string s1, string s2, string s3, int index1, int index2, vectorvectorint 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表示尚未计算vectorvectorint dp(s1.size() 1, vectorint(s2.size() 1, -1));// 从 index1 0, index2 0 开始return process(s1, s2, s3, 0, 0, dp);}
};大楼轮廓线问题
