算法专栏——双指针

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

1.移动零

        算法专栏——双指针,算法

题目链接:移动 0_牛客题霸_牛客网 (nowcoder.com)

算法原理:

        像这样子的将一整块数组划分很多部分可以称为数组划分,常用的解法可以是双指针。

说是双指针,但操作的对象是数组,因此下标就是指针。 

        双指针的精华就是通过俩个指针将数组划分成三个部分:算法专栏——双指针,算法

那我们让其这个规则贯彻就完成了

想要保证上述划分的区域不变的话,那就可以这样做:

        先让left指向 -1 ,right进行扫描整个数组。

        right遇到0继续++,遇到非0的话,然后swap(nums[left+1] ,nums[right]left++, right++

    public int[] moveZeroes (int[] nums) {
        // write code here
        int left = -1;
        int right = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[right] == 0){
                right++;
            }else{
                swap(left+1,right,nums);
                left++;
                right++;
            }
        }
        return nums;
    }

    public void swap(int left,int right,int[] nums){
        int num = nums[left];
        nums[left] = nums[right];
        nums[right] = num;
    }

2.复写零

        算法专栏——双指针,算法

算法原理: 

        看到这个题第一个想到的是:创建一个新的数组,遍历原数组然后普通数字直接复制到新数组上,0就复制俩次呗。

        但是有没有可以实现在这数组上直接进行操作呢?

        我们先从前往后试着模拟一下:

算法专栏——双指针,算法

        我们发现left会往前越过right,并且覆盖掉了 2这显然不可以的,那我们就试着从后往前遍历。

        那如果从后往前遍历的话,right指标肯定要先指向原数组最后的一个位置就比如上述的数据,right应该指向 val数据是 4 。left指向的是最后的元素。然后往前进行遍历,就不会出现覆盖的情况了。

        那就还有个问题,就是如何找到原数组最后出现的数呢?也可以用双指针从前往后,找到right最后的位置,然后left不需要进行换数据啥的,主要就是为了找到位置。


具体的步骤如下:

        算法专栏——双指针,算法

        

 文章来源地址https://www.toymoban.com/news/detail-693882.html

public void duplicateZeros(int[] arr) {
        //1.先找到原数组最后出现的位置 right就是目标位置
        int n = arr.length;
        int top = 0;
        int i = -1;
        while(top < n){
            i++;
            if(arr[i] != 0){
                top++;
            }else{
                top += 2;
            }
        }
        //边界问题
        int j = n - 1;
        if(top == n + 1){
            arr[j] = 0;
            j--;
            i--;
        }
        //从后往前遍历
        while(j >= 0){
            arr[j] = arr[i];
            j--;
            if(arr[i] == 0){
                arr[j] = arr[i];
                j--;
            }
            i--;
        }
    }

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

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

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

相关文章

  • 1.1 机器人运动控制算法专栏介绍

    本博客专栏将从理论到实践进行全面讲解,从机器人运动控制的基础理论到代码实现,读者将能够全面了解机器人运动控制的关键环节。本专栏从数学公式的推理,到代码实现的详细阐述,读者将能够更好地理解和应用机器人运动控制的相关知识。通过实例、图像、代码和解

    2024年02月09日
    浏览(50)
  • 【C++算法图解专栏】一篇文章带你掌握差分算法

    ✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343 📣专栏定位:为 0 基础刚入门数据结构与算法的小伙伴提供详细的讲解,也欢迎大佬们一起交流~ 📚专栏地址:https://blog.csdn.net/Newin2020/article/details/126445229 ❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创

    2024年04月11日
    浏览(44)
  • 【C++图解专栏】手撕数据结构与算法,探寻算法的魅力

    ✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343 📣专栏定位:为 0 基础刚入门数据结构与算法的小伙伴提供详细的讲解,也欢迎大佬们一起交流~ 📚专栏简介:在这个专栏,我将带着大家一起用 C++ 手撕基础的数据结构与算法,每一讲都有详细的讲解,29 篇文章共

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

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

    2024年04月15日
    浏览(51)
  • 【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   findContentChildren ( self ,  g :  List [ int ],  s

    2024年02月04日
    浏览(55)
  • 【Java程序员面试专栏 数据结构】四 高频面试算法题:哈希表

    一轮的算法训练完成后,对相关的题目有了一个初步理解了,接下来进行专题训练,以下这些题目就是汇总的高频题目,一个O(1)查找的利器哈希表,所以放到一篇Blog中集中练习 题目 解题思路 时间 空间 两数之和 辅助哈希 使用map存储出现过的值,key为值大小,v

    2024年02月22日
    浏览(59)
  • 双指针算法,基础算法实践,基本的算法的思想,双指针算法的实现

    双指针算法是一种常用于解决数组和链表问题的算法技巧。它的核心思想是使用两个指针在数据结构中按照一定的规则移动,从而达到快速搜索或处理数据的目的。这个技巧通常用于 优化算法 , 降低时间复杂度 ,提高程序的执行效率。双指针算法有多种应用场景,以下是其

    2024年02月11日
    浏览(40)
  • 【算法】双指针算法

    个人主页 : zxctscl 如有转载请先通知 一、题目分析 要将0放在所有数组的最后,而且非零元素的顺序保持不变,要求原地对数组进行移动。 二、算法原理 用两个指针来讲数组进行划分,一个cur:从左往右扫描数组,遍历数组;一个dest:已经处理的区间内,非零元素的最后一

    2024年04月25日
    浏览(29)
  • 算法学习---双指针算法

    在处理数组和链表相关问题时,双指针技巧是经常用到的,双指针技巧主要分为两类: 左右指针和快慢指针 对于单链表来说,大部分技巧都属于快慢指针,在数组中并没有真正意义上的指针,但我们可以把索引当做数组中的指针。 https://leetcode.cn/problems/remove-duplicates-from-so

    2024年03月11日
    浏览(37)
  • 算法基础学习|双指针算法

    题目 给定一个长度为  的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。 输入格式 第一行包含整数 。 第二行包含  个整数(均在  范围内),表示整数序列。 输出格式 共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。 数据

    2024年01月24日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包