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

Day69:283. 移动零、11. 盛最多水的容器、42. 接雨水

283. 移动零

leetcode链接:https://leetcode.cn/problems/move-zeroes/

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:输入: nums = [0]
输出: [0]
提示:1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶:你能尽量减少完成的操作次数吗?

这题就是一个典型的快慢指针问题,类似于从数组中删除指定元素。快指针依次遍历,慢指针用来存放元素。思路就是先把所有的0元素删除,再在数组末位填充0,代码如下:

class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;for(int  i = 0 ; i < nums.size(); i++){if(nums[i] != 0){nums[slow++] =nums[i];}}//把剩下的位置填充为0for(int i = slow; i < nums.size(); i++){nums[i] = 0;}}
};

11.盛最多水的容器

给定一个长度为 n 的整数数组 height 。
有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明:你不能倾斜容器。

这题是贪心算法,

  1. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。示例 1:输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 
示例 2:输入:height = [4,2,0,3,2,5]
输出:9

image

对于这种问题,我们不要想整体,而应该去想局部。仅仅对于位置 i,能装下多少水呢?

image

能装 2 格水,因为 height[i] 的高度为 0,而这里最多能盛 2 格水,2-0=2。

为什么位置 i 最多能盛 2 格水呢?因为,位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关,我们分别称这两个柱子高度为 l_maxr_max位置 i 最大的水柱高度就是 min(l_max, r_max)

也就是说:

water[i] = min(# 左边最高的柱子max(height[0..i]),  # 右边最高的柱子max(height[i..end]) ) - height[i]

根据该思路写一个暴力解法。

暴力解法

class Solution {
public:int trap(vector<int>& height) {int res = 0;for(int i = 1; i < height.size() - 1; i++){//这样才能保证左右都有柱子int leftMax= 0, rightMax = 0;for (int j = i; j < height.size(); j++)rightMax = max(rightMax, height[j]);// 找左边最高的柱子for (int j = i; j >= 0; j--)leftMax = max(leftMax, height[j]);cout<< leftMax << ',' << rightMax << endl;res += max(0, min(leftMax,rightMax) - height[i]);}return res;}
};

时间复杂度O(n2),实际上不需要每次都遍历,可以借助备忘录。

这里实际上res加的时候时候不需要和0比较,因为在计算 l_max 数组的时候是取「自己高度」和「目前左边最高」的最大值,因此 l_max[i] >= height[i] 是恒成立的。r_max 同理。

备忘录

不用每次都计算left和right,计算一次就好,存储在两个数组中:

class Solution {
public:int trap(vector<int>& height) {if (height.size() == 0) {return 0;}int res = 0;vector<int> leftMax(height.size(), 0);vector<int> rightMax(height.size(), 0);leftMax[0] = height[0];rightMax[height.size() - 1] = height[height.size() - 1];for(int i = 1; i < height.size() - 1; i++){//这样才能保证左右都有柱子leftMax[i] = max(height[i], leftMax[i - 1]);}for(int i = height.size() - 2; i >= 0; i--){rightMax[i] = max(height[i], rightMax[i + 1]);}for(int i = 1; i < height.size() - 1; i++){res += min(leftMax[i],rightMax[i]) - height[i];}return res;}
};

把时间复杂度降低为 O(N),已经是最优了,但是空间复杂度是 O(N)。双指针法可以把空间复杂度降到O(1)。

双指针法

之前不管是暴力解法还是备忘录,leftMax和rightMax分别代表 height[0..i]height[i..end] 的最高柱子高度:

image

而在双指针法中,代表的是 height[0..left]height[right..end] 的最高柱子高度:

image

我们只在乎 min(l_max, r_max)对于上图的情况,我们已经知道 l_max < r_max 了,至于这个 r_max 是不是右边最大的,不重要。重要的是 height[i] 能够装的水只和较低的 l_max 之差有关。

最终代码:

class Solution {
public:int trap(vector<int>& height) {int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;int res = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);// res += min(leftMax, rightMax) - height[i]if (leftMax < rightMax) {res += leftMax - height[left];left++;} else {res += rightMax - height[right];right--;}}return res;}
};

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,
第 i 条线的两个端点是 (i, 0)(i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明:你不能倾斜容器。

image

输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49

跟上面的题类似,直接贴代码:

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

这里要注意双指针的移动顺序,为什么是往height[i]小的那边移动?因为矩形的最大面积是由最短的那条边决定的:如果移动较低的那一边,那条边可能会变高,使得矩形的高度变大,进而就「有可能」使得矩形的面积变大;相反,如果你去移动较高的那一边,矩形的高度是无论如何都不会变大的,所以不可能使矩形的面积变得更大。

总结

感觉这样复习还是太零散没有体系了,从明天开始,还是按照模块来,先把原来的题二刷掉,然后再找拓展题。

相关文章:

Day69:283. 移动零、11. 盛最多水的容器、42. 接雨水

283. 移动零 leetcode链接&#xff1a;https://leetcode.cn/problems/move-zeroes/ 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。示例 1:…...

tensorrt的安装和使用

安装 提前安装好 CUDA 和 CUDNN&#xff0c;登录 NVIDIA 官方网站下载和主机 CUDA 版本适配的 TensorRT 压缩包即可。 以 CUDA 版本是 10.2 为例&#xff0c;选择适配 CUDA 10.2 的 tar 包&#xff0c;然后执行类似如下的命令安装并测试&#xff1a; #安装c版本 cd /the/pat…...

电压放大器在电子测试中的应用有哪些方面

电压放大器是一种常见的电子设备&#xff0c;广泛应用于各种测试和测量应用中。以下是电压放大器在电子测试中的几个主要方面应用的简要介绍。 信号采集与处理&#xff1a;电压放大器通常用于信号采集和处理&#xff0c;在测试过程中将低电平信号放大到适合进一步处理或分析的水…...

39.地址算术运算

如果p是一个指向数组中某个元素的指针&#xff0c;那么p将会对p进行自增运算并指向下一个元素&#xff0c;而pi将对p进行加i的增量运算&#xff0c;使其指向指针p当前所指向的元素之后的第i个元素。这类运算时指针或地址算术运算中最简单的形式。 allocbuf中的空间使用状况也是…...

没有外网的麒麟系统上搭建GitLab服务并且无需客户端账号密码验证

要在没有外网的麒麟系统上搭建GitLab服务并且无需客户端账号密码验证&#xff0c;可以按照以下步骤进行操作&#xff1a; 安装必要的依赖包和软件 sudo yum install curl policycoreutils-python openssh-server openssh-clients sudo systemctl enable sshd sudo systemctl …...

微服务生态系统:使用Spring Cloud构建分布式系统

文章目录 什么是微服务&#xff1f;为什么选择Spring Cloud&#xff1f;Spring Cloud的关键组件示例&#xff1a;构建一个简单的微服务步骤1&#xff1a;创建Spring Boot项目步骤2&#xff1a;配置Eureka服务发现步骤3&#xff1a;创建REST控制器步骤4&#xff1a;运行项目步骤…...

DIY 一个汽车方向盘游戏外设(MMOS OSW DIY)

OSW-MMOS直驱方向盘DIY过程记录 - 简书 (jianshu.com) DIY 一个汽车方向盘游戏外设&#xff08;MMOS OSW DIY&#xff09; 首先讲一下这个直驱系统大概的框架&#xff0c;首先是电脑&#xff0c;电脑里装MMOS的软件(这个软件国内高手把它汉化了的)&#xff0c;电脑通过USB线&a…...

校园网络技术需求分析

路由技术&#xff1a; 路由协议工作在 OSI 参考模型的第 3 层&#xff0c;因此它的作用主要是在通信 子网间路由数据包。路由器具有在网络中传递数据时选择最佳路径的能力。 除了可以完成主要的路由任务&#xff0c;利用访问控制列表&#xff08;Access Control List&#x…...

计算机网络(二):TCP篇

文章目录 1. TCP头部包含哪些内容&#xff1f;2. 为什么需要 TCP 协议&#xff1f; TCP 工作在哪一层&#xff1f;3. 什么是 TCP &#xff1f;4. 什么是 TCP 连接&#xff1f;5. 如何唯一确定一个 TCP 连接呢&#xff1f;6. UDP头部大小是多少&#xff1f;包含哪些内容&#xf…...

测试登录界面:Python

import unittest from selenium import webdriver class LoginTest(unittest.TestCase): def setUp(self): self.driver webdriver.Chrome() def test_login(self): # 打开登录页面 self.driver.get("http://example.com/login") # 输入用户名和密码 user…...

Rust踩雷笔记(7)——两个链表题例子初识裸指针

目录 leetcode 234leetcode 19 leetcode 234 题目在这https://leetcode.cn/problems/palindrome-linked-list/&#xff0c;leetcode 234的回文链表&#xff0c;思路很简单&#xff0c;就是fast和slow两个指针&#xff0c;fast一次移动两个、slow一次一个&#xff0c;最后slow指…...

用什么命令看Linux系统的体系架构

要查看Linux系统的体系架构&#xff0c;可以使用uname命令。在终端中运行以下命令&#xff1a; uname -m该命令将返回系统的体系架构&#xff0c;例如x86_64表示64位系统&#xff0c;i686表示32位系统。 uname 使用方法 uname命令用于获取操作系统的相关信息。它可以用于显示…...

消息中间件大揭秘:选择之前你必须知道的关键信息

Hello大家好&#xff01;我是小米&#xff0c;很高兴再次和大家见面&#xff01;今天的话题非常精彩&#xff0c;我们将深入探讨消息中间件&#xff0c;并了解一些常见的消息队列&#xff1a;RabbitMQ、RocketMQ、Kafka以及Redis。如果你正在准备面试&#xff0c;或者只是对这些…...

【Unity基础】4.动画Animation

【Unity基础】4.动画Animation 大家好&#xff0c;我是Lampard~~ 欢迎来到Unity基础系列博客&#xff0c;所学知识来自B站阿发老师~感谢 &#xff08;一&#xff09;Unity动画编辑器 &#xff08;1&#xff09;Animation组件 这一张我们要学习如何在unity编辑器中&…...

FreeRTOS移植以及核心功能

文章目录 freertos和ucos区别&#xff0c;优缺点比较移植步骤核心功能内存管理&#xff08;5种内存管理策略&#xff09;FreeRTOS任务调度算法有三种时间管理通信管理 栈管理 freertos和ucos区别&#xff0c;优缺点比较 FreeRTOS&#xff08;Free Real-Time Operating System&…...

重装系统(配置环境)

这里写目录标题 0.重装系统1.python1.1 anaconda1.2 pycharm1.3 深度学习环境配置 2.java2.1.安装JDK2.2.配置JDK环境变量2.3IDEA2.4 Maven 3.大数据3.1 虚拟机3.2 Hadoop平台3.3 存储3.4 采集3.5 计算3.6 查询3.7 可视化 0.重装系统 // An highlighted block var foo bar;1.…...

docker系列-报错以及解决指南

1. windows运行docker报错Windows Hypervisor is not presentDocker Desktop is unable to detect a Hypervisor.Hardware assisted virtualization and data execution protection must be enabled in the BIOS. Docker Desktop - Windows Hypervisor is not presentDocker D…...

Vue3快速上手

1.Vue3简介 2020年9月18日&#xff0c;Vue.js发布3.0版本&#xff0c;代号&#xff1a;One Piece&#xff08;海贼王&#xff09;耗时2年多、2600次提交、30个RFC、600次PR、99位贡献者github上的tags地址&#xff1a;Release v3.0.0 One Piece vuejs/core GitHub 2.Vue3带…...

二叉搜索树(BST,Binary Search Tree)

文章目录 1. 二叉搜索树1.1 二叉搜索树概念1.2 二叉搜索树的查找1.3 二叉搜索树的插入1.4 二叉搜索树的删除 2 二叉搜索树的实现3 二叉搜索树的应用3.1二叉搜索树的性能分析 1. 二叉搜索树 1.1 二叉搜索树概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xf…...

分析key原理

总结&#xff1a; key是虚拟dom对象的标识&#xff0c;当数据发生变化时&#xff0c;vue会根据新数据生成新的虚拟dom&#xff0c;随后vue进行新虚拟dom与旧虚拟dom的差异比较 比较规则&#xff1a; ①旧虚拟dom中找到了与新虚拟dom相同的key 若虚拟dom中的内容没变&#xff0c…...

[CISCN2019 华东南赛区]Web11 SSTI

这道SSTI 差点给我渗透的感觉了 全是API 我还想去访问API看看 发现这里读取了我们的ip 我们抓包看看是如何做到的 没有东西 我们看看还有什么提示 欸 那我们可不可以直接修改参数呢 我们传递看看 发现成功了 是受控的 这里我就开始没有思路了 于是看了wp 说是ssti 那我们看…...

百度春招C++后端面经总结

这次的面经,主要都是问操作系统、网络编程、C++ 这三大方向。 能明显感觉到,C++面试和Java或者Go面试重点,Java/Go主要是问MySQL、Redis。 一、介绍一下webserver项目 服务器开始运行,创建(初始化)线程池(IO密集型,线程数n+1); 创建 epoll 对连接进行监听 监听到连…...

小程序开发一个多少钱啊

在今天的数字化时代&#xff0c;小程序已经成为一种非常流行的应用程序形式。由于它们的便捷性、易用性和多功能性&#xff0c;小程序吸引了越来越多的用户和企业。但是&#xff0c;很多人在考虑开发一个小程序时&#xff0c;都会遇到同一个问题&#xff1a;开发一个小程序需要…...

C# 随机数生成 Mersenne Twister 马特赛特旋转演算法 梅森旋转算法

NuGet安装MathNet.Numerics 引用: using MathNet.Numerics.Random; /// <summary>/// 包括lower&#xff0c;不包括upper/// </summary>/// <param name"lower"></param>/// <param name"upper"></param>/// <para…...

C++进阶(二)

目录 1、Vector2D 默认构造、重载 2、char 深度理解 3、深度理解简单的类操作 1、Vector2D 默认构造、重载 #include <iostream> #include <cmath>class Vector2D { private:double x; // X坐标double y; // Y坐标public:// 默认构造函数&#xff0c;将向量初…...

zoneinfo

在Linux系统中&#xff0c;zoneinfo是一个包含了世界各地时区信息的目录&#xff0c;通常位于/usr/share/zoneinfo。这个目录下的子目录和文件名对应了各个时区的名称。例如&#xff0c;/usr/share/zoneinfo/America/Los_Angeles文件就包含了美国洛杉矶的时区信息。 你可以通过…...

基于微信小程序的实验室预约管理系统设计与实现

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…...

腾讯mini项目-【指标监控服务重构】2023-08-17

今日已办 定位昨日发现的问题 来回测试发现依然出现该问题 将 pub/sub 的库替换为原来官方基于 sarama 的实现&#xff0c;发现问题解决了&#xff0c;所以问题的根本是 kafkago 这个库本身存在问题 依据官方的实现&#xff0c;尝试自定义实现 pub/sub sarama 与 kafka-go …...

前端需要知道的计算机网络知识----网络安全,自学网络安全,学习路线图必不可少,【282G】初级网络安全学习资源分享!

网络安全&#xff08;英语&#xff1a;network security&#xff09;包含网络设备安全、网络信息安全、网络软件安全。 黑客通过基于网络的入侵来达到窃取敏感信息的目的&#xff0c;也有人以基于网络的攻击见长&#xff0c;被人收买通过网络来攻击商业竞争对手企业&#xff0…...

#循循渐进学51单片机#定时器与数码管#not.4

1、熟练掌握单片机定时器的原理和应用方法。 1&#xff09;时钟周期&#xff1a;单片机时序中的最小单位&#xff0c;具体计算的方法就是时钟源分之一。 2&#xff09;机器周期&#xff1a;我们的单片机完成一个操作的最短时间。 3)定时器&#xff1a;打开定时器“储存寄存器…...

各类郑州网站建设/刚刚中国突然宣布

2019独角兽企业重金招聘Python工程师标准>>> 转载于:https://my.oschina.net/2726276586/blog/683938...

网站建设企业模板/seo sem是指什么意思

一、在线防护的需求现在在网络安全方面存在着许多安全风险&#xff0c;并且呈现不断上升的趋势&#xff0c;这些不断增长的风险包含更多的复杂性和变化性。安全管理员需要一种途径来检测和阻止这些***&#xff0c;并且能够经常了解新的***行为&#xff0c;以便阻止这些***。图2…...

网站栏目划分/永久免费自助建站平台

http://codeforces.com/contest/351/problem/E 题意&#xff1a; 给出一些数&#xff0c;可以改变任意数的正负&#xff0c;使序列的逆序对数量最少 因为可以任意加负号&#xff0c;所以可以先把所有数看作正数 序列中的数无论怎么改&#xff0c;都不会改变与绝对值最大的数的逆…...

视频网站建设公司/如何建立免费个人网站

2.把MXS的帮助文档搬到了码云&#xff0c;以后在线帮助就可以更快加载和使用在线翻译了 https://trykle.gitee.io/3dsmax-2020.1-maxscript-help 1.MXS混淆器添加了一个操作&#xff0c;让目前市面上的解析器部分失效 转载于:https://www.cnblogs.com/trykle/p/11337184.html...

密云住房和城乡建设部网站首页/培训机构哪家好

这些题目都是大一刚入学时学习C语言的课后作业&#xff0c;在OJ上看到还保留着&#xff0c;就都整理下发出来吧......(只有题和代码)【问题描述】编写程序&#xff0c;打开一篇英文文章(存在当前目录下的文件in.txt中)&#xff0c;为该文章生成词汇表(存到当前目录下的另一个文…...

网站制作模板程序/中国法律服务网app最新下载

学习了Python的各种基础语法和常用包后&#xff0c;你是否对如何使用Python在实际工作中进行数据分析一头雾水&#xff1f;如果是&#xff0c;今天这篇文章一定能带给你一些用数据分析解决实际问题的思路。数据分析的目的决定了你的分析步骤&#xff0c;比如你的分析的目标是提…...