OJ刷题日记:1、双指针(1)

简介: OJ刷题日记:1、双指针(1)

1、283.移动零

题目:

283. 移动零 - 力扣(LeetCode)

https://leetcode.cn/problems/move-zeroes/description/

给定一个数组 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;
    }
};


目录
相关文章
|
1月前
|
算法 容器
OJ刷题日记:2、双指针(2)
OJ刷题日记:2、双指针(2)
18 0
|
1月前
|
算法
LeetCode刷题---21.合并两个有序链表(双指针)
LeetCode刷题---21.合并两个有序链表(双指针)
|
1月前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
1月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
21天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
22 0
|
1月前
|
算法 测试技术 容器
【刷题】双指针进阶
请看入门篇 :双指针入门
16 0
【刷题】双指针进阶
|
1月前
|
算法 测试技术 容器
【刷题】双指针入门
经过这四道题目的洗礼,我大概对双指针有了初步印象,接下来我会继续努力!!!
52 13
【刷题】双指针入门
|
1月前
数据结构--链表刷题(一)快慢指针(下)
数据结构--链表刷题(一)快慢指针
18 0
|
1月前
数据结构--链表刷题(一)快慢指针(上)
数据结构--链表刷题(一)快慢指针
22 0
|
1月前
|
存储 算法
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)