双指齐下:那晚我与算法的不解之缘
1.快乐数
1.1题目说明
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是快乐数就返回 true
;如果不是,则返回 false
。
示例 1
输入:n = 19
输出:true
解释:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
示例 2
输入:n = 2
输出:false
1.3题目分析
我们这个题类似于判断链表是否有环
我们这里的两种情况,一种是最后都是1,一种是进行不同数字之间的循环
那么我们在解决快慢双指针的时候用到的就是快慢双指针的方法
1.定义快慢指针
2.慢指针每次向后移动一步,快指针向后每次移动两步
3.判断相遇的时候的值就行了,
我们在链表中利用快慢指针进行不同速度的走,看看最后我们的两个指针能不能相遇,如果相遇了的话,那么这个就是带环的链表
这个题的话我们仅仅需要判断我们相遇的的值是不是1
我么可以将数字定义为指针
我们这里一开始可以将指针定义给2,然后下一次就是4,那么现在的slow就指向了4
那么这个slow就被修改了
其实这个题有可能存在第三种情况的,就是一直进行变化,没有循环
1.4代码部分
class Solution {
public:
int bitSum(int n)//返回n这个数每一位上面的平方和
{
int sum=0;
while(n)
{
int t=n%10;//将最后一位拿出来
sum+=t*t;
n/=10;
}
return sum;
}
bool isHappy(int n)
{
int slow=n,fast=bitSum(n);//让fast指针指向这个第二个数字,就是第一个数字所有位上的数字的平方之和
while(slow!=fast)
{
slow=bitSum(slow);
fast=bitSum(bitSum(fast));//快指针走两步
}
//这里连个指针就相遇了
return slow==1;//如果等于1的话就是快乐数,不等于1就不是快乐数了
}
};
1.5代码解析
我们先写出一个计算一个数的每一位上的数字的平方之和的函数,这里我们是bitSum
来实现这个功能
然后我们在主函数中进行快慢指针的定义,快指针走两步,慢指针走一步,直到最后的数值相等了
那么这个时候我们只需要判断这个数字是不是1就行了,是1的话就返回true,不是1的话就返回这个0
2.复写0
2.1题目说明
从图片中提取的信息如下:
给你一个长度固定的整数数组 arr
,请你将数组中出现的每个零都复写一遍,并将其余的元素向右平移。
注意:请不要在超过该数组长度的情况下插入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。
示例 1
输入:arr = [1, 0, 2, 3, 0, 4, 5, 0]
输出:[1, 0, 0, 2, 3, 0, 0, 4]
解释:调用函数后,输入的数组将修改为 [1, 0, 0, 2, 3, 0, 0, 4]
。
示例 2
输入:arr = [1, 2, 3]
输出:[1, 2, 3]
解释:调用函数后,输入的数组将修改为 [1, 2, 3]
。
2.2题目分析
如果是非0就写一遍,如果遇到的是0的话,就写两遍
我们这里同样采用双指针解法
我们创建一个新的数组,cur
指针指向原数组的第一个元素,从左到右进行一个扫描的操作
然后我们的dest
指向新数组的第一个元素
cur
在遍历数组的时候会遇到两种情况,一种是0,一种是非0,那么我们就需要分情况讨论了
这种是异地操作,那么我们如何改成就地操作呢?
就是我们不用两个数组,将这两个指针定义在一个数组中
如何我们利用两个指针从左向右进行操作的话是会存在数据覆盖的
然后后面的数字全部被覆盖为0了
所以我们从右边开始进行运算
1.先找到最后一个复写的数
-
双指针算法:先定义
cur
指向第一个数,然后dest
指向-1,然后cur从前完后进行数组的遍历操作,决定这个dest
向后移动一步还是两步 -
1.1.我们先判断
cur
指向的数是0还是非0, -
1.2.根据
cur
位置的值决定dest
向后移动一步或者是两步。如果是非0的话我们dest向后移动一步,如果是0的话就移动两步 -
1.3.判断一下
dest
是否已经到结束为止 -
1.4.
cur++
经过这四步操作我们就能得到下面的指针的指向
这个时候我们就能发现此时的cur
是我们需要复写的数,
存在特例,如果是这样的话就会存在特例,dest
就会存在越界的现象
如果是越界访问的话,我们直接就是会进行报错的
cur
的位置是没问题的,但是我们的dest
是会存在问题的
1.5处理边界情况:越界的情况就是cur指向的数是0的情况,然后dest
走了两步,然后因为走了一步就到最后的位置了,再走一步就到了边界之外了
所以我么需要将n-1
位置的值修改为0,然后dest-=2 cur--
2.从后向前完成复写操作
先找到这个最后一个我们需要进行复写操作的值
找到之后我们将边界情况处理下
然后我们就从后往前进行复写的操作
这里虽然是两个while循环,但是常数循环的话时间复杂度是o(1)
空间复杂度是o(1)
2.3代码部分
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
//1.找到最后一个复写的数
int cur=0,dest=-1,n=arr.size();
while(cur<n)
{
if(arr[cur])//非0的情况,dest向后走一位
{
dest++;
}
else//遇到0就走两位
{
dest+=2;
}
if(dest>=n-1) //越界
{
break;//这个时候的cur指向的值就是我们最后复写的数,那么我们就退出就行了
}
cur++;//这个时候我们的dest没有越界,我们的cur++,继续用往后找
}
//2.处理边界情况
if(dest==n)//就是最后的时候cur指向的数是0,然后dest多向后面移动了一步
{
arr[n-1]=0;
cur--;
dest-=2;
//让cur往坐走一步,dest望左走两步
}
//3.从后向前完成复写的操作
while(cur>=0)
{
if(arr[cur])//当前的位置不是0,我们只需要将当前的值抄到dest位置上
{
arr[dest--]=arr[cur--];
//先用dest和cur再--
//抄完之后就继续往左边走,--操作
}
else//是0的情况下
{
//将两个位置都复写成为0,然后dest每次都--
arr[dest--]=0;
arr[dest--]=0;
//到这里我们的dest已经减了两次了
cur--;
}
}
}
};
2.4代码解析
在这个代码中,我们先利用双指针从左到右遍历整个数组,去找到这个数组中最后一个复写的数字
我们先开始将cur
定义为0,dest
定义为-1,
然后我们利用这个while
循环进行遍历这个数组
遍历的条件是cur
的大小小于这个数组的大小,假设数组的元素个数为n
,那么我们的cur
的大小要小于n
,cur
最大的值就是n-1
,我们在循环里面进行cur
指向的数据的判断,如果指向的数据是非0的话,我们的dest
就往后面走一步,如果遇到的是0的话我们的dest
就走两步
然后如果我们的dest>=n-1
的话,就说明我们的dest
已经越界了,那么此时的cur
指向的值就是我们最后复写的数,那么我们退出就行了
然后我们这个循环里面最后就让我们的cur
走一步
那么这个时候我们的cur
已经指向最后一个我们需要复写的数了,那么我们需要判断下边界情况并进行处理下
如果经过上面的循环后我们的dest
此时等于n,就是在这个数组外面,这个是因为当我们数组最后倒数第二个数是0的话,然后cur
指向了这个数,然后触发了dest
往后面走了两步出界了,然后我们就需要进行处理下,让dest
回到正常的范围里面去
我们直接让这个数组最后一个数变为0,然后cur--
,dest-=2
,cur
退一步,dest
退两步,然后就回到了正常的范围里面了
最后我们就从后往前进行复写的操作,遇到0就写两遍,非0就写一遍
我们在while
这个循环里面,循环条件是cur>=0
不出界就行了
我们在循环里面进行判断cur
指向的当前位置是不是0,如果是非0的话我们就让dest
和cur
当前的指向的两个数交换位置,
然后都进行减减的操作,往左边走,
如果cur
指向的是0的话,我们就将dest
当前的位置变为0,然后dest
往左边走一个位置,然后这个位置的数也变成0,然后dest
再往左边走一位进行后面的判断操作
到这里我们的dest
已经走了两次了,那么我们的cur
也是需要走一次的
原文地址:https://blog.csdn.net/2301_80863610/article/details/142918973
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!