【算法刷题】Day8

文章目录

  • 202. 快乐数
    • 解法:
  • 11. 盛最多水的容器
    • 解法:

202. 快乐数

在这里插入图片描述
在这里插入图片描述
原题链接


拿到题,我们先看题干
把一个整数替换为每个位置上的数字平方和,有两种情况:

  1. 重复这个过程始终不到 1(无限死循环)
  2. 结果变成 1(快乐数)

接下来我们画图看一下是不是这两种情况
在这里插入图片描述
在这里插入图片描述
画完图我们就可以发现,这个跟曾经数据结构学过的判断链表是否有环非常相似
判断是不是快乐数,就是看入环的数字是几,如果是 1 那么就是快乐数

解法:

(快慢双指针)

  1. 定义快慢双指针 slow 和 fast
  2. 慢指针每次向后移动一位
    快指针每次向后移动两位
  3. 判断相遇的值是不是 1
class Solution {public int isSum(int n) {int sum = 0;while(n != 0) {int t = n % 10;sum += t*t;n = n / 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = isSum(n);while(slow != fast) {slow = isSum(slow);fast = isSum(isSum(fast));}return slow == 1;}
}

在这里插入图片描述

11. 盛最多水的容器

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
[原题链接](https://leetcode.cn/problems/container-with-most-water/


先看题干,貌似就是求体积,再看示例,就是求两段之间最小的那个值 乘 两段之间的差值

解法:

一:(暴力枚举)
运用两个 for 循环进行枚举
但是时间复杂度为 O(n2)
会导致时间溢出

二:(利用单调性,使用双指针)
这里我们先看一下什么是单调性
在这里插入图片描述
先用 [ 6, 2, 5, 4 ] 来举例
6 > 4
所以如果 4 不变,从右向左一个一个计算体积
4 * 3 = 12
2 * 2 = 4
4 * 1 = 4
发现只有第一个的体积是最大的
这样我们可以直接删去 4 ,从 6 开始向 5 进行遍历
这就是单调性

利用这样的规律,我们在看原数组,我们就可以这样解题
在这里插入图片描述

  1. 定义双指针 left 和 right
  2. 把 最大的体积存放到 ret 中
  3. left 和 right 比较大小
    left < right : left ++;
    left > right : right–;
  4. 直到 left 和 right 相遇
class Solution {public int maxArea(int[] height) {int left = 0;int right = height.length-1;int ret = 0;while(left < right) {int v = Math.min(height[left],height[right]) * (right - left);ret = Math.max(ret,v);if(height[left] < height[right]) {left++;}else {right--;}   }return ret;}
}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

P27 C++this 关键字

目录 前言 01 this关键字的引入 02 this关键字 前言 本章的主题是 C 中的 this 关键字。 以前第一次学qt的时候就遇到了this关键字&#xff0c;那时候还不是很会C&#xff0c;所以有点懵&#xff0c;现在我们就来讲解以下C中的this关键字 C 中有一个关键字 this&#xff0…

考过了PMP,面试的时候应该怎么办?

近期喜番在后台收到了很多同学们的私信&#xff0c;表示自己已经过了8月份的PMP考试&#xff0c;开始着手往项目管理岗位转型&#xff0c;但是对于项目管理岗位的面试却一筹莫展。放轻松&#xff0c;大家的需求喜番都了解了&#xff0c;喜番给大家总结了一些项目经理在面试的时…

漏电保护器工作原理

漏电保护器 漏电保护器是低压线路中最常用的保护器之一&#xff0c;简称漏保&#xff0c;又称漏电开关或漏电断路器。漏电保护器除了具有空开的所有保护功能外&#xff0c;还具备漏电保护功能。 需要了解 一根通电导线可以产生磁场&#xff0c;磁场与电流方向遵循右手螺旋关…

【深度学习】学习率及多种选择策略

学习率是最影响性能的超参数之一&#xff0c;如果我们只能调整一个超参数&#xff0c;那么最好的选择就是它。相比于其它超参数学习率以一种更加复杂的方式控制着模型的有效容量&#xff0c;当学习率最优时&#xff0c;模型的有效容量最大。本文从手动选择学习率到使用预热机制…

深入理解OS--硬件高速缓存,缓存一致性,存储设备

存储技术 1.SRAM&#xff0c;DRAM 静态&#xff1a;更快&#xff0c;用作高速缓存存储器。处理器高速缓存采用SRAM。 动态&#xff1a;用作主存及图形系统的帧缓冲区。内存采用DRAM。 2.内存 2.1.内存数据访问示例 设备控制器存在缓存。设备芯片自身存在缓存。 2.2.采用并行…

【算法刷题】Day7

文章目录 283. 移动零1089. 复写零 283. 移动零 原题链接 看到题目&#xff0c;首先看一下题干的要求&#xff0c;是在原数组内进行操作&#xff0c;平切保持非零元素的相对顺序 这个时候我们看到了示例一&#xff1a; [ 0, 1, 0, 3,12 ] 这个时候输出成为了 [ 1, 3, 12, 0, …

【图论】重庆大学图论与应用课程期末复习资料(私人复习资料)

考试章节范围 第一章&#xff1a;1.1、1.2、1.3 填空 顶点集和边集都有限的图&#xff0c;称为有限图只有一个顶点的图&#xff0c;称为平凡图边集为空的图&#xff0c;称为空图顶点数为n的图&#xff0c;称为n阶图连接两个相同顶点的边的条数称为边的重数&#xff1b;重数大…

k8s安装步骤

环境&#xff1a; 操作系统&#xff1a;win10 虚拟机&#xff1a;VMware linux发行版&#xff1a;CentOS7.9 CentOS镜像&#xff1a;CentOS-7-x86_64-DVD-2009 master和node节点通信的ip(master)&#xff1a; 192.168.29.164 0.检查配置 本次搭建的集群共三个节点&#xff0c;…

C语言基础程序设计题

1.个人所得税计算 应纳税款的计算公式如下&#xff1a;收入<&#xff1d;1000元部分税率为0&#xff05;&#xff0c;2000元>&#xff1d;收入>1000元的部分税率为5&#xff05;&#xff0c;3000元>&#xff1d;收入>2000元的部分税率为10&#xff05;&#xf…

【开源】基于Vue和SpringBoot的个人健康管理系统

项目编号&#xff1a; S 040 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S040&#xff0c;文末获取源码。} 项目编号&#xff1a;S040&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 健康档案模块2.2 体检档案模块2.3 健…

Edit And Resend测试接口工具(浏览器上的Postman)

优点 可以不用设置Cookie或者Token&#xff0c;只设置参数进行重发接口测试API 使用Microsoft Rdge浏览器 F12——然后点击网络——在页面点击发起请求——然后选择要重发的请求右键选择Edit And Resend——在网络控制台设置自己要设置的参数去测试自己写的功能

qt实现一个安卓测试小工具

qt实现一个安卓测试小工具 最终效果&#xff1a;目录结构源码gui.py 主要是按钮&#xff0c;文本控制代码main.py 主要是逻辑代码gui.spec 是打包使用的adb.ui 打包为exe 最终效果&#xff1a; 目录结构 上面2个是打包的生成的不用管 源码 gui.py 主要是按钮&#xff0c;文…

第二十章总结

一.线程简介 二.创建线程 1.继承Thread类 Thread类中常用的两个构造方法如下&#xff1a; public Thread():创建一个新的线程对象。 public Thread(String threadName):创建一个名称为threadName的线程对象。 继承Thread类创建一个新的线程的语法如下&#xff1a; p…

Blender动画导入Three.js

你是否在把 Blender 动画导入你的 ThreeJS 游戏(或项目)中工作时遇到问题? 您的 .glb (glTF) 文件是否正在加载,但没有显示任何内容? 你的骨骼没有正确克隆吗? 如果是这样,请阅读我如何使用 SkeletonUtils.js 解决此问题 1、前提条件 你正在使用 Blender 3.1+(此版本…

centos无法进入系统之原因解决办法集合

前言 可爱的小伙伴们&#xff0c;由于精力有限&#xff0c;暂时整理了两类。如果没有你遇到的问题也没有关系&#xff0c;欢迎底下留言评论或私信&#xff0c;小编看到后第一时间帮助解决 一. Centos 7 LVM xfs文件系统修复 情况1&#xff1a; [sda] Assuming drive cache:…

flask web开发学习之初识flask(一)

一、概念 flask是一个使用python编写的轻量级web框架&#xff0c;作者为Armin Ronacher&#xff08;中文名&#xff1a;阿尔敏罗纳彻&#xff09;&#xff0c;它广泛被应用于web开发和API。flask提供了简洁而灵活地方式来构建web应用&#xff0c;它不会强加太多约束&#xff0…

大数据平台/大数据技术与原理-实验报告--部署全分布模式HBase集群和实战HBase

实验名称 部署全分布模式HBase集群和实战HBase 实验性质 &#xff08;必修、选修&#xff09; 必修 实验类型&#xff08;验证、设计、创新、综合&#xff09; 综合 实验课时 2 实验日期 2023.11.07-2023.11.10 实验仪器设备以及实验软硬件要求 专业实验室&#xff…

如何在Ubuntu的Linux系统中安装MySQL5.7数据库

前往MySQL数据库官网链接地址下载5.7数据库。 MySQL :: Download MySQL Community Server (Archived Versions)使用ssh的可视化工具将下载的mysql-5.7.40-linux-glibc2.12-x86_64.tar.gz文件上传到Linux服务器&#xff0c;并解压文件 tar -zxvf mysql-5.7.40-linux-glibc2.12-x…

vue+SpringBoot的图片上传

前端VUE的代码实现 直接粘贴过来element-UI的组件实现 <el-uploadclass"avatar-uploader"action"/uploadAvatar" //这个action的值是服务端的路径&#xff0c;其他不用改:show-file-list"false":on-success"handleAvatarSuccess"…