大概兩千名
不上不下
姆咪
第一題
給一個陣列
從0的地方開始往左或右走
碰到1 就把那個地方-1
然後回頭走
看不能能把1走完
思路
反正看兩邊牆壁有沒有一樣多就可以知道了
如果其中一邊多一個
那就是只能先往那邊走
```cpp
class Solution {
public:
int countValidSelections(vector<int>& nums)
{
int cnt = 0;
for(int i : nums)cnt += i;
int n = nums.size();
int res = 0;
vector<int> paper(n,0);
paper[0] = nums[0];
for(int i = 1 ;i < n ; i ++)
{
paper[i] = nums[i] + paper[i-1];
// cout << paper[i] << " ";
}
for(int i = 0 ; i < n ; i ++)
{
if(nums[i] == 0)
{
int k = paper[i]*2;
if( paper[i]*2 == paper[n-1])
{
res += 2;
}
else if( abs(paper[i]*2 - paper[n-1]) <= 1 )
{
res++;
}
}
}
return res;
}
};
```
第二題
給個陣列nums 跟一些queries
queries[i]裡面代表可以操作的區間
在那些區間裡面 可以把nums-1
看能不能把nums全部都變成0
思路
用前綴和紀錄區間的值
然後檢查
這是O n
```cpp
class Solution {
public:
bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries)
{
int qn = queries.size();
int n = nums.size();
vector<int> pre(n,0);
for(int i = 0 ; i < qn ; i ++)
{
pre[queries[i][0]]