Posted on 2023-01-20 22:37
Uriel 阅读(38)
评论(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