對欸只要記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