Golang每日一练(leetDay0062) BST迭代器、地下城游戏

2023-05-29 79

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0062) BST迭代器、地下城游戏

173. 二叉搜索树迭代器 Binary Search Tree Iterator

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。

boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。

int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

提示：

树中节点的数目在范围 [1, 10^5] 内

0 <= Node.val <= 10^6

最多调用 10^5 次 hasNext 和 next 操作

进阶：

你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 O(h) 内存。其中 h 是树的高度。

代码：

package main
import "fmt"
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
type BSTIterator struct {
  stack []*TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
  stack := []*TreeNode{}
  node := root
  for node != nil {
    stack = append(stack, node)
    node = node.Left
  }
  return BSTIterator{stack}
}
func (it *BSTIterator) next() int {
  node := it.stack[len(it.stack)-1]
  it.stack = it.stack[:len(it.stack)-1]
  if node.Right != nil {
    n := node.Right
    for n != nil {
      it.stack = append(it.stack, n)
      n = n.Left
    }
  }
  return node.Val
}
func (it *BSTIterator) hasNext() bool {
  return len(it.stack) > 0
}
func main() {
  nums := []int{7, 3, 15, null, null, 9, 20}
  root := buildTree(nums)
  bSTIterator := Constructor(root)
  fmt.Println(bSTIterator.next())    // 返回 3
  fmt.Println(bSTIterator.next())    // 返回 7
  fmt.Println(bSTIterator.hasNext()) // 返回 True
  fmt.Println(bSTIterator.next())    // 返回 9
  fmt.Println(bSTIterator.hasNext()) // 返回 True
  fmt.Println(bSTIterator.next())    // 返回 15
  fmt.Println(bSTIterator.hasNext()) // 返回 True
  fmt.Println(bSTIterator.next())    // 返回 20
  fmt.Println(bSTIterator.hasNext()) // 返回 False
}

输出：

true

false

174. 地下城游戏 Dungeon Game

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。

我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

说明:

骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

代码1： 动态规划

func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[m-1][n-1] = max(1-dungeon[m-1][n-1], 1) // 初始化右下角的值
    for i := m-2; i >= 0; i-- { // 递推最后一列的值
        dp[i][n-1] = max(dp[i+1][n-1]-dungeon[i][n-1], 1)
    }
    for j := n-2; j >= 0; j-- { // 递推最后一行的值
        dp[m-1][j] = max(dp[m-1][j+1]-dungeon[m-1][j], 1)
    }
    for i := m-2; i >= 0; i-- {
        for j := n-2; j >= 0; j-- {
            dp[i][j] = max(min(dp[i+1][j], dp[i][j+1])-dungeon[i][j], 1)
        }
    }
    return dp[0][0]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

代码2： 二分查找

func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])
    left, right := 1, 1000000
    for left < right {
        mid := left + (right-left)/2
        if canSave(mid, dungeon, m, n) {
            right = mid
        } else {
            left = mid+1
        }
    }
    return left
}
func canSave(x int, dungeon [][]int, m, n int) bool {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[0][0] = x + dungeon[0][0]
    if dp[0][0] <= 0 {
        return false
    }
    for i := 1; i < n; i++ { // 处理第一行
        dp[0][i] = dp[0][i-1] + dungeon[0][i]
        if dp[0][i] <= 0 {
            return false
        }
    }
    for i := 1; i < m; i++ { // 处理第一列
        dp[i][0] = dp[i-1][0] + dungeon[i][0]
        if dp[i][0] <= 0 {
            return false
        }
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + dungeon[i][j]
            if dp[i][j] <= 0 {
                return false
            }
        }
    }
    return true
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}