[Swift]LeetCode594.最长和谐子序列|LongestHarmoniousSubsequence

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

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

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

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

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

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

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].

说明: 输入的数组长度最大不超过20,000.

156ms

 1 class Solution {
 2     func findLHS(_ nums: [Int]) -> Int {
 3         if nums.count == 0{
 4             return 0 
 5         }
 6         var result = 0
 7         var map:[Int:Int] = [:]
 8         for num in nums{
 9             if let val = map[num]{
10                 map[num] = val + 1
11             }else{
12                 map[num] = 1
13             }
14         }
15         for (index,num) in map {
16             if let value = map[index + 1] {
17                 result = max(result, map[index]! + map[index + 1]!);
18             }
19         }
20         return result
21     }
22 }

232ms

 1 class Solution {
 2     func findLHS(_ nums: [Int]) -> Int {
 3         var map: [Int: Int] = [:]
 4         nums.forEach { (num) in
 5             if let count = map[num] {
 6                 map[num] = count + 1
 7             } else {
 8                 map[num] = 1
 9             }
10         }
11 
12         var result = 0
13         map.forEach { (key, value) in
14             result = max(result, value + (map[key - 1] ?? -value))
15             result = max(result, value + (map[key + 1] ?? -value))
16         }
17 
18         return result
19     }
20 }

256ms

 1 class Solution {
 2     func findLHS(_ nums: [Int]) -> Int {
 3     var map = [Int: Int]()
 4     
 5     for num in nums {
 6         if let value = map[num] {
 7             map[num] = value + 1
 8         } else {
 9             map[num] = 1
10         }
11     }
12     
13     let sortedKeys = map.keys.sorted()
14     var i = 1
15     var long = 0
16     
17     while i < sortedKeys.count {
18         let key1 = sortedKeys[i - 1]
19         let key2 = sortedKeys[i]
20         if abs(key1 - key2) == 1 {
21             let len = map[key1]! + map[key2]!
22             if len > long {
23                 long = len
24             }
25         }
26         
27         i += 1
28     }
29     
30     return long
31 }
32 }

552ms

 1 class Solution {
 2     func findLHS(_ nums: [Int]) -> Int {
 3     var dic = [Int: Int]() //num: count
 4     
 5     nums.forEach {
 6         dic[$0, default: 0] += 1
 7     }
 8     
 9     var result = 0
10     
11     for k in dic.keys {
12                 
13         if let l = dic[k], let r = dic[k + 1] {
14             result = max(result, (l + r))
15         }
16         
17     }
18     
19     return result
20     }
21 }

576ms

 1 class Solution {
 2     func findLHS(_ nums: [Int]) -> Int {
 3         //将数组中的值存入字典
 4         var map:[Int:Int] = [Int:Int]()
 5         for i in nums
 6         {
 7             if map[i] == nil
 8             {
 9                 map[i] = 1
10             }
11             else
12             {
13                 map[i]! += 1
14             }
15             
16         }
17         
18         //最长和谐子序列
19         var maxLen:Int = 0
20         for i in map.keys
21         {
22             var value1:Int = map[i]!
23             var value2:Int = Int()
24             if map[i+1] != nil
25             {
26                 value2 = map[i + 1]!
27                 if (value1 + value2) > maxLen
28                 {
29                     maxLen = value1 + value2
30                 }
31             }
32         }
33         return maxLen
34     }
35 }

696ms

 1 class Solution {
 2     func findLHS(_ nums: [Int]) -> Int {
 3     var dic = [Int: Int]() //num: count
 4     
 5     nums.forEach {
 6         dic[$0, default: 0] += 1
 7     }
 8     
 9     var result = 0
10     
11     for k in dic.keys.sorted() {
12                 
13         if let l = dic[k], let r = dic[k + 1] {
14             result = max(result, (l + r))
15         }
16         
17     }
18     
19     return result
20     }
21 }