admin 管理员组

文章数量: 887006

7月8号

  1. 剑指 Offer 31. 栈的压入、弹出序列
  • 用stack来判断是否需要更新index
func validateStackSequences(pushed []int, popped []int) bool {stack := make([]int, 0)index := 0for _, val := range pushed {stack = append(stack, val)for (len(stack) > 0 && popped[index] == stack[len(stack) - 1]) {index++stack = stack[:len(stack) - 1]}}return len(stack) == 0
}
  1. 剑指 Offer 33. 二叉搜索树的后序遍历序列
  • 每次都是一个新的子问题，所以用递归来解决
  • 边界条件要控制好
func verifyPostorder(postorder []int) bool {return verify(postorder, 0, len(postorder) - 1)
}func verify(post []int, left, right int) bool {if left >= right {return true}rootVal := post[right]split := leftfor post[split] < rootVal {split++}for split < right {if post[split] < rootVal {return false}split++}return verify(post, left, split - 1) && verify(post, split, right-1)
}
  1. 剑指 Offer 34. 二叉树中和为某一值的路径
  • Slice
func pathSum(root *TreeNode, sum int) [][]int {res := make([][]int, 0)if root == nil {return res}backtrack(root, sum, &res, make([]int, 0))return res
}func backtrack(root *TreeNode, sum int, res *[][]int, path []int) {if root == nil {return}path = append(path, root.Val)if root.Left == nil && root.Right == nil && sum == root.Val {//slice是一个指向底层的数组的指针结构体//因为是先序遍历，如果 root.Right != nil ,arr 切片底层的数组会被修改//所以这里需要 copy arr 到 tmp，再添加进 ret，防止 arr 底层数据修改带来的错误// 保持各个路径切片path独立tmp := make([]int,len(path))copy(tmp,path)*res = append(*res, tmp)return}backtrack(root.Left, sum - root.Val, res, path)backtrack(root.Right, sum - root.Val, res, path)path = path[:len(path) - 1]
}

本文标签： 7月8号

版权声明：本文标题：7月8号 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732355201h1534233.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。