Re: [闲聊] 每日leetcode

楼主: oin1104 (是oin的说)   2024-11-12 00:01:29
※ 引述 《JIWP (神楽めあ的钱包)》 之铭言:
:  
: 2601. Prime Subtraction Operation
:  
: 有一个长度为n的矩阵:nums
:  
: 你可以执行多次以下的操作
:  
: 选择nums里的一个元素nums[i],并将nums[i]减去一个比他小的质数
:  
: 请问你执行若干次上述的操作后
:  
: nums是否可以变成一个严格递增的矩阵?
:  
: 思路:
:  
: 这题最难的就是找到有哪些质数
:  
: 因为题目限制,所以找1000以下的质数就好
:  
思路:
一样
每次都把最大可以减掉的质数减掉就好了
姆咪
@rainkaras
@DJ宝
@sustainer
刷题时间到了
```cpp
class Solution {
public:
vector<int> ppp;
bool isp(int p)
{
for(int i = 2 ; i <= sqrt(p) ; i ++)
{
if(p%i == 0)return 0;
}
return 1;
}
void primefind()
{
for(int i = 2 ; i < 1000 ; i ++)
{
if(isp(i))ppp.push_back(i);
}
}
int findap(int num )
{
int l = 0 ;
int r = ppp.size()-1;
while(l<=r)
{
int m = (l+r)/2;
if(ppp[m] < num)
{
l = m+1;
}
else
{
r = m-1;
}
}
return ppp[r];
}
bool primeSubOperation(vector<int>& nums)
{
primefind();
int n = nums.size();
for(int i = 0 ; i < nums.size() ; i ++)
{
// cout << findap(nums[i]) << " ";
int take = nums[i];
if(i != 0)
{
take -= nums[i-1];
}
if(take <= 2 )continue;
nums[i] -= findap(take);
}
// cout << endl;
// for(int i = 0 ; i < nums.size() ; i ++)cout << nums[i] << " ";
for(int i = 1 ; i < nums.size() ; i ++)
{
if(nums[i] <= nums[i-1])return 0;
}
return 1;
}
};
```
作者: mrsonic (typeB)   2024-11-12 00:16:00
几点了还在刷

Links booklink

Contact Us: admin [ a t ] ucptt.com