初探算法之双指针开篇

ChatGPT / Claude 官方直充代充值

初探算法之双指针开篇

目录

前言:

此篇作为算法篇章的首篇文章,自然得简单说上几句。算法部分呢,多刷题是必不可少的。从暴力解法过渡到算法解法,过程着实有些艰辛,而算法的思考尤为关键。所以算法部分的讲解大多借助题目直接展开,以题目来传授算法知识。鉴于每个人对算法的接受程度有别,每篇通常涵盖两题左右,难题部分一般只设一道,且题目均取自LeetCode,本文会以最优解法来阐释不同的算法,通过题目解析、算法原理、算法编写这三个部分来解决问题。

双指针算法

题目一:

示例如下:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

题目解析:
给定一个数组,需要将其中的0移动到数组末尾,同时无需考虑0的相对顺序,但要保留非零元素的相对顺序。若不使用双指针,有诸多解法,例如把所有非零元素移到开头,不过每移动一次得遍历一次,时间复杂度接近O(N²),这属于暴力解法。那该如何运用双指针呢?

算法原理:
借助双指针可将数组划分成三个区域:[0,dest]为非零元素区域,[dest,cur]是0元素区域,[cur,end]是未遍历区域。双指针并非传统意义上的指针,而是一种形象的指向概念。这里借助数组下标来定义两个指针。起始时二者均从0开始,dest初始可先不明确,cur遍历数组,遇到非零元素时,将其放到dest位置,具体操作是dest从-1开始,找到非零元素后,dest先自增,再与cur位置元素交换,cur继续往后遍历。

算法编写:

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]);
        }
    }
};

简单分析时间复杂度,此为一次遍历,时间复杂度为O(N),相较暴力解法有显著优化。

题目链接:283. 移动零 - 力扣(LeetCode)

题目二:

示例如下:

输入: n = 19
输出: true
解释: 1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

题目解析:
题目叫做快乐数,来瞧瞧它有多“快乐”。快乐数的定义是:将一个数的每一位数字的平方相加,多次操作后若能得到1,那这个数就是快乐数;若一直循环却无法得到1,就不是快乐数。这类题目没有暴力解法,因为暴力的话很可能陷入死循环出不来,所以直接进入算法原理部分。

算法原理:
我们可以通过画图来看看变化情况。以19为例,经过4次变化得到1;而2经过多次变化后,会出现和第一次变化相同的值4。可以理解为2在变化时形成了一个环,且数的变化无法跳出这个环,所以不是快乐数。那19是否也有环呢?换个角度想,19变化时会不会形成一个仅包含1的环呢?此时大家应该明白了,我们可以用两个指针,一个走得快,一个走得慢,它们必定会相遇,相遇时判断是否为1即可。那为什么一定会出现环呢?这就要用到鸽巢原理了。LeetCode中给出了n的最大取值,我们考虑最大情况,比如10个9组成的数,计算其一次变化后的值为810,所以变化后的值最大不超过810。定义函数F(x)表示一次变化,那么一个数经过811次变化会产生811个数,但可能的取值区间只有810个,根据鸽巢原理,必然有重复的数,也就形成了环。

算法编写:

class Solution 
{
public:
    int _isHappy(int num)
    {
        int ans = 0,sum = 0;
        while(num)
        {
            sum = num % 10;
            ans = ans + sum * sum;
            num /= 10;
        }
        return ans;
    }
    bool isHappy(int n) 
    {
        int slow = n,fast = n;
        while(1)
        {
            slow = _isHappy(slow);
            fast = _isHappy(_isHappy(fast));
            if(slow == fast)
            {
                if(slow == 1)
                return true;
                else
                return false;
            }
        }
    }
};

今日算法分享至此,感谢阅读!

文章整理自互联网,只做测试使用。发布者:Lomu,转转请注明出处:https://www.it1024doc.com/13683.html

赞 (0)
LomuLomu
上一篇 2025 年 9 月 20 日
下一篇 2025 年 9 月 20 日

相关推荐

  • GPT和Claude会员购买前怎么选2026

    GPT和Claude会员购买前,按用途、预算和支付方式选择Plus、Pro或Claude Pro。

    未分类 2026 年 5 月 25 日
    30400
  • 2025年最新DataGrip永久破解教程(附激活码/注册码)🔥

    适用于JetBrains全家桶(IDEA/PyCharm/DataGrip/Goland等)的终极破解方案✨ 先给大家看看最新破解成果👉 有效期直接拉到2099年,简直不要太爽!🎉 下面就用最详细的图文教程,手把手教你搞定DataGrip永久激活!💪 这个方法同样适用于旧版本哦~ 第一步:下载官方安装包📥 还没安装的小伙伴看这里:1. 访问官网 https:…

    2025 年 5 月 19 日
    1.0K00
  • IDEA 2026.1 永久激活教程,附可用激活码

    本教程适用于IDEA、PyCharm、DataGrip、Goland等,支持Jetbrains全家桶! 废话不多说,先上最新 IDEA 版本破解成功的截图,如下,可以看到已经成功破解到 2099 年辣,舒服! 接下来,我就将通过图文的方式, 来详细讲解如何激活 IDEA至 2099 年。 当然这个激活方法,同样适用于之前的旧版本! 不管你是什么操作系统,什么…

    IDEA破解教程 2026 年 4 月 11 日
    2.4K00
  • GoLand破解2026年最新版图文教程亲测可用

    GoLand 永久激活指南:详细步骤与注意事项 声明:本文分享的 GoLand 破解补丁与激活码均来源于网络,仅供个人学习研究使用,请勿用于商业目的。如涉及侵权,请联系删除。鼓励有条件的用户支持正版软件。 GoLand 是 JetBrains 公司推出的一款功能强大的 Go 语言集成开发环境,支持 Windows、Mac 和 Linux 操作系统。本教程将逐…

    2026 年 5 月 22 日
    35100
  • 免费idea激活码2025年版+实用破解教程

    免责声明:本文所涉及的 IntelliJ IDEA 破解补丁与激活码均来源于互联网公开分享,仅供个人学习研究之用,禁止商业用途。若遇版权争议,请立即联系作者删除。经济条件允许时,请支持官方正版! 废话少说,先上图:IDEA 2025.2.1 已顺利解锁至 2099 年,爽翻! 下面用图文方式手把手教你搞定最新版 IDEA 的激活。 嫌折腾?直接入手官方正版,…

    IDEA破解教程 2025 年 11 月 13 日
    1.1K00

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信