[Swift]LeetCode673.最长递增子序列的个数|NumberofLongestIncreasingSubsequence ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

108ms

 1 class Solution {
 2     func findNumberOfLIS(_ nums: [Int]) -> Int {
 3         if nums.count <= 1 {
 4             return nums.count
 5         }
 6         
 7         var lengths = [Int](repeating: 0, count: nums.count)
 8         var rank = [Int : Int]()
 9         let uniArr = Array(Set(nums)).sorted()
10         for (k, v) in uniArr.enumerated() {
11             rank[v] = k
12         }
13                
14         let n = uniArr.count
15         var binaryIndexed = [Int](repeating: 0, count: n+1)
16         
17         func update(_ index: Int, _ val: Int) -> Void {
18             var x = index
19             while x <= n {           
20                 binaryIndexed[x] = max(binaryIndexed[x], val)
21                 x += x&(-x)
22             }
23         }
24         
25         func query(fromOneTo index: Int) -> Int {
26             var rval = 0
27             var x = index
28             while x > 0 {
29                 rval = max(binaryIndexed[x], rval)
30                 x &= x-1
31             }
32             return rval
33         }
34         
35         var longestLen = 0
36         for i in 0..<nums.count {
37             let bIndex = rank[nums[i]]! + 1
38             lengths[i] = query(fromOneTo: bIndex-1) + 1
39             longestLen = max(longestLen, lengths[i])
40             update(bIndex, lengths[i])
41         }
42         
43         if longestLen == nums.count {
44             return 1
45         } else if longestLen == 1 {
46             return nums.count
47         }        
48         
49         var dp = [Int](repeating: 0, count: nums.count)
50         // table stores the indexes of nums, sort by lengths and then nums
51         var table = Array(0..<nums.count)
52         table.sort{
53             lengths[$0] == lengths[$1] ? nums[$0] < nums[$1] : lengths[$0] < lengths[$1]
54         }        
55         var lengthIndexDict = [Int:Int]()
56 
57         for (i, v) in table.enumerated() where i == 0 || lengths[v] != lengths[table[i-1]] {
58             lengthIndexDict[lengths[v]] = i
59         }        
60 
61         for i in 0..<nums.count {
62             if lengths[i] == i+1 || lengths[i] == 1 {
63                 dp[i] = 1
64             } else {
65                 let len = lengths[i]-1
66                 let tableIndex = lengthIndexDict[len]!
67                 for j in tableIndex..<table.count {
68                     let index = table[j]
69                     if nums[index] >= nums[i] || lengths[index] != len {
70                         break
71                     }
72                     if index < i {
73                         dp[i] += dp[index]
74                     } 
75                 }
76             }
77         }
78                 
79         var ans = 0
80         for i in 0..<dp.count where lengths[i] == longestLen {
81             ans += dp[i]
82         }
83         
84         return ans
85     }
86 }

Runtime: 140 ms

Memory Usage: 18.9 MB

 1 class Solution {
 2     func findNumberOfLIS(_ nums: [Int]) -> Int {
 3         var res:Int = 0
 4         var mx:Int = 0
 5         var n:Int = nums.count
 6         var len:[Int] = [Int](repeating:1,count:n)
 7         var cnt:[Int] = [Int](repeating:1,count:n)
 8         for i in 0..<n
 9         {
10             for j in 0..<i
11             {
12                 if nums[i] <= nums[j] {continue}
13                 if len[i] == len[j] + 1 {cnt[i] += cnt[j]}
14                 else if len[i] < len[j] + 1
15                 {
16                     len[i] = len[j] + 1
17                     cnt[i] = cnt[j]
18                 }
19             }
20             mx = max(mx, len[i])
21         }
22         for i in 0..<n
23         {
24             if mx == len[i]
25             {
26                 res += cnt[i]
27             }
28         }
29         return res    
30     }
31 }

140ms

 1 class Solution {
 2     func findNumberOfLIS(_ nums: [Int]) -> Int {
 3         return lengthOfLISDP(nums)
 4     }
 5     
 6     func lengthOfLISDP(_ nums: [Int]) -> Int {
 7         var matrix = Array(repeating: 0, count: nums.count)
 8         var matrixCount = Array(repeating: 1, count: nums.count)
 9         var maxResult = 0
10         var maxResultCount = 0
11         
12         for i in 0..<nums.count {
13             var maxInside = 0
14             var maxInsideCount = 1
15             for j in 0..<i {
16                 if nums[i] > nums[j] {
17                     if matrix[j] > maxInside {
18                         maxInside = matrix[j]
19                         maxInsideCount = matrixCount[j]
20                     } else if matrix[j] == maxInside {
21                         maxInsideCount += matrixCount[j]
22                     }
23                 }
24             }
25             
26             matrix[i] = 1 + maxInside
27             matrixCount[i] = maxInsideCount
28             
29             if matrix[i] > maxResult {
30                 maxResult = matrix[i]
31                 maxResultCount = maxInsideCount
32             } else if matrix[i] == maxResult {
33                 maxResultCount += maxInsideCount
34             } 
35         }
36         
37         return maxResultCount
38     }
39 }

144ms

 1 class Solution {
 2     func findNumberOfLIS(_ nums: [Int]) -> Int {
 3         guard nums.count > 1 else {
 4             return nums.count 
 5         }
 6         
 7         var LISDP = [Int](repeating: 1, count: nums.count)
 8         var count = [Int](repeating: 0, count: nums.count)
 9         count[0] = 1
10         var LIS: Int = 1
11         for i in 1..<nums.count {
12             let currentNum = nums[i]
13             for j in 0..<i {
14                 let movingNum = nums[j]
15                 if currentNum > movingNum {
16                     if LISDP[i] < LISDP[j] + 1 {
17                         LISDP[i] = LISDP[j] + 1
18                         count[i] = count[j]
19                     } else if LISDP[i] == LISDP[j] + 1 {
20                         count[i] += count[j]
21                     }
22                     
23                 }
24             }
25             if count[i] == 0 { count[i] = 1 }
26             LIS = max(LIS, LISDP[i])
27         }
28         print(count)
29         var result: Int = 0 
30         for (index, increasingSequence) in LISDP.enumerated() {
31             if increasingSequence == LIS {
32                 result += count[index] 
33             }
34         }
35         return result
36     }
37 }

148ms

 1 class Solution {
 2     func findNumberOfLIS(_ nums: [Int]) -> Int {
 3         if nums.count == 0 {
 4             return 0
 5         }
 6         // 长度
 7         var dp = Array(repeating: 1, count: nums.count)
 8         // count
 9         var count = Array(repeating: 1, count: nums.count)
10         dp[0] = 1
11         dp[0] = 1
12         for (index, num) in nums.enumerated() where index != 0 {
13             for i in 0...index-1 {
14                 if nums[i] < num {
15                     if dp[i] + 1 > dp[index] {
16                         dp[index] = dp[i] + 1
17                         count[index] = count[i]
18                     } else if dp[i] + 1 == dp[index]{
19                         count[index] += count[i]
20                     }
21                 }
22             }
23         }
24         var sum = 0
25         let _max = dp.max()!
26         for (index, count) in count.enumerated() {
27             if dp[index] == _max {
28                 sum += count
29             }
30         }
31         return sum
32     }
33 }

172ms

 1 class Solution {    
 2     func findNumberOfLIS(_ nums: [Int]) -> Int {
 3         let n = nums.count
 4         
 5         var length = [Int](repeating:1, count:n)
 6         var count = [Int](repeating:1, count: n)
 7         
 8         for i in 0..<n {
 9             for j in 0..<i {
10                 if nums[i] > nums[j] {
11                     if length[i] == length[j] + 1 {
12                         count[i] += count[j]
13                     }
14                     if length[i] < length[j] + 1 {
15                         length[i] = length[j] + 1
16                         count[i] = count[j]
17                     }
18                 }
19             }
20         }
21         
22         var result = 0
23         var maxLength = 0
24         
25         length.forEach({ maxLength = max(maxLength, $0) })
26         
27         for i in 0..<n { 
28             result += length[i] == maxLength ? count[i] : 0
29         }
30         
31         return result
32     }
33 }

184ms

 1 class Solution {
 2     
 3     func findNumberOfLIS(_ nums: [Int]) -> Int {
 4         let n = nums.count
 5         
 6         var result = 0
 7         var maxLength = 0
 8         
 9         var length = [Int](repeating:0, count:n)
10         var count = [Int](repeating:0, count: n)
11         
12         for i in 0..<n {
13             length[i] = 1
14             count[i] = 1
15             for j in 0..<i {
16                 if nums[i] > nums[j] {
17                     if length[i] == length[j] + 1 {
18                         count[i] += count[j]
19                     }
20                     if length[i] < length[j] + 1 {
21                         length[i] = length[j] + 1
22                         count[i] = count[j]
23                     }
24                 }
25             }
26             if maxLength == length[i] {
27                 result += count[i]
28             }
29             if maxLength < length[i] {
30                 maxLength = length[i]
31                 result = count[i]
32             }
33         }
34         return result
35     }
36 }