当前位置： 首页 > article >正文

【基础算法总结】双指针

article 2024/9/24 5:32:09

目录

  • 一，双指针算法介绍
  • 二，算法原理和代码实现
    • 283.移动零
    • 1089.复写零
    • 202.快乐数
    • 11.盛最多水的容器
    • 611.有效三角形的个数
    • LRC179.和为s的两个数
    • 15.三数之和
    • 18.四数之和
  • 三，算法总结

一，双指针算法介绍

双指针算法是基础算法之一，一般用于涉及数组分块/数组划分这类问题 。这里的"指针"是利用数组下标或是一个数来充当的。

在遍历过程中，两个指针的位置：
cur：从左往右扫描数组，遍历数组。
dest：指向已处理的区间内，非0元素的最后一个位置。如下图
在这里插入图片描述
所以两个指针把数组分成了三个区间：
在这里插入图片描述

二，算法原理和代码实现

283.移动零

在这里插入图片描述

在这里插入图片描述

算法原理：

我们也是定义两个变量 cur 和 dest，根据上面介绍的两个指针的位置，初始化 cur = 0, dest = -1。

在 cur 从前往后遍历的过程中，无非两种情况：
1. 遇到0元素：cur++
2. 遇到非0元素：先swap(dest+1, cur), 再cur++, dest++

代码实现：

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

1089.复写零

在这里插入图片描述
在这里插入图片描述

算法原理：

这道题看起来简单，但是有很多坑，很多细节。我们使用双指针先在草稿纸上模拟，不难发现从前往后复写是不行的，会覆盖后面的数据。但是要如何从后往前复写呢，起始位置怎么确定？

所以解决这个题有两个步骤：

1. 先找到最后一个复写的数。
这一步骤也要用双指针算法：
在这里插入图片描述
当走完这个双指针，此时 cur 指向的数就是最后一个要复写的数，dest 指向的位置就是开始复写的第一个位置。
2. 再从后往前进行复写操作：
在 cur 从后往前遍历的过程中，无非两种情况：
(1) 遇到0元素：dest向前复写两个0,cur–,dest -= 2
(2) 遇到非0元素：先arr[dest] = arr[cur], 再cur++, dest++

细节/技巧问题：

(1) 在第一步的第三小步中，一定要先判断 dest 是否已经结束
(2) 还要处理一种特殊情况：[1,0,2,3,0,4]。根据第一步的双指针，此时dest会越界，就要做特殊处理，当 dest == n 时，直接把 arr[n-1] = 0, cur–, dest -= 2。

代码实现：

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        // 找到最后一个要复写的位置
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n)
        {
            if (arr[cur]) dest++;
            else dest += 2;

            if (dest >= n - 1) break;
            cur++; // 注意每次++之前都要先判断dest是否越界
        }

        // 处理特殊情况
        if (dest == n) arr[n - 1] = 0, cur--, dest -= 2;

        // 从后往前开始复写操作
        while (cur >= 0)
        {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest] = 0, arr[dest - 1] = 0;
                dest -= 2;
                cur--;
            }
        }
    }
};

下面是一开始我写的错误代码，以示警戒：

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        // 先找到最后一个要复写的数
        int n = arr.size();
        int cur = 0, dest = -1;
        for (; dest < n - 1;)
        {
            if (arr[cur] != 0) dest++;
            else dest += 2;

            if (dest != n - 1)
                cur++;
        }

        // 处理边界情况
        if (dest == n) arr[n - 1] = 0, cur--, dest -= 2;

        // 从后往前完成复写操作
        for (; cur >= 0 && dest >= 0; )
        {
            if (arr[cur] != 0) arr[dest] = arr[cur], dest--;
            else arr[dest] = 0, arr[dest - 1] = 0, dest -= 2;

            cur--;
        }
    }
};

202.快乐数

在这里插入图片描述

在这里插入图片描述

算法原理：

首先来理解题目：
在这里插入图片描述
所以这道题可以抽象成另类的 “链表是否带环问题”。只不过这道题是一定带环的，只要根据环内的数进行判断即可。

使用经典的快慢双指针算法：
(1) 定义快慢指针
(2) 慢指针每次向后走一步，快指针向后走两步
(3) 判断相遇时候的值即可

拓展：为什么这个题一定成环？

使用鸽巢原理证明。
在这里插入图片描述

细节/技巧问题：

(1) 这题的双指针不再是数组下标，而是一个数。
(2) 在进入第一次循环时，先让 fast 指向第二个数，不然进不了循环。

代码实现：

class Solution 
{
public:
    bool isHappy(int n) 
    {
        int slow = n, fast = mypow(n);
        while(slow != fast)
        {
            slow = mypow(slow);
            fast = mypow(mypow(fast));
        }
        if(slow == 1)
            return true;
        else
            return false;
    }

    int mypow(int n)
    {
        int sum = 0;
        while(n)
        {
            int a = n % 10;
            n /= 10;
            sum += a*a;
        }
        return sum;
    }
};

11.盛最多水的容器

在这里插入图片描述
在这里插入图片描述

算法原理：

解法1：暴力枚举，O(N*N)。这应该是大家心中第一个闪过的想法，就是使用两层for循环计算出全部体积，再求出最大值。但是这个解法超时。

解法2：利用单调性，使用双指针，O(N)
首先观察一个规律：
我们固定一个数，再向外枚举，会出现下面的情况，结果都是缩小，就可以把这个数直接抹去，避免无用枚举。
在这里插入图片描述
所以可以把这个规律推广到全部数据：
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/a1dee81bedce4fab936c08ca8ba7f279.png
定义两个指针指向开头和结尾，此时可以计算出一个体积，根据上面的规律把较小的那个高度直接舍去，指针向里缩，继续计算体积…，直到两个指针相遇，统计出最大体积。

细节/技巧问题：

体积= 高度 * 宽度。根据木桶原理，高度是小的那个，而宽度是两个下标相减。

代码实现：

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int cur1 = 0, cur2 = height.size() -1;
        int maxV = 0;
        while(cur1 <= cur2)
        {
            int H = min(height[cur1], height[cur2]);
            maxV = max(maxV, (cur2 - cur1) * H);
            // 利用单调性
            if(height[cur1] < height[cur2]) cur1++;
            else cur2--;
        }
        return maxV;
    }
};

611.有效三角形的个数

在这里插入图片描述
在这里插入图片描述

算法原理：

首先补充一个数学知识，只要一次判断，得出是否能构成三角形：

若a <= b <= c 且 a +b > c，则可以构成三角形。
所以可以得出一个优化：先把数组排序，O(N*logN)。

数组排完序后：

解法1：暴力枚举，O(N*logN + N^3)，三层for循环，绝对超时。

解法2：利用单调性，使用双指针算法,O(N*logN + N^2)。
(1) 先用c固定最大的元素，定义left 和right分别指向第一个元素，c的下一个元素。
(2) 若nums[left] + nums[right] > nums[c]，由于left和 right之间的数都比 nums[left] 大，与 nums[right] 相加后一定大于c，构成三角形了，就不要一个个枚举了，直接right- -。
(3) 此时三角形个数 = right - left。
(4) 若nums[left] + nums[right] <= nums[c]，由于left和 right之间的数都比 nums[right] 小，与 nums[left] 相加后一定小于c，也不要一个个枚举了，直接left++。
(5) 以上是走完一趟的个数，再c–，固定下一个数。
在这里插入图片描述

代码实现：

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
    	// 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        int ret = 0; // 记录个数
        for(int c = n-1; c >= 2; c--)
        {
            int left = 0, right = c - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[c])
                {
                    ret += right - left;
                    right--;
                } 
                else left++;
            }
        }
        return ret;
    }
};

LRC179.和为s的两个数

在这里插入图片描述
在这里插入图片描述

算法原理：

解法1：暴力枚举，两层for循环，O(N^2)，绝对超时。没有好好利用单调递增这个特性!!

解法2：和上一题的解法2类似，也是利用单调性和双指针算法，O(N)。
在这里插入图片描述

细节/技巧问题：

找到数对后就直接 break 结束循环。

代码实现：

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

15.三数之和

在这里插入图片描述
在这里插入图片描述

算法原理：

解法1：排序+暴力枚举+利用set去重，O(N^3).

解法2：排序+双指针，O(N^2).
这道题其实是上一题的进阶版，首先排序，再固定一个数 a，在该数后面的区间内使用双指针算法快速的找到两个数的和是 -a。
在这里插入图片描述

难点/细节/技巧：

这道题的算法不难想，难的是保证不重不漏。

(1) 去重操作有两个方面：一是找到一种结果后，left 和 right 指针要跳过重复元素，二是当使用完一次双指针后，i 也需要跳过重复元素，此时要注意越界。
(2) 还有一个小优化就是当固定的那个数是正数时，后面再也找不到两数和为负数了，直接结束。

代码实现：

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        // 排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();

        for(int i = 0; i <= n-3; i++) // 固定数 a
        {
            if(nums[i] > 0) break; // 小优化
            int left = i +1, right = n-1, a = nums[i];
            // 双指针
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > -a) right--;
                else if(sum < -a) left++;
                else 
                {
                    vv.push_back({nums[i], nums[left], nums[right]});
                    // 去重，注意越界
                    while(left < right && nums[left] == nums[left+1]) left++;
                    while(left < right && nums[right] == nums[right-1]) right--;

                    left++;
                    right--;
                }
            }
            while(i < n-1 && nums[i] == nums[i+1]) i++;
        }
        return vv;
    }
};

18.四数之和

在这里插入图片描述
在这里插入图片描述

算法原理：

本道题又是上一题的进阶版。

在这里插入图片描述

难点/细节/技巧：

这道题会出现数据溢出的风险。所以当计算两个固定是数之和时，类型定义为 long long。
其余细节参考上一题。

代码实现：

class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        // 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> vv;
        for(int i = 0; i < n; i++) // 固定数a
        {
            // 三数和
            for(int j = i+1; j < n; j++)// 固定数b
            {
                // 双指针算法
                int left = j+1, right = n-1;
                long long t = (long long)target - (nums[i] + nums[j]);
                while(left < right)
                {
                    long long sum = nums[left] + nums[right];
                    
                    if(sum > t) right--;
                    else if(sum < t) left++;
                    else
                    {
                        vv.push_back({nums[i], nums[j], nums[left], nums[right]});
                        // 去重
                        while(left < right && nums[left] == nums[left+1]) left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }
                while(j < n-1 && nums[j] == nums[j+1]) j++;
            }
            while(i < n-1 && nums[i] == nums[i+1]) i++;
        }
        return vv;
    }
};

三，算法总结

双指针算法是一种基础，但是十分经典的算法。通过上面的若干道题可知，"双指针"使用起来是十分灵活的，有时代指数组下标，有时也可以代指一个数。使用双指针算法的关键之一就是要控制好边界，稍不留神就会出现数组越界的问题，并且在使用这个算法时强烈建议各位一定要多画图，光靠想象容易出错并且会忽略很多细节问题。


http://www.kler.cn/news/293503.html

相关文章：

  • 【Hadoop|HDFS篇】DataNode
  • 梯度弥散问题及解决方法
  • C++ Dll 库 的创建与使用方法记录
  • 打造安心宠物乐园：EasyCVR平台赋能猫咖/宠物店的智能视频监控解决方案
  • Linux——进程概念
  • 数据结构（邓俊辉）学习笔记】排序 2——快速排序：性能分析
  • springboot项目引入Sentinel熔断
  • SpringBoot和Mybatis框架怎么防止SQL注入
  • 轴承知识大全，详细介绍（附3D图纸免费下载）
  • Codeforces Round 970 (Div. 3)(ABCDEF)
  • LLVM IR指令VM混淆分析
  • 【LeetCode面试150】——205同构字符串
  • 解决解压缩时的错误提示 “无法成功完成操作, 因为文件包含病毒或者潜在垃圾文件“
  • 论文解读 | KDD2024 演化图上的森林矩阵快速计算
  • 【OpenCV1】虚拟环境的使用、opencv的使用、图像和视频的创建和显示
  • 政府招商引资管理数字化平台：渠道、意向客户、项目管理、招商载体、绩效一体化管理平台
  • Spring MVC思想 实践开发 核心组件 流程分析
  • 【go-zero】win启动rpc服务报错 panic: context deadline exceeded
  • 设计模式学习-命令模式
  • HTTP 方法
  • Redis 的内存淘汰策略详解
  • 电机驱动及编码器测速（基于STM32F103C8T6HAL库）
  • ARM32开发——GD32F4 DMA功能查询
  • windows手工杀毒-寻找可疑进程之线程
  • 如何在Selenium中使用Chrome DevTools进行交互
  • python的sqlalchemy使用@contextmanager来定义上下文管理器
  • shell脚本编程（正则表达式与grep +awk+sed+expect详解）
  • OpenCV中的颜色映射函数
  • [pytorch] --- pytorch基础之损失函数与反向传播
  • VUE3父子组件传参