一般的企业网站开发价格,深圳网络推广哪家,公司方案策划书,顶尖手机网站建设文章目录 算法:双指针移动零复写零快乐数盛最多水的容器有效三角形的个数查找总价格为目标值的两个商品三数之和四数之和 总结 算法:双指针
移动零 定义两个指针,slow和fast.用这两个指针把整个数组分成三块. [0,slow]为非零元素,[slow1,fast-1]为0元素,[fast,num.length]为未… 文章目录 算法:双指针移动零复写零快乐数盛最多水的容器有效三角形的个数查找总价格为目标值的两个商品三数之和四数之和 总结 算法:双指针
移动零 定义两个指针,slow和fast.用这两个指针把整个数组分成三块. [0,slow]为非零元素,[slow1,fast-1]为0元素,[fast,num.length]为未处理的元素. 初始情况下slow-1,fast0,因为此时还没有对数组进行处理. 用fast遍历整个数组:
当fast指向的元素不为0时,此时让slow,并交换fast与slow所指向的元素.交换完毕后fast,继续向后处理元素.当fast指向的元素为0时,直接fast.
class Solution {public void moveZeroes(int[] nums) {int slow -1;int fast 0;while(fast nums.length) {if(nums[fast] ! 0) {slow;int tmp nums[fast];nums[fast] nums[slow];nums[slow] tmp;}fast;}}
}复写零 这道题目如果没有要求空间复杂度为O(1)的话,那确实是简单题.直接申请一块数组,遍历,然后放进去,最后把数组的引用交换一下就行了. 但是实际上,这道题还是有点难度的,需要考虑的细节情况很多,自己上手写写就知道了.
解决这道题,最关键的就是找到数组中最后一个要被修改的数,我们可以使用双指针来找.
定义两个指针slow和fast并初始化为0.使用slow向后遍历数组,当slow遇到0时,fast向后移动两步,slow向后移动一步.当slow指向的元素不为零时,fast和slow都向后移动一步.重复上述过程,直到fast大于数组长度.循环结束后,此时fast和slow多移动了一步,所以要减掉.在这里还需要考虑fast向后移动了两步的情况(slow指向了0元素,而此时fast已经位于数组的最后一个元素了),判断一下fast是否越界,如果越界,修改fast的指向,让fast指向数组的最后一个元素,因为这时slow指向的元素肯定是0,所以我们可以将数组的最后一位修改成0,之后让slow和fast向前移动一位.当程序运行到这里时,所有的特殊情况我们就都处理完了.接下来就是简单的移动和赋值了,这里就不再赘述了~
class Solution {public void duplicateZeros(int[] arr) {int fast 0;int slow 0;while(fast arr.length) {if(arr[slow] 0) fast;fast;slow;}--slow;--fast;if(fast arr.length) {fast arr.length-1;arr[fast--] arr[slow--];}while(slow 0) {if(arr[slow] 0) {arr[fast--] 0;}arr[fast--] arr[slow--];}}
}也可以看看宫水三叶大佬写的代码,大佬在力扣上写了题解,可以去看看.
class Solution {public void duplicateZeros(int[] arr) {int n arr.length, i 0, j 0;while (j n) {if (arr[i] 0) j;i; j;}i--; j--;while (i 0) {if (j n) arr[j] arr[i];if (arr[i] 0 --j 0) arr[j] 0;i--; j--;}}
}作者宫水三叶
链接https://leetcode.cn/problems/duplicate-zeros/solutions/1607062/by-ac_oier-zivq/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。快乐数 这道题条件给的很全,如果题目没给重复这个过程直到这个数变为1,也可能是无限循环但始终变不到1这个条件. 那么就需要好好的想一想了,上面的条件是可以证明出来的.运用到了数学上的思想鸽巢原理,这个放到最后再写吧,先写题解~
将一个正整数替换为它每个位置上的数字的平方和这个我们可以把它写成一个方法,方便调用,写法也很简单,这里就不写了.这道题最核心的地方在于你怎么判断它无限循环永远到不了1我们可以使用双指针来帮助我们判断如果你之前做过环形链表那么就很容易想到。定义两个指针slow和fast并初始化为n首先让fast先走一步(做一次替换,因为之后的循环内需要判断fast和slow是否相等).紧接着进入循环,循环条件为fast ! 1 || fun(fast) ! 1,因为之后fast要一次向后走两步,所以fast的当前值和fast的下一个值都要判断.循环内如果fast与slow相等,说明有环了,直接return false.如果不相等,slow向后走一步,fast向后走两步.如果fast走着走着跳出了循环(表示fast可以被替换成1),此时直接return true.
class Solution {public static int fun(int n) {int sum 0;while(n 0) {int tmp n%10;sum tmp*tmp;n/10;}return sum;}public boolean isHappy(int n) {int slow n;int fast fun(n);while(fast ! 1 || fun(fast) ! 1) {if(fast slow) {return false;}fast fun(fun(fast));slow fun(slow);}return true;}
}鸽巢原理讲解: 以下是不太严谨的证明~ 举个例子,比如说n 9999999999. n经过一次变换之后n 9^2*10 810.也就是说变换的区间就在[1,810]这个范围内. 如果我们将n变换810次,最差的情况就是[1,810]内所有的数都出现了一次.如果n在此基础上再次变换,那么这个数肯定就会落在这个区间内,此时就形成了环路.
盛最多水的容器 写这道题时,我们就要分析分析了. 设盛水容量为v,底部变长为s,高为h.左指针为left指向最左边,右指针为right指向最右边,两个指针向对方移动. 根据题意,我们可得:
v s * h;s right - left;h min(left,right); 当我们移动指向的最高的线的指针时,有以下两种情况:s 减小(两指针之间的距离变短了), 移动后指针的指向的线高于移动前的线,h 不变(因为盛水多少取决于最低的线),那么 v 减小s 减小,移动后指针的指向的线低于移动前的线,h 不变或减小(因为盛水多少取决于最低的线,移动后的指针指向的线可能比另一个指针指向的线短,也可能在移动后仍然比另一个指针指向的线长),那么 v 减小. 可以看到,当我们移动指向的最高的线的指针时,v并不会增大.
当我们移动指向的最低的线的指针时,有以下两种情况:
s 减小(两指针之间的距离变短了), 移动后指针的指向的线高于移动前的线,h 增大(因为盛水多少取决于最低的线),那么 v 的变化不能确定.s 减小,移动后指针的指向的线低于移动前的线,h 减小(因为盛水多少取决于最低的线),那么 v 减小. 综合上述分析,我们可以得到,只有在移动指向的最低的线的指针,并且移动后,指针的指向的线,高于移动前的线时,v才有可能变大.
有了以上的分析,代码就很好写啦~
class Solution {public int maxArea(int[] height) {int left 0;int right height.length - 1;int v 0;while(left right) {int s Math.min(height[left],height[right]);int tmp s*(right-left);if(tmp v) {v tmp; }if(height[left] s) {left;} else {right--;}}return v;}
}有效三角形的个数 先给数组排个序. 从后向前固定一个i值(循环1),当left小于right时(循环2),让left和right指向的数相加,判断是否大于i指向的数.
大于i,让sumright-left; right–;小于或等于i,让left向右移. class Solution {public int triangleNumber(int[] nums) {int left 0;int right 0;Arrays.sort(nums);int sum 0;for(int inums.length - 1;i 2;i--) {right i-1;left 0;while(left right) {if(nums[left]nums[right] nums[i]) {sum right -left;right--;} else {left;}}}return sum;}
}查找总价格为目标值的两个商品 感觉没什么可说的~
class Solution {public int[] twoSum(int[] price, int target) {int left 0;int right price.length - 1;while(left right) {if(price[left] price[right] target) {right--;} else if(price[left] price[right] target) {left;} else{return new int[]{price[left],price[right]};}}return null;}
}三数之和 自己写的代码,在最开始new ArrayListListInteger()的时候不会new,忘了.(后来发现不用这么麻烦写e) 还有我最开始是在最内层循环里面使用了list.contains(list2),然后超时了qwq. 后来去看题解,发现还能这样去重! 改了改就成现在这样了,虽然效率还是很低就是了.
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger list new ArrayListListInteger();Arrays.sort(nums);int left 0;int right nums.length - 1;for(int i nums.length-1; i 2; i--) {if(i nums.length - 1 nums[i] nums[i1]) continue;right i - 1;left 0;while(left right) {if(right ! i-1 right left 1 nums[right] nums[right1]) {right--;continue;}int tmp nums[left] nums[right] nums[i];if(tmp 0) {right--;} else if(tmp 0) {left;} else {ArrayListInteger list2 new ArrayList();list2.add(nums[left]); list2.add(nums[right]); list2.add(nums[i]); list.add(list2);right--;}}}return list;}
}看了讲解后:
ListListInteger list new ArrayListListInteger();其实可以写成 ListListInteger list new ArrayList(); 里面可以啥都不写.当num[i]0时,此时最大的数都小于0了,肯定三数之和就不可能等于0了,直接跳过.第一次见还能这样写: list.add(new ArrayList(Arrays.asList(nums[left],nums[right],nums[i])));当三数和为0时,left和right可以都移动一步(我写的只有right移动一步).当三数和为0并且left和right移动后,此时就可以开始去重了,不必在内层循环用if和continue去重(这样多判断了right ! i-1),而且我只对right去重了,left还是要经过整个循环emmm,虽然也达到了去重的效果(歪打正着,我当时还在想为啥if和continue不能换成while?被自己蠢哭了qwq).其实没必要,直接同时去重就OK了.
虽然自己第一次写的代码能通过,但是可优化的地方还有很多.没有大佬写的代码优雅~
以下是改后的代码:
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger list new ArrayList();Arrays.sort(nums);int left 0;int right nums.length - 1;for (int i nums.length - 1; i 2; i--) {if (nums[i] 0)break;if (i nums.length - 1 nums[i] nums[i 1])continue;right i - 1;left 0;while (left right) {int tmp nums[left] nums[right] nums[i];if (tmp 0) {right--;} else if (tmp 0) {left;} else {list.add(new ArrayListInteger(Arrays.asList(nums[left],nums[right],nums[i])));right--;left;while (right left nums[right] nums[right 1]) {right--;}while (right left nums[left] nums[left - 1]) {left;}}}}return list;}
}四数之和 自己写出来的,中间改了好几次,终于过了~ 跟上一题很像. 自己写的代码:
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger list new ArrayList();Arrays.sort(nums);if (nums[nums.length - 1] 0 target 0) {return list;}for (int i 0; i nums.length - 3; i) {if (nums[i] 0 target 0) {break;}if (i ! 0) {while (i nums.length - 3 nums[i] nums[i - 1]) {i;}}for (int j i 1; j nums.length - 2; j) {if (j ! i 1) {while (j nums.length - 2 nums[j] nums[j - 1]) {j;}}int left j 1;int right nums.length - 1;while (left right) {long sum nums[left] nums[right] nums[i] nums[j];if (sum target) {right--;} else if (sum target) {left;} else {list.add(new ArrayList(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));left;right--;while (left right nums[left] nums[left - 1]) {left;}while (left right nums[right] nums[right 1]) {right--;}}}}}return list;}
}看了讲解后:
去重操作可以放在最后写
改后代码:
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger list new ArrayList();Arrays.sort(nums);if (nums[nums.length - 1] 0 target 0) {return list;}for (int i 0; i nums.length - 3;) {if (nums[i] 0 target 0) {break;}for (int j i 1; j nums.length - 2;) {int left j 1;int right nums.length - 1;while (left right) {int sum nums[left] nums[right] nums[i] nums[j];if (sum target) {right--;} else if (sum target) {left;} else {list.add(new ArrayList(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));left;right--;while (left right nums[left] nums[left - 1]) {left;}while (left right nums[right] nums[right 1]) {right--;}}}j;while (j nums.length - 2 nums[j] nums[j - 1]) {j;}}i;while (i nums.length - 3 nums[i] nums[i - 1]) {i;}}return list;}
}总结
使用双指针:
一般是在数组中使用,通常需要对数组进行排序.数据要有单调性.使用双指针可以把时间复杂度降一维.O(n3)变O(n2);
