[已解决]Python：每日一题 378

zltzlt

今天的题目：

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

给定一个整数数组，在这个数组所有为和谐数组的子序列中找到最长的和谐子序列的长度。

示例：

输入：[1, 3, 2, 2, 5, 2, 3, 7]
输出：5
解释：最长的和谐数组是：[3, 2, 2, 2, 3] 。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

永恒的蓝色梦想

2020-4-17 18:52:34

方法超级捞

1. class Solution:
   
2.     def findLHS(self, nums: List[int]) -> int:
   
3.         map=collections.Counter(nums)
   
4.         max=0
   
5. 
   
6.         for i,j in map.items():
   
7.             i=map[i+1]
   
8. 
   
9.             if i:
   
10.                 j+=i
    
11. 
    
12.                 if j>max:
    
13.                     max=j
    
14. 
    
15.         return max

复制代码

跳转到最佳答案楼层

kinkon

试试看能不能通过，速度应该是很慢的

1. from collections import Counter
   
2. def f378(nums):
   
3.     res = Counter(nums)
   
4.     res = sorted(res.items())
   
5.     out,stack = 0, []
   
6.     for val, c in res:      
   
7.         #print(stack)
   
8.         if len(stack) == 1:
   
9.             if val - 1 == stack[-1][0]:
   
10.                 out = max(out, c + stack[-1][1])        
    
11.             stack.pop()
    
12.         stack.append([val, c])
    
13.     return out

复制代码

永恒的蓝色梦想

方法超级捞

1. class Solution:
   
2.     def findLHS(self, nums: List[int]) -> int:
   
3.         map=collections.Counter(nums)
   
4.         max=0
   
5. 
   
6.         for i,j in map.items():
   
7.             i=map[i+1]
   
8. 
   
9.             if i:
   
10.                 j+=i
    
11. 
    
12.                 if j>max:
    
13.                     max=j
    
14. 
    
15.         return max

复制代码

March2615

1. from collections import Counter
   
2. 
   
3. 
   
4. def daily378(nums: list) -> int:
   
5.     # 解题思路：
   
6.     # 首先对nums元素进行计数
   
7.     # 如果两元素差1，则返回两者个数之和
   
8.     count_nums = Counter(nums)
   
9.     result = 0
   
10.     set_nums = set(nums)
    
11.     for num in set_nums:
    
12.         if num + 1 in set_nums:
    
13.             result = max(result, count_nums[num] + count_nums[num+1])
    
14.     return result

复制代码

_2_

占楼
偷偷的想到双指针

_2_

……我觉得你可以自己出题，不用在力扣上找……

永恒的蓝色梦想

_2_ 发表于 2020-4-17 19:28
占楼
偷偷的想到双指针

子序列，和双指针没半毛钱关系

小甲鱼de粉丝

一定要连续的吗

kinkon

优化一下

1. def f378(nums):
   
2.     res = Counter(nums)
   
3.     out = 0
   
4.     for val, c in res.items():      
   
5.         if val - 1 in res:
   
6.             out = max(out, c + res[val - 1])        
   
7.     return out

复制代码

小甲鱼de粉丝

我可能要30分钟

小甲鱼de粉丝

kinkon 发表于 2020-4-17 18:47
试试看能不能通过

我觉得最好用内置函数

kinkon

小甲鱼de粉丝 发表于 2020-4-17 19:57
我觉得最好用内置函数

多谢提醒，Counter原来也是内置函数，用字典也可以实现这个功能，代码比较多，当练习了

小甲鱼de粉丝

kinkon 发表于 2020-4-17 20:03
多谢提醒，Counter原来也是内置函数，用字典也可以实现这个功能，代码比较多，当练习了

嗯，一起学习吧

TJBEST

这个可能超时

1. def fun378(arr):
   
2.     dictionary = dict()
   
3.     for each in arr:
   
4.         try:
   
5.             dictionary[each] += 1
   
6.         except:
   
7.             dictionary[each] = 1
   
8.     method = list(dictionary.items())
   
9.     method.sort()
   
10.     previous = method[0]
    
11.     Num = previous[1]
    
12.     for temp in method[1:]:
    
13.         if temp[0] - previous[0] == 1:
    
14.             if temp[1] + previous[1] > Num:
    
15.                 Num = temp[1] + previous[1]
    
16.             else:
    
17.                 pass
    
18.         else:
    
19.             if temp[1]> Num:
    
20.                 Num = temp[1]
    
21.             else:
    
22.                 pass
    
23.         previous = temp
    
24.     return Num

复制代码

March2615

我就纳闷了，为什么速度会差这么多，明明都是差不都的方法，
是从不同地方读取的速度不一样吗？

zltzlt

March2615 发表于 2020-4-17 20:13
我就纳闷了，为什么速度会差这么多，明明都是差不都的方法，
是从不同地方读取的速度不一样吗？

力扣的测速都不太准确，所以我有时用 unittest 测

March2615

zltzlt 发表于 2020-4-17 20:17
力扣的测速都不太准确，所以我有时用 unittest 测

我想着这么简单就去力扣通过了再来
结果老是给我说超时
看完答案后发现就是for _ in _ 的不同

fan1993423

1. from collections import Counter
   
2. def fun378(lst):
   
3.     result=0
   
4.     c=sorted(Counter(lst).items(),reverse=True)
   
5.     for i in range(len(c)-1):
   
6.         if c[i][0]-c[i+1][0]==1:
   
7.             result=max(result,c[i][1]+c[i+1][1])
   
8.     return result

复制代码

fan1993423

我这个如果运气好，也许第一个i就能出答案哦，另外版主能不能314,349测一下，我最近想出来的

kinkon

fan1993423 发表于 2020-4-17 21:10

按数量排序有可能会出错，例如,[1,2,2,3,2,6,2,2,7,7,7,7,7]