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 # 跑完代表嚴格遞增完成 -- ※ 發信站: 批踢踢實業坊(ptt-site.org.tw), 來自: 220.129.80.152 (臺灣) ※ 文章網址: https://ptt-site.org.tw/Marginalman/M.1731330980.A.105