Re: [閒聊] 每日leetcode
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.cc), 來自: 185.213.82.158 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731330217.A.7D4.html
→
11/11 21:04,
1年前
, 1F
11/11 21:04, 1F
→
11/11 21:07,
1年前
, 2F
11/11 21:07, 2F
推
11/11 21:09,
1年前
, 3F
11/11 21:09, 3F
→
11/11 21:17,
1年前
, 4F
11/11 21:17, 4F
→
11/11 22:01,
1年前
, 5F
11/11 22:01, 5F
討論串 (同標題文章)
完整討論串 (本文為第 1109 之 1548 篇)：