算法——双指针

双指针经常服务于需要一边遍历数组,一边对数组元素进行改动的题目,有些人也称双指针为快慢指针

同时双指针只是一种思想,实际做题时并不一定会真的采用指针

移动零

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

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

示例 1:

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

本题的思路,并非是着重于将0往后移,实际上是要将非0数按顺序往前移

由题意,我们可以将数据分成两大类:0和非0,那么我们的两个指针,一个就去找0,一个就去找非0

两个指针均从0下标开始,其中cur找0,dest找非0。cur找到0即停下,dest找到非0即停下

这样,dest总会走在cur的前面,两者将数据进行交换,就可以将非0元素前移,0元素后移。直至dest走到数组末尾。

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

 快乐数

「快乐数」 定义为:

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

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

示例 1:

输入:n = 19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2:

输入:n = 2
输出:false

通过实例的分析,这个题目我们不难理解,值得提醒的是,无论这个数起始是多少,变化了多少次,他最终都一定会进入循环比如示例2,就会在4这个数字进入死循环,这个我们不做讲解,感兴趣的小伙伴可以自己去尝试分析解惑

还有一点要注意的是,实际上当数最后变为1时,如果在进行运算,是一直以1在进行循环

所以这道题的关键解法就在于,找到循环的数字,并判断是否为1

 不知道小伙伴们还记不记得,在链表阶段,有一种循环链表的存在:

 其中,我们就是通过使用快慢指针的方法,来找到这个循环的入口,也就是本题要找的快乐数

慢指针每次走一步,快指针每次走两步,二者相等之时,即为在入口处相遇

class Solution {
int sum(int n)
{
    int num = 0;
    while(n)
    {
        int x = n % 10;
        num += x * x;
        n /= 10;
    }
    return num;
}
public:
    bool isHappy(int n) {
        int slow = n;
        int fast = sum(n);
        while(slow != fast)
        {
            slow = sum(slow);
            fast = sum(sum(fast));
        }
        if(slow == 1)
            return true;
        else
            return false;
    }
};

因为要经常进行运算,所以我们直接将其封装为函数方便调用

然后我们就让slow从n开始,fast从n运算后的数开始进行循环判断,循环结束即两者相等,再判断此时值是否为1,即可完成本题的解答

查找总价格为目标值的两个商品

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况,返回任一结果即可。

示例 1:

输入:price = [3, 9, 12, 15], target = 18
输出:[3,15] 或者 [15,3]

示例 2:

输入:price = [8, 21, 27, 34, 52, 66], target = 61
输出:[27,34] 或者 [34,27]

这个题可以说是足够简单了,对于暴力解法来说,只需要两层for循环去依次尝试两个商品的和是否等于目标值即可,但是这样的算法复杂度为0(n^2)

那么是否可以有更加高效的方法呢?没错,就是双指针

 题目明确给出,数组里的值已经是升序了(如果不是升序,我们可以利用排序使其变为升序),所以我们可以从两头出发,left指向最小值,right指向最大值,当两者的和大于目标值时,right–去找较小的值,反之让left++去找更大的值直至两者的和等于目标值,或者不存在两个商品的和等于目标值为止

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0;
        int right = price.size() - 1;
        int sum = 0;
        vector<int> v;
        while(left < right)
        {
            sum = price[left] + price[right];
            if(sum > target)
                right--;
            else if(sum < target)
                left++;
            else
            {
                v.push_back(price[left]);
                v.push_back(price[right]);
                break;
            }
        }
        return v;
    }
};

总结

不难看出,双指针算法最适用的场景即为线性表这样的数据结构类型,通过分析出问题的关键点,然后利用双指针,要么均从头开始,要么均从尾开始,要么一头一尾,逐步去解决问题

关于双指针就分享这么多,喜欢本篇文章记得一键三连,我们下期再见!

版权声明:本文为博主作者:很楠不爱原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/2303_78442132/article/details/138035729

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
xiaoxingxing的头像xiaoxingxing管理团队
上一篇 2024年5月6日
下一篇 2024年5月6日

相关推荐