[Swift]LeetCode646.最长数对链|MaximumLengthofPairChain

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

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

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

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

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

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

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

The number of given pairs will be in the range [1, 1000].

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]

注意：

给出数对的个数在 [1, 1000] 范围内。

Runtime: 236 ms

Memory Usage: 19.1 MB

 1 class Solution {
 2     func findLongestChain(_ pairs: [[Int]]) -> Int {
 3         var pairs = pairs
 4         var res:Int = 0
 5         var end:Int = Int.min
 6         pairs.sort(by:{(a:[Int],b:[Int]) -> Bool in 
 7                        return a[1] < b[1]                      
 8                       })
 9         for pair in pairs
10         {
11             if pair[0] > end
12             {
13                 res += 1
14                 end = pair[1]
15             }
16         }
17         return res
18     }
19 }

284ms

 1 class Solution {
 2     func findLongestChain(_ pairs: [[Int]]) -> Int {
 3         let sortPairs = pairs.sorted { $0[1] < $1[1] }
 4         var ans = 0, curEnd = Int.min
 5         for pair in sortPairs {
 6             if pair[0] > curEnd {
 7                 ans += 1
 8                 curEnd = pair[1]
 9             }
10         }
11         return ans
12     }
13 }

296ms

 1 class Solution {   
 2     func findLongestChain(_ pairs: [[Int]]) -> Int {
 3     guard pairs.count > 1 else{
 4         return pairs.count
 5     }
 6     let sorted = pairs.sorted(by: {$0[1] < $1[1]})
 7     var count : Int = 1
 8     var currentPair = sorted[0]
 9     for pair in sorted{
10         if pair.first! > currentPair.last!{
11             count += 1
12             currentPair = pair
13         }
14     }    
15     return count    
16     }
17 }

1260ms

 1 sample 1260 ms submission
 2 class Solution {
 3     func findLongestChain(_ pairs: [[Int]]) -> Int {
 4         let n = pairs.count
 5         if n <= 1{ return n }
 6         
 7         let sorted = pairs.sorted { $0[0] < $1[0] }
 8         var f = [Int](repeating: 1, count: n)
 9         var result = 1
10         
11         for i in 1..<n {
12             for j in 0..<i {
13                 if sorted[j][1] < sorted[i][0] {
14                     f[i] = max(f[i], f[j] + 1)
15                     result = max(result, f[i])
16                 }
17             }
18         }
19         
20         return result
21     }
22 }

1272ms

 1 class Solution {
 2     func findLongestChain(_ pairs: [[Int]]) -> Int {
 3         guard pairs.count > 1 else { return 1 }
 4         let pairs = pairs.sorted(by: {
 5             return $0[0] < $1[0]
 6         })
 7         
 8         let n = pairs.count
 9         var dp: [Int] = Array(repeating: 0, count: n)
10         dp[0] = 1
11         
12         for i in  1 ..< n {
13             for j in 0 ..< i {
14                 if pairs[i][0] > pairs[j][1] {
15                     dp[i] = max(dp[i], dp[j])
16                 }
17             }
18             dp[i] += 1
19         }
20         
21         return dp[n - 1]
22     }
23 }