双指针的问题解法以及常见的leetcode例题。

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

目录

介绍:

问题1:双指针 剑指offer57  和为S的两个数字。

问题2:剑指Offer 21. 调整数组顺序使奇数位于偶数前面

问题3:连续奇数子串(笔试遇到的真题)

问题4:滑动窗口的最大值


介绍:

双指针的问题通常需要理解问题的核心,然后选择合适的双指针策略来解决问题。以下是一种通用的解决方法:

  1. 首先,对数组进行排序,这样相同的元素会在一起,并且可以更好地控制数组的遍历。
  2. 定义两个指针,一个快指针和一个慢指针。通常,快指针是慢指针的两倍速度。
  3. 从数组的两侧开始遍历,比较两个指针指向的元素之和与目标值的大小。
  4. 根据和的大小调整指针的位置,例如,如果和等于目标值,则将两个指针都向后移动一位。如果和小于目标值,则慢指针向后移动一位,快指针向前移动两位。如果和大于目标值,则慢指针向前移动一位,快指针向后移动两位。
  5. 当快指针和慢指针相遇时,就找到了解。

这种解决方案适用于很多问题,但是具体实现需要根据问题的具体要求进行调整。

问题1:双指针 剑指offer57  和为S的两个数字。

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/?envType=study-plan-v2&envId=coding-interviews

tag:easy.

// 输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

示例 1:因为已经排序完成了,定义了两个指针.从两侧进行即可。

输入:nums = [2,7,11,15], target = 9

输出:[2,7] 或者 [7,2]

示例 2:

输入:nums = [10,26,30,31,47,60], target = 40

输出:[10,30] 或者 [30,10]

class Solution10
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {

        vector<int> ans;

        int left = 0, right = nums.size() - 1;

        while (left <= right)
        {

            if (nums[left] + nums[right] == target)
            {
                ans.push_back(nums[left]);
                ans.push_back(nums[right]);
                break;
            }

            else if (nums[left] + nums[right] > target)
            {

                right--;
            }
            else
            {
                left++;
            }
        }
        return ans;
    }
};

问题2:剑指Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。

https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/?envType=study-plan-v2&envId=coding-interviews。

输入:nums = [1,2,3,4]
输出:[1,3,2,4] 
注:[3,1,2,4] 也是正确的答案之一
class Solution11 {
public:
    vector<int> exchange(vector<int>& nums) {

  
        int left=0;
        int right=0;

        while(right<nums.size()){
             
            if(nums[right]%2!=0){
                swap(nums[left++],nums[right++]);
            }
            else{
                right++;
            }


        }
        return nums;


    }
    
};

问题3:连续奇数子串(笔试遇到的真题)

若有一组最小值大于0,数目大于1的连续的奇数的和等于指定正整5数

字,那么此连续的奇数序列称为此正整数数字的一个奇序列。如数字12,总共能找出一个奇序列 (5,7),数字16 能找出两个奇序列 (1,3,5,7)和(7,9)

数字17 找不出,那么12的奇序列数为1,16的奇序列数为2,17的奇序列数为0。

输入 17

输入 0

输入 16

输出 2

输入 12

输出 1

函数用于计算奇序列数  从1 开始 加到 n/2,计算累计和超过n进入while 循环. 如果等于就是+2, 否则就停止。

1 3 5 7 9 11

 3 5 7 9

5 7 9 。。。小于n就可以了。 

int main()
{

    int n;

    cin >> n;

    int start = 0;
    int count = 0;
    int sum = 0;
    int i = 0;

    for (start = 1; start < n / 2; start += 2)
    {

        i = start;
        sum = 0;

        while (sum < n)
        {

            sum += i;
            i += 2;
        }

        if (sum == n)
        {
            count++;
        }
    }

    cout << count << endl;

    system("pause");
    return 0;
}

问题4:滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值

 给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)   {


        int n=nums.size();
        priority_queue<pair<int,int>> q;
        for(int i=0;i<k;i++){
            q.emplace(nums[i],i);
        }
        vector<int> ans={q.top().first};
        for(int i=k;i<n;i++){
            q.emplace(nums[i],i);
            //离开了滑动窗口里面了,永久移除了
            while(q.top().second<=i-k){
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;

    }
        


    
};

      ======================待补充===========================文章来源地址https://www.toymoban.com/news/detail-699469.html

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

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

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

相关文章

  • 【每日挠头算法题】Leetcode 989. 数组形式的整数加法 —— 高精度加法解法

    👑作者主页:@进击的安度因 🏠学习社区:进击的安度因(个人社区) 📖专栏链接:每日挠头算法题 如果无聊的话,就来逛逛 我的博客栈 吧! 🌹 今天为大家带来的是力扣上的一道简单题:数组形式的整数加法。这道题我在2个月前就尝试过,但是没有解答出来。两个月后

    2024年01月25日
    浏览(42)
  • 数据挖掘|决策树算法以及相关算法实现和例题讲解

    声明:本专栏的所有内容皆是本人接触到的系统学习的老师的讲解内容,仅做整理分享。 出处来源:分类问题:决策树+ID3算法+C4.5算法+考试例题讲解_哔哩哔哩_bilibili 资料整理:链接:https://pan.baidu.com/s/1q786VaYJ9-1G7ZdfC6KL7A  提取码:3k7m

    2024年01月16日
    浏览(39)
  • 磁盘调度算法例题解析以及C语言实现

    如果当前停留在第122号磁道上,接下来8个磁道按顺序分别是 120,98,4,51,180,195,140,23。请写出最短寻道时间优先和扫描算 法的访问顺序以及各自的平均寻道长度。 最短寻道时间优先算法: SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间

    2024年02月12日
    浏览(45)
  • 【算法】【算法杂谈】折纸问题(完全二叉树解法)

    当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 原问题 一张纸从下往上对折之后,出现一条折痕,该折痕凸起向下,所以叫“下折痕”,反之如果摊开之后,凸起向上,则叫

    2024年02月01日
    浏览(36)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

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

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

    2024年02月12日
    浏览(84)
  • Python 算法基础篇:背包问题的动态规划解法

    背包问题是计算机科学中一个重要的组合优化问题,动态规划是解决该问题的高效算法技术。本篇博客将重点介绍背包问题的动态规划解法,包括状

    2024年02月16日
    浏览(39)
  • 【算法专题--双指针算法】leetcode--283. 移动零、leetcode--1089. 复写零

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月17日
    浏览(42)
  • LeetCode算法小抄 -- 链表(快慢指针、双指针、回文链表)

    ⚠申明: 未经许可,禁止以任何形式转载,若要引用,请标注链接地址。 全文共计10077字,阅读大概需要10分钟 🌈更多学习内容, 欢迎👏关注👀文末我的个人微信公众号:不懂开发的程序猿 个人网站:https://jerry-jy.co/ Collection 子接口之 Queue (LeetCode上经常用,手撕算法题!

    2023年04月08日
    浏览(38)
  • 算法:数组常见套路1---双指针、取模、打擂台法

    1、题目: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对

    2024年02月09日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包