好久没打周赛了，所以状态有些下滑，今天晚上的丢了几次低级失误，但是因为题目不难，所以还是做完了，最后的排名也不是很好：
| 图 1：Leetcode 第 23 场周赛排名（临时） |
|---|
|
Q1：统计最大组的数目
这到题目稍微有点转折，但是，其实还是一道排序题，可以分为三步来操作：
- 构建数字和个数的数组
- 对个数的数组进行降序排序
- 数量下相同的前 N 个系列即可
[[email protected]]# cat Q1.go
import "sort"
func countLargestGroup(n int) int {
var (
i int
total []int
countMap = map[int]int{}
)
for i = 1; i <= n; i++ {
countMap[count(i)] ++
}
for _, v := range countMap {
total= append(total,v)
}
sort.Slice(total, func(i, j int) bool {
return total[i] > total[j]
})
for i = 1; i< len(total); i++ {
if total[i] != total[0] {
return i
}
}
return len(total)
}
func count(n int) (rst int) {
for n > 0 {
rst += (n % 10)
n /= 10
}
return
}
Q2：构造 K 个回文字符串
这道题也是看上去有点难，但是，仔细想一下也是比较简单的。构造回文条件其实很简单，要么是这个串中拥有的所有字符都是 2 个倍数，例如 aa, aabb，或者只有一个不是 2 个倍数（例如 bab，abcccbb）。
所以如果要构建 K 个回文串，那么判断是否满足 K 个这个条件就可以了：
- 至少有 2K 个字符
- 不超过 K 个不是 2 倍数的字符
[[email protected]]# cat Q2.go
func canConstruct(s string, k int) bool {
var (
i int
length = len(s)
charCount = 0
charMap = map[uint8]int{}
)
for i = 0; i < length; i++ {
charMap[s[i]] ++
}
length = 0
for _, v := range charMap {
charCount ++
if v %2 == 1 {
length++
}
}
if length > k {
return false
}
return len(s) >= k
}
Q3：圆和矩形是否有重叠
这道题就是一道简单的数学题了，只有两种情况需要分析，分别是：
- 如果圆在长方形的正（左/右/上/下）方，那么直接判断 x（y）轴之间的距离是否小于等于半径即可
- 否则，需要判断圆心距离最近的角的长度是否小于等于半径
这里我为了方便，直接在第二种情况的时候把距离 4 个角的长度都求了一遍，然后找最小值就是最短距离了：
[[email protected]]# cat Q3.go
import "math"
func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
if xCenter <= x1 && y1 <= yCenter && yCenter <= y2 && x1-xCenter <= radius {
return true
}
if xCenter >= x2 && y1 <= yCenter && yCenter <= y2 && xCenter-x2 <= radius {
return true
}
if yCenter <= y1 && x1 <= xCenter && xCenter <= x2 && y1-yCenter <= radius {
return true
}
if yCenter >= y2 && x1 <= xCenter && xCenter <= x2 && yCenter-y2 <= radius {
return true
}
if xCenter >= x1 && xCenter <= x2 && yCenter >= y1 && yCenter <= y2{
return true
}
minDist := min(dist(x1, y1, xCenter, yCenter), dist(x1, y2, xCenter, yCenter))
minDist = min(minDist, dist(x2, y1, xCenter, yCenter))
minDist = min(minDist, dist(x2, y2, xCenter, yCenter))
return minDist <= float64(radius)
}
func min(a, b float64) float64 {
if a < b {
return a
}
return b
}
func dist(a, b, c, d int) float64 {
return math.Sqrt(float64((c-a)*(c-a) + (d-b)*(d-b)))
}
Q4：做菜顺序
这道题看上去就是一道 DP 题，再看一下数据规模是 N <= 500，所以直接 O(N2) 的复杂度是可接受的，所以直接先排序，因为数字大的肯定放在最后是最划算的，然后直接 DP：
dp[i]j][k]：第 i 小的数在第 j 道被 (k==1) 做时的满意度
这里就有一些条件：
- i <= j：第 i 小的数不可能在 i +1 以及更后面的位置上做
- dp[i][j][1]：一定满足 dp[i-1][j-1][1] 存在，否则第 i 道菜不可能在第 j 位被做出来
所以最后代码就很简单了：
[[email protected]]# cat Q4.go
import (
"math"
"sort"
)
func maxSatisfaction(s []int) int {
var (
i, j int
length = len(s)
// dp[i][j][k]: 在第 j 次选择（k)了 s[i]
dp = make([][][]int, length)
)
sort.Ints(s)
for i = 0; i < length; i++ {
dp[i] = make([][]int, length)
for j = 0; j < length; j++ {
dp[i][j] = []int{0, math.MinInt32}
}
}
dp[0][0][0] = 0
dp[0][0][1] = s[0]
for i = 1; i < length; i++ {
dp[i][0][1] = s[i]
for j = 1; j <= i; j++ {
// selected j-1
dp[i][j][1] = dp[i-1][j-1][1] + s[i]*(j+1)
}
}
rst := 0
for i = 0; i < length; i++ {
if dp[length-1][i][0] > rst {
rst = dp[length-1][i][0]
}
if dp[length-1][i][1] > rst {
rst = dp[length-1][i][1]
}
}
return rst
}