OJ刷题日记：1、双指针（1）

1、283.移动零

2、1089.复写零

3、202.快乐数

1、283.移动零

题目：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

下方代码就是这题的解法，我是利用for循环去遍历找出0的值，如果找到0了，这时就停在这里，然后进行判断，利用两个指针进行判断，一个是j一个是k，j就是当前0的位置，k就是去向下去遍历剩余数组的指针，如果找到不等于0的就和j进行交换，再把k的位置给给j，这样就能找出数组中的0了。

class Solution {
public:void moveZeroes(vector<int>& nums) {int sz=nums.size()-1;for(int i=0;i<sz;i++){if(nums[i]==0){int j=i;int k=i+1;while(k<=sz){if(nums[k]!=0){swap(nums[j],nums[k]);j=k;}++k;}}}}
};

然后还有另外一种方式就是利用两个指针，类似于快慢指针的方式，right指针一直走，遇到非0就和left交换数据，然后leift才++，这样只需要走一遍就可以把所有数据交换完成，不用和上面一样每次都需要挪动，消耗就会特别大。

class Solution {
public:void moveZeroes(vector<int>& nums) {int sz=nums.size();int left=0;int right=0;while(right<sz){if(nums[right]){swap(nums[left],nums[right]);left++;}right++;}}
};

2、1089.复写零

1089. 复写零 - 力扣（LeetCode）https://leetcode.cn/problems/duplicate-zeros/description/

题目：

给你一个长度固定的整数数组 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]

提示：

1 <= arr.length <= 104
0 <= arr[i] <= 9

这题我第一开始的想法是遇到0然后进行挪动一下数据，测试用例过了，可是有几个没过，超出时间限制了，代码如下

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n=arr.size()-1;for(int i=0;i<n;i++){if(arr[i]==0){int j=n;while(j>i){arr[j]=arr[j-1];cout<<j<<endl;--j;}i=i+1;arr[i]=0;}}}
};

然后我就开始从写，想出下方的代码，就是遇到0之后在这个位置插入一个0，然后尾删一个，也就是库函数里面的pop_back()函数，代码如下，然后过了。

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n=arr.size()-1;for(int i=0;i<n;i++){if(arr[i]==0){arr.pop_back();arr.insert(arr.begin()+i,0); ++i;}}}
};

3、202.快乐数

202. 快乐数 - 力扣（LeetCode）https://leetcode.cn/problems/happy-number/description/

题目：

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 231 - 1

下面我说一下我这题的思路，首先题目说了可能是无限循环，也就是说这就是个环，因为1也是无限循环，所以这里就用了类似于约瑟夫环这里的判断方式快慢指针，一个走一步，一个走两步，直到两个指针相等，这时退出循环，判断这个数是否等于1就能解决这个问题了，代码和测试结果如下。

class Solution {
public:int bitSum(int 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);while(slow!=fast){slow=bitSum(slow);fast=bitSum(bitSum(fast));}return slow==1;}
};