刷题训练之双指针问题

发布时间:2024年01月06日

> 作者简介:?旧言~,目前大二,现在学习Java,c,c++,Python等
> 座右铭:松树千年终是朽,槿花一日自为荣。

> 目标:熟练掌握双指针,并且能把下面的题目做出

> 毒鸡汤:人生就像一场马拉松比赛,不是看谁跑得最快,而是看谁坚持到最后。

> 望小伙伴们点赞👍收藏?加关注哟💕💕?

🌟前言分析

????????最早博主续写了牛客网130道题,这块的刷题是让同学们快速进入C语言,而我们学习c++已经有一段时间了,知识储备已经足够了但缺少了实战,面对这块短板博主续写刷题训练,针对性学习,把相似的题目归类,系统的刷题,而我们刷题的官网可以参考:??????

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

而今天我们的板块是双指针问题。

?知识讲解

双指针有两种形式,一种是对撞指针,另一种是左右指针(快慢指针)。

对撞指针:

  • 对撞指针从两端向中间移动。?个指针从最左端开始,另?个从最右端开始,然后逐渐往中间逼近。
  • 对撞指针的终?条件?般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循 环)

快慢指针:

  • 在一次循环中,每次让慢的指针向后移动一位,而快的指针往后移动两位,实现一快一慢。

?经典题型

🌙topic-->1

题目原型:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目分析:

题目说的是,把一个数组含有0的数字甩到数组末尾,但不改变原数组顺序。

讲解算法原理:


编写代码:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //两个指针
        int cur = 0;
        int dest = -1;
        for(int i = 0;i < nums.size();i++)
        {
            //如果遇到0就交换
            if(nums[cur] != 0)
            {
                swap(nums[++dest],nums[cur]);
            }
            //cur加加
            cur++;
        }
    }
};

?🌙topic-->2

题目原型:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目分析:

题目说,数组有0就再复写一遍,但是不能超过数组原来的长度。

讲解算法原理:

编写代码:

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        // 求出数组元素个数
        int n = arr.size();
        int top = 0;
        int i = -1;
        // 入栈
        while(top < n)
        {
            i++;
            if(arr[i] == 0)
            {
                top = top + 2;
            }
            else
            {
                top++;
            }
        }
        // 处理边界情况
        int j = n - 1;
        if(top == n + 1)
        {
            arr[j] = 0;
            j--;
            i--;
        }
        // 开始出栈
        while(j >= 0)
        {
            arr[j] = arr[i];
            j--;
            // 如果i下标为0就让j再赋值一遍
            if(arr[i] == 0)
            {
                arr[j] = arr[i];
                j--;
            }
            i--;
        }
    }
};

?🌙topic-->3

题目原型:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目分析:

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

讲解算法原理:

编写代码:

class Solution {
public:
  // 返回每一次剥离的结果
    int bitSquareSum(int n)
    {
        int sum = 0;
        while(n > 0)
        {
            int t = n % 10; 
            sum = sum + t*t;
            n = n / 10;
        }
        return sum;
    }
    bool isHappy(int n) 
    {
        // 定义两个快慢指针
        int fast = bitSquareSum(n);
        int slow = n;
        // 让快指针走2步,慢指针走1步
        while(fast != slow)
        {
            fast = bitSquareSum(bitSquareSum(fast));
            slow = bitSquareSum(slow);
        }
        return slow == 1;
    }

};

🌙topic-->4

题目原型:. - 力扣(LeetCode)

题目分析:

求容量的最大能存水,用最小的柱高(y)乘以容量的宽(x)。

讲解算法原理:


编写代码:

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        // 定义左右指针
        int left = 0;
        int right = height.size() - 1;
        // 定义最大容量v
        int ret = 0;
        // 开始循环
        while(left < right)
        {
            int v = min(height[left],height[right]) * (right - left);
            ret = max(v,ret);
            // 判断指针的移动
            if(height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ret;
    }
};

?🌙topic-->5

题目原型:. - 力扣(LeetCode)

题目分析:

在数组中找三个数看看有多少个可以组成三角形。

讲解算法原理:

编写代码:

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        // 先让数组排升序
        sort(nums.begin(),nums.end());
        // 利用双指针来解决问题
        int count = 0;
        int n = nums.size();
        for(int i = n - 1;i >=2;i--)// 固定最大值
        {
            // 定义双指针
            int left = 0;
            int right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    count = count + right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return count;
    }
};

?🌙topic-->6

题目原型:. - 力扣(LeetCode)

题目分析:

在数组中找两个数之和能等于target就返回这两个数。

讲解算法原理:

编写代码:

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        // 定义双指针
        int left = 0;
        int right = price.size() - 1;
        // 循环
        while(left < right)
        {
            int sum = price[left] + price[right];
            if(sum > target)
                right--;
            else if(sum < target)
                left++;
            else
                return {price[left],price[right]};
        }
        // 如果没有的话就返回空
        return {};
    }
};

🌙topic-->7

题目原型:. - 力扣(LeetCode)

题目分析:

在数组中找三个数之和是否为0,如果为0就返回这三个数,并且不能重复。

讲解算法原理:


编写代码:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        // 定义数组
        vector<vector<int>> ret;
        // 让数组升序
        sort(nums.begin(),nums.end());
        int n = nums.size();
        // 定住一个数字,利用双指针法
        for(int i = 0;i < n;)
        {
            // 优化
            if(nums[i] > 0)
                break;
            // 定义双指针
            int left = i + 1;
            int right = n - 1;
            // 标记
            int target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target)
                    right--;
                else if(sum < target)
                    left++;
                else
                {
                    // 尾插
                    ret.push_back({nums[i],nums[left],nums[right]});
                    right--,left++;
                    // 去重left和right
                    while(left < right && nums[left] == nums[left-1])
                        left++;
                    while(left < right && nums[right] == nums[right+1])
                        right--;                   
                }
            }
            // 去重I
            i++;
            while(i < n && nums[i] == nums[i-1])
                i++;
        }
        return ret;
    }
};

?🌙topic-->8

题目原型:. - 力扣(LeetCode)

题目分析:

在数组中找四个数之和是否为0,如果为0就返回这四个数,并且不能重复。

讲解算法原理:

这里就不讲解原理了,这里和第 7 道题相似的。

编写代码:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        // 定义数组
        vector<vector<int>> ret;
        // 让数组升序
        sort(nums.begin(),nums.end());
        // 利用双指针
        int n = nums.size();
        for(int i = 0;i < n;)
        {
            // 使用三数之和的方法
            for(int j = i + 1;j < n;)
            {
                // 定义双指针
                int left = j + 1;
                int right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                // 循环
                while(left < right)
                {
                    int sum = nums[left] + nums[right];
                    if(sum < aim)
                        left++;
                    else if(sum > aim)
                        right--;
                    else
                    {
                        // 尾插
                        ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});
                        // 去重left
                        while(left < right && nums[left] == nums[left - 1])
                            left++;
                        while(left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                j++;
                // 去重j
                while(j < n && nums[j] == nums[j - 1])
                    j++;
            }
            i++;
            // 去重i
            while(i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};

?🌟结束语

? ? ? ?今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。

文章来源:https://blog.csdn.net/AAlykk/article/details/135003740
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。