Golang每日一练(leetDay0118) 扁平化嵌套列表迭代器、整数拆分

341. 扁平化嵌套列表迭代器 Flatten Nested List Iterator

给你一个嵌套的整数列表

nestedList

。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类

NestedIterator

：

• NestedIterator(List<NestedInteger> 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 *直到 *hasNex*t 返回 false，*next *返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

**输入：**nestedList = [1,[4,[6]]]
**输出：**[1,4,6]
**解释：**通过重复调用 *next *直到 *hasNex*t 返回 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）暂停更