LeetCode 第25场双周赛

第一题:拥有最多糖果的孩子

难度简单

题目描述

给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子,检查是否存在一种方案,将额外的 extraCandies 个糖果分配给孩子们之后,此孩子有 最多 的糖果。注意,允许有多个孩子同时拥有 最多 的糖果数目。

示例 1:

示例 2:

示例 3:

提示:

  • 2 <= candies.length <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50

题目链接

https://leetcode-cn.com/problems/kids-with-the-greatest-number-of-candies/

思路:

  数组中的最大值减去额外的糖果🍬数,如果小朋友的糖果数大于等于这个数,就能成为糖果最多的孩子。否则就不能成为糖果最多的孩子。

代码:

第二题:改变一个整数能得到的最大差值

难度中等

题目描述

给你一个整数 num 。你可以对它进行如下步骤恰好 两次

  • 选择一个数字 x (0 <= x <= 9).
  • 选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x
  • num 中所有出现 x 的数位都用 y 替换。
  • 得到的新的整数 不能 有前导 0 ,得到的新整数也 不能 是 0 。

令两次对 num 的操作得到的结果分别为 ab

请你返回 ab最大差值

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= num <= 10^8

题目链接

https://leetcode-cn.com/problems/max-difference-you-can-get-from-changing-an-integer/

思路:

  这题表述的有一点歧义。其实就是改变一个整数能获得的最大数值,和改变一个整数能获得的最小数值,它们的差。

  最大数值把第一个不是9的数替换成9即可。最小数值由于要考虑前导0,替换规则如下:

  ① 如果第一个数不是1,把它替换成1

  ② 如果第一个数是1,把第一个不是01的数替换成0(因为如果把1替换成0会出现前导0)。

代码:

第三题:检查一个字符串是否可以打破另一个字符串

难度中等

题目描述

给你两个字符串 s1s2 ,它们长度相等,请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列,或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y (两者长度都为 n )需满足对于所有 i(在 0n - 1 之间)都有 x[i] >= y[i](字典序意义下的顺序)。

示例 1:

示例 2:

示例 3:

提示:

  • s1.length == n
  • s2.length == n
  • 1 <= n <= 10^5
  • 所有字符串都只包含小写英文字母。

题目链接

https://leetcode-cn.com/problems/check-if-a-string-can-break-another-string/

思路:

  对两个字符串即可,如果s1的所有字符都大于等于s2,或者s2的所有字符都大于s1,则满足要求。

代码:

第四题:每个人戴不同帽子的方案数

难度困难

题目描述

总共有 n 个人和 40 种不同的帽子,帽子编号从 140

给你一个整数列表的列表 hats ,其中 hats[i] 是第 i 个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子,确保每个人戴的帽子跟别人都不一样,并返回方案数。

由于答案可能很大,请返回它对 10^9 + 7 取余后的结果。

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[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]

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注