Re: [閒聊] 每日LeetCode已回收
491. Non-decreasing Subsequences
給你一個 array nums，要你回傳他的所有非嚴格遞增的 subsequences，順序任意
subsequence 長度至少要是 2
Example 1:
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Example 2:
Input: nums = [4,4,3,2,1]
Output: [[4,4]]
思路:
1.類似 DFS，每個 num[i] 都遞迴往後找挑與不挑的結果
目前的 subsequence 就放在參數裡往下傳就好
因為這題不要輸出長相一樣的 subsequence 所以不用 list 用 tuple 直接塞進 set 裡
遇到出現過的 subsequence 也可以不用往下找(感覺有點疑慮不過應該是對的)
Python code:
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = set()
def dfs(idx, arr):
if len(arr) >= 2:
res.add(arr)
for i in range(idx+1, n):
tup = arr+(nums[i],)
if (idx == -1 or nums[i] >= nums[idx]) and tup not in res:
dfs(i, tup)
dfs(-1, ())
return res
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.202.128 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674227199.A.2EF.html
推
01/20 23:06,
2年前
, 1F
01/20 23:06, 1F
→
01/21 01:29,
2年前
, 2F
01/21 01:29, 2F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 199 之 719 篇)：