Leetcode 連結
解法一
首先我們需要找出小於 1000 的所有質數，我們可以使用 Sieve of Eratosthenes 來快速找出這些質數。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<int> Sieve(){
vector<bool> p(1001, true);
p[0] = p[1] = false;
for (int i = 2; i * i <= 1000; i++){
if (p[i]){
for (int j = i * i; j <= 1000; j += i){
p[j] = false;
}
}
}
vector<int> primes;
for (int i = 0; i <= 1000; i++){
if (p[i]){
primes.push_back(i);
}
}
return primes; // primes 是小於1000的所有質數所成的陣列
}
|
接下來我們想要讓 nums 變成嚴格遞增的陣列。
若是我們從前面處理到後面，想要讓陣列變成嚴格遞增的，在處理 nums[i] 時，nums[i] 能變得越小越好，同時不能小於等於 nums[i - 1]。
也就是說我們想要找到最大的質數使得 nums[i] - prime > nums[i - 1]，移項後發現這個質數要滿足 prime < nums[i] - nums[i - 1]，我們可以使用 binary search 快速找到這樣的質數。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool primeSubOperation(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++){
// 利用 binary search 找到第一個大於等於 nums[i] - nums[i - 1] 的質數
// 他的前一個就會是小於 nums[i] - nums[i - 1] 的質數
auto it = lower_bound(primes.begin(), primes.end(), i == 0? nums[i]: nums[i] - nums[i - 1]);
if (it != primes.begin()){
nums[i] -= *prev(it);
}
// 做完操作後若是發現不滿足 nums[i - 1] < nums[i]，回傳 false
if (i > 0 && nums[i] <= nums[i - 1]){
return false;
}
}
return true;
}
|
解法二
若是我們從後面處理到前面，那就要反過來處理。在處理 nums[i] 時，nums[i] 在扣除質數後能越大越好，同時不能大於等於 nums[i + 1]。
也就是說我們想要找到最小的質數使得 nums[i] - prime < nums[i + 1]，移項後發現這個質數要滿足 prime > nums[i] - nums[i + 1]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool primeSubOperation(vector<int>& nums) {
int n = nums.size();
// 注意現在是後面處理到前面
for (int i = n - 2; i >= 0; i--){
// nums[i] < nums[i + 1]，什麼都不用做
if (nums[i] < nums[i + 1]){
continue;
}
// 利用 binary search 找到第一個大於 nums[i] - nums[i + 1] 的質數
auto it = upper_bound(primes.begin(), primes.end(), nums[i] - nums[i + 1]);
// 找到的prime要小於原本的數
if (it != primes.end() && *it < nums[i]){
nums[i] -= *it;
}
// 做完操作後若是發現不滿足 nums[i] < nums[i + 1]，回傳 false
if (nums[i] >= nums[i + 1]){
return false;
}
}
return true;
}
|
這題有很多特殊的情況要考慮： it 會不會是 prime.begin() 或是 prime.end()，找到的質數會不會大於原本的數。
當初在打週賽的時候處理很久，最後直接遍歷所有的質數（不使用 binary search）發現也會過，不過還是把好的解法寫一遍，多練習一下。