网页框架代码青岛关键词优化seo
题目详解
需求：判断给定区间内的元素是否满足“特殊数组”要求
尝试: 暴力求解?
如果试着直接对每个queries中的区间进行检测而不做其他处理，那么最后不出意外地超时了。。
细想优化策略，不难察觉到其中可能存在大量的重复运算
那还等什么（doge）？记忆化！
记忆化
设置rem数组，rem[ i ] = k 意味着nums从 i 到 k 的元素均满足“特殊数组”要求
int *rem = (int *)calloc(sizeof(int), sz+1);
//更新rem示例：
for(int m=st; m<=ed; m++) rem[m] = ed;一个错误想法：
不妨思考，下面利用 rem 的记录判断符合“特殊数组”的考虑，完善吗？
int st = queries[i][0];//起始位置
int ed = queries[i][1];//终止位置
if(rem[st] != 0 && rem[ed] != 0) return true；答案是否定的，比如下面这种情况，就会漏掉中间绿色部分的检验。
那怎么办嘞？
其实不难，只要再加上rem值相等的条件就好啦~
if(rem[st] != 0 && rem[ed] != 0 && rem[st] == rem[ed]) return true；记忆化，越多越好吗?
按理说，后面的思路应该就很清楚了，只要根据 rem[st] 和 rem[ed] 取值的不同情况，分别检验 & 记忆化处理即可。
但写完提交，虽然AC了，但是，本以为记忆化能大大提升时间效率的我，却碰上远低于平均值的结果。
其实，边写的时候，笔者也隐约感觉有些重复，毕竟更新rem的过程本身就是耗费时力的
于是，笔者试着注释掉一些记忆化操作，保留了两处较为主要的部分，果然，去掉了部分记忆化，反倒轻松多了~
// 虽然跟大佬们比起来还是差很多（小声），后面笔者会去学习一下优秀代码，再写篇解读文章~
AC代码见下
// 由于分类讨论较多，显得有点冗长（小声）
class Solution {
public:vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {int sz = nums.size();int *rem = (int *)calloc(sizeof(int), sz+1);vector<bool>ret;//返回数组//遍历 queriesfor(int i=0; i<queries.size(); i++){int st = queries[i][0];int ed = queries[i][1];if(rem[st] != 0 && rem[ed] != 0 && rem[st] == rem[ed]) ret.push_back(true);else if(rem[st] != 0){st = rem[st];int j=st+1;for(; j<=ed; j++){if(nums[j]%2 == nums[j-1]%2) {ret.push_back(false);break;}}if(j > ed) ret.push_back(true);}else if(rem[ed] != 0){for(int k=st+1; k<=ed; k++){if(nums[k]%2 == nums[k-1]%2) {ret.push_back(false); break;}if(rem[k] == rem[ed]){ret.push_back(true);//记忆化for(int m=st; m<=k; m++)rem[m] = rem[ed];break;}}}else{int k=st+1;for(; k<=ed; k++){if(nums[k]%2 == nums[k-1]%2){ret.push_back(false); break;}if(rem[k] != 0) k = rem[k];}if(k > ed){ret.push_back(true); //记忆化for(int m=st; m<=ed; m++)rem[m] = ed;}}}return ret;}
};