【leetcode图文详解】特殊数组II : 空间换时间的“记忆化”，越多越好吗？

题目详解

需求：判断给定区间内的元素是否满足“特殊数组”要求

尝试: 暴力求解?

如果试着直接对每个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;}
};

~希望对你有启发~