2601. Prime Subtraction Operation ## 思路 假如新遞增陣列的前一個值是prev, 下一個值 num-prime 要大於 prev => 先建質數表, 掃陣列用Binary Search找最大可能的prime 並更新prev ## Code ```python class Solution: def primeSubOperation(self, nums: List[int]) -> bool: is_prime = [True] * 1001 is_prime[0] = is_prime[1] = False for i in range(2, int(sqrt(1001)) + 1): if not is_prime[i]: continue for j in range(2*i, 1001, i): is_prime[j] = False primes = [i for i in range(2, 1001) if is_prime[i]] prev = 0 for num in nums: if num <= prev: return False idx = bisect_left(primes, num - prev) - 1 prev = num - primes[idx] if idx != -1 else num return True ``` -- ※ 發信站: 批踢踢實業坊(ptt-site.org.tw), 來自: 185.213.82.158 (臺灣) ※ 文章網址: https://ptt-site.org.tw/Marginalman/M.1731330217.A.7D4

→ DJYOMIYAHINA: 大師 11/11 21:04