入门力扣自学笔记277 C++ (题目编号:42)(动态规划)
42. 接雨水
题目:
给定 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
提示:
n == height.length1 <= n <= 2 *0 <= height[i] <=
思路:
首先,获取数组长度。
其次,获取每一个点的左侧和右侧的最大高度。
最后,找到每一个点左侧和右侧最大高度较小的那个(因为只有较小的那个高度才能限制雨水容量)。将这个减去该位置的高度,即可得到该位置的雨水单位数,将其累加到最终结果中。
代码:
class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);//cout << leftMax[i] << '|';}//cout << endl;vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);//cout << rightMax[i] << '|';}//cout << endl;int ans = 0;for (int i = 0; i < n; ++i) {ans += min(leftMax[i], rightMax[i]) - height[i];//cout << min(leftMax[i], rightMax[i]) - height[i] << '|';}return ans;}
};
相关文章:
入门力扣自学笔记277 C++ (题目编号:42)(动态规划)
42. 接雨水 题目: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组…...
SwiftUI实现iPad多任务分屏
1. 概述 iPadOS引入了多任务分屏功能,使用户能够同时在一个屏幕上使用多个应用程序。这为用户提供了更高效的工作环境,可以在同一时间处理多个任务。 iPad多任务分屏有两种常见的模式:1/2分屏和Slide Over(滑动覆盖)…...
maven依赖,继承
依赖的范围 compile引入的依赖 对main目录下的代码有没有效,main目录下的代码能不能用compile引入的依赖中的类等 以test引入的依赖,在main中是否可以使用 provided(已提供),有了就不要带到服务器上,打包…...
仿`gRPC`功能实现像调用本地方法一样调用其他服务器方法
文章目录 仿gRPC功能实现像调用本地方法一样调用其他服务器方法 简介单体架构微服务架构RPCgPRC gRPC交互逻辑服务端逻辑客户端逻辑示例图 原生实现仿gRPC框架编写客户端方法编写服务端方法综合演示 仿 gRPC功能实现像调用本地方法一样调用其他服务器方法 简介 在介绍gRPC简介…...
分布式环境下的数据同步
一般而言elasticsearch负责搜索(查询),而sql数据负责记录(增删改),elasticsearch中的数据来自于sql数据库,因此sql数据发生改变时,elasticsearch也必须跟着改变,这个就是…...
无涯教程-Flutter - 数据库
SQLite" class"css-1occaib">SQLite数据库是基于事实和标准SQL的嵌入式数据库引擎,它是小型且经过时间考验的数据库引擎,sqflite软件包提供了许多函数,可以有效地与SQLite数据库一起使用,它提供了操作SQLite数据…...
算法笔记:平衡二叉树
1 介绍 平衡二叉树(AVL树)是一种特殊的二叉搜索树(BST),它自动确保树保持低高度,以便实现各种基本操作(如添加、删除和查找)的高效性能。 ——>时间都维持在了O(logN)它是一棵空…...
redis 通用命令
目录 通用命令是什么 SET & GET keys EXISTS DEL EXPIRE TTL redis 的过期策略 定时器策略 基于优先级队列定时器 基于时间轮的定时器 TYPE 通过 redis 客户端和 redis 服务器交互。 所以需要使用 redis 的命令,但是 redis 的命令非常多。 通用命令…...
Pycharm配置及使用Git教程
文章目录 1. 安装PyCharm2. 安装Git3. 在PyCharm中配置Git插件4. 连接远程Gtilab仓库5. Clone项目代码6. 将本地文件提交到远程仓库6.1 git add6.2 git commit6.3 git push6.4 git pull 平时习惯在windows下开发,但是我们又需要实时将远方仓库的代码clone到本地&…...
CSS transition 过渡
1 前言 水平居中、垂直居中是前端面试百问不厌的问题。 其实现方案也是多种多样,常叫人头昏眼花。 水平方向可以认为是内联方向,垂直方向认为是块级方向。 下面介绍一些常见的方法。 2 内联元素的水平垂直居中 首先,常见内联元素有&…...
Unity中Shader的UV扭曲效果的实现
文章目录 前言一、实现的思路1、在属性面板暴露一个 扭曲贴图的属性2、在片元结构体中,新增一个float2类型的变量,用于独立存储将用于扭曲的纹理的信息3、在顶点着色器中,根据需要使用TRANSFORM_TEX对Tilling 和 Offset 插值;以及…...
Automotive 添加一个特权APP
Automotive 添加一个特权APP platform: android-13.0.0_r32 一. 添加一个自定义空调的app为例 路径:packages/apps/Car/MyHvac app内容可以自己定义,目录结构如下: 1.1 Android.bp package {default_applicable_licenses: ["Andr…...
自定义TimeLine
自定义TimeLine 什么是TimeLineData(数据)Clip(片段)Track(轨道)Mixer(混合) 什么是TimeLine 在 Unity 中,TimeLine(时间轴)是一种用于创建和管理…...
如何使用SQL系列 之 如何在SQL中使用WHERE条件语句
引言 在结构化查询语言 (SQL)语句中,WHERE子句限制了给定操作会影响哪些行。它们通过定义特定的条件(称为搜索条件)来实现这一点,每一行都必须满足这些条件才能受到操作的影响。 本指南将介绍WHERE子句中使用的通用语法。它还将概述如何在单个WHERE子句…...
leetcode:1941. 检查是否所有字符出现次数相同(python3解法)
难度:简单 给你一个字符串 s ,如果 s 是一个 好 字符串,请你返回 true ,否则请返回 false 。 如果 s 中出现过的 所有 字符的出现次数 相同 ,那么我们称字符串 s 是 好 字符串。 示例 1: 输入:s…...
Echarts 各种点击事件监听
目录 一、鼠标事件1.1、左击1.2、双击1.3、右击1.4、右键双击1.5、中轴滚动二、时间轴2.1、时间轴监听三、拖动3.1、拖动事件一、鼠标事件 1.1、左击 chart.on(click, function(params)...
《智能网联汽车自动驾驶功能测试规程》
一、 编制背景 2018 年4 月12 日,工业和信息化部、公安部、交通运输部联合发布《智能网联汽车道路测试管理规范(试行)》(以下简称《管理规范》),对智能网联汽车道路测试申请、审核、管理以及测试主体、测试驾驶人和测试车辆要求等…...
NVIDIA CUDA Win10安装步骤
前言 windows10 版本安装 CUDA ,首先需要下载两个安装包 CUDA toolkit(toolkit就是指工具包)cuDNN 1. 安装前准备 在安装CUDA之前,需要完成以下准备工作: 确认你的显卡已经正确安装,在设备管理器中可以看…...
Elasticsearch、Kibana以及Java操作ES 的快速使用
docker 安装elastic search 、 kibana(可视化管理elastic search) docker pull elasticsearch:7.12.1 docker pull kibana:7.12.1创建docker自定义网络 docker自定义网络可以使得容器之间使用容器名网络互连,默认的网络不会有这功能。 一定…...
逐鹿人形机器人,百度、腾讯、小米卷起来
长期不温不火的人形机器人产业迎来新风口,技术显著提升、新品层出不穷、资本投资态度也逐渐好转。 8月18日,2023世界机器人大会博览会正式开放,全面展示了机器人行业的新技术、新产品和新应用。据悉,此次展会展览总面积达4.5万平…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
