这周的竞赛算法考察得不是那么强,考急转弯的题目我觉得有两道,然后前面两道是送分题(然而我还是由于着急没有测试直接提交错了两次)

Q1. 统计有序矩阵中的负数

这道题是道送分题,因为题目的要求很简单,就是统计负数的个数,而且条件也很宽松:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

所以可以直接提交:

[[email protected]]# cat Q1.go
func countNegatives(grid [][]int) int {
    var (
        i, j, count int
        length      = len(grid)
    )

    if length == 0 {
        return 0
    }

    for i = 0; i < length; i++ {
        for j = 0; j < len(grid[0]); j++ {
            if grid[i][j] < 0 {
                count++
            }
        }
    }
    return count
}

Q2. 最后 K 个数的乘积

这道题也算是送分题吧,虽然题目的条件好像有点大,但事实上,直接写也是可以通过的:

[[email protected]]# cat Q2.go
type ProductOfNumbers struct {
    nums []int
}

func Constructor() ProductOfNumbers {
    pn := ProductOfNumbers{
        nums: []int{},
    }
    return pn
}

func (this *ProductOfNumbers) Add(num int) {
    this.nums = append(this.nums, num)
}

func (this *ProductOfNumbers) GetProduct(k int) int {
    sum := 1
    length := len(this.nums)
    for i := 0; i < k; i++ {
        sum *= this.nums[length-1-i]
        if sum == 0 {
            return 0
        }
    }
    return sum
}

小结一下,这里我犯了两个蠢,一个是把题目的意思的乘积写成了加法,错了一次,第二次是把 sum 初始化成了 0,又错了一次。

Q3. 最多可以参加的会议数目

这道题目看上去是道 DP,我一开始就是以 DP 的思路在考虑,但是,怎么也推导不出来表达式,后面换种思路想,要不用贪心吧,第一次上去错了,分析一下问题在于我的贪心的排序是以 start 为主序,end 为次序,都以升序进行排序,这样会有一种情形就是这个case:

[1, 2]
[1, 2]
[3, 3]
[1, 5]

所以我调整了一下排序策略,变成 end 为主序,升序排列,start 为次序,降序排列,然后就通过了。其实,这基于一个经验(当然我没有第一时间反应过来),那就是对于 interval 的题目,大多数情况都是可以这么贪心的,只不过怎么排序是个问题。

[[email protected]]# cat Q3.go
import (
    "sort"
)

func maxEvents(events [][]int) int {
    var (
        i, j, k, maxEnd int
        length          = len(events)
        visitedDays     []bool
    )
    if length == 0 {
        return 0
    }
    maxEnd = events[0][1]
    sort.Slice(events, func(i, j int) bool {
        if events[i][1] > maxEnd {
            maxEnd = events[i][1]
        }
        if events[i][1] == events[j][1] {
            return events[i][0] > events[j][0]
        }
        return events[i][1] < events[j][1]
    })
    visitedDays = make([]bool, maxEnd+1)

    for i = 0; i < length; i++ {
        for j = events[i][0]; j <= events[i][1]; j++ {
            if !visitedDays[j] {
                visitedDays[j] = true
                break
            }
        }
    }

    for i = 0; i <= maxEnd; i++ {
        if visitedDays[i] {
            k++
        }
    }
    return k
}

updated:看到有人说这样出现 105 个 [1, 100000] 的数据会超时,其实也很好改,修改一下内循环的条件即可:

    maxDay = events[i][0]
    for i = 0; i < length; i++ {
        for j = max(events[i][0], maxDay); j <= events[i][1]; j++ {
            if !visitedDays[j] {
                visitedDays[j] = true
                maxDay = j
                break
            }
        }
    }

这样可以保证最坏的情况也不会超过 O(N2)

Q4. 多次求和构造目标数组

这道题目我觉得是个智力题,一开始我想直接 BF 的,但是一看题目条件:

N == target.length
1 <= target.length <= 5 * 10^4
1 <= target[i] <= 10^9

果断放弃,这是不可能的。然后又想是不是什么数学数列,这一时半会也没什么思路,那也就放弃了;那么既然没现成的知识,那么就尝试自己推导吧,一开始一直顺着推,然而发现有点难度,因为有可能数字很大,而且很容易发散出去,情况太复杂。

到了最后 15 分钟的时候,突然灵光一闪,反着推试一下,结果真的可以,最后 3 分钟通过了。其实反着推和顺着推一样的,既然规则是和替换某个元素,那么这个元素必定是最大的,所以,就可以反着推将最大的数替换掉原来的,一直这么推下去,如果最后可以变成全 1,那么没疑问,这是正确的:

[[email protected]]# cat Q4.go
func isPossible(target []int) bool {
    if len(target) == 0 {
        return true
    }
    for j := 0; j < len(target); j++ {
        sum := 0
        maxIdx := 0
        maxNum := target[0]
        for i := 0; i < len(target); i++ {
            if target[i] <= 0 {
                return false
            }
            if target[i] > maxNum {
                maxIdx = i
                maxNum = target[i]
            }
            sum += target[i]
        }
        if maxNum == 1 {
            return true
        }
        if maxNum<<1-(sum) <= 0 || maxNum<<1-sum >= target[maxIdx] {
            return false
        }
        target[maxIdx] = maxNum<<1 - sum
    }
    return true
}

update:

这里也是,有人说这样是 O(N2),因为我内部计算 Sum 和求 MaxNum 用了 O(N) 的时间复杂度,所以这里一个改进可以用堆来维护数组,并且不用每次都求 Sum,每个循环可以直接求出下一步的 Sum。