1. 检查整数及其两倍数是否存在
这道题应该也是个送分题，快的人一两分钟就提交通过了，就是 O(N2) 的复杂度，然后分别对比前后是否成 2 倍关系即可：
[[email protected]]# cat Q1.go
func checkIfExist(arr []int) bool {
var (
i, j int
length = len(arr)
)
for i = 0; i < length; i++ {
for j = i + 1; j < length; j++ {
if arr[i] == arr[j]*2 || arr[i]*2 == arr[j] {
return true
}
}
}
return false
}
2. 制造字母异位词的最小步骤数
这道题目的意思不是很好理解，我带猜的情况下算是猜对了，其实就是你可以选择任意字母替换字符串 t 中的字符，然后最终的结果就是 s 和 t 不一样，但是所含的字母的个数是一样的，例如示例一中的 s 和 t 最终都含有 1 个 a 和 2 个 b。
那这样就简单了，直接比较原始的 s 和 t 中不同的字母数量有几个，例如 ab 和 bc，不同的字母值有一个 a 和 c，这里可以直接用一个 map 来计数：
[[email protected]]# cat Q2.go
func minSteps(s string, t string) int {
var commonChar = 0
var charA = map[uint8]int{}
for i := 0; i < len(s); i++ {
charA[s[i]]++
}
for i := 0; i < len(t); i++ {
charA[t[i]]--
}
for _, v := range charA {
commonChar += abs(v)
}
return commonChar / 2
}
最后这里之所以要减去一半是因为不同的字母我这里算了两次，例如 ab 和 bc，其中 a 最终的数值是 1，c 的数值是 -1，按道理，其实我只需要累加非负部分即可，但是，我觉得最后减半代码更好看，所以就这么做了。
3. 推文计数
这道题目是道坑壁题，一个是题目意思有一点隐藏，另外一个是提交错误的时候提示的内容是错的，导致最终没有提交正确。这里的注意点有：
- 如果指定区间内没有 tweet，那么需要返回 0 条
- 最后一个 endTime 是包含 endTime 的
一开始我还使用二分查找去寻找 startTime 的上界，然而最终发现根本没必要，遍历都可以通过，然后其实其他就很简单了，本来是道送分题，结果成了进坑题：
[[email protected]]# cat Q3.go
import "sort"
type TweetCounts struct {
tweets map[string][]int
}
func Constructor() TweetCounts {
tc := TweetCounts{
tweets: map[string][]int{},
}
return tc
}
func (this *TweetCounts) RecordTweet(tweetName string, time int) {
this.tweets[tweetName] = append(this.tweets[tweetName], time)
}
func (this *TweetCounts) GetTweetCountsPerFrequency(freq string, tweetName string, startTime int, endTime int) (rst []int) {
sort.Ints(this.tweets[tweetName])
var freqSecond = 60
switch freq {
case "minute":
break
case "hour":
freqSecond = 3600
case "day":
freqSecond = 24 * 3600
}
var tweets = this.tweets[tweetName]
rst = make([]int, (endTime-startTime)/freqSecond+1)
for i := 0; i < len(tweets); i++ {
if tweets[i] < startTime {
continue
}
if tweets[i] > endTime {
return rst
}
rst[(tweets[i]-startTime)/freqSecond]++
}
return rst
}
4. 参加考试的最大学生数
必须老实说，这道题我没做出来，我一致在考虑回溯，然而，毫无疑问，超时了。然后看了第一的代码之后，原来这是一道 DP。
当知道是 DP 之后，似乎一切都恍然大悟，第二行只依赖于自己和前面一行，是一个很明显的 DP 特征，但是，DP 也推倒不出来。再从代码中看时，一切都了然，原来还是需要遍历一行中的所有状态的，不过人家的遍历写得很有意思，例如，如果记录放置学生的状态，这里使用的是位来表示，如果一个 bit 为 0，表示不放置学生，如果一个 bit 为 1 则表示这个位放置了学生，这样得话，判断左右是否有学生就可以这么做了：
s & (s << 1) == 0 && s & (s >> 1) == 0
至于左前和右前也是同样的道理。最后，这是我修改后的自己的版本：
[[email protected]]# cat Q4.go
func maxStudents(seats [][]byte) int {
var (
// 某一行中处于 state i 时，可以坐 stateCount[i] 个学生
stateCount = make([]int, 256)
// 前 i 排在第 i 排处于 state j 时可以坐 lineStateCount[i][j] 个学生
lineStateCount = make([][]int, 9)
badSeats = make([]int, 9)
lenX = len(seats)
lenY = len(seats[0])
i, j, k int
ans = 0
)
for i = 1; i < 256; i++ {
stateCount[i] = stateCount[i>>1] + (i & 1)
}
for i = 0; i <= lenX; i++ {
lineStateCount[i] = make([]int, 256)
//for j = 0; j < 256; j++ {
// lineStateCount[i][j] = 0
//}
}
for i = 0; i < lenX; i++ {
badSeats[i] = 0
for j = 0; j < lenY; j++ {
if seats[i][j] == '#' {
badSeats[i] |= 1 << j
}
}
}
lineStateCount[0][0] = 0
for i = 0; i < lenX; i++ {
// 对于第 i 排的 state j 作判断
for j = 0; j < 1<<lenY; j++ {
// 没有坏座位： j&badSeats[i] == 0
// 对于每个坐了人的座位，左右都没有人：j&j>>1 == 0 && j&j<<1 == 0
if j&badSeats[i] == 0 && j&(j>>1) == 0 && j&(j<<1) == 0 {
for k = 0; k < 1<<lenY; k++ {
// 对于每个坐了人的座位，左前和右前都没有人
if j&(k>>1) == 0 && j&(k<<1) == 0 {
// stateCount[j]：状态 j 下可以这一排可以坐多少人
lineStateCount[i+1][j] = max(lineStateCount[i+1][j], lineStateCount[i][k]+stateCount[j])
}
}
}
}
}
for i = 0; i < 1<<lenY; i++ {
ans = max(ans, lineStateCount[lenX][i])
}
return ans
}
5. 小结
这一次的提交很失败，一个半小时也只写了 2 道，除开第 3 道或许和系统有关之外，第四道应该是再给一小时也通过不了的，看别人的评论，似乎是以前有类似的题目出现过，这可能可以认为是见识不够的缘故（且当是安慰一下自己吧）。