算法刷题笔记 (14) 二叉树的完全性检验 最长连续序列 寻找旋转排序数组中的最小值 寻找峰值

二叉树的完全性检验

二叉树的完全性检验

解题思路

对一个完全二叉树进行层序遍历时，其特点就是：若遍历到一个节点左/右子树为空，那么这个节点的所有右边的节点和下层节点的左右子树都为空。可以根据这个特性来进行二叉树的完全性检验

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCompleteTree(root *TreeNode) bool {
    q := []*TreeNode{root}  // 队列
    var flag bool   // 标记是否已经碰到过左/右子树为空的节点

    // 开始层序遍历
    for i := 0; len(q) > 0; i++ {
        p := []*TreeNode{}  // p记录下一层节点
        for j := 0; j < len(q); j++ {
            cur := q[j] // 当前遍历节点

            if cur.Left != nil && !flag{
                // 左子树入队
                p = append(p, cur.Left)
            } else if cur.Left != nil && flag{
                // 已经遇到了左/右子树为空的节点，且当前节点的左子树非空，不是完全二叉树
                return false
            } else {
                flag = true
            }

            if cur.Right != nil && !flag{
                // 右子树入队
                p = append(p, cur.Right)
            } else if cur.Right != nil && flag{
                // 已经遇到了左/右子树为空的节点，且当前节点的右子树非空，不是完全二叉树
                return false
            } else {
                flag = true
            }
        }
        q = p   // 访问下一层节点
    }

    // 遍历完成，说明是完全二叉树
    return true
}

最长连续序列

最长连续序列

解题思路

1. 用哈希表记录数组中的元素。对于数组中的元素x，首先查看数组中是否有x-1，若有则跳过x；若没有x-1，则进行枚举x+1, x+2, ...，同时记录连续序列的长度，从而得到最长连续序列的长度

解题代码

1. 哈希表

func longestConsecutive(nums []int) int {
    hashMap := map[int]bool{}  // 哈希表记录已有数字
    for _, v := range nums {    // 初始化哈希表
        hashMap[v] = true
    }
    var MaxLength int  // 数字连续的最长序列的长度

    for _, v := range nums {
        if !hashMap[v-1] {     // 没有等于v-1的元素，无需跳过
            curLength := 1  // 当前数字连续的序列长度
            i := 1
            for hashMap[v+i] {
                curLength++
                i++
            }
            if curLength > MaxLength {
                // 更新最大长度
                MaxLength = curLength
            }
        }
    }

    return MaxLength
}

寻找旋转排序数组中的最小值

寻找旋转排序数组中的最小值

解题思路

因为整个升序数组在旋转后，可以分为两部分，并且这两部分都是升序排列的，同时第一部分的所有元素比第二部分的所有元素大。基于二分查找，通过判断mid指向第一部分还是第二部分来更新low和high指针：

• 若nums[mid] > nums[high]，则mid指向第一部分，最小元素在mid左侧，low更新为mid+1
• 否则mid指向第二部分，最小元素为mid或者在mid右侧，high更新为mid

解题代码

func findMin(nums []int) int {
    low, high := 0, len(nums)-1
    var mid int

    for low < high {
        mid = (low+high)/2
        if nums[mid] > nums[high] {
            // 最小元素在mid左侧
            low = mid + 1
        } else {
            // 最小元素为mid或者在mid右侧
            high = mid
        }
    }

    return nums[low]
}

寻找峰值

寻找峰值

解题思路

1. 因为nums[-1] = nums[n] = -∞，索引找到数组中的最大值即可，这个最大值就是峰值

2. 爬坡的思想，随机一个下标i，沿着上升的方向走，一定可以到峰值

   • 若nums[i] < nums[i+1]，则向右侧走一定可以到达峰值
   • 否则，向左侧走一定可以到达峰值

3. 基于二分查找，查找时比较nums[mid]与nums[mid+1]的值：

   • 如果nums[mid] < nums[mid+1]，则右侧存在峰值，low = mid+1
   • 否则，左侧存在峰值，high = mid

解题代码

1. 找到最大值

func findPeakElement(nums []int) int {
    max := nums[0]   // 最大值初始化为nums[0]
    maxIndex := 0   // 最大值元素的下标

    for i := 1; i < len(nums); i++ {    // 寻找最大值，最大值必为峰值
        if nums[i] > max {
            max = nums[i]
            maxIndex = i
        }
    }

    return maxIndex
}

2. 爬坡

func findPeakElement(nums []int) int {
    n := len(nums)  // 数组长度
    i := rand.Intn(n)   // 随机下标i
    right := (i+1 < n) && (nums[i+1] > nums[i])  // 向右走的标记，true为向右走，false为向左走

    for {
        if right {  // 向右走
            if i+1 < n && nums[i+1] > nums[i] {
                i++     // 继续向右
            } else {
                // 到达峰值
                break
            } 
        }

        if !right {    // 向左走
            if i-1 >= 0 && nums[i-1] >nums[i] {
                i--     // 继续向左
            } else {
                // 到达峰值
                break
            }   
        }
    }

    return i
}

3. 二分查找

func findPeakElement(nums []int) int {
    low, high := 0, len(nums)-1

    for low < high {
        mid := (low+high)/2
        
        if nums[mid] < nums[mid+1] {    // 右侧存在峰值
            low = mid + 1
        } else {    // 左侧存在峰值
            high = mid
        }
    }

    return low
}