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