【优选算法】—— 双指针问题

这篇具有很好参考价值的文章主要介绍了【优选算法】—— 双指针问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

从今天开始,整个暑假期间。我将不定期给大家带来有关各种算法的题目,帮助大家攻克面试过程中可能会遇到的算法这一道难关。


目录

(一) 基本概念

(二)题目讲解

1、难度:easy

1️⃣移动零

2️⃣复写零

2、难度:medium

1️⃣快乐数

2️⃣盛⽔最多的容器

3、难度:difficult

2️⃣最大得分

总结


(一) 基本概念

双指针算法是一种常用的算法技巧,它通常用于在数组或字符串中进行快速查找、匹配、排序或移动操作。双指针算法使用两个指针在数据结构上进行迭代,并根据问题的要求移动这些指针。

常⻅的双指针有两种形式:

  • ⼀种是对撞指针
  • ⼀种是左右指针
     

对撞指针:⼀般⽤于顺序结构中,也称左右指针。
• 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。
• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环),也就是:
          ◦ left == right (两个指针指向同⼀个位置)
          ◦ left > right (两个指针错开)



快慢指针:⼜称为⻳兔赛跑算法,其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动


这种⽅法对于处理环形链表或数组⾮常有⽤。


其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使⽤快慢指针的思想。


快慢指针的实现⽅式有很多种,最常⽤的⼀种就是:
        • 在⼀次循环中,每次让慢的指针向后移动⼀位,⽽快的指针往后移动两位,实现⼀快⼀慢
 

【优势】 

  1. 双指针算法的优势在于它们能够在一次迭代中完成操作,时间复杂度通常比较低,并且不需要额外的空间;
  2. 通过合理地移动指针,可以有效地减少不必要的计算和比较,提高算法的效率。

在具体应用双指针算法时,需要根据问题的特点和要求选择合适的指针移动策略,确保算法的正确性和高效性。同时,注意处理边界条件和特殊情况,以避免错误和异常。


(二)题目讲解

接下来,我们通过几道题目让大家具体的感受一下。(题目由易到难

1、难度:easy

1️⃣移动零

链接如下:283. 移动零
【题⽬描述】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 【解法】(快排的思想:数组划分区间-数组分两块

算法思路:

  1. 在本题中,我们可以⽤⼀个 cur 指针来扫描整个数组,另⼀个 dest 指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur 在扫描的过程中,遇到的不同情况,分类处理,实现数组的划分。
  2. 在 cur 遍历期间,使 [0, dest] 的元素全部都是⾮零元素, [dest + 1, cur - 1] 的元素全是零

【算法流程】

a. 初始化 cur = 0 (⽤来遍历数组),dest = -1 (指向⾮零元素序列的最后⼀个位置。
因为刚开始我们不知道最后⼀个⾮零元素在什么位置,因此初始化为  -1 )


b. cur 依次往后遍历每个元素,遍历到的元素会有下⾯两种情况:


    i. 遇到的元素是 0 , cur 直接 ++ 。因为我们的⽬标是让 [dest + 1, cur - 1] 内
的元素全都是零,因此当 cur 遇到 0 的时候,直接 ++ ,就可以让 0 在 cur - 1
的位置上,从⽽在 [dest + 1, cur - 1] 内;
    ii. 遇到的元素不是 0 , dest++ ,并且交换 cur 位置和 dest 位置的元素,之后让cur++ ,扫描下⼀个元素。

  •  因为 dest 指向的位置是⾮零元素区间的最后⼀个位置,如果扫描到⼀个新的⾮零元素,那么它的位置应该在 dest + 1 的位置上,因此 dest 先⾃增 1 ;
  •  dest++ 之后,指向的元素就是 0 元素(因为⾮零元素区间末尾的后⼀个元素就是0 ),因此可以交换到 cur 所处的位置上,实现 [0, dest] 的元素全部都是⾮零元素, [dest + 1, cur - 1] 的元素全是零。

【算法实现】

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

【结果展示】

【优选算法】—— 双指针问题,LeetCode 热题,算法 【性能分析】

具体的性能分析如下:

  • 时间复杂度:代码中使用了一个循环来遍历数组,因此时间复杂度为 O(n),其中 n 是数组的长度。
  • 空间复杂度:代码中没有使用额外的空间,只是通过交换数组元素的方式来实现移动,所以空间复杂度为 O(1)

该算法的性能较好,处理速度快,且空间开销较小。由于只进行一次遍历,并且只进行元素交换操作,因此在大多数情况下,时间复杂度为线性级别。然而,在某些特殊情况下,比如数组中几乎所有元素都是非零元素时,仍需要遍历整个数组,但交换操作的次数会减少。

 


2️⃣复写零
 

链接如下:1089. 复写零

【题⽬描述】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

【解法】(原地复写---双指针

  • 算法思路:

① 如果「从前向后」进⾏原地复写操作的话,由于 0 的出现会复写两次,导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。


② 但是「从后向前」复写的时候,我们需要找到「最后⼀个复写的数」,因此我们的⼤体流程分两步:

  • 先找到最后⼀个复写的数;
  • 然后从后向前进⾏复写操作
     

 

【算法流程】

a. 初始化两个指针 cur = 0 , dest = 0 ;


b. 找到最后⼀个复写的数:
   i. 当 cur < n 的时候,⼀直执⾏下⾯循环:
        • 判断 cur 位置的元素:
                ◦ 如果是 0 的话, dest 往后移动两位;
                ◦ 否则, dest 往后移动⼀位。
        • 判断 dest 时候已经到结束位置,如果结束就终⽌循环;
        • 如果没有结束, cur++ ,继续判断。


c. 判断 dest 是否越界到 n 的位置:
        i. 如果越界,执⾏下⾯三步:
                1. n - 1 位置的值修改成 0 ;
                2. cur 向移动⼀步;
                3. dest 向前移动两步。


d. 从 cur 位置开始往前遍历原数组,依次还原出复写后的结果数组:
        i. 判断 cur 位置的值:
                1. 如果是 0 : dest 以及 dest - 1 位置修改成 0 , dest -= 2 ;
                2. 如果⾮零: dest 位置修改成 0 , dest -= 1 ;
        ii. cur-- ,复写下⼀个位置

【算法实现】

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1. 先找到最后⼀个数
        int cur = 0, dest = -1, n = arr.size();
        while(cur < n)
        {
            if(arr[cur]) dest++;
            else dest += 2;
            if(dest >= n - 1) break;
            cur++;
        }
        // 2. 处理⼀下边界情况
        if(dest == n)
        {
            arr[n - 1] = 0;
            cur--; dest -=2;
        }
        // 3. 从后向前完成复写操作
        while(cur >= 0)
        {
            if(arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

【结果展示】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

【性能分析】

具体的性能分析如下:

  • 时间复杂度:代码中使用了两个循环,第一个循环用于找到最后一个数、处理边界情况,第二个循环用于从后向前完成复写操作。由于第二个循环是针对数组长度的常数倍进行的操作,因此时间复杂度为 O(n),其中 n 是数组的长度。
  • 空间复杂度:代码中没有使用额外的空间,只是通过修改原数组实现复写操作,所以空间复杂度为 O(1)

该算法的性能较好,时间复杂度为线性级别,空间开销较小。在最坏情况下,需要遍历整个数组进行复写操作,但仍保持了线性时间复杂度。


2、难度:medium


1️⃣快乐数
 

链接如下:202. 快乐数

【题⽬描述】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

【解法】(快慢指针)

使用双指针的算法判断快乐数的基本思路如下:

  1. 定义两个指针,一个指针快指针(fast)每次向前移动两步,一个慢指针(slow)每次向前移动一步。
  2. 将给定的正整数转换为字符串形式。
  3. 在一个循环中,不断计算当前数字的各个位上的数字的平方和。
  4. 将得到的平方和作为下一个数字,继续计算平方和,直到平方和等于 1,或者出现循环。
  5. 判断循环是否发生,如果发生循环并且平方和不等于 1,说明该数字不是快乐数。

【算法流程】

a. 初始化快慢指针为给定的正整数。

b. 在一个循环中,计算快慢指针指向的数字的各个位上的数字的平方和,并将结果赋值给快指针。

c. 同时,慢指针移动一步。

d. 检查快指针和慢指针是否指向同一个数字,如果是,则说明存在循环,退出循环。

e. 如果快指针指向的数字等于 1,则说明是快乐数,返回 true。

f. 否则,将慢指针指向的数字赋值给快指针,重复步骤 b-e。

g. 如果循环结束仍未找到快乐数,则返回 false。

【算法实现】

class Solution {
public:
    int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

    bool isHappy(int n) {
        int slow = n;
        int fast = getNext(n);

        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }

        return fast == 1;
    }
    
};

【结果展示】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

【性能分析】

具体的性能分析如下:

  1. 时间复杂度:

    • 在计算下一个数字的过程中,需要遍历每个数字的位数,因此时间复杂度为 O(logn),其中 n 是给定的数字。
    • 快慢指针在循环中遍历数字,直到找到结果或者出现循环。最坏情况下,循环次数是一个数字中各个位数的总和,也就是 O(logn)。
    • 因此,总体时间复杂度为 O(logn)
  2. 空间复杂度:只使用了常量级别的额外空间,不随输入规模变化,因此空间复杂度为 O(1)


 

2️⃣盛⽔最多的容器
 

链接如下:11. 盛最多水的容器

【题⽬描述】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

【解法】(对撞指针)

  • 首先,初始时左指针指向数组的起始位置,右指针指向数组的结束位置。计算当前区间内的容器的盛水量,并更新最大盛水量。
  • 接着,判断两个指针所指向的元素的高度,将较小的元素的指针向内移动一步。这样可以保证每次移动都在选择更高的边界线,以获得可能的更大盛水量。
  • 重复上述步骤,直到两个指针相遇,即左指针大于等于右指针。此时遍历完成,返回最大盛水量。

【算法流程】

a.初始化最大盛水量 maxArea 为 0,左指针 left 指向数组起始位置,右指针 right 指向数组结束位置。

b.进入循环,判断条件为左指针小于右指针。

       ◦   计算当前区间的宽度、最小高度以及当前盛水量。

       ◦   更新最大盛水量,取当前盛水量与历史最大盛水量的较大值。

       ◦   判断两个指针所指向元素的高度,将较小元素的指针向内移动一步。

c. 循环结束后,返回最大盛水量作为结果。

【算法实现】

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int left = 0;
        int right = height.size() - 1;

        while (left < right) {
            int width = right - left;
            int minHeight = min(height[left], height[right]);
            int v = width * minHeight;
            res = max(res, v);

            if (height[left] < height[right]) {
                left++;
            } 
            else {
                right--;
            }
        }

        return res;
    }
};

【结果展示】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

【性能分析】

具体的性能分析如下:

  • 时间复杂度分析:对撞指针移动的过程中,每次都排除了一部分区域,因此时间复杂度为 O(n),其中 n 是数组的长度。
  • 空间复杂度分析:该算法只使用了常数级别的额外空间,存储了少量的变量和指针。因此,空间复杂度为 O(1),与输入规模无关。

3、难度:difficult

2️⃣最大得分

链接如下:1537. 最大得分

【题⽬描述】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

【算法流程】

  1. 初始化双指针 ij 分别为 0,并初始化两个变量 sum1sum2 用于记录当前路径的和,初始化 res 用于记录最大得分。

  2. 在循环中,比较当前指针位置上 nums1[i]nums2[j] 的值:

    • 如果 nums1[i] < nums2[j],则将 nums1[i] 加到 sum1 中,并将指针 i 向后移动一位。
    • 如果 nums1[i] > nums2[j],则将 nums2[j] 加到 sum2 中,并将指针 j 向后移动一位。
    • 如果 nums1[i] 和 nums2[j] 相等,意味着遇到了相同的值,此时需要考虑路径的切换。比较 sum1 和 sum2 的大小,将较大的值加到 res 中,并将 sum1 和 sum2 清零。然后将 nums1[i] 加到 res中,同时将指针 i 和 j 向后移动一位。
  3. 循环结束后,可能还会存在剩余未遍历的元素。此时,需要将剩余路径的和加到 res中。

  4. 返回 res % num,即对 10^9 + 7 取余后的最大得分。

 

【算法实现】

class Solution {
public:
    const int num = 1e9 + 7;

    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        int i = 0, j = 0;
        long long sum1 = 0, sum2 = 0;  // 使用 long long 类型防止整数溢出
        long long res = 0;

        while (i < n1 && j < n2) {
            if (nums1[i] < nums2[j]) {
                sum1 += nums1[i++];
            } 
            else if (nums1[i] > nums2[j]) {
                sum2 += nums2[j++];
            } 
            else {                     // 遇到相同值,取两个路径中的较大值
                res += max(sum1, sum2) + nums1[i];
                sum1 = 0, sum2 = 0;
                
                i++;
                j++;
            }
        }

        // 处理剩余的元素
        while (i < n1) {
            sum1 += nums1[i++];
        }
        while (j < n2) {
            sum2 += nums2[j++];
        }

        res += max(sum1, sum2);  // 加上剩余路径的和

        return res % num;
    }
};

【结果展示】

【优选算法】—— 双指针问题,LeetCode 热题,算法

 

 【性能分析】

具体的性能分析如下:

  • 时间复杂度分析: O(n1 + n2),其中 n1 和 n2 分别是两个输入数组的长度。因为我们同时遍历了两个数组,所以时间复杂度与两个数组的总长度成线性关系。
  • 空间复杂度分析: O(1),只使用了几个变量来保存结果,所以额外空间是固定的,不会随输入规模增加而增加。

总结

以上便是本期关于双指针算法的全部讲解内容。如果大家掌握了上述知识,再去勤加练习的话我相信以后在遇到此类问题都可迎刃而解。文章来源地址https://www.toymoban.com/news/detail-546330.html

到了这里,关于【优选算法】—— 双指针问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode热题100 【cpp】题解(一)哈希表和双指针

    题单链接: LeetCode 热题 100 leetcode题目链接 题解1:暴力枚举 时间复杂度: O ( n 2 ) O(n^2) O ( n 2 ) 题解2:哈希表 时间复杂度: O ( n ) O(n) O ( n ) 使用hash表来存target - x的差值的下标。这里使用cpp里面的 unordered_map ,它的查找效率为 O ( 1 ) O(1) O ( 1 ) 补充 unordered_map 查找key的方法:

    2024年02月09日
    浏览(28)
  • 【优选算法】专题1 -- 双指针 -- 复写0

    前言: 补充一下前文没有写到的双指针入门知识:专题1 -- 双指针 -- 移动零 目录 基础入门知识: 1. 复写零(easy) 1. 题⽬链接:1089.复习0 - 力扣(LeetCode) 2. 题⽬描述: 3.算法原理: 异地操作 本地操作 【从后向前的复写过程】 整体思路: 🎯1.先找到最后一个“复写”的

    2024年04月17日
    浏览(33)
  • 【优选算法】双指针 -- 快乐数 和 盛最多水的容器

    前言: 🎯个人博客:Dream_Chaser 🎈刷题专栏:优选算法篇 📚本篇内容:03快乐数 和 04盛最多水的容器 目录 一、快乐数(medium) 1. 题⽬链接:202. 快乐数 2. 题⽬描述: 3. 题⽬分析: 4.算法原理 二、盛最多水的容器 1. 题⽬链接:11.盛最多水的容器 - 力扣(LeetCode) 2. 题⽬描述

    2024年04月17日
    浏览(34)
  • 《热题100》字符串、双指针、贪心算法篇

    思路:对于输入的的字符串,只有三种可能,ipv4,ipv6,和neither ipv4:四位,十进制,无前导0,小于256 ipv6:八位,十六进制,无多余0(00情况不允许),不为空 class Solution:     def solve(self , IP: str) - str:         if \\\'.\\\' in  IP: #有可能是IPV4             res = IP.split(\\\'.\\\')            

    2024年02月09日
    浏览(43)
  • 【LeetCode 热题 100】矩阵 专题(大多原地算法,需要一定思维)

    解题思路 在 代码注释中!

    2024年02月15日
    浏览(51)
  • 【优选算法】—— 滑动窗口类问题

    本期,我给大家带来的是关于滑动窗口类算法的介绍,并通过具体的题目帮助大家思考理解。     目录 (一)基本概念 (二)题目讲解 1、难度:medium 1️⃣长度最小的子数组 2️⃣找到字符串中所有字⺟异位词 2、难度:hard 1️⃣最⼩覆盖⼦串 2️⃣串联所有单词的⼦串 总

    2024年02月02日
    浏览(52)
  • 【算法优选】 动态规划之路径问题——贰

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的

    2024年02月05日
    浏览(49)
  • 【算法优选】 动态规划之简单多状态dp问题——贰

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表示 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格 设计一个算法计算出最大利润。在满足以下约束条件下,

    2024年04月12日
    浏览(35)
  • 【优选算法专栏】专题十六:BFS解决最短路问题---前言

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:算法从入门到精通 🚚代码仓库:小小unicorn的代码仓库

    2024年04月15日
    浏览(51)
  • Leetcode | 对撞指针算法笔记

    对撞指针的基本思想是在 数组或链表等数据结构 中使用两个指针( left 或 right 、 start 或 end 等表示),分别从不同的方向(通常是数组的两端)移动,以便有效地进行 搜索、遍历或判断 。 对撞指针常见的运用场景包括: 排序数组的查找 :对撞指针可以用于在已排序的数

    2024年02月12日
    浏览(86)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包