推 Meaverzt: 太卷了吧 11/17 12:37
噓 mrsonic: 你就一輩子做作業 11/17 12:39
推 sustainer123: 大師 11/17 12:49
推 jensheng09: 屌 11/17 12:49
大概兩千名
不上不下
姆咪
第一題
給一個陣列
從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]] -- ;
if(queries[i][1]+1 < n)pre[queries[i][1]+1] ++;
}
int now = 0;
for(int i = 0 ; i < n ; i ++)
{
now += pre[i];
nums[i] += now;
}
for(int i = 0 ; i < n ; i ++)
{
if(nums[i] >0)return false;
}
return true;
}
};
```
第三題
一樣是問區間能不能變成0
但是這次要用前k個
問你最小的k是多少
思路
判斷能不能變成全部0的函式小改一點
然後用二分搜來找0~queries.size()
這樣應該會是O nlogn
再回傳就可以惹
```cpp
class Solution {
public:
bool isZeroArray(vector<int> nums, vector<vector<int>>& queries , int p)
{
int qn = queries.size();
int n = nums.size();
vector<int> pre(n,0);
for(int i = 0 ; i <= p ; i ++)
{
pre[queries[i][0]] -= queries[i][2];
if(queries[i][1]+1 < n)pre[queries[i][1]+1] += queries[i][2];
}
int now = 0;
for(int i = 0 ; i < n ; i ++)
{
now += pre[i];
nums[i] += now;
}
for(int i = 0 ; i < n ; i ++)
{
if(nums[i] >0)return false;
}
return true;
}
int minZeroArray(vector<int>& nums, vector<vector<int>>& queries)
{
int qn = queries.size();
int n = nums.size();
int l = 0 ;
int r = qn-1;
int ok = 1;
for(int i = 0 ; i < n ; i ++)
{
if(nums[i] != 0)ok = 0;
}
if(ok)return 0;
if( !isZeroArray(nums , queries , qn-1) )return -1;
while(l <= r)
{
int m = (l+r)/2;
if(isZeroArray(nums , queries , m))r = m-1;
else l = m+1;
}
return l+1;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.165.82 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731818074.A.C7F.html