前言
这次周赛蛮简单的,第三题二分注意边界,还是不够熟练- -
难度上来说,两道简单,两道中等
第一题
6055.转化时间需要的最少操作数
6055.转化时间需要的最少操作数
题解
题目很简单,模拟即可
代码
func convertTime(current string, correct string) int { one := strings.Split(current, ":") two := strings.Split(correct, ":") oneH, _ := strconv.Atoi(one[0]) oneM, _ := strconv.Atoi(one[1]) twoH, _ := strconv.Atoi(two[0]) twoM, _ := strconv.Atoi(two[1]) tot := (twoH-oneH)*60 + twoM - oneM ans := 0 for tot != 0 { if tot >= 60 { tot -= 60 } else if tot >= 15 { tot -= 15 } else if tot >= 5 { tot -= 5 } else if tot >= 1 { tot -= 1 } ans++ } return ans }
第二题
5235.找出输掉零场或一场比赛的玩家
5235.找出输掉零场或一场比赛的玩家
题解
这题没难度的,跟着题目要求写就可以了。。。
代码
func findWinners(matches [][]int) [][]int { mapWin := make(map[int]int) mapLos := make(map[int]int) zero := make([]int, 0) los := make([]int, 0) for _, v := range matches { w, l := v[0], v[1] mapWin[w]++ mapLos[l]++ } for k := range mapWin { if mapLos[k] == 0 { zero = append(zero, k) } } for k := range mapLos { if mapLos[k] == 1 { los = append(los, k) } } sort.Ints(zero) sort.Ints(los) return [][]int{zero, los} }
第三题
5219.每个小孩最多能分到多少糖果
5219.每个小孩最多能分到多少糖果
题解
题目就是说有k个孩子,每个孩子只能获得一次糖并且糖的数量要一致
有一个candies的数组,可以拆分成若干堆给孩子拿,求最大能拿多少糖
思路:设孩子最大拿n个糖,则candies[i] / n >=1 的累计数量,即代码中的temp要>=k , 才能满足题目要求。那么这个n怎么去确定呢,从1~max(candies[i])都可以,数据范围过大,不能暴力。这里可以想到用二分答案,二分前将数组排序即可
代码
func maximumCandies(candies []int, k int64) int { //用二分需要有序 sort.Ints(candies) var tot int64 for _, v := range candies { tot += int64(v) } //特判 if tot < k { //如果糖果的总数小于孩子,肯定不够 return 0 } else if tot == k { //如果刚好等于,则为1 return 1 } //普遍情况 l, r := 1, candies[len(candies)-1] ans := 0 for l <= r { //二分推出答案 mid := (l + r) / 2 temp := 0 //以mid作为每一堆的糖果数量,计算一共有多少堆 for _, v := range candies { cnt := v / mid temp += cnt } //如果满足k个孩子,则l=mid+1去推更大的值更优的答案 if int64(temp) >= k { ans = mid l = mid + 1 } else if int64(temp) < k { //不满足,说明mid太大了,缩小范围 r = mid - 1 } } return ans }
第四题
5302.加密解密字符串
5302.加密解密字符串
题解
题目:
给一个字符串,让你加密,之后解密,解密可能有多个答案,在一个答案字典里面匹配,能匹配上几个就返回匹配几个的数量。key数组中有多个字符,每个字符对应values数组中的字符串,即字符->字符串,遍历需要加密的字符串,将每一个字符变成values中的字符串。
解密就是取出字符串,变成key数组中的字符,然后去匹配答案字典,返回数量。
思路:加密很简单,模拟就行,这里我们来考虑解密返回匹配数量
原字符串 -> 加密 -> 解密 = 答案字典其中一个或多个,答案字典 = 加密字符串被解密
为什么解密后会有多种可能?原因是加密的时候,不同key对应同一个val,导致同一个val解密的时候,对应不同的key。
我们从这里入手,加密后的字符串肯定是唯一的,那么我们加密答案字典即可,如果不同的字符串,加密后,同为了同一个字符串,那么就对这个map[string]计数即可,因为这个被加密后的字符串,解密时,一定会变成上面不同的字符串
代码
type Encrypter struct { keyToVal [26]string DicEnc map[string]int } func Constructor(keys []byte, values []string, dictionary []string) Encrypter { kToV := [26]string{} for idx, v := range keys { kToV[v-'a'] = values[idx] } encrypter := Encrypter{ keyToVal: kToV, DicEnc: make(map[string]int), //从解密统计字典变成加密统计字典 } for _, s := range dictionary { encrypter.DicEnc[encrypter.Encrypt(s)]++ } return encrypter } func (e *Encrypter) Encrypt(word1 string) string { ans := "" for _, ch := range word1 { s := e.keyToVal[ch-'a'] ans += s } return ans } func (e *Encrypter) Decrypt(word2 string) int { return e.DicEnc[word2] } /** * Your Encrypter object will be instantiated and called as such: * obj := Constructor(keys, values, dictionary); * param_1 := obj.Encrypt(word1); * param_2 := obj.Decrypt(word2); */