当前位置: 首页 > news >正文

[双指针] --- 快乐数 盛最多水的容器

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:       9ilk

(๑•́ ₃ •̀๑) 文章专栏:    算法Journey  


本篇博客我们分享一下双指针算法中的快慢指针以及对撞双指针,下面我们开始今天的学习吧~


🏠 快乐数

📒 题目解析

题目链接:202. 快乐数 - 力扣(LeetCode)

题目内容:

对于这道题,题中告诉了我们快乐数的定义,也就是说9对于一个正整数经过变换会进入两种循环:1.一种是一直循环12.另一种是不同数的循环

📒 算法原理

思路1  找规律

这个思路本人按照以往学数学的规律,发现不满足快乐数的会陷入4-16-37-58-89-145-42-20的循环当中

因此我们的思路是申请一块数组空间,当某个正整数变化到这个数组中的某个数时,说明不是快乐数;反之,一直变化都没出现这里面的数,变化到1停止,说明就是快乐数。

参考代码

class Solution
{
public:int squre(int n){int sum = 0 ;while(n > 0){sum += ((n%10)*(n%10));n /= 10;}return sum;}bool find(vector<int>& v1,int x){for(int i = 0 ; i < v1.size();i++){if(v1[i] == x)return true;}return false;}bool isHappy(int n) {if(n == 1)return true;vector<int> v1= {4,16,37,58,89,145,42,20};int sum = n;while(sum != 1){sum = squre(sum);if(find(v1,sum))return false;elsecontinue;   }return true;}
};

思路2 快慢指针

思路1属于投机取巧的做法,猜到就是赚到,万一猜不到呢?

我们由题目可知,这个正整数只有两种变化情况,有的朋友可能会想是否有可能不会进入循环一直变成不同的数呢?答案是不可能 !

证明过程:

1.鸽巢(抽屉)原理:如果有n个巢,n+1只鸽子,那么至少有一个巢的鸽数大于1.

2.对于这道题而言最大为21亿多( 2147483647),也就是最多有10个位,假设每一位都是9,即9999999999,那么经过一次变换就是9*9*10 = 810

3.int范围内每个正整数经过一次变化在[0,810]这个闭区间内,那么假设存在某个数经过810次变换后都是不同的数,但再变一次这个数一定是之前变换过程中的一个数,类比来看,这个闭区间就相当于"鸽巢",因此一定会进入循环!

既然只有两种情况,我们看到两种环是否感到熟悉,我们在解决链表是否带环问题,常用的解决方法就是快慢指针

这里我们要打破固有思维,我们要理解的是快慢指针的应用场景,在这里slow走一步相当于这个正整数变化一次,fast走两步,相当于这个正整数变化两次

总结快慢指针思路:slow变化一次,fast变化两次,通过判断他们相遇时(变化成的数相等时),这个数是否变化为1,为1则说明是快乐数;反之不是.

参考代码

class Solution {
public:int squre(int x){int sum = 0;while(x > 0){sum += ((x%10)*(x%10));x /= 10;} return sum;}bool isHappy(int n){int slow = squre(n);int fast = squre(squre(n));while(slow != fast){slow = squre(slow);fast = squre(squre(fast));}if(slow == 1){return true;}return false;}};

🏠 盛最多水的容器

📒 题目解析

题目链接:11. 盛最多水的容器 - 力扣(LeetCode)

题目内容:

这道题目简单来说就是让我们确定横坐标差值m以及纵坐标n,使得m*n最大

📒 算法原理

思路1 暴力求解

对于这道题我第一时间能想到的就是暴力求解套两个循环,定义一个max变量,不断比较更新max

class Solution {
public:int maxArea(vector<int>& height){int maxV = 0;for(int i = 0 ; i < height.size() ; i++){for(int j = i +1 ; j < height.size() ; j++){int row = j - i;int col = height[i] < height[j] ? height[i] : height[j];if(maxV < row*col)maxV = row*col;}}return maxV;}
};

但题目不给我们过O(N^2)的解法,需要另寻他路

思路2 对撞指针

发现规律:

假设在【6,2,3,4】这个区间,我们设横坐标值为m,纵坐标的值为n,则固定住4,4左边的数分别与4求体积我们会发现这样的一个规律:

结论:当区间左右端点值较小的值固定住后,不断逼近过程中,V一定是一定减小的,那么左右端点值形成的V就是这段区间中最大的!!

发现完这个规律,我们就可以避免了很多不必要情况的枚举,直捣黄龙取“最大”。

对撞指针:所谓对撞指针就是定义一个left指针和一个指针,分别指向容器的左右端,left和right分别向中间逼近,当left > right或 left == right时,停止遍历。

结合我们发现的规律以及对撞指针的原理,我们的代码思路就是left和right分别向中间逼近,比较left和right 位置对应位置的较小值固定 left / right,求出左右端点值对应的v;由发现的规律知,此时的v就是这个对应左右边界最大的v;接着移动left / right,继续下一个左右区间...直到left 和 right 相遇。

参考代码

class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size() - 1;vector<int> v1;while(left < right){int v = (right-left)*(height[left] < height[right] ? height[left] :height[right]);v1.push_back(v);cout << v << " left :"<<left << "right: "<< right << endl;if(height[left] < height[right]){left++;}else if(height[left] > height[right]){right--;}else{left++;}}int maxV = 0;for(int i = 0 ; i < v1.size();i++){if(v1[i]>maxV)maxV = v1[i];}return maxV;}
};


总结:本篇博客我们介绍了双指针算法中的快慢指针和对撞指针;快慢指针常用于解决“带环”问题,对撞指针需要我们先发现规律确定好对撞停止条件以及对撞指针更新的条件,一般适用于排除区间或查找某种条件是否成立的场景

相关文章:

[双指针] --- 快乐数 盛最多水的容器

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; 算法Journey 本篇博客我们分享一下双指针算法中的快慢指针以及对撞双指针&#xff0c;下面我们开始今天的学习吧~ &#x1f3e0; 快乐数 &#x1f4d2; 题…...

操作系统 - 输入/输出(I/O)管理

输入/输出(I/O)管理 考纲内容 I/O管理基础 设备&#xff1a;设备的基本概念&#xff0c;设备的分类&#xff0c;I/O接口 I/O控制方式&#xff1a;轮询方式&#xff0c;中断方式&#xff0c;DMA方式 I/O软件层次结构&#xff1a;中断处理程序&#xff0c;驱动程序&#xff0c;…...

代码随想录算法训练营第22天(py)| 二叉树 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树 力扣链接 给定一个二叉搜索树&#xff0c;同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树&#xff0c;使得所有节点的值在[L, R]中 (R>L) 思路 如果当前节点元素小于low&#xff0c;递归右子树&#xff0c;返回符合条件的头节点 如果当前节点元…...

使用C语言实现学生信息管理系统

前言 在我们实现学生信息管理系统的过程中&#xff0c;我们几乎会使用到C语言最常用最重要的知识&#xff0c;对于刚学习完C语言的同学来说是一次很好的巩固机会&#xff0c;其中还牵扯到数据结果中链表的插入和删除内容。 实现学生信息管理系统 文件的创建与使用 对于要实现…...

上下文视觉提示实现zero-shot分割检测及多visual-prompt改造

文章目录 一、Closed-Set VS Open-set二、DINOv2.1 论文和代码2.2 内容2.3 安装部署2.4 使用效果 三、多visual prompt 改造3.1 获取示例图mask3.2 修改函数参数3.3 推理代码3.4 效果的提升&#xff01; 四、总结 本文主要介绍visual prompt模型DINOv&#xff0c;该模型可输入八…...

WebGL学习(一)渲染关系

学习webgl 开发理解渲染关系是必须的&#xff0c;也非常重要&#xff0c;很多人忽视了这个过程。 我这里先简单写一下&#xff0c;后面尽量用通俗易懂的方式&#xff0c;举例讲解。 WebGL&#xff0c;全称Web Graphics Library&#xff0c;是一种在网页上渲染3D图形的技术。它…...

人生建议:向猫学习

心安理得地被爱 猫从不担心自己不配得到爱&#xff0c;也正是这幅理所应当、宠辱不惊的样子&#xff0c;让人欲罢不能。或许 当你相信自己值得世界上最好的爱时&#xff0c;你就会拥有。 多晒太阳多睡觉 猫喜欢睡觉&#xff0c;尤其喜欢躺阳光好的地方。阳光和睡眠&#xff0c…...

软件架构设计属性之三:结构性属性浅析

文章目录 引言一、结构性属性的定义二、结构性属性的关键要素1. 组件化2. 模块化3. 层次化4. 接口定义5. 数据流6. 依赖管理 三、结构性属性的设计原则1. 高内聚低耦合2. 松耦合3. 清晰的接口4. 可维护性5. 可扩展性 四、结构性属性的实现策略1. 组件划分2. 模块化设计3. 接口设…...

JAVA:多线程常见的面试题和答案

请关注微信公众号&#xff1a;拾荒的小海螺 博客地址&#xff1a;http://lsk-ww.cn/ 1、并发编程三要素&#xff1f; 原 子 性 原子性指的是一个或者多个操作&#xff0c;要么全部执行并且在执行的过程中不被其他操作打断&#xff0c;要么就全部都不执行。可 见 性 可见性指多…...

短信平台-平台群发短信

时代的进步带来了我们生活的便利&#xff0c;而其中最受欢迎和广泛应用的方式之一就是通过短信传递信息。在这个飞速发展的数字时代&#xff0c;我们需要一个高效、可靠的短信平台来满足不断增长的通讯需求。而今天&#xff0c;我要向大家推荐的正是这样一款卓越的短信平台——…...

C++:类和对象

一、前言 C是面向对象的语言&#xff0c;本文将通过上、中、下三大部分&#xff0c;带你深入了解类与对象。 目录 一、前言 二、部分&#xff1a;上 1.面向过程和面向对象初步认识 2.类的引入 3.类的定义 4.类的访问限定符及封装 5.类的作用域 6.类的实例化 7.类的…...

JavaScript条件语句与逻辑判断:解锁代码逻辑的奥秘【含代码示例】

JavaScript条件语句与逻辑判断&#xff1a;解锁代码逻辑的奥秘【含代码示例】 基本概念与作用if...else&#xff1a;决策的基础switch&#xff1a;多路分支的能手逻辑运算符&#xff1a;连接逻辑的纽带三元运算符&#xff1a;简洁的力量 功能使用思路与技巧短路求值优化防止swi…...

sparksql自定义函数

前言 Spark SQL UDF(也称为用户定义函数)是Spark SQL&DataFrame最有用的功能,它扩展了Spark内置功能。在本文中,我将解释什么是UDF?为什么我们需要它,以及如何使用Java、Scala示例在DataFrame和SQL上创建和使用它。 注意:UDF是最昂贵的操作,因此只有在必要时才使用…...

新人开发新系统,旧人维护旧系统

通常来说旧系统存在一些难以解决的问题&#xff0c;软件架构及逻辑实现可能会有一定的缺陷和复杂度&#xff0c;甚至有些烂系统可以称为”焦油坑“&#xff0c;意思是出现问题难以分析解决&#xff0c;谁来谁陷进去。因此&#xff0c;如果同时存在新系统&#xff08;可能正在开…...

鸿蒙应用模型:【Stage模型开发】概述

Stage模型开发概述 基本概念 下图展示了Stage模型中的基本概念。 图1 Stage模型概念图 [AbilityStage] 每个Entry类型或者Feature类型的HAP在运行期都有一个AbilityStage类实例&#xff0c;当HAP中的代码首次被加载到进程中的时候&#xff0c;系统会先创建AbilityStage实例…...

java使用jdbcTemplatep批量插入数据

JdbcTemplate 是 Spring 框架中提供的一个简化 JDBC 操作的工具类&#xff0c;它封装了 JDBC 的核心功能&#xff0c;使得开发者能够更方便、简洁地进行数据库操作。 下面是一个使用 JdbcTemplate 进行批量插入的示例&#xff1a; import org.springframework.jdbc.core.Batch…...

K8s service 进阶

文章目录 K8s service 进阶Service 工作逻辑Service 具体实现Service 资源类型ClusterIPNodePortLoadBalancerExternalName Service 与 EndpointEndpoint 与 容器探针自定义Endpoint Service 相关字段sessionAffinityexternalTrafficPolicyinternalTrafficPolicypublishNotRead…...

CompletableFuture详细讲解

目录 一、基本概念 1.1 异步编程 1.2 CompletableFuture简介 二、创建和完成CompletableFuture 2.1 创建CompletableFuture对象 2.2 手动完成CompletableFuture 2.3 异常完成CompletableFuture 三、异步计算和回调 3.1 异步任务的执行 3.2 处理计算结果 四、组合多个…...

【Linux】初识Linux和Linux环境配置

1.什么是Linux操作系统 说到电脑系统 我想有大多数人会脱口而出&#xff1a;windows、mac 是的&#xff0c;这也是如今市场上主流的两种操作系统。 但是对于IT相关的人士来说&#xff0c;还有一种系统也是必须有姓名 那就是Linux Linux&#xff0c;Linux Is Not UniX 的…...

redis-cli help使用

1. redis-cli命令使用—先连接上服务器 连接到 Redis 服务器&#xff1a; 使用 redis-cli 命令即可连接到本地运行的 Redis 服务器&#xff0c;默认连接到本地的 6379 端口。 redis-cli如果 Redis 服务器不在本地或者端口不同&#xff0c;可以使用 -h 和 -p 参数指定主机和端…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...