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
}