网站建设中请稍后再访问,vs2017网站开发教程,二维码 wordpress,百度app免费下载安装最新版594 最大和谐字符串
这道题属于字符串类型题目#xff0c;解决的办法还是有很多的#xff0c;暴力算法#xff0c;二分法#xff0c;双指针等等。
题目描述
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在#xff0c;给你一个整数数组 nums …594 最大和谐字符串
这道题属于字符串类型题目解决的办法还是有很多的暴力算法二分法双指针等等。
题目描述
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在给你一个整数数组 nums 请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。 这题一上来描述贼多例子给的是比较简单的。直接扔出两个例子让你理解好了是看着好像是简单的字符串一类。遥想当年还是在大学坐在教室后排在上听着年老的大学教授讲着C与字符串是多么的犯困倚着头看着心仪班花的时候。。。啪继续看题 既然是面试那咱们可不能让面试官久等了。
小明OK完事儿等着面试官来表扬自己吧。他肯定会说小子你是个好手工位都给你准备好了工资你说了算。
暴力解法 public static int longestHarmoniousSubsequence(int[] nums) {// 最长和谐子序列的长度int maxLength 0;// 遍历所有可能的子序列for (int i 0; i nums.length; i) {// 当前子序列的长度int currentLength 1;// 从当前元素开始向后遍历for (int j i 1; j nums.length; j) {// 如果差为 1则更新当前子序列的长度if (Math.abs(nums[i] - nums[j]) 1) {currentLength 1;} else {// 如果差不为 1则结束当前子序列break;}}// 如果当前子序列的长度大于最长子序列的长度则更新最长子序列的长度if (currentLength maxLength) {maxLength currentLength;}}return maxLength;}面试官嗯你这个要是nums 数组 要是给了十万个数是不是会影响性能
小明OS今年这个找工市场人言洛阳花似锦偏我来时不逢春。。。怎的技能要求突然涨了不是做出来就行
好吧逼我拿出压箱底的东西是吧。的确这个算法是偏慢一些但是这不是想着去请班花吃饭么。
这里我个人小白理解分析
对于最长和谐子序列问题我们可以使用滑动窗口来维护一个包含所有元素的和谐子序列。窗口的大小为 2窗口中的元素之差为 1。
具体来说我们可以从第一个元素开始遍历整个数组。对于每个元素我们将其添加到窗口中。如果窗口中的元素之差不为 1则我们将窗口中的最小元素移出窗口。
这样我们就可以确保窗口中始终包含一个和谐子序列。
Sliding Window public static int findLHS(int[] nums) {// 将数组升序排列Arrays.sort(nums);// 窗口的左边界int left 0;// 窗口的右边界int right 1;// 最长和谐子序列的长度int maxLength 0; // 每次循环后的数组大小int len 0;while(right nums.length) {// 计算前后两个指针数字只差int diff nums[right] - nums[left];// 如果窗口中的元素之差大于1并且左指针小于右指针增加左指针while(diff 1 left right) {left;diff nums[right] - nums[left];}// 就算当前符合要求的len长度if(nums[right] ! nums[left]) {len right - left 1;}// 更新最长和谐子序列的长度maxLength Math.max(len, maxLength);right;}return maxLength;好了时间复杂度O(n)了下一面继续
