LeetCode No.133,134,135
2024-09-06 08:07:53
No.133 CloneGraph 克隆图
题目
- 给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
- 图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
class Node {
public int val;
public List<Node> neighbors;
}
- 测试用例格式:
- 简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1,第二个节点值为 2,以此类推。该图在测试用例中使用邻接列表表示。
- 邻接列表是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
- 给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
示例
输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
输入:adjList = [[]]
输出:[[]]
解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。
输入:adjList = []
输出:[]
解释:这个图是空的,它不含任何节点。
输入:adjList = [[2],[1]]
输出:[[2],[1]]
- 提示:
- 节点数介于 1 到 100 之间。
- 每个节点值都是唯一的。
- 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
- 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
- 图是连通图,你可以从给定节点访问到所有节点。
思路
代码
No.134 CanCompleteCircuit 加油站
题目
- 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
- 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
- 如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
- 说明:
- 如果题目有解,该答案即为唯一答案。
- 输入数组均为非空数组,且长度相同。
- 输入数组中的元素均为非负数。
示例
- 输入: gas = [1,2,3,4,5],cost = [3,4,5,1,2]
- 输出: 3
- 解释:
- 从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
- 开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
- 开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
- 开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
- 开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
- 开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
- 因此,3 可为起始索引。
- 输入: gas = [2,3,4],cost = [3,4,3]
- 输出: -1
- 解释:
- 你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
- 我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
- 开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
- 开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
- 你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
- 因此,无论怎样,你都不可能绕环路行驶一周。
思路
代码
No.135 Candy 分发糖果
题目
- 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
- 你需要按照以下要求,帮助老师给这些孩子分发糖果:
- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中,评分高的孩子必须获得更多的糖果。
- 那么这样下来,老师至少需要准备多少颗糖果呢?
示例
- 输入: [1,0,2]
- 输出: 5
- 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
- 输入: [1,2,2]
- 输出: 4
- 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
- 第三个孩子只得到 1 颗糖果,这已满足上述两个条件。
思路
代码
最新文章
- 定义返回Block的函数
- [转]nopcommerce商城系统--如何编写一个插件
- hdu 1860统计字符
- [转载]iTOP-4412开发板搭建最小linux系统
- 【python】在python中调用mysql
- 什么是bower
- [SQL]sql语句bug
- POJ 3468 A Simple Problem with Integers(树状数组)
- C语言入门(21)——使用DBG对C语言进行调试
- codefirst mvc Self referencing loop detected for property
- hdu_5711_Ingress(TSP+贪心)
- 【Spark篇】---Spark中Action算子
- open
- Django之第三方登陆模块
- LNMP下动静分离部署phpmyadmin软件包
- 机器学习算法中的偏差-方差权衡(Bias-Variance Tradeoff)
- a标签返回上一页,并刷新
- ReactCSSTransitionGroup
- 第14月第1天 uialterview 键盘 uibutton圆角
- 真机提示Undefinedsymbolsforarchitecturearm64
热门文章
- Tensorflow学习教程------过拟合
- CNN:卷积输出分辨率计算
- VC++ DLL 2 静态链接库
- 13. react 基础 redux 的基本介绍 及 用 antd 编写 TodoList 的样式
- (day 1)创建项目--1
- PHP+InfiniteScroll实现网页无限滚动加载数据实例
- Android aar同步Failed to resolve: :nuisdk:
- 指针数组的初始化和遍历,并且通过for循环方式、函数传参方式进行指针数组的遍历
- count(1),count(*)和count(列)的比较
- 吴裕雄--天生自然Linux操作系统:Linux 文件基本属性