题目详解

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

尝试: 暴力求解?

如果试着直接对每个queries中的区间进行检测而不做其他处理，那么最后不出意外地超时了。。

细想优化策略，不难察觉到其中可能存在大量的重复运算

那还等什么（doge）？记忆化！

记忆化

设置rem数组，rem[ i ] = k 意味着nums从 i 到 k 的元素均满足“特殊数组”要求

<code>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值相等的条件就好啦~

<code>if(rem[st] != 0 && rem[ed] != 0 && rem[st] == rem[ed]) return true；

记忆化，越多越好吗?

        按理说，后面的思路应该就很清楚了，只要根据 rem[st] 和 rem[ed] 取值的不同情况，分别检验 & 记忆化处理即可。

        但写完提交，虽然AC了，但是，本以为记忆化能大大提升时间效率的我，却碰上远低于平均值的结果。

 其实，边写的时候，笔者也隐约感觉有些重复，毕竟更新rem的过程本身就是耗费时力的

        于是，笔者试着注释掉一些记忆化操作，保留了两处较为主要的部分，果然，去掉了部分记忆化，反倒轻松多了~

  // 虽然跟大佬们比起来还是差很多（小声），后面笔者会去学习一下优秀代码，再写篇解读文章~

AC代码见下

// 由于分类讨论较多，显得有点冗长（小声）

<code>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;//返回数组

//遍历 queries

for(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;

}

};

~希望对你有启发~