从零开始的力扣刷题记录-第八十八天

本文主要是介绍从零开始的力扣刷题记录-第八十八天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣每日四题

98. 验证二叉搜索树-中等
162. 寻找峰值-中等
150. 逆波兰表达式求值-中等
654. 最大二叉树-中等
总结

98. 验证二叉搜索树-中等

题目描述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

题解：
一开始以为直接递归判断左小右大就行了，结果忘记考虑左子树上的右侧节点可能会比根节点大的情况了，修改一下使用一个最大值和一个最小值来把范围保存下来，向左搜索时更新最大值，向右搜索时更新最小值即可

代码（Go）：

func isValidBST(root *TreeNode) bool {return check(root,math.MaxInt64,math.MinInt64)
}func check(root *TreeNode,high int, low int)bool{if root == nil{return true}if root.Val <= low || root.Val >= high{return false}return check(root.Left,root.Val,low) && check(root.Right,high,root.Val)
}

162. 寻找峰值-中等

题目描述：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

题解：
难点就在O（logn)的时间复杂度，看到这个时间复杂度就知道是二分查找，每次查找到一个元素时和它前后两个元素对比，如果该元素最大就返回，否则向更大的元素方向靠拢。由于有两侧边缘情况，我写的代码处理的有点烂，贴下官方代码，通过一个函数获取nums的值，把nums[-1]和nums[n]的设成负无穷就不用写一堆if判断了

代码（Go）：

func findPeakElement(nums []int) int {n := len(nums)get := func(i int) int {if i == -1 || i == n {return math.MinInt64}return nums[i]}left, right := 0, n-1for {mid := (left + right) / 2if get(mid-1) < get(mid) && get(mid) > get(mid+1) {return mid}if get(mid) < get(mid+1) {left = mid + 1} else {right = mid - 1}}
}

150. 逆波兰表达式求值-中等

题目描述：
给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是向零截断。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位整数表示。

题解：
常规题，使用栈即可计算。

代码（Go）：

func evalRPN(tokens []string) int {stack := []int{}for _, token := range tokens {val, err := strconv.Atoi(token)if err == nil {stack = append(stack, val)} else {num1, num2 := stack[len(stack)-2], stack[len(stack)-1]stack = stack[:len(stack)-2]switch token {case "+":stack = append(stack, num1+num2)case "-":stack = append(stack, num1-num2)case "*":stack = append(stack, num1*num2)default:stack = append(stack, num1/num2)}}}return stack[0]
}

654. 最大二叉树-中等

题目描述：
给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的子数组前缀上构建左子树。
递归地在最大值右边的子数组后缀上构建右子树。
返回 nums 构建的最大二叉树。

题解：
用最简单的方法递归做的，但是时间复杂度O（n²），官方题解使用单调栈可以达到O（n）的时间复杂度，但是具体很复杂，有点难懂

代码（Go）：

func constructMaximumBinaryTree(nums []int) *TreeNode {if len(nums) == 0{return nil}max := 0locate := 0for i := 0;i < len(nums);i++{if nums[i] > max{max = nums[i]locate = i}}var root TreeNoderoot.Val = maxroot.Left = constructMaximumBinaryTree(nums[:locate])root.Right = constructMaximumBinaryTree(nums[locate + 1:])return &root
}