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

【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器

 202. 快乐数 

202. 快乐数icon-default.png?t=N6B9https://leetcode.cn/problems/happy-number/

题目:

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

「快乐数」 定义为:

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

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

 解题思路:

 我们先通过这两个测试用例来看看是什么情况

 我们发现不管是19还是2都会形成一个环状结构(19的环状结构内都是1)

那这样我们就可以使用快慢指针来操作!!!

定义一个slow和fast,slow一次走一步,fast一次走两步

他们一定会相遇的,只不过相遇的时候会有两种情况,相遇的数是1或者不是1

那为什么一定会形成环状结构呢?我们来简单论证一下!

鸽巢原理:就是当n个巢穴,n+1个鸽子的时候,一定至少有一个巢穴的鸽子>1

我们注意一下n的范围,n最大为2的31次方,也就是2亿多(10位数),那我们将它放大10个9(也就是最大的那个10位数,我懒得打9了),也就是说,它最多就是10个9,经过f操作最大就是9^2*10=810,也就是相当于我们最多有810个位置,我们处理813次的f,肯定会有重复的数出现!

那同理:

 

解题代码:

class Solution {
public:int f(int n){int arr[11] = { 0 };int i = 1;for (int i = 1; i < 11; ++i){if (n < 10){arr[i] = n;break;}arr[i] = n % 10;n = n / 10;}int x = 0;for (int i = 1; i < 11; ++i){x += (arr[i] * arr[i]);}return x;}bool isHappy(int n) {//快慢双指针int slow = n;int fast = n;//更新slow和fastslow = f(slow);fast = f(fast);fast = f(fast);if (slow == fast && slow == 1)return true;while (slow != fast){//更新slow和fastslow = f(slow);fast = f(fast);fast = f(fast);}if (slow == 1)return true;elsereturn false;}
};

11. 盛最多水的容器

11. 盛最多水的容器icon-default.png?t=N6B9https://leetcode.cn/problems/container-with-most-water/

题目描述:

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

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

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

说明:你不能倾斜容器。

解题思路:

体积V=h*w,当我们利用双指针从左右两边向中间逼近,w一定是减小的,只有当h增大才可能增大

解题代码:

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

 

 

相关文章:

【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器

202. 快乐数 202. 快乐数https://leetcode.cn/problems/happy-number/ 题目&#xff1a; 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为&#xff1a; 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个…...

【Hilog】鸿蒙系统日志源码分析

【Hilog】鸿蒙系统日志源码分析 Hilog采用C/S结构&#xff0c;Hilogd作为服务端提供日志功能。Client端通过API调用&#xff08;最终通过socket通讯&#xff09;与HiLogd打交道。简易Block图如下。 这里主要分析一下。Hilog的读、写、压缩落盘&#xff0c;以及higlog与android…...

keil下载程序具体过程4:flash下载算法

引言 本篇文章将介绍flash算法文件&#xff0c;阐述从jlink如何下载镜像文件写入到内部的falsh。 一、XIP 在谈flash下载算法文件时&#xff0c;先说明XIP是什么。 芯片的启动方式有很多种&#xff1a;可以从RAM中启动、内部的flash、外部的flash等等&#xff08;还有从sd卡、…...

如何快速的让自己从月入2000变成月入两万?

从月入2000变成月入两万 前言我们可以这么做&#xff1a;1.提升自己的技能&#xff1a;2.寻找更好的工作机会&#xff1a;寻找更好的工作机会是一个重要的目标&#xff0c;以下是几个建议&#xff1a; 3.开展副业或兼职工作&#xff1a;4.创业或投资&#xff1a;5.构建个人品牌…...

使用 CycleGAN 进行图像到图像转换

介绍 在人工智能和计算机视觉领域,CycleGAN 是一项非凡的创新,它重新定义了我们感知和操作图像的方式。这种尖端技术彻底改变了图像到图像的转换,实现了领域之间的无缝转换,例如将马变成斑马或将夏日风景变成雪景。在本文中,我们将揭开 CycleGAN 的魔力,并探索其在各个领…...

Svg使用和注册components文件夹内部全部为全局组件

1.安装SVG依赖插件 pnpm install vite-plugin-svg-icons -D 2. 封装SvgIcon <template><div><svg :style"{ width: width, height: height }"><use :xlink:href"prefix name" :fill"color"></use></svg>…...

解决idea编辑application.yml文件或properties文件没有提示问题

注意&#xff1a;这里说的没有提示&#xff0c;是针对application.properties和application.yml文件 解决办法&#xff1a;在idea的插件面板中&#xff0c;禁用或卸载 wl Spring Assistant插件即可解决问题。...

前端懒加载

懒加载的概念 懒加载也叫做延迟加载、按需加载&#xff0c;指的是在长网页中延迟加载图片数据&#xff0c;是一种较好的网页性能优化的方式。在比较长的网页或应用中&#xff0c;如果图片很多&#xff0c;所有的图片都被加载出来&#xff0c;而用户只能看到可视窗口的那一部分…...

【手动配置ip地址后,电脑仍自动分配ip的问题】

现象 手动给电脑分配了一个ipv4地址&#xff0c;但是电脑会自动分配一个169开头的ipv4&#xff0c;导致虽然可以上网&#xff0c;但访问不了局域网内其他的设备&#xff08;我配置的另一个网关&#xff0c;所以可以上网&#xff09; 原因 ip地址冲突了&#xff0c;把电脑的i…...

移远RM500U-CN模块直连嵌入式ubuntu实现拨号上网

目录 1 平台&#xff1a; 2 需要准备的资料 3 参考文档 4 编译环境与驱动移植 4.1 内核驱动添加厂家ID和产品ID 4. 2.添加零包处理 4.3 增加复位恢复机制 4.4 增加批量输出 批量输出 URB 的数量和容量 的数量和容量 4.5 内核配置与编译 5 QM500U-CN拨号&#xff08;在开…...

【JavaWeb】MySQL基础操作

1 通用语法规则 SQL语句可以单行或者多行书写&#xff0c;以分号结尾SQL语句不区分大小写&#xff0c;关键字建议使用大写单行注释 --注释内容&#xff08;通用&#xff09; # 注释内容&#xff08;MySQL独有&#xff09;多行注释 /* 注释内容 */ 2 语句 数据库 -- 查…...

【Tool】虚拟机安装与调试与设置与主机共享文件

前言 安装了vm17&#xff0c;实现了与主机文件共享&#xff0c; 步骤 下载虚拟机&#xff08;试用版&#xff09; Download VMware Workstation Pro 双击安装 暂不激活或者 使用如下激活码 KRNJX-22GXY-HCW46-MWYHY-YWRDB RDHTN-YFFKY-8YVR7-Q996Y-K74X3 N2XRH-GCH84-MV…...

Spring中的接口使用

技术主题 在我们的项目中,经常会使用一些注解,注解带给我们代码简洁,本质是用于在代码中添加元数据信息,从而实现更加灵活、高效和可维护的代码结构。 技术原理 注解一@Target(ElementType.TYPE) 这个注解表示被它修饰的注解可以应用在类、接口、枚举等类型上。换句话说…...

爬虫017_urllib库_get请求的quote方法_urlencode方法_---python工作笔记036

按行来看get请求方式 比如这个地址 上面这个地址复制粘贴过来以后 可以看到周杰伦变成了一堆的Unicode编码了 所以这个时候我们看,我们说https这里,用了UA反爬,所以这里 我们构建一个自定义的Request对象,里面要包含Us...

Http、SSE、Websocket的区别

从传输方向上看 http是客户端发送请求&#xff0c;然后服务端进行响应的单向通道网络传输协议&#xff1b; SSE&#xff08; Server-sent Events &#xff09;则相反&#xff0c;只能是服务器向客户端发送消息&#xff0c;如果客户端需要向服务器发送消息&#xff0c;则需要一…...

【资料分享】全志科技T507工业核心板硬件说明书(一)

目 录 前言 1硬件资源 1.1CPU 1.2ROM 1.3RAM 1.4时钟系统 1.5电源 1.6LED...

JavaScript类

JavaScript 类(class) 类是用于创建对象的模板。 我们使用 class 关键字来创建一个类&#xff0c;类体在一对大括号 {} 中&#xff0c;我们可以在大括号 {} 中定义类成员的位置&#xff0c;如方法或构造函数。 每个类中包含了一个特殊的方法 constructor()&#xff0c;它是类…...

One-4-All: Neural Potential Fields for Embodied Navigation 论文阅读

论文信息 题目&#xff1a;One-4-All: Neural Potential Fields for Embodied Navigation 作者&#xff1a;Sacha Morin, Miguel Saavedra-Ruiz 来源&#xff1a;arXiv 时间&#xff1a;2023 Abstract 现实世界的导航可能需要使用高维 RGB 图像进行长视野规划&#xff0c;这…...

【ES】笔记-函数参数默认值

函数参数默认值 ES6 允许给函数参数赋值初始值 1. 形参初始值 具有默认值的参数&#xff0c;一般放到最后 function add(a,b,c10){return abc}let resultadd(1,2);console.log(result);2. 与解构赋值结合 function connect({host"127.0.0.1",username,password,port…...

安装harbor

目录 1. 安装docker-compose Compose 项目是 Docker 官方的开源项目&#xff0c;负责实现对 Docker 容器集群的快速编排。使用前面介绍的Dockerfile我们很容易定义一个单独的应用容器。然而在日常开发工作中&#xff0c;经常会碰到需要多个容器相互配合来完成某项任务的情况。例…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...