对欸只要记start就好
只有我还在笨笨的连end一起寄了
寄了。
class Solution {
public:
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries)
int n = nums.size();
vector<bool> res;
vector < pair<int, int>* > dp( n , nullptr);
nums[0] %= 2;
pair<int, int>* t = new pair<int, int>;
bool flipflag = false;
for(int i = 1; i < n; i++){
nums[i] %= 2;
if(nums[i] != nums[i-1]){
if(!flipflag){
flipflag = true;
t = new pair<int, int>;
t->first = i-1;
dp[i-1] = t;
}
t->second = i;
dp[i] = t;
}
else{
flipflag = false;
}
}
for(auto v: queries){
if(v[0] == v[1]){
res.push_back(true);
continue;
}
if(dp[v[0]] == nullptr){
res.push_back(false);
}
else{
if(dp[v[0]]->second >= v[1]){
res.push_back(true);
}
else res.push_back(false);
}
}
return res;
}
};
※ 引述《DJYOSHITAKA (franchouchouISBEST)》之铭言：
: 再随便挑一题来写
: 3152. Special Array II
: 给你一个array 还有一堆query: q[i] = [s_i, e_i]
: 每个query要回传arr[s_i:e_i+1]是不是"special array"
: special的定义是 每个相邻pair不可同时为奇数或偶数
: 简单来说就是要 奇偶相间
: init一个array 第i个element是 其往左找"连续奇偶相间数列"的开始点
: 其实就是for loop下去 遇到相邻都是奇数or相邻都是偶数的pair就更新start_i
: 如果持续奇偶相间的话就不更新start_i这样
: 最后就单纯一个if就有答案了
: def isArraySpecial(self, nums: List[int], queries: List[List[int]]) ->
: List[bool]:
: mem = [-1 for _ in range(len(nums))]
: start_i = 0
: pre = -1
: for i,k in enumerate(nums):
: if k%2 == pre:
: start_i = i
: else:
: pre = k%2
: mem[i] = start_i
: ans = [ mem[q[1]] <= mem[q[0]] for q in queries ]
: return ans