微信朋友圈推广怎么做网站,学校资源网站建设目标,做冷库的网站,北京大学廉政建设研究中心网站前缀和的优势 给定一个数组#xff0c;前缀和的特点在于#xff0c;任意给出一对始末位置#xff0c;能够用O(1)的时间复杂度得到始末位置之间所有元素的某种关系。
题型分析 这道题目正是“给出始末位置#xff0c;检测其中元素特点”那一类#xff0c;那我们就想#…
前缀和的优势 给定一个数组前缀和的特点在于任意给出一对始末位置能够用O(1)的时间复杂度得到始末位置之间所有元素的某种关系。
题型分析 这道题目正是“给出始末位置检测其中元素特点”那一类那我们就想如果能够将这种 “元素关系” 与 “奇偶性交替的检验” 挂钩便可大大提高检测效率。
可以说本解法可推广解决几乎所有 判断给定区间元素是否恒满足某种关系 那一类需求。 核心部分解释关于预处理
关于判断语句 (nums[i]%2 ! nums[i-1]%2) 为什么可以用 int 型接收 由此就不难理解后面的判断
若 prefix[ A ] prefix[ B ]则说明位置A B间所有元素使 (nums[i]%2 nums[i-1]%2) 0也就是均满足 (nums[i]%2 ! nums[i-1]%2) true
class Solution {
public:vectorbool isArraySpecial(vectorint nums, vectorvectorint queries) {vectorintprefix(nums.size());//辅助数组,记录前缀和for(int i1; inums.size(); i){prefix[i] prefix[i-1] (nums[i]%2 nums[i-1]%2);}vectorboolret;for(auto p: queries){ret.push_back(prefix[p[0]] prefix[p[1]]); }return ret;}
};思路来源
本解法借鉴解题达人 灵茶山艾府膜拜大佬 ~希望对你有启发~
