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

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

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)暂停更


目录
相关文章
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2
|
3月前
|
Python
【Leetcode刷题Python】53. 最大子数组和
LeetCode第53题"最大子数组和"的Python解决方案,利用动态规划的思想,通过一次遍历数组并维护当前最大和以及全局最大和来求解。
107 2
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
37 1
|
1月前
|
机器学习/深度学习 并行计算 大数据
【Python篇】NumPy完整指南(上篇):掌握数组、矩阵与高效计算的核心技巧2
【Python篇】NumPy完整指南(上篇):掌握数组、矩阵与高效计算的核心技巧
69 10
|
1月前
|
索引 Python
【Python篇】NumPy完整指南(上篇):掌握数组、矩阵与高效计算的核心技巧1
【Python篇】NumPy完整指南(上篇):掌握数组、矩阵与高效计算的核心技巧
87 4
|
3月前
|
存储 数据处理 索引
如何删除 Python 数组中的值?
【8月更文挑战第29天】
152 8
|
3月前
|
索引 Python
向 Python 数组添加值
【8月更文挑战第29天】
44 8
|
3月前
|
存储 缓存 C语言
|
3月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
27 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
3月前
|
存储 测试技术 Python
Python 数组和列表有什么区别?
【8月更文挑战第29天】
405 4