公主请阅
- 1.快乐数
- 1.1题目说明
- 示例 1
- 示例 2
- 1.3题目分析
- 1.4代码部分
- 1.5代码解析
- 2.复写0
- 2.1题目说明
- 示例 1
- 示例 2
- 2.2题目分析
- 2.3代码部分
- 2.4代码解析
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也是需要走一次的
