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

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)
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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-1
    for {
        mid := (left + right) / 2
        if 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
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

654. 最大二叉树-中等

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

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

代码（Go）：

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0{
        return nil
    }
    max := 0
    locate := 0
    for i := 0;i < len(nums);i++{
        if nums[i] > max{
            max = nums[i]
            locate = i
        }
    }
    var root TreeNode
    root.Val = max
    root.Left = constructMaximumBinaryTree(nums[:locate])
    root.Right = constructMaximumBinaryTree(nums[locate + 1:])
    return &root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

总结

目前还是处于复健状态，做的题有点水，等过一阵子再上强度