341. 扁平化嵌套列表迭代器 Flatten Nested List Iterator
给你一个嵌套的整数列表 nestedList
。每个元素要么是一个整数,要么是一个列表;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化,使之能够遍历这个列表中的所有整数。
实现扁平迭代器类 NestedIterator
:
NestedIterator(List nestedList)
用嵌套列表nestedList
初始化迭代器。int next()
返回嵌套列表的下一个整数。boolean hasNext()
如果仍然存在待迭代的整数,返回true
;否则,返回false
。
你的代码将会用下述伪代码检测:
initialize iterator with nestedList res = [] while iterator.hasNext() append iterator.next() to the end of res return res
如果 res
与预期的扁平化列表匹配,那么你的代码将会被判为正确。
示例 1:
输入:nestedList = [[1,1],2,[1,1]]
输出:[1,1,2,1,1]
解释:通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:
输入:nestedList = [1,[4,[6]]]
输出:[1,4,6]
解释:通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]。
提示:
1 <= nestedList.length <= 500
- 嵌套列表中的整数值在范围
[-10^6, 10^6]
内
代码:
package main import "fmt" type NestedInteger struct { IsInteger bool Value int List []*NestedInteger } type NestedIterator struct { FlattenedList []int // 扁平化后的列表 Index int // 当前迭代位置的索引 } func Constructor(nestedList []*NestedInteger) *NestedIterator { flattenedList := make([]int, 0) dfs(nestedList, &flattenedList) return &NestedIterator{FlattenedList: flattenedList, Index: -1} } // 使用深度优先搜索将嵌套列表扁平化 func dfs(nestedList []*NestedInteger, flattenedList *[]int) { for _, ni := range nestedList { if ni.IsInteger { *flattenedList = append(*flattenedList, ni.Value) } else { dfs(ni.List, flattenedList) } } } func (it *NestedIterator) HasNext() bool { return it.Index+1 < len(it.FlattenedList) } func (it *NestedIterator) Next() int { it.Index++ return it.FlattenedList[it.Index] } func main() { nestedList := []*NestedInteger{ &NestedInteger{IsInteger: false, List: []*NestedInteger{ &NestedInteger{IsInteger: true, Value: 1}, &NestedInteger{IsInteger: true, Value: 1}, }}, &NestedInteger{IsInteger: true, Value: 2}, &NestedInteger{IsInteger: false, List: []*NestedInteger{ &NestedInteger{IsInteger: true, Value: 1}, &NestedInteger{IsInteger: true, Value: 1}, }}, } iterator := Constructor(nestedList) result := make([]int, 0) for iterator.HasNext() { result = append(result, iterator.Next()) } fmt.Println(result) nestedList = []*NestedInteger{ &NestedInteger{true, 1, nil}, &NestedInteger{false, 0, []*NestedInteger{ &NestedInteger{true, 4, nil}, &NestedInteger{false, 0, []*NestedInteger{ &NestedInteger{true, 6, nil}, }}, }}, } iterator = Constructor(nestedList) result = make([]int, 0) for iterator.HasNext() { result = append(result, iterator.Next()) } fmt.Println(result) }
输出:
[1 1 2 1 1]
[1 4 6]
343. 整数拆分 Integer Break
给定一个正整数 n
,将其拆分为 k
个 正整数 的和( k >= 2
),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
代码:
package main import "fmt" func integerBreak(n int) int { if n <= 3 { return n - 1 } dp := make([]int, n+1) dp[2] = 1 for i := 3; i <= n; i++ { for j := 1; j < i-1; j++ { dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j])) } } return dp[n] } func max(a, b int) int { if a > b { return a } return b } func main() { fmt.Println(integerBreak(2)) fmt.Println(integerBreak(10)) }
输出:
1
36
🌟 每日一练刷题专栏 🌟
✨持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页: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)暂停更 |