目录
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;
}
};