https://leetcode.com/problems/prime-subtraction-operation
2601. Prime Subtraction Operation
给一个长度为 n 的 0 索引整数数组 nums
可以做任意次数以下的操作
选一个没选过的索引 i 选择严格小于 nums[i] 的质数 p 然后 nums[i] - p
回传 true 当做完上面的操作后能使 nums 是严格递增的数组 否则回传 false
严格递增数组 指每个元素都严格大于前一个元素的数组
Example 1:
Input: nums = [4,9,6,10]
Output: true
Explanation:
i = 0, p = 3 => [1,9,6,10]
i = 1, p = 7 => [1,2,6,10]
Example 2:
Input: nums = [6,8,11,12]
Output: true
Explanation: 已严格递增
Example 3:
Input: nums = [5,8,3]
Output: false
Explanation: 无解
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 1000
nums.length == n
思路：
就是每个位置只能减一次 又要严格递增 所以从最后一个开始处理
先做出 1000 以内的所有质数 判断质数从小到大哪个能使两数变递增
如果无法变成递增就直接回传 False
Python Code:
class Solution:
def primeSubOperation(self, nums: List[int]) -> bool:
primes = (2, 3, 5, 7, ..., 971, 977, 983, 991, 997) # 太多就不列出了
n = len(nums) - 1
while n:
num = nums[n-1]
if num < nums[n]: # 已严格递增
n -= 1
continue
for p in primes:
if num <= p:
return False # 因为要求 p < num 找不到代表无法达成
if num - p < nums[n]:
nums[n-1] = num - p
n -= 1
break
else:
return False # 在没有 break 的情况下 一样代表无法递增
return True # 跑完代表严格递增完成