首页 > 编程语言 >力扣594(java&python)-最长和谐子序列(简单)

力扣594(java&python)-最长和谐子序列(简单)

时间:2022-10-11 10:13:48浏览次数:79  
标签:right java 594 nums python res while 指针 left

题目:

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

现在,给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

 

示例 1:

输入:nums = [1,3,2,2,5,2,3,7]
输出:5
解释:最长的和谐子序列是 [3,2,2,2,3]
示例 2:

输入:nums = [1,2,3,4]
输出:2
示例 3:

输入:nums = [1,1,1,1]
输出:0
 

提示:

1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-harmonious-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

 滑动窗口+双指针:先给数组排序,然后利用滑动窗口定义两个指针,从头开始遍历数组。如果窗口内的数差在1以内就扩大窗口,否则就缩小窗口。

滑动窗口的模板:来自@【负雪明烛 】

滑动窗口又叫做【虫取法】:前脚不动,向前移动后脚;后脚不动,向前移动前脚。

基本思路:以右指针作为驱动,拖着左指针向前走。右指针每次只移动一步,而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移,探索未知的新区域;左指针是被迫移动,负责寻找满足题意的区间。

模板的整体思想是:

  • 定义两个指针 left 和 right 分别指向区间的开头和结尾,注意是闭区间;定义 sums 用来统计该区间内的各个字符出现次数;
  • 第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界;当 right 每次到了新位置,需要增加 right 指针的求和/计数;
  • 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置;当 left 每次移动到了新位置,需要减少 left 指针的求和/计数;
  • 在第二重 while 循环之后,成功找到了一个符合题意的 [left, right] 区间,题目要求最大的区间长度,因此更新 res 为 max(res, 当前区间的长度) 。
  • right 指针每次向右移动一步,开始探索新的区间。

注意:模板中的 sums 需要根据题目意思具体去修改,如果是求和题目把sums 定义成整数用于求和;如果是计数题目,就需要改成字典用于计数。当左右指针发生变化的时候,都需要更新 sums 。另外一个需要根据题目去修改的是内层 while 循环的判断条件,即: 区间 [left, right]。

python代码模板:

 1 def findSubArray(nums):
 2     N = len(nums) # 数组/字符串长度
 3     left, right = 0, 0 # 双指针,表示当前遍历的区间[left, right],闭区间
 4     sums = 0 # 用于统计 子数组/子区间 是否有效,根据题目可能会改成求和/计数
 5     res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
 6     while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
 7         sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
 8         while 区间[left, right]不符合题意: # 此时需要一直移动左指针,直至找到一个符合题意的区间
 9             sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
10             left += 1 # 真正的移动左指针,注意不能跟上面一行代码写反
11         # 到 while 结束时,我们找到了一个符合题意要求的 子数组/子串
12         res = max(res, right - left + 1) # 需要更新结果
13         right += 1 # 移动右指针,去探索新的区间
14     return res

python解题代码:

 1 class Solution:
 2     def findLHS(self, nums: List[int]) -> int:
 3         nums.sort()
 4         left, right = 0, 0
 5         res = 0
 6         # 第一重while判断右指针是否超出边界
 7         while right < len(nums):
 8             # 第二重while让左指针移动到[left, right]区间中
 9             while nums[right] - nums[left] > 1:
10                 left += 1
11             if nums[right] - nums[left] == 1:
12                 # 更新最大长度
13                 res = max(res, right - left + 1)
14             # right指针向右移动,探索新的区间
15             right += 1
16         return res

java解题代码:

 1 class Solution {
 2     public int findLHS(int[] nums) {
 3         Arrays.sort(nums);
 4         int max = 0;
 5         int left = 0, right = 0;
 6         while(right < nums.length){
 7             while(nums[right] - nums[left] > 1){
 8                 left++;
 9             }
10             if(nums[right] - nums[left] == 1){
11                 max = Math.max(max, right-left+1);
12             }
13             right++;
14         }
15         return max;
16     }
17 }

标签:right,java,594,nums,python,res,while,指针,left
From: https://www.cnblogs.com/liu-myu/p/16778059.html

相关文章

  • Java学习之路:运算符
    2022-10-1010:34:08......
  • Java反序列化之C3P0链学习
    0x01前言 再多打一点基础吧,后续打算先看一看 XStream,Weblogic,strusts2 这些个0x02C3P0 组件介绍C3P0 是一个开源的 JDBC 连接池,它实现了数据源和 JNDI 绑定,......
  • JavaWeb学习(一)SQL
    一、简介1、以分号结尾2、不区分大小写3、注释: --空格    #    /**/二、DDL:操作数据库、表等1、查询:showdatabases 2、创建:createdatab......
  • python study
    pythonpycharmPythonpip安装与使用pythonpippipinstallpyqt5pipinstallpyqt5_toolsqtdesigner就在python目录下:.\Python36\Lib\site-packages\pyqt5-tools。pyqt5_to......
  • 密码强度的正则表达式(JavaScript)总结
    密码强度的正则表达式(JavaScript)总结简言本文给出了两个密码强度的正则表达式方案,一个简单,一个更复杂和安全。并分别给出了两个方案的解析和测试程序。一般大家可以根据......
  • Java全局唯一ID生成策略
    在分布式系统中常会需要生成系统唯一ID,生成ID有很多方法,根据不同的生成策略,以满足不同的场景、需求以及性能要求。1、数据库自增序列这是最常见的一种方式,利用DB来生成全......
  • Win10 环境下 vscode 没法在终端使用 conda activate 命令来更换 Python 环境的解决方
    在vscode上激活conda镜像如报下面错误:CommandNotFoundError:Yourshellhasnotbeenproperlyconfiguredtouse'condaactivate'.Ifusing'condaactivate'fr......
  • docker 容器内的 java 进程自动退出排查
    一个简单的javaweb程序,运行在docker容器中,提供对外接口服务现象:使用dockerrun启动容器后可以正常运行,访问一切正常,但是隔了几十分钟后容器自动退出,java日志一切......
  • java无法加载maper.xml问题
    项目依赖其他模块,模块中有mapper,本项目也有mapper,导致项目无法正常运行。解决办法:1、配置mybatis:#搜索指定包别名typeAliasesPackage:com.XXX.XXX,com.YYY.......
  • java文本转语音
    下载jar包https://github.com/freemansoft/jacob-project/releases  解压,将jacob-1.18-xxx.dll相应放到项目使用的JAVA_HOME\bin下  创建项目,导入jarja......