Posted on 2023-01-20 22:37
Uriel 閱讀(50)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給出一個數列，輸出所有不重復的單調不減子序列
DFS，用python的tuple存儲中間結果（因為tuple類型支持哈希）
1 #491
2 #Runtime: 209 ms (Beats 62.86%)
3 #Memory: 22.1 MB (Beats 44.29%)
4
5 class Solution(object):
6 def findSubsequences(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[List[int]]
10 """
11 self.ans = set()
12 def DFS(i, t):
13 if len(t) > 1:
14 self.ans.add(tuple(t))
15 if i == len(nums):
16 return
17 if not t or nums[i] >= t[-1]:
18 DFS(i + 1, t + [nums[i]])
19 DFS(i + 1, t)
20
21 DFS(0, [])
22 return self.ans