283. 移动零 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cur = 0, prev = -1;//cur是0区间后的第一个非0,prev是0区间前的最后一个非0
while(cur < nums.size())
{
if(nums[cur])
{
swap(nums[++prev], nums[cur]);
}
cur++;
}
}
};
1089. 复写零 给你一个长度固定的整数数组 arr,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。 注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int prev = -1, cur = 0, n = arr.size();//双指针,找到修改后数组的最后一个元素
while(cur < n)
{
if(arr[cur] != 0)
{
prev++;
}
else
{
prev += 2;
}
if(prev >= n - 1) break;//prev已经到终止位置
cur++;
}
//处理边界(如果prev超出数组边界2个位置,说明cur判断的最后一个元素是0,因为数组的空间有限,cur最后遍历到的0无法进行复制,因此我们要对这种情况进行修复,即将数组最后一个元素修改为0(直接后移不进行复制)。然后让cur退一步,prev退两步,再进行向后移动元素的操作即可)
if(prev == n)
{
arr[n - 1] = 0;
cur--;
prev -= 2;
}
//从最后一个元素开始从后往前移动,遇到0就往后填充两个0.
while(cur >= 0)
{
if(arr[cur] == 0)
{
arr[prev--] = 0;
arr[prev--] = 0;
cur--;
}
else
{
arr[prev--] = arr[cur--];
}
}
}
};
202. 快乐数 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ;不是,则返回 false 。
class Solution {
public:
int bitsum(int n)
{
int ret = 0;
while(n)
{
int t = n%10;
ret += t * t;
n /= 10;
}
return ret;
}
bool isHappy(int n) {
int slow = n, fast = bitsum(n);
while(slow != fast)
{
slow = bitsum(slow);
fast = bitsum(bitsum(fast));
}
return slow == 1;
}
};
今天是算法练习的第1天。 绳锯木断,水滴石穿,继续加油。 来源:力扣(LeetCode),著作权归领扣网络所有。 如果本篇文章对你有所启发的话,希望可以多多支持作者,谢谢大家!