第一题：拥有最多糖果的孩子
难度简单
题目描述
给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。
示例 1：
|
1 2 3 4 5 6 7 8 9 |
输入：candies = [2,3,5,1,3], extraCandies = 3 输出：[true,true,true,false,true] 解释： 孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。 孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。 孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。 孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。 孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。 |
示例 2：
|
1 2 3 4 |
输入：candies = [4,2,1,1,2], extraCandies = 1 输出：[true,false,false,false,false] 解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。 |
示例 3：
|
1 2 3 |
输入：candies = [12,1,12], extraCandies = 10 输出：[true,false,true] |
提示：
2 <= candies.length <= 1001 <= candies[i] <= 1001 <= extraCandies <= 50
题目链接
https://leetcode-cn.com/problems/kids-with-the-greatest-number-of-candies/
思路:
数组中的最大值减去额外的糖果🍬数，如果小朋友的糖果数大于等于这个数，就能成为糖果最多的孩子。否则就不能成为糖果最多的孩子。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]: maximal = max(candies) need = maximal - extraCandies ans = [] for candy in candies: if candy >= need: ans.append(True) else: ans.append(False) return ans |
第二题：改变一个整数能得到的最大差值
难度中等
题目描述
给你一个整数 num 。你可以对它进行如下步骤恰好 两次 ：
- 选择一个数字
x (0 <= x <= 9). - 选择另一个数字
y (0 <= y <= 9)。数字y可以等于x。 - 将
num中所有出现x的数位都用y替换。 - 得到的新的整数 不能 有前导 0 ，得到的新整数也 不能 是 0 。
令两次对 num 的操作得到的结果分别为 a 和 b 。
请你返回 a 和 b 的 最大差值 。
示例 1：
|
1 2 3 4 5 6 |
输入：num = 555 输出：888 解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。 第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。 现在，我们有 a = 999 和 b = 111 ，最大差值为 888 |
示例 2：
|
1 2 3 4 5 6 |
输入：num = 9 输出：8 解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。 第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。 现在，我们有 a = 9 和 b = 1 ，最大差值为 8 |
示例 3：
|
1 2 3 |
输入：num = 123456 输出：820000 |
示例 4：
|
1 2 3 |
输入：num = 10000 输出：80000 |
示例 5：
|
1 2 3 |
输入：num = 9288 输出：8700 |
提示：
1 <= num <= 10^8
题目链接
https://leetcode-cn.com/problems/max-difference-you-can-get-from-changing-an-integer/
思路:
这题表述的有一点歧义。其实就是改变一个整数能获得的最大数值，和改变一个整数能获得的最小数值，它们的差。
最大数值把第一个不是9的数替换成9即可。最小数值由于要考虑前导0，替换规则如下：
① 如果第一个数不是1，把它替换成1。
② 如果第一个数是1，把第一个不是0或1的数替换成0（因为如果把1替换成0会出现前导0）。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution: def maxDiff(self, num: int) -> int: s = str(num) n = len(s) maximal = minimal = s for i in range(n): if s[i] != '9': maximal = s.replace(s[i], '9') break if s[0] != '1': minimal = s.replace(s[0], '1') else: for i in range(1, n): if s[i] != '1' and s[i] != '0': minimal = s.replace(s[i], '0') break # print(maximal) # print(minimal) return int(maximal) - int(minimal) |
第三题：检查一个字符串是否可以打破另一个字符串
难度中等
题目描述
给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。
字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。
示例 1：
|
1 2 3 4 |
输入：s1 = "abc", s2 = "xya" 输出：true 解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。 |
示例 2：
|
1 2 3 4 |
输入：s1 = "abe", s2 = "acd" 输出：false 解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。 |
示例 3：
|
1 2 3 |
输入：s1 = "leetcodee", s2 = "interview" 输出：true |
提示：
s1.length == ns2.length == n1 <= n <= 10^5- 所有字符串都只包含小写英文字母。
题目链接
https://leetcode-cn.com/problems/check-if-a-string-can-break-another-string/
思路:
对两个字符串即可，如果s1的所有字符都大于等于s2，或者s2的所有字符都大于s1，则满足要求。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution: def checkIfCanBreak(self, s1: str, s2: str) -> bool: l1 = list(s1) l1.sort() l2 = list(s2) l2.sort() n = len(s1) flag = True for i in range(n): if l1[i] < l2[i]: break else: return True for i in range(n): if l1[i] > l2[i]: break else: return True return False |
第四题：每个人戴不同帽子的方案数
难度困难
题目描述
总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。
给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。
请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。
由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。
示例 1：
|
1 2 3 4 5 |
输入：hats = [[3,4],[4,5],[5]] 输出：1 解释：给定条件下只有一种方法选择帽子。 第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。 |
示例 2：
|
1 2 3 4 5 |
输入：hats = [[3,5,1],[3,5]] 输出：4 解释：总共有 4 种安排帽子的方法： (3,5)，(5,3)，(1,3) 和 (1,5) |
示例 3：
|
1 2 3 4 5 |
输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] 输出：24 解释：每个人都可以从编号为 1 到 4 的帽子中选。 (1,2,3,4) 4 个帽子的排列方案数为 24 。 |
示例 4：
|
1 2 3 |
输入：hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]] 输出：111 |
提示：
n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i]包含一个数字互不相同的整数列表。
题目链接
https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other/
思路:
由于帽子的数量相对较大，而人数相对较小。可以反过来考虑每顶帽子喜欢的人。
状态压缩dp。n个人是否选了喜欢的帽子的状态，可以用n位二进制来表示。dp[status]表示某种状态的种数。选了帽子的人就不能再次选帽子，因此状态转移方程dp'[cur | j] += dp[j]，其中j & cur == 0。
因为最后所有人的都要选帽子，所以返回的结果为dp['1111..111'](n个’1′)，也就是dp[2^n-1]。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
class Solution: def numberWays(self, hats: List[List[int]]) -> int: n = len(hats) # dp[] shown = set() # 所有的帽子 for line in hats: shown.update(set(line)) # dp[status] mem = defaultdict(list) # 每顶帽子喜欢的人 for i, line in enumerate(hats): for hat in line: mem[hat].append(i) dp = [0] * 2 ** n dp[0] = 1 for i in range(1, len(shown) + 1): temp = dp.copy() hat = shown.pop() # 下一顶帽子hat for j in range(2 ** n): if dp[j] == 0: # j的情况不可能出现 continue for person in mem[hat]: # 这顶帽子hat喜欢的所有人 cur = 1 << person # 这个人的二进制编码 if cur & j: # 这个人已经有了喜欢的帽子 continue temp[cur | j] += dp[j] # 更新新的状态 dp = temp # print(shown) return dp[-1] % (1000000000 + 7) |
