【leetcode】双指针算法题

文章目录

  • 1.算法思想
  • 2.移动零
  • 3.复写零
    • 方法一
    • 方法二
  • 4.快乐数
  • 5.盛水最多的容器
    • 方法一（暴力求解）
    • 方法二（左右指针）
  • 6.有效三角形的个数
    • 方法一（暴力求解）
    • 方法二（左右指针）
  • 7.两数之和
  • 8.三数之和
  • 9.四数之和

在这里插入图片描述

1.算法思想

常见的双指针有两种形式，⼀种是左右指针，⼀种是快慢指针。

  1. 左右指针：⼀般用于有序的结构中，也称左右指针。
  • 左右指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
  • 左右指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
    left == right （两个指针指向同⼀个位置）
    left > right (两个指针错开）
  1. 快慢指针：⼜称为龟兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
    这种方法对于处理环形链表或数组非常有用。
    其实不单单是环形链表或者是数组，如果研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
    快慢指针的实现⽅式有很多种，最常用的⼀种就是：
  • 在⼀次循环中，每次让慢的指针向后移动⼀位，而快的指针往后移动两位，实现⼀快⼀慢。

废话不多说，我们来做题。

2.移动零

在这里插入图片描述
leetcode 283.移动零

题目要求我们将数组中的0全部移动到数组的末尾，并且其它元素的相对顺序不变，而且不允许开辟额外的数组。
那我们应该如何来解决这一题呢？

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

最初，我们不知道非零序列的位置，所以将dest置为-1，cur置为0。cur进行扫描，在扫描过程中：

  • 若cur对应元素不为0，cur后移
  • 若cur对应元素为0，dest先后移，然后再交换cur与dest，最后cur再后移。

在这里插入图片描述

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int dest = -1;
        int cur = 0;
        int n = nums.size();
        while(cur < n)
        {
            //cur不为0，交换
            if(nums[cur] != 0)
            {
                dest++;
                swap(nums[dest],nums[cur]);
            }
            //cur为0,继续后移
            cur++;
        }
    }
};

这样咱们就过啦。
在这里插入图片描述

3.复写零

在这里插入图片描述
leetcode 1089.复写零

方法一

先统计数组中0的个数，计算复写后数组的大小，使用reserve为数组重新开新的空间，在新空间上直接进行复写，不存在数组越界问题；在复写完成后，再使用对数组进行缩容，使其空间保持原状。

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int count = 0;
        int n = arr.size();
        int cur = 0;
        while(cur < n)
        {
            if(arr[cur] == 0)
                count++;
            cur++;
        }
        //开辟新空间
        arr.reserve(n+count);
        //此时cur == n,
        cur--;//重新指向最后一个元素
        int dest = n+count-1;
        
        while(cur >= 0)
        {
            if(arr[cur])
            {
                //不是0，无需复写
                arr[dest--] = arr[cur--];
            }
            else
            {
                //复写0
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
        arr.reserve(n);//恢复数组原状
    }
};

在这里插入图片描述
简单分析一下复杂度：只遍历了数组，时间复杂度为O(N)；由于使用了reserve开辟了新空间，空间复杂度：O(N)

方法二

能不能在O(1)的空间复杂度下完成该题呢？

我们可以使用两个指针，cur指向最后一个要写的元素，dest指向数组的最后一个位置。

  • 若cur为0，复写0，dest移动两次
  • 若cur不为0，复写，dest移动一次

那现在的问题就是如何找最后一个要复写的位置。
通过模拟我们可以发现，cur = 0 ,dest = -1；让cur与dest同时走，若cur不为0，则都移动一次；若cur为0，cur移动一次，dest移动两次；直到dest走到数组的末尾，此时cur位置就是最后一个要写的位置

在这里插入图片描述

public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.size();
        while(dest < n-1)
        {
            if(arr[cur] == 0)
                dest += 2;
            else
                dest++;
            cur++;
            }
        }
        for( ; cur >=0; cur--)
        {
            if(arr[cur])
                arr[dest--] = arr[cur];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }
    }
};

在这里插入图片描述
此时我们发现程序没过，情况又没想全

在这里插入图片描述

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.size();
        while(cur < n)
        {
            if(arr[cur] == 0)
                dest += 2;
            else
                dest++;
            //防止越界
            if(dest >= n-1)
                break;
            cur++;
            
        }
        //已经越界，修正
        if(dest == n)
        {
            arr[n-1] = 0;
            dest-=2;
            cur--;
        }
        //从后向前复写
        for( ; cur >=0; cur--)
        {
            if(arr[cur])
                arr[dest--] = arr[cur];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }
    }
};

在这里插入图片描述

此时，该代码地时间复杂度为O(N)；空间复杂度为：O(1)

4.快乐数

在这里插入图片描述
leetcode 202.快乐数

根据题意，通过画图我们可以发现，这就是一种循环往复地题目。此时我们就可以考虑双指针算法。
在这里插入图片描述
看到这个环形，是不是会想起链表那里有一个判断环形链表的题目，这两题很相似。

我们可以知道，当重复执行x的时候，数据会陷⼊到⼀个「循环」之中。
而「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的（证明参考链表部分），也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是1，那么这个数⼀定是快乐数；如果相遇位置不是1的话，那么就不是快乐数。

class Solution {
public:
    int Sum(int n)
    {
        int sum = 0;
        while(n)
        {
            sum += (n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n;
        int fast = Sum(n);//让fast先走一步
        while(fast != slow)
        {
            slow = Sum(slow);
            fast = Sum(Sum(fast));
        }
        //当二者相等时，若为1，则是快乐数，否则则不是
        return slow == 1;
    }
};

5.盛水最多的容器

在这里插入图片描述
leetcode 11.盛水最多的容器
首先我们要明白，这个容器的容量是：两个柱子之间的距离×两柱中较矮的一个
所以此题我们可以利用双指针，寻找两柱中组成的容器中最大的一个即可。

方法一（暴力求解）

枚举出能构成的所有容器，找出其中容积最大的值。
容器容积的计算⽅式：
设两指针分别指向水槽板的最左端以及最右端，此时容器的宽度为j - i
由于容器的⾼度由两板中的短板决定，因此可得容积公式：v = (j - i) * min( height[i], height[j]）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int v = 0;
        int n = height.size();
        for(int i=0; i<n; i++)
        {
            for(int j = i+1; j<n; j++)
            {
                v = max(v,((j-i)*min(height[i],height[j])));
            }
        }
        return v;
    }
};

在这里插入图片描述

方法二（左右指针）

观察暴力解法以后，我们可以发现一个规律：
当使用最开始的左右区间算出来一个V1后，我们没必要使用这两个区间中较小的一个去和其它数枚举，因为枚举出来的结果一定是小于V1的。
在这里插入图片描述
所以，可以按照以下步骤：

  • 先根据当前两柱计算V
  • 舍去两柱子中较小的一个
  • 根据新的柱子再计算体积tmp，V = max(V,tmp)
class Solution {
public:
    int maxArea(vector<int>& height) {
        int v = 0;
        int left = 0;
        int right = height.size()-1;
        while(left < right)
        {
            //先计算当前两柱组成的大小
            int tmp = (right-left) * min(height[left],height[right]);
            v = max(v,tmp);
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        return v;
    }
};

6.有效三角形的个数

在这里插入图片描述

leetcode 611.有效三角形的个数

我们都知道，组成三角形的条件是：任意两边之和大于第三边。

方法一（暴力求解）

但是使用这个条件只想到一个暴力解法，虽然说是暴⼒求解，但是还是想优化⼀下
判断三⻆形的优化：

  • 如果能构成三⻆形，需要满⾜任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。
  • 因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三⻆形。
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int count = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                for(int k = j+1; k<n; k++)
                {
                    if(nums[i] + nums[j] > nums[k])
                        count++;
                }
            }
        }
        return count;
    }
};

方法二（左右指针）

将数组排序以后我们可以发现，如果我们固定最右侧数为第三条边，就只需使用左右指针找另外两条即可。
而且如果最左侧的数和右侧数加起来已经大于第三边了，那么左侧和右侧之间的数一定大于第三边，无需再枚举。

在这里插入图片描述

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //先按照升序排序
        sort(nums.begin(),nums.end());
        int max = nums.size() - 1;
        int ret = 0;

        //至少要存在3条边
        while(max >= 2)
        {
            int left = 0;
            int right = max - 1;

            while(left < right)
            {
                if(nums[left] + nums[right] > nums[max])
                {
                    ret += right - left;
                    right--;
                }
                else
                    left++;
            }
            max--;
        }
        return ret;
    }
};

7.两数之和

在这里插入图片描述
leetcode 179.和为target的两个数

由于该数组是升序的，那么我们可以直接使用双指针，计算左右指针之和

  • 若和小于target，左指针右移
  • 若和大于target，右指针左移

在这里插入图片描述

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

8.三数之和

在这里插入图片描述
leetcode 15.三数之和

这一题和上一题两数之和的解法非常类似，唯一的不同点就是：该题不允许有重复的三元组。

  • 先排序
  • 固定一个数aim
  • 使用两数之和法，找和为 - aim 的两个数即可
    • 不漏
      • 找到一个数以后，left++,right- -继续找
    • 去重
      • left 与right均需要去重，如果left++后任然和之前的相同，那就继续++；right同理，仍需要 - -
      • aim去重，如果aim移动后，仍然和上一个相等，那就继续移动

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int i = 0;
        while(i < n)
        {
            if(nums[i] > 0)//若num对应的都已经大于0，那么left 与right就更大，和不可能为0了
                break;
            int aim = -nums[i];//固定一个数，取其相反数
            int left = i+1;
            int right = n-1;
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > aim)
                    right--;
                else if(sum < aim)
                    left++;
                else
                {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    //避免遗漏，继续找
                    left++;
                    right--;
                    //left,right去重
                    while(left < right && nums[left] == nums[left-1])
                        left++;
                    while(left < right && nums[right] == nums[right+1])
                        right--;
                }
            }
            i++;
            while(i < n && nums[i] == nums[i-1])
                i++;
        }
        return ret;
    }
};

9.四数之和

在这里插入图片描述
leetcode 18.四数之和
该题是在三数之和的基础之上的变形。

仍然还是采用上面的做法，

  • 先排序
  • 固定一个数a
  • 利用三数之和，固定一个数b,找和为target - nums[a] - nums[b]的数
    • 不漏
      • 找到一个数以后，left++，right- -继续找
    • 去重
      • left 与right均需要去重，如果left++后任然和之前的相同，那就继续++；right同理，仍需要 - -
      • b去重，如果b移动后，仍然和上一个相等，那就继续移动
      • a去重，如果a移动后，仍然和上一个相等，那就继续移动
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        int a = 0;
        while(a < n)
        {
            int b = a+1;
            while(b < n)
            {
                long long aim = (long long)target -nums[a] - nums[b];
                int left = b+1;
                int right = n-1;
                while(left < right)
                {
                    if(nums[left] + nums[right] < aim)
                        left++;
                    else if(nums[left] + nums[right] > aim)
                        right--;
                    else
                    {
                        ret.push_back({nums[a],nums[b],nums[left],nums[right]});
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left-1])
                            left++;
                        while(left< right && nums[right] == nums[right+1])
                            right--;
                    }
                }
                b++;
                while(b < n && nums[b] == nums[b-1])
                    b++;
            }
            a++;
            while(a < n && nums[a] == nums[a-1])
                a++;
        }
        return ret;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/774906.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ONLYOFFICE 8.1版本震撼来袭，让办公更高效、更智能

ONLYOFFICE 8.1版本震撼来袭，让办公更高效、更智能

官网链接&#xff1a; 在线PDF查看器和转换器 | ONLYOFFICE 在线办公套件 | ONLYOFFICE 随着科技的不断发展&#xff0c;办公软件已经成为现代企业提高工作效率、实现信息共享的重要工具。在我国&#xff0c;一款名为ONLYOFFICE的在线办公套件受到了越来越多企业的青睐。今天…
阅读更多...
Prompt-Free Diffusion: Taking “Text” out of Text-to-Image Diffusion Models

Prompt-Free Diffusion: Taking “Text” out of Text-to-Image Diffusion Models

CVPR2024 SHI Labshttps://arxiv.org/pdf/2305.16223https://github.com/SHI-Labs/Prompt-Free-Diffusion 问题引入 在SD模型的基础之上&#xff0c;去掉text prompt&#xff0c;使用reference image作为生成图片语义的指导&#xff0c;optional structure image作为生成图片…
阅读更多...
深入理解【 String类】

深入理解【 String类】

目录 1、String类的重要性 2、常用方法 2、1 字符串构造 2、2 String对象的比较 2、3 字符串查找 2、4字符转换 数值和字符串转换&#xff1a; 大小写转化&#xff1a; 字符串转数组&#xff1a; 格式转化&#xff1a; 2、5 字符串替换 2、6字符串拆分 2、7 字符串…
阅读更多...
知名品牌因商标痛失市场：114家直营店山寨店7000多家！

知名品牌因商标痛失市场：114家直营店山寨店7000多家！

奶茶知名品牌“鹿角巷”当年红遍大江南北&#xff0c;是最早的新茶饮品牌&#xff0c;但是当年商标注册存在问题&#xff0c;被同行奶茶品牌抢占了先机&#xff0c;发声明“对大陆商标注册细则不详&#xff0c;在商标注册过程中让假店钻了法律空档”&#xff0c;最夸张的时候全…
阅读更多...
python如何不保留小数

python如何不保留小数

1、int() 向下取整&#xff08;内置函数&#xff09; n 3.75 print(int(n)) >>> 3 n 3.25 print(int(n)) >>> 3 2、round() 四舍五入&#xff08;内置函数&#xff09; n 3.75 print(round(n)) >>> 4 n 3.25 print(round(n)) >>> 3 …
阅读更多...
JavaScript(5)——数据类型和类型检测

JavaScript(5)——数据类型和类型检测

字符串类型String 通过单引号&#xff08; &#xff09;、双引号(" "&#xff09;或反引号&#xff08; &#xff09;都叫字符串&#xff0c;单引号和双引号本质上没有区别&#xff0c;一般使用单引号。 注意&#xff1a; 无论单引号或是双引号必须成对使用单引号和…
阅读更多...
人工智能系列-NumPy（二）

人工智能系列-NumPy（二）

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 链接数组 anp.array([[1,2],[3,4]]) print(第一个数组&#xff1a;) print(a) print(\n) bnp.array([[5,6],[7,8]]) print(第二个数组&#xff1a;) print(b) print(\n) print…
阅读更多...
PHP智慧门店微信小程序系统源码

PHP智慧门店微信小程序系统源码

&#x1f50d;【引领未来零售新风尚】&#x1f50d; &#x1f680;升级启航&#xff0c;智慧零售新篇章&#x1f680; 告别传统门店的束缚&#xff0c;智慧门店v3微信小程序携带着前沿科技与人性化设计&#xff0c;正式启航&#xff01;这个版本不仅是对过往功能的全面优化&a…
阅读更多...
【trition-server】运行一个pytorch的ngc镜像

【trition-server】运行一个pytorch的ngc镜像

ngc 提供了pytorch容器 号称是做了gpu加速的 我装的系统版本是3.8的python，但是pytorch似乎是用conda安装的3.5的： torch的python库是ls支持gpu加速是真的 英伟达的pytorch的说明书 root@a79bc3874b9d:/opt/pytorch# cat NVREADME.md PyTorch ======= PyTorch is a python …
阅读更多...
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树

【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树

目录 1 -> 底层结构 2 -> AVL树 2.1 -> AVL树的概念 2.2 -> AVL树节点的定义 2.3 -> AVL树的插入 2.4 -> AVL树的旋转 2.5 -> AVL树的验证 2.6 -> AVL树的性能 1 -> 底层结构 在上文中对对map/multimap/set/multiset进行了简单的介绍&…
阅读更多...
C++基础21 二维数组及相关问题详解

C++基础21 二维数组及相关问题详解

这是《C算法宝典》C基础篇的第21节文章啦~ 如果你之前没有太多C基础&#xff0c;请点击&#x1f449;C基础&#xff0c;如果你C语法基础已经炉火纯青&#xff0c;则可以进阶算法&#x1f449;专栏&#xff1a;算法知识和数据结构&#x1f449;专栏&#xff1a;数据结构啦 ​ 目…
阅读更多...
短视频父亲：成都柏煜文化传媒有限公司

短视频父亲：成都柏煜文化传媒有限公司

短视频父亲&#xff1a;镜头背后的温情与力量 在这个信息爆炸的时代&#xff0c;短视频以其短小精悍、直观生动的特点&#xff0c;迅速占据了人们碎片化的时间&#xff0c;成为情感交流与文化传播的重要平台。而在这些纷繁复杂的短视频中&#xff0c;有一类内容尤为触动人心—…
阅读更多...
如何让自动化测试更加灵活简洁？

如何让自动化测试更加灵活简洁？

简化的架构对于自动化测试和主代码一样重要。冗余和不灵活性可能会导致一些问题&#xff1a;比如 UI 中的任何更改都需要更新多个文件&#xff0c;测试可能在功能上相互重复&#xff0c;并且支持新功能可能会变成一项耗时且有挑战性的工作来适应现有测试。 页面对象模式如何理…
阅读更多...
ELK日志系统和Filebeat采集器的学习总结

ELK日志系统和Filebeat采集器的学习总结

ELK是ElasticSerach、Logstash、Kina Logstash负责采集数据&#xff0c;Logstash有三个插件&#xff0c;input、filter、output&#xff0c;filter插件作用是对采集的数据进行处理&#xff0c;过滤的&#xff0c;因此filter插件可以选&#xff0c;可以不用配置。 ElasticSear…
阅读更多...
ASUS/华硕枪神5 G533Q G733Q系列 原厂win10系统 工厂文件 带F12 ASUS Recovery恢复

ASUS/华硕枪神5 G533Q G733Q系列 原厂win10系统 工厂文件 带F12 ASUS Recovery恢复

华硕工厂文件恢复系统 &#xff0c;安装结束后带隐藏分区&#xff0c;一键恢复&#xff0c;以及机器所有驱动软件。 系统版本&#xff1a;Windows10 原厂系统下载网址&#xff1a;http://www.bioxt.cn 需准备一个20G以上u盘进行恢复 请注意&#xff1a;仅支持以上型号专用…
阅读更多...
Facebook广告被拒：常见原因以及避免屏蔽的方法

Facebook广告被拒：常见原因以及避免屏蔽的方法

大多数情况下&#xff0c;广告被屏蔽是因为违反了规则&#xff0c;这不仅仅是因为审核因素。有些规则并不明显&#xff0c;也没有在任何地方指定。例如&#xff0c;在广告中使用广告政策中未列出的停用词&#xff1b;审核算法确定照片描绘的模特过于暴露。下面小编将为你介绍Fa…
阅读更多...
鸿蒙系统的开发与学习

鸿蒙系统的开发与学习

1.开发工具的下载 DevEco Studio-HarmonyOS Next Beta版-华为开发者联盟 安装、环境配置时&#xff0c;建议 自定义目录 注意&#xff1a;路径中不要有 中文、特殊字符。 2.ArkTS基础总结 1&#xff09;三种数据类型 ① string 字符串&#xff1a;描述信息 ② number 数…
阅读更多...
【MySQL】mysql访问

【MySQL】mysql访问

mysql访问 1.引入MySQL 客户端库2.C/C 进行增删改3.查询的处理细节4.图形化界面访问数据库4.1下载MYSQL Workbench4.2MYSQL Workbench远程连接数据库 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&a…
阅读更多...
数据特征采样在 MySQL 同步一致性校验中的实践

数据特征采样在 MySQL 同步一致性校验中的实践

作者&#xff1a;vivo 互联网存储研发团队 - Shang Yongxing 本文介绍了当前DTS应用中&#xff0c;MySQL数据同步使用到的数据一致性校验工具&#xff0c;并对它的实现思路进行分享。 一、背景 在 MySQL 的使用过程中&#xff0c;经常会因为如集群拆分、数据传输、数据聚合等…
阅读更多...
C++ 仿QT信号槽二

C++ 仿QT信号槽二

// 实现原理 // 每个signal映射到bitset位&#xff0c;全集 // 每个slot做为signal的bitset子集 // signal全集触发&#xff0c;标志位有效 // flip将触发事件队列前置 // slot检测智能指针全集触发的标志位&#xff0c;主动运行子集绑定的函数 // 下一帧对bitset全集进行触发清…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站