上海-头条面试算法题解

字节算法题目

1.无序数组,第k大的数 (快排,快排+判断: 轴+k和轴比对)

// ===============  解题1 =============== //
// 力扣215题: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/submissions/
// 思路1: 快排 + 二分查找
// 思路2: 第k次-最大顶堆的尾节点元素: 构建最大顶堆 + 循环k次 [基于回溯算法的优化]
func findKthLargest(nums []int, k int) int {
    // return findKByquickSort(nums,k) // 快排解法
    return findKByMaxTopHeap(nums,k) // 最大顶堆解法
}
// 思路1: 快排 + 二分查找
// @param []int num 无序数组
// @param int k 第k大
// @return int 第k大的数,num[len(num)-k]
func findKByquickSort(num []int,k int) int {
    // 边界条件
    le := len(num)
    if 0 == le {
        return 0
    }
    // 快排
    var quickSort func(nums []int) []int
    quickSort = func(nums []int) []int {
        // 边界条件
        le2 := len(nums)
        if 0 == le2 {  // ***易错点:
            return []int{}
        }
        mid := nums[0]
        l,r := []int{},[]int{}
        // for i := 0; i < le; i++ { // ***易错点:
        for i := 1; i < le2; i++ {
            // ***易错点: 3种case别漏了,<,=,>
            if mid >= nums[i] { // <=存左边
                l = append(l,nums[i])
            } else if mid < nums[i] { // >存右边
                r = append(r,nums[i])
            }
        }
        // 递归执行
        l = quickSort(l)
        r = quickSort(r)
        // 合并数组
        l = append(l,mid)
        l = append(l,r...) // 批量追加: go合并切片方法,同下for循环用法
        // for _,v := range r {
            // l = append(l,v)
        // }
        return l
    }
    res := quickSort(num)
    // 二分查找
    return res[le-k]
}
// 思路2: 第k次-最大顶堆(顶点值max=nums[0]): 循环k次,每次循环中 {构建最大顶堆 => max=maxTopHeap[0] => 依次追加到尾节点处}
// 注: k=le-1时,和第一种快排时间复杂度相同
// 几个易错点:
//      1) for i := le; i > 0; i--  // ***易错点: 长度必须>=2,否则无需用maxTopHeap排序;
//      2) nums[i-1],nums[le-1] = nums[le-1],nums[i-1] // ***易错点: 最大顶堆顶点为max,即max=topHeap[0],把max移到尾节点,nodeCount-1,继续排序,故交换 nums[i-1]和nums[0],而非nums[i-1]和nums[len(nums)-1]
// @param []int num 无序数组
// @param int k 第k大
// @return int 第k大的数,num[len(num)-k]
func findKByMaxTopHeap(nums []int,k int) int {
    // 边界条件
    le := len(nums)
    if 0 == le || k > le {
        return 0
    }
    // 循环构建maxTopHeap,共构建k次,(取最大值=>maxTopHeap,取最小值=>minTopHeap)
    // 循环次数为 数组长度,而非数组右边界;
    // 递减循环: 因为第 n 次排序 N 个数,则第 (n+1) 次排序 (N-1) 个数;
    for i := le; i > (le-k); i-- {  // i > 1时(即le-k=1),则全部排序
        // 构建maxTopHeap
        buildMaxTopHeap(nums,i)
        // 交换max(maxTopHeap顶点值) 和 当前位置(尾节点元素值)
        nums[i-1],nums[0] = nums[0],nums[i-1]
    }
    // fmt.Println("******sortArr==",nums)
    // fmt.Println("res==",nums[le-k])
    return nums[le-k] // 最大值nums[le-1],第k大值为nums[le-k]
}
// 构建最大顶堆maxTopHeap;   [注意: 最大顶堆中for循环中递减的为元素范围长度length,而非下标值]
// 思路: maxTopHeap特征(二叉树): currNode>=leftSonNodes && currNode>=rightSonNodes, 否则需对调currNode和sonNode位置
//
// 几个问题:
//      1) 问题1: mid := (le-1)/2 是否可行??    [leng/2-1,leng/2都可以,能保证从中间root开始(因为同时遍历左右子树)即可]
//      2) 问题2: 循环遍历时,为何不是i++?       [因为未排序的元素越来越少]
//      3) 问题3: 这2行代码运行结果相同,有何区别:
//                  buildMaxTopHeap(nums,i) // O(logN),防止(已校验过的node)重复校验,建议使用
//                  buildMaxTopHeap(nums,leng) // O(N)
//
// @param []int nums 集合(可看作: 树的节点集合)
// @param int le (当前最大顶堆的,即排序元素的)长度
// @param []int 排序后的最大顶堆(最大值在尾节点)
func buildMaxTopHeap(nums []int,leng int) {
    // 边界条件 [可有可无,上一层已过滤]
    le := len(nums)
    if 0 == le {
        return
    }
    // 从中间root开始(因为同时遍历左右子树); i--因为未排序的元素越来越少
    mid := leng/2 - 1
    for i := mid; i >= 0; i-- {
        // root的左右子节点下标 (注: 树的左右子节点下标对应currIndex+1/currIndex+2,而非currIndex-1,currIndex+1)
        left := 2*i+1
        right := 2*i+2
        //## 校验并矫正 左/右子树,不满足maxTopHeap特性,则交换节点值
        // 左子树
        if left < leng && nums[left] > nums[i] {
            nums[left],nums[i] = nums[i],nums[left] // 交换节点值
            // 检验并矫正左子树的(左/右)子树
            if (2*left+1 < leng && nums[2*left+1] > nums[i]) || (2*left+2 < leng && nums[2*left+2] > nums[i]) {
                buildMaxTopHeap(nums,i) // O(logN),防止(已校验过的node)重复校验,建议使用
                // buildMaxTopHeap(nums,leng) // O(N)
            }
        }
        // 右子树
        if right < leng && nums[right] > nums[i] {
            nums[right],nums[i] = nums[i],nums[right]
            // 检验并矫正右子树的(左/右)子树
            if (2*right+1 < leng && nums[2*right+1] > nums[i]) || (2*right+2 < leng && nums[2*right+2] > nums[i]) {
                buildMaxTopHeap(nums,i) // O(logN),防止(已校验过的node)重复校验,建议使用
                // buildMaxTopHeap(nums,leng) // O(N)
            }
        }
    }
}

2. 求2个节点的最近公共祖先,如: [8,10] => 2 , [6,10] => 3 ,[5,9] => 5

nums := []int{2,1,3,4,5,6,7,8,9,10}

            2
     1                3
  4        5          6        7
8            9               10

 // ===============  解题2 =============== //
 // 详见力扣236题: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/
 // 参考: https://mp.weixin.qq.com/s/9RKzBcr3I592spAsuMH45g
 /**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
 // 1.应用场景: git树,git的操作rebase/merge
 //
 // 2.框架:
 //        递归3要素: 解决的问题(作用)/递归的变量/递归截止条件(拿到结果后如何处理)
 //        本题解析:  寻找(最近)公共祖先node / 变化的节点root / 截止条件+返回lcaNode
 //
 // 3.思路:
 //         公共祖先, root,p,q,lcaNode=root/p/q 三者之一 =>
 //         最近公共祖先节点: 后序遍历(自底向上),保证"最近"(第一个公共祖先node就是lcaNode); [left,right,root];
 //         ***注: 前序遍历是自顶向下
 //
 //     3种情况:
 //         1) p,q都在root下    (即都是root子节点,return root)
 //         2) p,q都不在root下  (即都不是root子节点,return nil)
 //         3) p,q其中有1个在root下 (即p/q其中1个是root子节点,return 非nil节点)
 //         [注: 本题解中,lowestCommonAncestor缩写为lcaNode,即公共祖先节点]
 //
 // @param *TreeNode root 二叉树
 // @param *TreeNode p 节点1
 // @param *TreeNode q 节点2
 // @return *TreeNode lcaNode 最近公共祖先节点
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 递归截止条件 (边界条件)
    if nil == root {
        return nil
    }
    // root和p/q重合,即p/q为lcaNode
    if p == root || q == root {
        return root
    }
    // 递归+逻辑: 后序遍历 => [left,right,root] => leftNode->rightNode->rootNode
    left := lowestCommonAncestor(root.Left,p,q)
    right := lowestCommonAncestor(root.Right,p,q)
    //### 3种情况, 递归过程中: p=leftNode,q=rightNode
    // 情况1: p/q都在root下 (即都是root子节点)
    if nil != left && nil != right {
        return root
    }
    // 情况2: p/q都不在root下 (即都不是root子节点)
    if nil == right && nil == left {
        return nil
    }
    //  p/q其中有1个在root下 (即p/q其中1个是root子节点)
    if nil == left {
        return right
    }
    return left
}