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

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

原作者: [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 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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