Rust每日一练(Leetday0014) 组合总和II、缺失正数、接雨水

目录
40. 组合总和 II Combination Sum II 🌟🌟
41. 缺失的第一个正数 First Missing Positive 🌟🌟🌟
42. 接雨水 Trapping Rain Water 🌟🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
40. 组合总和 II Combination Sum II
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5 输出: [ [1,2,2], [5] ]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
代码: 回溯法
fn combination_sum_ii(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {let mut res = Vec::new();if candidates.len() > 0 {let mut candidates = candidates;candidates.sort();backtrack(&candidates, 0, target, &mut Vec::new(), &mut res);}res
}fn backtrack(candidates: &Vec<i32>, start: usize, target: i32, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {if target == 0 {res.push(path.clone());return;}for i in start..candidates.len() {if i > start && candidates[i] == candidates[i - 1] {continue;}let cur = candidates[i];if cur <= target {path.push(cur);backtrack(candidates, i + 1, target - cur, path, res);path.pop();} else {break;}}
}fn main() {let candidates = vec![10, 1, 2, 7, 6, 1, 5];println!("{:?}", combination_sum_ii(candidates, 8));let candidates = vec![2, 5, 2, 1, 2];println!("{:?}", combination_sum_ii(candidates, 5));
}
输出:
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[[1, 2, 2], [5]]
41. 缺失的第一个正数 First Missing Positive
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0] 输出:3
示例 2:
输入:nums = [3,4,-1,1] 输出:2
示例 3:
输入:nums = [7,8,9,11,12] 输出:1
提示:
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1
代码1:
fn first_missing_positive(nums: Vec<i32>) -> i32 {let n = nums.len();let mut nums = nums;// 将数组中的每个数放到对应的位置上for i in 0..n {while nums[i] > 0 && nums[i] <= n as i32 && nums[nums[i] as usize - 1] != nums[i] {let j = nums[i] as usize - 1;nums.swap(i, j);}}// 遍历一遍数组,找到第一个位置上的数不是对应的数for i in 0..n {if nums[i] != i as i32 + 1 {return i as i32 + 1;}}return n as i32 + 1;
}fn main() {let nums = vec![1, 2, 0];println!("{}", first_missing_positive(nums));let nums = vec![3, 4, -1, 1];println!("{}", first_missing_positive(nums));let nums = vec![7, 8, 9, 11, 12];println!("{}", first_missing_positive(nums));
}
代码2:
use std::collections::HashSet;fn first_missing_positive(nums: Vec<i32>) -> i32 {let n = nums.len();let mut set = HashSet::new();for v in nums {set.insert(v);}for i in 1..=n {if !set.contains(&(i as i32)) {return i as i32;}}return n as i32 + 1;
}fn main() {let nums = vec![1, 2, 0];println!("{}", first_missing_positive(nums));let nums = vec![3, 4, -1, 1];println!("{}", first_missing_positive(nums));let nums = vec![7, 8, 9, 11, 12];println!("{}", first_missing_positive(nums));
}
代码3:
fn first_missing_positive(nums: Vec<i32>) -> i32 {let n = nums.len();// 将数组中所有小于等于0的数和大于n的数都替换成n+1let mut nums = nums.into_iter().map(|x| if x <= 0 || x > n as i32 { n as i32 + 1 } else { x }).collect::<Vec<i32>>();// 使用哈希表记录数组中出现的正整数for i in 0..n {let num = nums[i].abs();if num <= n as i32 {nums[(num - 1) as usize] = -nums[(num - 1) as usize].abs();}}// 从1开始遍历正整数,找到第一个没出现的即可for i in 1..=n {if nums[(i - 1) as usize] > 0 {return i as i32;}}return n as i32 + 1;
}fn main() {let nums = vec![1, 2, 0];println!("{}", first_missing_positive(nums));let nums = vec![3, 4, -1, 1];println!("{}", first_missing_positive(nums));let nums = vec![7, 8, 9, 11, 12];println!("{}", first_missing_positive(nums));
}
输出:
3
2
1
42. 接雨水 Trapping Rain Water
给定 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 * 10^40 <= height[i] <= 10^5
代码1: 双指针
fn trap(height: Vec<i32>) -> i32 {let n = height.len();if n == 0 {return 0;}let (mut left, mut right) = (0, n - 1); // 双指针let (mut max_left, mut max_right) = (0, 0); // 最高的柱子高度let mut res = 0;while left < right { // 当 left 和 right 相遇时结束循环if height[left] < height[right] {max_left = max(max_left, height[left]);res += max_left - height[left];left += 1;} else {max_right = max(max_right, height[right]);res += max_right - height[right];right -= 1;}}return res;
}fn max(a: i32, b: i32) -> i32 {if a > b {return a;}return b;
}fn main() {let height = vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];println!("{}", trap(height));let height = vec![4, 2, 0, 3, 2, 5];println!("{}", trap(height));
}
输出:
6
9
方法2: 循环暴力
fn trap(height: Vec<i32>) -> i32 {let n = height.len();if n == 0 {return 0;}let mut left: Vec<i32> = vec![0; n]; // 记录左边最高的柱子高度let mut right: Vec<i32> = vec![0; n]; // 记录右边最高的柱子高度left[0] = height[0];for i in 1..n {left[i] = max(left[i-1], height[i]);}right[n-1] = height[n-1];for i in (0..n-1).rev() {right[i] = max(right[i+1], height[i]);}let mut res = 0;for i in 1..n-1 {res += min(left[i], right[i]) - height[i];}return res;
}fn max(a: i32, b: i32) -> i32 {if a > b {return a;}return b;
}fn min(a: i32, b: i32) -> i32 {if a < b {return a;}return b;
}fn main() {let height = vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];println!("{}", trap(height));let height = vec![4, 2, 0, 3, 2, 5];println!("{}", trap(height));
}
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
|
| Rust每日一练 专栏(2023.5.16~)更新中... |
|
| Golang每日一练 专栏(2023.3.11~)更新中... |
|
| Python每日一练 专栏(2023.2.18~2023.5.18)暂停更 |
|
| C/C++每日一练 专栏(2023.2.18~2023.5.18)暂停更 |
|
| Java每日一练 专栏(2023.3.11~2023.5.18)暂停更 |
相关文章:
Rust每日一练(Leetday0014) 组合总和II、缺失正数、接雨水
目录 40. 组合总和 II Combination Sum II 🌟🌟 41. 缺失的第一个正数 First Missing Positive 🌟🌟🌟 42. 接雨水 Trapping Rain Water 🌟🌟🌟 🌟 每日一练刷题…...
EnjoyVIID部署
1、下载 git clone https://gitee.com/tsingeye/EnjoyVIID.git 2、导入数据库 创建表enjoyviid 导入数据库(修改数据库文件里的编码) EnjoyVIID/sql/tsingeye-viid.sql 3、修改配置 vim EnjoyVIID/tsingeye-admin/src/main/resources/application-dev.yml 修改数据库连接、re…...
用Python解决爱因斯坦的数学问题
1 问题 有一条阶梯,若每步跨2阶,则剩最后一阶,若每步跨3阶,则最后剩2阶,若每步跨5阶,则最后剩4阶,若每步跨6阶,则最后剩5阶,只有每次跨7阶,最后才刚好不剩&am…...
ChatGPT提示词攻略之基本原则
下面是调用openai的completion接口的函数。但在本文中并不是重点。了解一下就好。 import openai import osfrom dotenv import load_dotenv, find_dotenv _ load_dotenv(find_dotenv())openai.api_key os.getenv(OPENAI_API_KEY)def get_completion(prompt, model"gp…...
抖音seo源码如何开发部署?
前言:抖音seo源码,抖音矩阵系统源码搭建,抖音矩阵同步分发。抖音seo源码部署是需要对接到这些正规接口再来做开发的,目前账号矩阵程序开发的功能,围绕一键管理多个账号,做到定时投放,关键词自动…...
Java中常见锁的分类及概念分析
基于线程对同一把锁的获取情况分类 可重入锁 同一个线程可以多次获取锁 每次获取锁,锁的计数器加1,每次释放锁锁的计数器减1 锁的计数器归零,锁完全释放 Java中提供的synchronized,ReentrantLock,ReentrantReadWriteL…...
ConcurrentLinkedQueue的源码解析(基于JDK1.8)
ConcurrentLinkedQueue的源码解析(基于JDK1.8) ConcurrentLinkedQueue是Java集合框架中的一种线程安全的队列,它是通过CAS(Compare and Swap)算法实现的并发队列。在并发场景下,ConcurrentLinkedQueue能够…...
低资源方面级情感分析研究综述
文章目录 前言1. 引言2. 问题定义、数据集和评价指标2.1 问题定义2.2 任务定义2.3 常用数据集 3. 方面级情感分析的方法3.1 **方面词抽取**3.1.1 基于无监督学习的方法3.1.1.1 基于规则的方面词抽取3.1.1.2 基于统计的方面词抽取 3.1.2 基于有监督浅层模型的方法3.1.3 基于有监…...
将 PDF 压缩到 1 MB 或更小的 5 个工具
鉴于工作和生活中PDF文件的频繁传输,压缩文件大小成为PDF文件必不可少的一步,尤其是对于包含大量高清图片的文件。压缩不仅使您的文件兼容发送,还有助于存储优化。这意味着您将获得更多数据空间,适用于本地设备和云端。 想要将 …...
CSMA/CD协议之计算最短帧长问题
文章目录 前言CSMA/CD协议计算最短帧长 前言 本篇博客主要论述了如何计算 CSMA/CD 协议下的网络帧长问题,从概念入手,结合例题进行详细的分析。 CSMA/CD协议 概念: ① 载波监听多点接入/碰撞检测 ② 半双工通信 ③ 先听后发、边听边发、冲…...
第三章:什么是分库分表
文章目录 背景什么是分库分表为什么要分库分表性能可用性什么时候考虑分库分表什么时候分库什么时候分表背景 一个系统当伴随着用户量的激增,业务数据的不断增加,数据库表中的数据越来越多,如果再去对我们数据库中的表进行curd操作的时候,就会造成一些性能上的瓶颈问题! …...
SpringMVC第六阶段:数据在域中的保存(02)
数据在域中的保存(02) 1、Map或Model或ModelMap形式保存数据在request域中 在四个域中,我们使用最频繁的域就是request对象。往request域对象中,保存数据,还在以下的几种形式。 我们可以在Controller的方法中&#x…...
Springboot +spring security,认证方式---HTTP基本认证的实现
一.简介 这篇文章来学习下security的认证方式其中的HTTP基本认证。 二.Spring Security的认证方式 2.1什么是认证 认证: 就是用来判断系统中是否存在某用户,并判断该用户的身份是否合法的过程,解决的其实是用户登录的问题。认证的存在,是…...
2023年系统分析师案例及论文(回忆版)
2023年5月27日,全国计算机等级上半年考试如期举行 北京市软件分析师考试地点在北京市对外贸易学校,早上外面下起雨,正如考前紧张的心情。 看考场分布图,44个考场,推测有44*301320名考生,本人所在的考场&am…...
数据结构与算法面试题
(1) 红黑树的了解(平衡树,二叉搜索树),使用 场景 把数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一…...
C Primer Plus第十章编程练习答案
学完C语言之后,我就去阅读《C Primer Plus》这本经典的C语言书籍,对每一章的编程练习题都做了相关的解答,仅仅代表着我个人的解答思路,如有错误,请各位大佬帮忙点出! 1.修改程序清单10.7的rain.c程序&…...
奇舞周刊第493期:Hook 革命!浅谈 React 新 Hook 的未来与思想
关注前端生态发展,了解行业动向。 下面先一起看下本期周刊 摘要 吧~ 奇舞推荐 ■ ■ ■ Hook 革命!浅谈 React 新 Hook 的未来与思想 作者阳羡曾写文章对 React 新 Hook use 的设计理念和限制进行了深入分析,并提供了一个可能的实现来帮助读者…...
文件包含的本质、预处理符号、# vs ##
何为头文件? 在C语言中,文件包含是一种常见的编程技术,它允许程序员在一个源文件中使用另一个源文件中的函数或变量。 文件包含通常使用#include预处理指令来实现。#include指令告诉预处理器将文件的内容插入到当前文件的指定位置中。 例如&a…...
【JavaSE】Java基础语法(三十九):网络编程入门
文章目录 1. 网络编程概述2. 网络编程三要素3. IP地址4. InetAddress5. 端口和协议 1. 网络编程概述 计算机网络 是指将地理位置不同的具有独立功能的多台计算机及其外部设备,通过通信线路连接起来,在网络 操作系统,网络管理软件及网络通信协…...
中间件SOME/IP简述
SOME/IP SOME/IP 不是广义上的中间件,严格的来讲它是一种通信协议,但中间件这个概念太模糊了,所以我们也一般称 SOME/IP 为通信中间件。 SOME/IP 全称是 Scalable service-Oriented MiddlewarE over IP。也就是基于 IP 协议的面向服务的可扩…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
2.2.2 ASPICE的需求分析
ASPICE的需求分析是汽车软件开发过程中至关重要的一环,它涉及到对需求进行详细分析、验证和确认,以确保软件产品能够满足客户和用户的需求。在ASPICE中,需求分析的关键步骤包括: 需求细化:将从需求收集阶段获得的高层需…...




