早起刷题（Day 6）

本文是对第 287 场周赛的复盘总结

6055. 转化时间需要的最少操作数

#模拟题

题目描述

给你两个字符串 current 和 correct ，表示两个 24 小时制时间 。
24 小时制时间 按 “HH:MM” 进行格式化，其中 HH 在 00 和 23 之间，而 MM 在 00 和 59 之间。最早的 24 小时制时间为 00:00 ，最晚的是 23:59 。
在一步操作中，你可以将 current 这个时间增加 1、5、15 或 60 分钟。你可以执行这一操作 任意 次数。
返回将 current 转化为 correct 需要的 最少操作数 。

示例 1：
输入：current = "02:30", correct = "04:35"
输出：3
解释：
可以按下述 3 步操作将 current 转换为 correct ：
- 为 current 加 60 分钟，current 变为 "03:30" 。
- 为 current 加 60 分钟，current 变为 "04:30" 。 
- 为 current 加 5 分钟，current 变为 "04:35" 。
可以证明，无法用少于 3 步操作将 current 转化为 correct 。

示例 2：
输入：current = "11:00", correct = "11:01"
输出：1
解释：只需要为 current 加一分钟，所以最小操作数是 1 。

提示：
current 和 correct 都符合 "HH:MM" 格式
current <= correct

解题思路

(1). 本题其实是变种的零钱问题。初始状态是 current，最终状态是 correct，可用“零钱”面额有 [1,5,15,60]；
(2). 现将初始、最终两种状态转换成和“零钱”面额一样的计数单位——“分钟”；
(3). 使用动态规划，从初始状态一步步向最终状态逼近。

时间复杂度

O(N).

解题代码

func convertTime(current string, correct string) int {

	s1 := strings.Split(current, ":")
	h1, m1 := s1[0], s1[1]
	s2 := strings.Split(correct, ":")
	h2, m2 := s2[0], s2[1]
	
	// 使用分钟代表初始状态
	nowh, _ := strconv.Atoi(h1)
	nowm, _ := strconv.Atoi(m1)
	now := nowh*60+nowm
	
	// 使用分钟代表最终状态
	th, _ := strconv.Atoi(h2)
	tm, _ := strconv.Atoi(m2)
	t := th*60+tm
	
	// 将状态归一化到 (0,diff) 区间
	diff := abs(now, t)
	
	// 可用零钱面额
	choose := []int{1,5,15,60}
	
	dp := make([]int, diff+1)
	dp[0] = 0

	for i:=1; i<=diff; i++ {
		dp[i] = math.MaxInt32
		for j:=len(choose)-1; j>=0; j-- {
			if choose[j] > i {
				continue
			}
			dp[i] = min(dp[i], dp[i-choose[j]]+1)
		}
	}
	
	return dp[diff]
}



func abs(a, b int) int {
	if a > b {
		return a-b
	}

	return b-a
}



func min(a, b int) int {
	if a < b {
		return a
	}
	
	return b
}

5235. 找出输掉零场或一场比赛的玩家

#map

题目描述

给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。
返回一个长度为 2 的列表 answer ：
answer[0] 是所有 没有 输掉任何比赛的玩家列表。
answer[1] 是所有恰好输掉 一场 比赛的玩家列表。
两个列表中的值都应该按 递增 顺序返回。

注意：
只考虑那些参与 至少一场 比赛的玩家。
生成的测试用例保证 不存在 两场比赛结果 相同 。

示例 1：
输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
输出：[[1,2,10],[4,5,7,8]]
解释：
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。


示例 2：
输入：matches = [[2,3],[1,3],[5,4],[6,4]]
输出：[[1,2,5,6],[]]
解释：
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。
 

提示：
1 <= matches.length <= 105
matches[i].length == 2
1 <= winneri, loseri <= 105
winneri != loseri
所有 matches[i] 互不相同

解题思路

(1). 本题需要输出两个列表：其一是 入度 为 $0$ 且 出度 大于 $0$ 的编号，其二是 入度 恰好为 $1$ 的编号；
(2). 使用两个 map 分别保存每个编号的出度和入度；
(3). 首先遍历 入度 map，只要发现其长度为 $1$，那就加入输出中；
(4). 然后遍历 出度 map，检查对应编号的 入度 列表如果为 $0$，那么也加入输出中；
(5). 排序两个列表。

时间复杂度

O(N)

解题代码

func findWinners(matches [][]int) [][]int {

	m1 := make(map[int][]int, 0)
	m2 := make(map[int]bool, 0)
	
	// 遍历 matches，构建 出度 和 入度 map
	for i:=0; i<len(matches); i++ {
		win, lose := matches[i][0], matches[i][1]
		m1[lose] = append(m1[lose], win)
		m2[win] = true
	}

	ret := make([][]int, 2)

	for k, v := range m1 {
		if len(v) == 1 {
			ret[1] = append(ret[1], k)
		}
	}

	for k, _ := range m2 {
		if len(m1[k]) == 0 {
			ret[0] = append(ret[0], k)
		}
	}

	sort.Ints(ret[0])
	sort.Ints(ret[1])
	
	return ret
}

5219. 每个小孩最多能分到多少糖果

#二分查找

题目描述

给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目 。

示例 1：
输入：candies = [5,8,6], k = 3
输出：5
解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。

示例 2：
输入：candies = [2,5], k = 11
输出：0
解释：总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。因此，最后每个小孩都没有得到糖果，答案是 0 。
 

提示：
1 <= candies.length <= 10^5
1 <= candies[i] <= 10^7
1 <= k <= 10^12

解题思路

(1). 首先看一看数据量，明显暴力绝对会超时，那么别无选择，二分法搞起来；
(2). 首先判断一下边界情况，当 🍬总数 < 🧒总数 时，显然大家都没得分，return 0；如果 🍬总数 == 🧒总数 ，return 1
(3) 二分查找的左边界是 $1$，右边界是 🍬总数/🧒总数 ；
(4) 要查找满足条件的右边界，二分超找模板套起来。

时间复杂度

O(Nlog(N))

解题代码

func maximumCandies(candies []int, k int64) int {

	var total int64
	for i:=0; i<len(candies); i++ {
		total += int64(candies[i])
	}

	if total < k {
		return 0
	} else if total == k {
		return 1
	}

	var satisified func(int) bool
	satisified = func(n int) bool {
		var count int64
		for i:=0; i<len(candies); i++ {
			count += int64(candies[i]/n)
			if count >= k {
				return true
			}
		}
		
		return false
	}

	l, r := 1, int(total/k)
	if satisified(r) {
		return r
	}

	for l < r {
		m := l+(r-l)>>1
		if satisified(m) {
			l = m+1
		} else if !satisified(m) {
			r = m
		}
	}

	return l-1
}

5302. 加密解密字符串

#设计题

题目描述

给你一个字符数组 keys ，由若干 互不相同 的字符组成。还有一个字符串数组 values ，内含若干长度为 2 的字符串。另给你一个字符串数组 dictionary ，包含解密后所有允许的原字符串。请你设计并实现一个支持加密及解密下标从 0 开始字符串的数据结构。
字符串 加密 按下述步骤进行：
1.对字符串中的每个字符 c ，先从 keys 中找出满足 keys[i] == c 的下标 i 。
2.在字符串中，用 values[i] 替换字符 c 。
字符串 解密 按下述步骤进行：
1.将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 s ，找出满足 values[i] == s 的一个下标 i 。如果存在多个有效的 i ，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。
2.在字符串中，用 keys[i] 替换 s 。
实现 Encrypter 类：
1.Encrypter(char[] keys, String[] values, String[] dictionary) 用 keys、values 和 dictionary 初始化 Encrypter 类。
2.String encrypt(String word1) 按上述加密过程完成对 word1 的加密，并返回加密后的字符串。
3.int decrypt(String word2) 统计并返回可以由 word2 解密得到且出现在 dictionary 中的字符串数目。

解题思路

(1). 注意到 values 中有相同的字符串，因此不同的字符串加密后可能是一样的，从而一个字符串解密出的结果可能不是唯一的；
(2). 根据提示 1，直接解密较为复杂，不妨逆向思考，即加密 dictionary 中的每个字符串。用哈希表记录每个加密后的字符串的出现次数。这样每次调用 decrypt 时，返回哈希表中 word2 的出现次数即可。

解题代码

type Encrypter struct {
	mp  [26]string
	cnt map[string]int
}

func Constructor(keys []byte, values, dictionary []string) Encrypter {
	mp := [26]string{}
	for i, key := range keys {
		mp[key-'a'] = values[i]
	}
	e := Encrypter{mp, map[string]int{}}
	for _, s := range dictionary {
		e.cnt[e.Encrypt(s)]++
	}
	return e
}

func (e *Encrypter) Encrypt(word1 string) string {
	res := make([]byte, 0, len(word1)*2)
	for _, ch := range word1 {
		s := e.mp[ch-'a']
		if s == "" { return "" }
		res = append(res, s...)
	}
	return string(res)
}

func (e *Encrypter) Decrypt(word2 string) int { return e.cnt[word2] }