Golang每日一练(leetDay0105) 最小高度树、戳气球
目录
310. 最小高度树 Minimum Height Trees 🌟🌟
310. 最小高度树 Minimum Height Trees
树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。
给你一棵包含 n
个节点的树,标记为 0
到 n - 1
。给定数字 n
和一个有 n - 1
条无向边的 edges
列表(每一个边都是一对标签),其中 edges[i] = [ai, bi]
表示树中节点 ai
和 bi
之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x
作为根节点时,设结果树的高度为 h
。在所有可能的树中,具有最小高度的树(即,min(h)
)被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
示例 1:
输入:n = 4, edges = [[1,0],[1,2],[1,3]]
输出:[1]
解释:如图所示,当根是标签为 1 的节点时,树的高度是 1 ,这是唯一的最小高度树。
示例 2:
输入:n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出:[3,4]
提示:
1 <= n <= 2 * 10^4
edges.length == n - 1
0 <= ai, bi < n
ai != bi
- 所有
(ai, bi)
互不相同 - 给定的输入 保证 是一棵树,并且 不会有重复的边
代码:
-
package main
-
-
import "fmt"
-
-
func findMinHeightTrees(n int, edges [][]int) []int {
-
if n == 1 {
-
return []int{0}
-
}
-
//创建邻接列表
-
edgesmap := make([]map[int]bool, n)
-
for i := 0; i < n; i {
-
edgesmap[i] = make(map[int]bool)
-
}
-
for _, edge := range edges {
-
edgesmap[edge[0]][edge[1]] = true
-
edgesmap[edge[1]][edge[0]] = true
-
}
-
// 处理叶节点
-
leaves := []int{}
-
for i := 0; i < n; i {
-
if len(edgesmap[i]) == 1 {
-
leaves = append(leaves, i)
-
}
-
}
-
// 最小高度的树
-
for n > 2 {
-
n -= len(leaves)
-
newLeaves := []int{}
-
for _, i := range leaves {
-
var j int
-
for j = range edgesmap[i] {
-
break
-
}
-
delete(edgesmap[j], i)
-
if len(edgesmap[j]) == 1 {
-
newLeaves = append(newLeaves, j)
-
}
-
}
-
leaves = newLeaves
-
}
-
-
return leaves
-
}
-
-
func main() {
-
n := 4
-
edges := [][]int{{1, 0}, {1, 2}, {1, 3}}
-
fmt.Println(findMinHeightTrees(n, edges))
-
-
n = 6
-
edges = [][]int{{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}}
-
fmt.Println(findMinHeightTrees(n, edges))
-
}
输出:
[1]
[3 4]
相关:
312. 戳气球 Burst Balloons
有 n
个气球,编号为0
到 n - 1
,每个气球上都标有一个数字,这些数字存在数组 nums
中。
现在要求你戳破所有的气球。戳破第 i
个气球,你可以获得 nums[i - 1] * nums[i] * nums[i 1]
枚硬币。 这里的 i - 1
和 i 1
代表和 i
相邻的两个气球的序号。如果 i - 1
或 i 1
超出了数组的边界,那么就当它是一个数字为 1
的气球。
求所能获得硬币的最大数量。
示例 1:
输入:nums = [3,1,5,8]
输出:167
解释:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 3*5*8 1*3*8 1*8*1 = 167
示例 2:
输入:nums = [1,5]
输出:10
提示:
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
代码:
-
package main
-
-
import "fmt"
-
-
func maxCoins(nums []int) int {
-
n := len(nums)
-
// 添加两个边界
-
newNums := make([]int, n 2)
-
newNums[0], newNums[n 1] = 1, 1
-
for i := 1; i <= n; i {
-
newNums[i] = nums[i-1]
-
}
-
// 定义dp数组
-
dp := make([][]int, n 2)
-
for i := range dp {
-
dp[i] = make([]int, n 2)
-
}
-
// 状态转移
-
for l := 3; l <= n 2; l { // 区间长度,从3开始
-
for i := 0; i l-1 <= n 1; i { // 起始点
-
j := i l - 1 // 结束点
-
for k := i 1; k < j; k { // 最后被扎破的气球
-
dp[i][j] = max(dp[i][j], dp[i][k] dp[k][j] newNums[i]*newNums[k]*newNums[j])
-
}
-
}
-
}
-
return dp[0][n 1]
-
}
-
-
func max(x, y int) int {
-
if x > y {
-
return x
-
}
-
return y
-
}
-
-
func main() {
-
nums1 := []int{3,1,5,8}
-
fmt.Println(maxCoins(nums1))
-
-
nums2 := []int{1,5}
-
fmt.Println(maxCoins(nums2))
-
}
输出:
167
10
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页: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)暂停更 |
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfbkie
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01