【优选算法题练习】day1

摘星

发布于 2023-10-15 15:51:48

1130

发布于 2023-10-15 15:51:48

文章被收录于专栏：C/C++学习C/C++学习

双指针：

一、283. 移动零

1.题目简介

283. 移动零给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

2.解题思路

3.代码

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++;
        }
    }
};

4.运行结果

二、1089. 复写零

1.题目简介

1089. 复写零给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

2.解题思路

3.代码

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--];
            }
        }
    }
};

4.运行结果

三、202. 快乐数

1.题目简介

202. 快乐数编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果这个过程结果为 1，那么这个数就是快乐数。如果 n 是快乐数就返回 true ；不是，则返回 false 。

2.解题思路

3.代码

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