四川省铁路建设有限公司网站,广州互联网营销师,北京外贸网站建设价格,网站建设维护费欢迎关注个人主页#xff1a;逸狼 创造不易#xff0c;可以点点赞吗~ 如有错误#xff0c;欢迎指出~ 目录 移动零 分析 代码 复写零 分析 代码 快乐数 分析 代码 盛最多水的容器 分析 代码 移动零
题目链接 分析
双指针算法,利用两个指针cur和dest将数组划分为三个区间… 欢迎关注个人主页逸狼 创造不易可以点点赞吗~ 如有错误欢迎指出~ 目录 移动零 分析 代码 复写零 分析 代码 快乐数 分析 代码 盛最多水的容器 分析 代码 移动零
题目链接 分析
双指针算法,利用两个指针cur和dest将数组划分为三个区间: cur从0下标开始遍历,dest从-1开始
两个指针的作用:
cur:从左到右遍历数组dest:已处理的区间内,非零元素的最后一个位置 cur从前往后遍历的过程中:
遇到0元素,cur遇到非0元素,交换dest1和cur对应的元素,dest,cur 代码
class Solution {public void moveZeroes(int[] nums) {for(int cur0,dest -1;cur nums.length; cur){if(nums[cur] ! 0){int tmpnums[cur];nums[cur]nums[dest1];nums[dest1]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 cur0, dest-1,narr.length;//1.找最后一个复写位置while(curn){if(arr[cur]!0){dest;}else{dest2;}if(destn-1) break;cur;}//1.5处理边界情况if(destn){arr[n-1]0;dest-2;cur--;}//2.从后往前开始复写while(cur0){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 sum0;while(n!0){int mn%10;summ*m;n /10;}return sum;}public boolean isHappy(int n) {int slown,fastbitSum(n);while(slow!fast){slowbitSum(slow);fastbitSum(bitSum(fast));}if(slow1){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 ret0,left0,rightheight.length-1;while(leftright){int vMath.min(height[right],height[left])*(right-left);retMath.max(ret,v);if(height[left]height[right]) left;else right--;}return ret;}
}
