• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode491.递增子序列|IncreasingSubsequences

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10348625.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] 

Note:

  1. The length of the given array will not exceed 15.
  2. The range of integer in the given array is [-100,100].
  3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

  1. 给定数组的长度不会超过15。
  2. 数组中的整数范围是 [-100,100]。
  3. 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。

Runtime: 472 ms
Memory Usage: 17.3 MB
 1 class Solution {
 2     func findSubsequences(_ nums: [Int]) -> [[Int]] {
 3         var res:Set<[Int]> = Set<[Int]>()
 4         var cur:[[Int]] = [[]]
 5         for i in 0..<nums.count
 6         {
 7             var n:Int = cur.count
 8             for j in 0..<n
 9             {
10                 if !cur[j].isEmpty && cur[j].last! > nums[i]
11                 {
12                     continue
13                 }
14                 cur.append(cur[j])
15                 cur[cur.count - 1].append(nums[i])
16                 if cur[cur.count - 1].count >= 2
17                 {
18                     res.insert(cur.last!)
19                 }
20             }
21         }
22         return [[Int]](res)
23     }
24 }

15810 kb

 1 class Solution {
 2     func findSubsequences(_ nums: [Int]) -> [[Int]] {
 3         guard nums.count > 0 else { return [[Int]]() }
 4         
 5         var visit = [Bool](repeating: false, count: nums.count)
 6         var res = [[Int]]()
 7         
 8         dfs(nums, 0, &res, &visit, getPrev(nums), [Int]())
 9         
10         return res
11     }
12     
13     private func dfs(_ nums: [Int], _ index: Int, _ res: inout [[Int]], _ visit: inout [Bool], _ prev: [Int], _ list: [Int]) {
14         if list.count > 1 {
15             res.append(list)
16         }
17         
18         var list = list
19         
20         for i in index..<nums.count {
21             if index >= 1, nums[i] < nums[index-1] {
22                 continue
23             }
24             
25             if prev[i] != -1, visit[prev[i]] == false, (list.count == 0 || prev[i] > index-1) {
26                 continue
27             } 
28             
29             list.append(nums[i])
30             visit[i] = true
31             dfs(nums, i+1, &res, &visit, prev, list)
32             visit[i] = false
33             list.removeLast()
34         }
35     }
36     
37     private func getPrev(_ nums: [Int]) -> [Int] {
38         var map = [Int: Int]()
39         var prev = [Int](repeating: -1, count: nums.count)
40         
41         for i in 0..<nums.count {
42             if let value = map[nums[i]] {
43                 prev[i] = value
44             } 
45             map[nums[i]] = i
46         }
47         
48         return prev
49     }
50 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift 集合发布时间:2022-07-13
下一篇:
swift的可选值(optional)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap