双指针习题篇(上)

双指针习题篇(上)

文章目录

  • 双指针习题篇(上)
    • 1.移动零
      • 题目描述:
      • 算法原理:
      • 算法流程:
      • 代码实现:
    • 2.复写零
      • 题目描述:
      • 算法原理:
      • 算法流程:
      • 代码实现:
    • 3.快乐数
      • 题目描述:
      • 算法原理:
      • 算法流程:
      • 代码实现:
    • 4.盛最水多的容器
      • 题目描述:
      • 算法原理:
        • 解法一:暴力枚举(超时)O(N^2^)
          • 算法思路:
          • 算法代码:
        • 解法二:利用单调性,使用双指针来解决问题 O(N)
          • 算法思路:
          • 代码实现:

1.移动零

题目描述:

给定⼀个数组 nums ,编写⼀个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序

请注意 ,必须在不复制数组的情况下原地对数组进行操作

⽰例 1:

​ 输⼊: nums = [0,1,0,3,12]

​ 输出: [1,3,12,0,0]

⽰例 2:

​ 输⼊: nums = [0]

​ 输出: [0]

算法原理:

数组划分,数组分块(将一个数组分为非0和0两部分)

首先我们可以想到用双指针算法(利用数组下标来充当指针)

两个指针的作用:

cur:从左往右扫描数组,遍历数组(cur前是处理过的元素,cur后是待处理的元素)

dest:已处理的区间内,非零元素的最后一个位置(在处理过的元素中,继续划分,前是非零元素,后是为零元素)

整个数组被划分为三部分:

[0,dest] ——非零元素

[dest+1,cur-1] ——零元素

[cur,n-1]——待处理元素

算法流程:

1.初始化 cur = 0 (从头到尾遍历数组), dest = -1 (因为刚开始我们不知道最后⼀个非零元素是否存在,因此初始化为 -1,来记录非零数序列的最后⼀个位置 )

2.cur从前往后遍历的过程中:

(1).遇到0元素: cur ++ ;

(2).遇到非零元素: swap(dest+1,cur); dest++,cur++;

  • 因为 dest 指向的位置是非零元素区间的最后⼀个位置,如果扫描到⼀个新的非零元素,那么它的位置应该在 dest + 1 的位置上,因此 dest 先自增 1 ;

  • dest++ 之后,指向的元素就是零元素(因为非零元素区间末尾的后⼀个元素就是0 ),因此可以交换到 cur 所处的位置上,实现 [0, dest] 的元素全部都是非零元素,[dest + 1, cur - 1] 的元素全是零。

双指针的思想是快排中最核心的一步:数据划分

代码实现:

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

2.复写零

题目描述:

给你⼀个⻓度固定的整数数组 arr ,请你将该数组中出现的每个零都复写⼀遍,并将其余的元素向右平移。

注意:请不要在超过该数组⻓度的位置写⼊元素。请对输⼊的数组就地进⾏上述修改,不要从函数返回任何东西

⽰例 1:

​ 输⼊: arr = [1,0,2,3,0,4,5,0]

​ 输出: [1,0,0,2,3,0,0,4]

解释:

​ 调用函数后,输⼊的数组将被修改为: [1,0,0,2,3,0,0,4]

算法原理:

解法(原地复写 - 双指针):先根据”异地“操作,然后优化成双指针下的”就地“操作。

算法流程:

如果「从前向后」进行原地复写操作的话,由于 0 的出现会复写两次,导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。

但是「从后向前」复写的时候,我们需要找到「最后⼀个复写的数」,因此我们的大体流程分两步:

1.先找到最后⼀个“复写”的数;

双指针算法

(1).先判断cur位置的值;

(2).决定dest向后移动一步或者两步;

(3).判断一下dest是否已经结束;

(4).cur++.

  • 处理边界情况(当cur=0时,dest“复写零”可能发生越界)

(1).让n-1位置的元素等于零;

(2).cur- -;

(3).dest-=2;

  1. “从后向前” 完成复写操作。

cur 位置开始往前遍历原数组,依次还原出复写后的结果数组:

(1).判断 cur 位置的值:

  • 如果是零: dest 以及 dest - 1 位置修改成0dest -= 2

  • 如果非零: dest 位置修改成复写 ,dest -= 1

(2).cur-- ,复写下⼀个位置。

代码实现:

class Solution
{
public:
 	void duplicateZeros(vector<int>& arr) 
     {
         // 1. 先找到最后⼀个数
         int cur = 0, dest = -1, n = arr.size();
         while(cur < n)
         {
             if(arr[cur]) dest++;
             else dest += 2;
             if(dest >= n - 1) break;
             cur++;
         }
         // 2. 处理⼀下边界情况
         if(dest == n)
         {
             arr[n - 1] = 0;
             cur--; dest -=2;
         }
         // 3. 从后向前完成复写操作
         while(cur >= 0)
         {
         	if(arr[cur]) 
                arr[dest--] = arr[cur--];
         	else
            {
                 arr[dest--] = 0;
                 arr[dest--] = 0;
                 cur--;
            }
         }
     }
};

时间复杂度为O(N)

3.快乐数

快乐数的定义:

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

题目描述:

编写⼀个算法来判断⼀个数n是不是快乐数。

示例 1:

​ 输⼊: n = 19

​ 输出: true

解释:

19 -> 1 * 1 + 9 * 9 = 82

82 -> 8 * 8 + 2 * 2 = 68

68 -> 6 * 6 + 8 * 8 = 100

100 -> 1 * 1 + 0 * 0 + 0 * 0 = 1

例 2:

​ 输⼊: n = 2

​ 输出: false

提示:

  • 1 <= n <= 231 - 1

解释:(这⾥省去计算过程,只列出转换后的数)

2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16

往后就不必再计算了,因为出现了重复的数字,最后结果肯定不会是 1

算法原理:

  • 情况一:一直在 1 中死循环,即 1 -> 1 -> 1 -> 1…
  • 情况二:在历史的数据中死循环,但始终变不到 1.

由这两个死循环我们可以联想到之前学过的判断链表是否有环的解决方法——快慢双指针

快慢双指针:

1.定义快慢指针;

2.慢指针每次向后移动一步,快指针每次向后移动两步;

3.判断相遇时候的值即可。

这里我们可以用一个数来代替指针,一次操作(对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和)就相当于走了一步。不过为什么它这里一定会成环?

鸽巢原理(抽屉原理):有n个巢,n+1个鸽子,——>至少有一个巢里面的鸽子数大于1

简单证明:

因为n的最大值为231 - 1=21474 83647,我们选⼀个比它更大的数 99999 99999

所选的数经过⼀次变化之后的最大值为 9^2 * 10 = 810 。也就是说变化的区间在[1, 810]之间
根据「鸽巢原理」,⼀个数变化 811 次之后,必然会形成⼀个循环;
因此,变化的过程最终会走到⼀个圈里面,因此可以用「快慢指针」来解决

算法流程:

为了方便叙述,将「对于一个正整数,每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个操作记为 x 操作;
根据上述的题目分析,我们可以知道,当重复执行 x 的时候,数据会陷⼊到⼀个「循环」之中。
而「快慢指针」有⼀个特性,就是在⼀个圆圈中,快指针总是会追上慢指针的,也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是1 ,那么这个数⼀定是快乐数;如果相遇位置不是1的话,那么就不是快乐数

补充知识:如何求⼀个数 n 每个位置上的数字的平方和。

  1. 把数 n 每⼀位的数提取出来:

    循环迭代下⾯步骤:

    int t = n % 10 提取个位;

    n /= 10干掉个位;

    直到 n 的值变为 0 ;

  2. 提取每⼀位的时候,⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平方和
    tmp = tmp + t * t

代码实现:

class Solution {
public:
    int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和
    {
        int sum = 0;
        while(n)
        {
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) 
    {
        int slow = n, fast = bitSum(n);
        while(slow != fast)
        {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }
};

4.盛最水多的容器

题目描述:

给定⼀个长度为n的整数数组 height 。有 n 条垂线,第i条线的两个端点是(i, 0)(i, height[i])

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

​ 输入: [1,8,6,2,5,4,8,3,7]

​ 输出: 49

在这里插入图片描述

解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7] 。

在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49 。(8-1)*7=49。

算法原理:

解法一:暴力枚举(超时)O(N2)
算法思路:

枚举出能构成的所有容器,找出其中容积最大的值。

容器容积的计算方式:

设两指针i, j ,分别指向⽔槽板的最左端以及最右端,此时容器的宽度为j - i。由于容器的⾼度由两板中的短板决定,因此可得容积公式 : v = (j - i) * min( height[i], height[j])

算法代码:
class Solution {
public:
   int maxArea(vector<int>& height) 
   {
       int n = height.size();
       int ret = 0;
       // 两层 for 枚举出所有可能出现的情况
       for (int i = 0; i < n; i++)
       {
          for (int j = i + 1; j < n; j++) 
          {
          	// 计算容积,找出最⼤的那⼀个
          	ret = max(ret, min(height[i], height[j]) * (j - i));
           }
        }
     	return ret;
   }
};
解法二:利用单调性,使用双指针来解决问题 O(N)
算法思路:

设两个指针 left right 分别指向容器的左右两个端点,此时容器的容积 :

v = (right - left) * min( height[right], height[left])

容器的左边界为height[left] ,右边界为height[right]

为了方便叙述,我们假设「左边边界」小于「右边边界」。

如果此时我们固定⼀个边界,改变另⼀个边界,水的容积会有如下变化形式:

假设height[left]>height[right],固定右端点,向内枚举,宽度一定变小;

要是在向内枚举的过程中遇到一个小于height[right]的height,那么高度也会变小,v就会变小;

要是遇到一个大于height[right]的height,那么高度不变,v变小。

由此可见,向内枚举,v一定变小。所以我们可以right- -跳过这个边界,继续用上述方法去判断下⼀个左右边界。

当我们不断重复上述过程,每次都可以舍去大量不必要的枚举过程,直到 left 与 right 相遇。期间产生的所有的容积里面的最大值,就是最终答案。

代码实现:
class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int left=0,right=height.size()-1,ret=0;
        while(left<right)
        {
            int v=min(height[left],height[right])*(right-left);
            ret=max(ret,v);
            //移动指针
            if(height[left]<height[right]) 
                left++;
            else 
                right--;
        }
        return ret;
    }
};

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

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

相关文章

更安全高效的文件传输工具,Ftrans国产FTP替代方案可以了解

文件传输协议&#xff08;FTP&#xff09;&#xff0c;诞生于1971年&#xff0c;自20世纪70年代发明以来&#xff0c;FTP已成为传输大文件的不二之选。内置有操作系统的 FTP 可提供一个相对简便、看似免费的文件交换方法&#xff0c;因此得到广泛使用。 随着企业发展过程中新增…

Leetcode21:合并两个有效链表

原题地址&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4]示…

《Mini-internVL》论文阅读:OpenGVLab+清华/南大等开源Mini-InternVL | 1~4B参数,仅用5%参数实现90%性能

论文地址Mini-InternVL: A Flexible-Transfer Pocket Multimodal Model with 5% Parameters and 90% PerformanceGitHub仓库地址模型使用教程和权重下载地址 该论文发表于2024年10月份&#xff0c;截止2024年11月&#xff0c;引用数<10 文章目录 论文摘要1. 引用介绍2. 本文…

双目视觉标定——1原理与实践

0 前言 双目视觉定位是目前机器&#xff08;机器人&#xff09;等领域中使用得非常广泛的视觉定位技术&#xff0c;双目视觉是模拟人的视觉系统利用两个不同位置的摄像头的视差来确定物体的位置。由于有需要采集两个摄像头的图像共同参与计算&#xff0c;所以双目相机装配要求…

免杀对抗—DLL劫持白加黑隐写分离EDRSyscall-hook

前言 今天讲点比较高端的东西—DLL反射注入&#xff0c;首先什么是DLL文件&#xff0c;简答来说就是程序为了实现某个功能而调用的文件。举个例子&#xff0c;某个代码想要实现某个功能是不是会调用一些封装好的函数&#xff0c;exe同样如此&#xff0c;想要实现某个功能就会调…

故障诊断 | MTF-TLSSA-DarkNet-GRU-MSA迁移学习故障识别程序(t分布+莱维飞行改进麻雀优化)

故障诊断 | 故障诊断实例代码 目录 故障诊断 | 故障诊断实例代码效果一览基本介绍程序设计参考资料 效果一览 基本介绍 利用了迁移学习和多项技术改进&#xff0c;包括麻雀搜索法、DarkNet19、GRU、多头注意力机制等&#xff0c;以提高故障识别的准确性和效率 模型框架&#x…

MyBatis中的多级缓存机制(一级缓存和二级缓存)

MyBatis中的多级缓存机制&#xff08;一级缓存和二级缓存&#xff09; 缓存&#xff08;Cache&#xff09;技术在互联网系统的开发过程中应用非常广泛。当系统中出现性能瓶颈时&#xff0c;很多场景都可以使用缓存技术来重构业务处理流程&#xff0c;从而获取性能的提升。缓存…

day14:RSYNC同步

一&#xff0c;概述 概述 rsync &#xff08;开源&#xff09;是一个高效的文件同步和传输工具&#xff0c;广泛用于 Linux 和 Unix 系统中。它可以在本地和远程系统之间同步文件和目录&#xff0c;同时支持增量备份&#xff0c;能够只传输更改过的文件部分&#xff0c;以减少…

Matlab实现白鲸优化算法(BWO)求解路径规划问题

目录 1.内容介绍 2.部分代码 3.实验结果 4.内容获取 1内容介绍 白鲸优化算法&#xff08;BWO&#xff09;是一种受自然界白鲸捕食行为启发的新型优化算法&#xff0c;它通过模拟白鲸的群体捕猎策略和社会互动来探索问题的最优解。BWO因其强大的全局搜索能力和高效的局部搜索能…

python 模块和包、类和对象

模块 模块是包含 Python 代码的文件&#xff0c;通常用于组织相关的函数、类和其他语句。模块可以被导入并在其他 Python 文件中使用。 创建模块 假设你创建了一个名为 mymodule.py 的文件&#xff0c;内容如下&#xff1a; # mymodule.pydef greet(name): return f"…

SpringBoot节奏:Web音乐网站构建手册

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

使用Django REST framework构建RESTful API

使用Django REST framework构建RESTful API Django REST framework简介 安装Django REST framework 创建Django项目 创建Django应用 配置Django项目 创建模型 迁移数据库 创建序列化器 创建视图 配置URL 配置全局URL 配置认证和权限 测试API 使用Postman测试API 分页 过滤和排序…

MySQL 9从入门到性能优化-系统信息函数

【图书推荐】《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;》-CSDN博客 《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;&#xff08;数据库技术丛书&#xff09;》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) MySQL9数据库技术_夏天又到了…

芯片上音频相关的验证

通常芯片设计公司&#xff08;比如QUALCOMM&#xff09;把芯片设计好后交由芯片制造商&#xff08;比如台积电&#xff09;去生产&#xff0c;俗称流片。芯片设计公司由ASIC部门负责设计芯片。ASIC设计的芯片只有经过充分的验证&#xff08;这里说的验证是FPGA&#xff08;现场…

$tab的所有用法以及vue关闭页面的方法汇总

1、最简单粗暴的就是直接window.close(); 2.可以设置一个窗口的显示隐藏变量&#xff0c;比如点击新增按钮时&#xff0c;新增页面窗口就进行显示&#xff0c;点击关闭就把这个值置为flase 在最外层绑定open 初始值设为false 点击新增和修改按钮时&#xff0c;把状态置为true即…

深度学习(八) TensorFlow、PyTorch、Keras框架大比拼(8/10)

一、深度学习框架概述 深度学习框架在当今人工智能和机器学习领域中占据着至关重要的地位。其中&#xff0c;TensorFlow 由 Google 开发&#xff0c;自 2015 年发布以来&#xff0c;凭借其灵活的计算图、自动微分功能以及跨平台支持等特点&#xff0c;迅速成为主流深度学习框架…

<HarmonyOS第一课>HarmonyOS SDK开放能力简介的课后习题

不出户&#xff0c;知天下&#xff1b; 不窥牖&#xff0c;见天道。 其出弥远&#xff0c;其知弥少。 是以圣人不行而知&#xff0c;不见而明&#xff0c;不为而成。 本篇<HarmonyOS第一课>HarmonyOS SDK开放能力简介是简单介绍了HarmonyOS SDK&#xff0c;不需要大家过多…

WPF自定义日历控件Calendar 的方法

推荐下载地址 https://www.haolizi.net/example/view_2107.html <UserControl.Resources><local1:DayConverter x:Key"DayConverter"/><!--导入转换器--><Style x:Key"CalendarStyle1"TargetType"{x:Type Calendar}">&…

园区网典型技术应用

工厂、政府机关、商场、写字楼、校园、公园等&#xff0c;这些场所内为了实现数据互通而搭建的网络都可以称之为园区网 1. 园区网络架构与常见技术概述 某高校校园网络采用三层架构&#xff0c;核心层和汇聚层各有其明确的职责&#xff1a; 核心层&#xff1a;部署两台核心交…

计算机考研,选择西安交通大学还是哈工大?

C哥专业提供——计软考研院校选择分析专业课备考指南规划 经过全面分析&#xff0c;2025年考研西安交通大学和哈尔滨工业大学计算机专业的报考难度对比如下&#xff1a; 西安交通大学计算机专业 > 哈尔滨工业大学计算机专业 对于想要报考985高校计算机专业但核心目标是优…