欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
目录
移动零
分析
代码
复写零
分析
代码
快乐数
分析
代码
盛最多水的容器
分析
代码
移动零
题目链接
分析
双指针算法,利用两个指针cur和dest将数组划分为三个区间:
cur从0下标开始遍历,dest从-1开始
两个指针的作用:
cur:从左到右遍历数组dest:已处理的区间内,非零元素的最后一个位置
cur从前往后遍历的过程中:
遇到0元素,cur++遇到非0元素,交换dest+1和cur对应的元素,dest++,cur++
代码
class Solution { public void moveZeroes(int[] nums) { for(int cur=0,dest = -1;cur < nums.length; cur++){ if(nums[cur] != 0){ int tmp=nums[cur]; nums[cur]=nums[dest+1]; nums[dest+1]=tmp; dest++; } } }}复写零
题目链接
分析
使用双指针算法,定义两个数组下标变量cur和dest,
cur 来判断元素是否为0dest用来复写因为题目要求的是 就地 复写,如果从左往右复写是不行的(复写的0会覆盖掉后面的非0值)
该题要采取从后往前的复写,以下是解题步骤
先找到最后一个要复写的数 先判断cur位置的值决定dest相后移动一步(非0时)或者两步(0时)判断一下dest是否已经到结束位置cur++再从后往前进行复写下图演示的是如何 寻找最后一个复写位置,其中n为数组长度
处理一下特殊情况,当通过上述逻辑时可能最后出现下图中的情况:
cur的位置没有问题,但dest的位置越界了
处理办法:
直接将n-1位置修改为0cur--dest -=2代码
class Solution { public void duplicateZeros(int[] arr) { int cur=0, dest=-1,n=arr.length; //1.找最后一个复写位置 while(cur<n){ if(arr[cur]!=0){ dest++; }else{ dest+=2; } if(dest>=n-1) break; cur++; } //1.5处理边界情况 if(dest==n){ arr[n-1]=0; dest-=2; cur--; } //2.从后往前开始复写 while(cur>=0){ if(arr[cur]!=0){ arr[dest--]=arr[cur--]; }else{ arr[dest--]=0; arr[dest--]=0; cur--; } } }}快乐数
题目链接
分析
分析题目得出 计算每位数的和相加一共有两种情况:
最后结果为1 成环最后结果不为1 成环这就和 判断链表是否有环的题 解法类似, 采用快慢指针法
定义快慢'指针'(这里的'指针' 代表 是计算的值)慢指针每次向后'移动'一步,快指针每次向后移动两步(这里的'移动几步' 代表 计算n的每位数的和 的次数)判断相遇时的值代码
class Solution { //计算每位数的和 public int bitSum(int n){ int sum=0; while(n!=0){ int m=n%10; sum+=m*m; n /=10; } return sum; } public boolean isHappy(int n) { int slow=n,fast=bitSum(n); while(slow!=fast){ slow=bitSum(slow); fast=bitSum(bitSum(fast)); } if(slow==1){ return true; }else{ return false; } }}盛最多水的容器
题目链接
分析
容水量=两边高度的最小值 * 宽度
解法1:暴力枚举,将所有可能的值 都列举出来,求最大值--->结果会超时,时间复杂度为O(n^2)
解法2:利用单调性,使用双指针来解决--->时间复杂度为O(n)
步骤:
定义两个指针 left和right,left从左到右,right从右到左遍历数组left和right对于元素小的移动一位(left小,left++;right小,right--),当left和right相遇,循环结束记录每次计算的容水量 v1,v2,v3...对容水量取最大值代码
class Solution { public int maxArea(int[] height) { int ret=0,left=0,right=height.length-1; while(left<right){ int v=Math.min(height[right],height[left])*(right-left); ret=Math.max(ret,v); if(height[left]<height[right]) left++; else right--; } return ret; }}