0. 概述

这周的题目相对也是比较容易，但是很遗憾，我没有全做完，最后一道题编码水平不行，TO 了两次，最后遗憾收场。

图 1：Leetcode 周赛 180 排名

Q1：矩阵中的幸运数

这道题绕了一些，不过还是很容易的，第一步就是判断每一行的最小值，然后第二步判断这个最小值是否在当前列中属于最大值即可：

[[email protected]]# cat Q1.go
func luckyNumbers (matrix [][]int) (rst []int) {
    var (
        i, j,k, minIdx int
        lenX = len(matrix)
        lenY = len(matrix[0])
    )

    for i = 0;i < lenX; i++ {
        minIdx = 0
        for j = 1;j < lenY; j++ {
            if matrix[i][j] < matrix[i][minIdx] {
                minIdx = j
            }
        }
        for k = 0; k < lenX; k++ {
            if k == i {
                continue
            }
            if matrix[k][minIdx] > matrix[i][minIdx] {
                goto NEXT_ROW
            }
        }
        rst = append(rst, matrix[i][minIdx])
        NEXT_ROW:
    }
    return
}

Q2： 设计一个支持增量操作的栈

这种题目就是比较容易的送分题啦，这里我觉得一个点就是不要用链表，用数组就很容易了：

[[email protected]]# cat Q2.go
type CustomStack struct {
    elems []int
    count int
}

func Constructor(maxSize int) CustomStack {
    return CustomStack{
        elems: make([]int, maxSize),
        count: 0,
    }
}

func (this *CustomStack) Push(x int) {
    if this.count >= len(this.elems) {
        return
    }
    this.elems[this.count] = x
    this.count++
}

func (this *CustomStack) Pop() int {
    if this.count == 0 {
        return -1
    }
    rtn := this.elems[this.count-1]
    this.count--
    return rtn
}

func (this *CustomStack) Increment(k int, val int) {
    for i := 0; i < this.count && i < k; i++ {
        this.elems[i] += val
    }
}

Q3： 将二叉搜索树变平衡

这道题坑了我一下，当然，看到题目的第一想法我是想左旋和右旋的，但是，仔细想一下，左旋和右旋一般在只有一个高度需要调整的情况下用比较好，对于这种情况，很可能会旋转非常多，所以又仔细看了一下题目，发现没有特殊要求，所以我就直接中序遍历了一下，然后重新构造树：

[[email protected]]# cat Q3.go
func balanceBST(root *TreeNode) *TreeNode {
    var (
        nodes []*TreeNode
    )
    nodes = inOrder(root)
    root = buildTree(nodes)
    return root
}

func inOrder(root *TreeNode) []*TreeNode {
    if root == nil {
        return []*TreeNode{}
    } else if root.Left == nil && root.Right == nil {
        return []*TreeNode{root}
    }
    nodes := inOrder(root.Left)
    nodes = append(nodes, root)
    return append(nodes, inOrder(root.Right)...)
}

func buildTree(nodes []*TreeNode) *TreeNode {
    if len(nodes) == 0 {
        return nil
    } else if len(nodes) == 1 {
        nodes[0].Left = nil
        nodes[0].Right = nil
        return nodes[0]
    }
    root := nodes[len(nodes)/2]
    root.Left = buildTree(nodes[:len(nodes)/2])
    root.Right = buildTree(nodes[len(nodes)/2+1:])
    return root
}

Q4： 最大的团队表现值

这道题我一开始想用贪心，但是觉得不太合适，所以很快就放弃了贪心的想法。

接着就尝试了回溯，果不其然，必须超时。然后就思考了很久，想到了一个突破口，因为回溯的复杂度太高了，有 Nk，于是就考虑按照 efficiency 排序，然后从低到高选择 K 个数的最大和即可，这里我做错的地方在于第二步这里我用了 NlogN 的复杂度，这样整个复杂度就是 N2logN。其实在比赛的时候这里我尝试用了部分贪心（没有意识到），但是还是因为思路不明确，导致写出来的代码还是 N2logN。

于是只能参考别人的思路了，后面这里选择 K 个数的最大和可以通过堆达到 logN，整体是 NlogN，最终赛后我修改了一下代码：

[[email protected]]# cat Q4.go
import (
    "container/heap"
    "sort"
)

type Item struct {
    index      int
    speed      int
    efficiency int
}

func maxPerformance(n int, speed []int, efficiency []int, k int) int {
    var (
        i, sum  int
        objs    = make([]*Item, n)
        tmpSum  int64
        newHeap = minHeap(make([]int, 0))
    )
    for i = 0; i < n; i++ {
        objs[i] = &Item{
            index:      i,
            efficiency: efficiency[i],
            speed:      speed[i],
        }
    }
    sort.Slice(objs, func(i, j int) bool {
        return objs[i].efficiency > objs[j].efficiency
    })

    heap.Init(&newHeap)
    for i = 0; i < n; i++ {
        heap.Push(&newHeap, objs[i].speed)
        sum += objs[i].speed
        if len(newHeap) > k {
            sum -= heap.Pop(&newHeap).(int)
        }
        currSum := int64(sum) * int64(objs[i].efficiency)
        if currSum > tmpSum {
            tmpSum = currSum
        }
    }
    return int(tmpSum % 1000000007)
}

type minHeap []int

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *minHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}