Re: [閒聊] 每日leetcode
題目
找一段最短的陣列裡面 | 全部的值至少k
思路
其實想蠻久的
最後是紀錄裡面的每個位子的bit數量
然後sliding window
找到每個至少k值的長度
```cpp
class Solution {
public:
vector<int> nums;
int n ;
int k ;
int val(vector<long long>& now)
{
int res = 0;
for(int i = 0 ; i < 32 ; i ++)
{
if(now[i])res += pow(2,i);
}
return res;
}
int minimumSubarrayLength(vector<int>& nums2, int k2)
{
nums = nums2;
k = k2;
n = nums.size();
int res = INT_MAX;
vector<long long> paper(32,0);
int i = 0;
int l = 0;
for(i = 0 ; i < n ; i ++ )
{
for(int t = 0 ; t < 31 ; t ++)
{
if(nums[i] & (int)pow(2,t))paper[t] ++;
}
vector<long long> paper2 = paper;
for(int t = 0 ; t < 31 ; t ++)
{
if(nums[l] & (int)pow(2,t))paper2[t] --;
}
while(val(paper2) >= k && l<i)
{
l++;
paper = paper2;
for(int t = 0 ; t < 31 ; t ++)
{
if(nums[l] & (int)pow(2,t))paper2[t] --;
}
}
if(val(paper) >= k)res = min ( res , i-l+1);
}
if(res == INT_MAX)return -1;
return res;
}
};
```
--
邊版的小母雞 — fuckchicken
https://i.imgur.com/wglAuYR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.167.248 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731218853.A.5CD.html
推
11/10 14:10,
1年前
, 1F
11/10 14:10, 1F
推
11/10 14:12,
1年前
, 2F
11/10 14:12, 2F
→
11/10 14:12,
1年前
, 3F
11/10 14:12, 3F
→
11/10 14:12,
1年前
, 4F
11/10 14:12, 4F
推
11/10 14:17,
1年前
, 5F
11/10 14:17, 5F
推
11/10 14:18,
1年前
, 6F
11/10 14:18, 6F
→
11/10 14:21,
1年前
, 7F
11/10 14:21, 7F
→
11/10 14:22,
1年前
, 8F
11/10 14:22, 8F
討論串 (同標題文章)
完整討論串 (本文為第 1108 之 1548 篇)：