网站logo图标,海原电商网站建设,php不用框架怎么做网站,冯站长之家题目详解
需求#xff1a;判断给定区间内的元素是否满足“特殊数组”要求
尝试: 暴力求解?
如果试着直接对每个queries中的区间进行检测而不做其他处理#xff0c;那么最后不出意外地超时了。。 细想优化策略#xff0c;不难察觉到其中可能存在大量的重复运算
那还等什…
题目详解
需求判断给定区间内的元素是否满足“特殊数组”要求
尝试: 暴力求解?
如果试着直接对每个queries中的区间进行检测而不做其他处理那么最后不出意外地超时了。。 细想优化策略不难察觉到其中可能存在大量的重复运算
那还等什么doge记忆化 记忆化
设置rem数组rem[ i ] k 意味着nums从 i 到 k 的元素均满足“特殊数组”要求
int *rem (int *)calloc(sizeof(int), sz1);
//更新rem示例
for(int mst; med; 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:vectorbool isArraySpecial(vectorint nums, vectorvectorint queries) {int sz nums.size();int *rem (int *)calloc(sizeof(int), sz1);vectorboolret;//返回数组//遍历 queriesfor(int i0; iqueries.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 jst1;for(; jed; 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 kst1; ked; 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 mst; mk; m)rem[m] rem[ed];break;}}}else{int kst1;for(; ked; 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 mst; med; m)rem[m] ed;}}}return ret;}
};
~希望对你有启发~
