移动零
算法原理:
1.数组划分,数组分块
2.双指针算法
(利用数组下标来充当指针)
两个指针的作用:
cur:从左往右扫描数组,遍历数组
dest:已处理的区间内,非零元素的最后一个位置
代码实现:
cur 从前往后遍历的过程中:
1.遇到0元素:cur++;
2.遇到 非零元素:
swap(dest + 1, cur);
dest++, cur++;
class Solution {public void move(int[] nums) {for (int cur = 0, dest = -1; cur < nums.length; cur++) {if (nums[cur] != 0) {dest++;// 交换当前元素与目标位置的元素int temp = nums[cur];nums[cur] = nums[dest];nums[dest] = temp;}}}
}
复写零
2.算法原理
解法:双指针算法
先根据“异地”操作,然后优化成双指针下的“就地”操作,先找到最后一个“复写”的数;
双指针算法
1.先判断 cur位置的值
2. 决定dest向后移动一步或者两步
3.判断一下dest是否已经到结束为止
4. cur++
1.5处理一下边界情况
代码:
class Solution {public void duplicateZeros(int[] arr) {int n = arr.length;int top = 0;int i = -1;while (top < n) {i++;if (arr[i] != 0) {top++;} else {top += 2;}}int j = n - 1;if (top == n + 1) {arr[j] = 0;j--;i--;} while (j >= 0) {arr[j] = arr[i];j--;if (arr[i] == 0) {arr[j] = arr[i];j--;} i--;}}
}
快乐数
题目解析:
2.算法原理
2.1第一种情况不是快乐树,那么最后值不为一,且会返回到原来值,形成一个环
2.2第二种情况是快乐树,那么最后值为一,形成一个全是一的环
因此,我们只需要采用快慢指针法,判断他们相遇时环中值是否为一,若为一则是快乐树,反之
3.代码实现
class Solution {public int bitSum(int n) {int sum = 0;while (n > 0) { // 确保 n 大于 0int t = n % 10;sum += t * t;n = n / 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = bitSum(n);while (slow != fast) {slow = bitSum(slow); // 更新 slowfast = bitSum(bitSum(fast)); // 更新 fast}return slow == 1; // 检查 slow 是否到达 1}
}
解析:
-
bitSum
方法:循环条件现在正确检查n > 0
,确保我们能处理完所有的数字位。 -
isHappy
方法:slow
指针初始为n
,会通过数字的平方和序列逐步更新。fast
指针通过两次调用bitSum
来加快循环检测的速度。- 当
slow
和fast
相遇时,表示可能出现了循环或达到了 1。
盛水最多的容器:
题目解析:
计算两条直线与x轴围成的水的体积,以最低的线计算高
算法原理:
将各个线的高度看作一个数组,采双指针法,分别计算每个容器的体积,并比较出最大的容器
class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1, volume = 0;while (left < right) {int v = Math.min(height[left], height[right]) * (right - left);volume = Math.max(volume, v);// 移动较短的边if (height[left] < height[right]) {left++;} else {right--;}}return volume;}
}
有效三角形的个数
2.算法原理
1.暴力算法:
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length;j++){
for(int k=0;k<arr.length;k++){
check(i,j,k);
}
}
}
2.利用单调性,双指针算法
1.先固定最大的数
2.在最大的左区间内使用双指针算法,统计出三元组的个数
1a+b>c left=right,right--;
2.a+b<=c left++
3.代码实现
public int solution{
Arrays.sort(nums);
int ret=0,n=nums.length;
for(int i=n-1;i>=2;i--){
int left=0,right=i-1;
while(left>right){
if(nums[left]+nums[right]>nums[i]){
ret+=right-left;
right--;}else{
left++;
}
}
}
return ret;
}
和为s的两个数字
算法原理:
1.暴力算法
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length;j++){
check(i,j);
}
}
2.双指针(与上题同理)
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int i = 0;int j = nums.size() - 1;//双指针while(i < j){auto s = nums[i] + nums[j];if(s < target)i++;if(s > target)j--;if(s == target)return{nums[i], nums[j]};}return {};}
};
到这里竹竹零就要和大家说再见了
希望时光不负赶路人,愿我们做最好的自己!!!
如果您觉得有失偏颇请您在评论区指正,如果您觉得不错的话留个好评再走吧!!
您的鼓励就是对我最大的支持! ! !