leetcode周赛225
难度顺序：
。
5661. 替换隐藏数字得到的最晚时间
给你一个字符串 time ，格式为 hh:mm（小时：分钟），其中某几位数字被隐藏（用 ? 表示）。
有效的时间为 00:00 到 23:59 之间的所有时间，包括 00:00 和 23:59 。
替换 time 中隐藏的数字，返回你可以得到的最晚有效时间。
示例 1：
输入：time = "2?:?0"
输出："23:50"
解释：以数字 '2' 开头的最晚一小时是 23 ，以 '0' 结尾的最晚一分钟是 50 。
示例 2：
输入：time = "0?:3?"
输出："09:39"
示例 3：
输入：time = "1?:22"
输出："19:22"
提示：
time的格式为hh:mm- 题目数据保证你可以由输入的字符串生成有效的时间
思路：
贪心题。
一位位的去分析即可，只要越靠前的位数字越大，时间就会越大。分析的同时保证时间合法，前两位的分析有点坑。
时间复杂度：
.
class Solution:
def maximumTime(self, time: str) -> str:
if time[0] == '?' :
if time[1] < '4' or time[1] == '?' :
time = '2' + time[1:]
else :
time = '1' + time[1:]
if time[1] == '?' :
if time[0] == '2' :
time = '23' + time[2:]
else :
time = time[0] + '9' + time[2:]
if time[3] == '?' :
time = time[0:3] + '5' + time[4]
if time[4] == '?' :
time = time[:4] + '9'
return time
5662. 满足三条件之一需改变的最少字符数
给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。
操作的最终目标是满足下列三个条件 之一 ：
a中的 每个字母 在字母表中 严格小于b中的 每个字母 。b中的 每个字母 在字母表中 严格小于a中的 每个字母 。a和b都 由 同一个 字母组成。
返回达成目标所需的 最少 操作数*。*
示例 1：
输入：a = "aba", b = "caa"
输出：2
解释：满足每个条件的最佳方案分别是：
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。
示例 2：
输入：a = "dabadd", b = "cda"
输出：3
解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。
提示：
1 <= a.length, b.length <= 10^5a和b只由小写字母组成
思路：
第三种方案最简单把每个字符串分别变成出现次数最多的字符即可。
第一种方案的话就枚举将字符串a所有字符变成小于等于k和字符串b所有字符大于k的答案，取最小值。
第二种方案类似。
答案是三种方案取最小值。
时间复杂度：
.
class Solution:
def minCharacters(self, a: str, b: str) -> int:
ans = [10000001, 10000001, 0]
cnta = [0 for i in range(26)]
cntb = [0 for i in range(26)]
for c in a :
cnta[ord(c) - ord('a')] += 1
for c in b :
cntb[ord(c) - ord('a')] += 1
ans[2] = len(a) - max(cnta) + len(b) - max(cntb)
for i in range(ord('a'), ord('z')) :
res = [0, 0]
for c in a :
if ord(c) > i :
res[0] += 1
else :
res[1] += 1
for c in b :
if ord(c) <= i :
res[0] += 1
else :
res[1] += 1
ans[0] = min(ans[0], res[0])
ans[1] = min(ans[1], res[1])
return min(ans)
5663. 找出第 K 大的异或坐标值
给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
示例 1：
输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
示例 2：
输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
示例 3：
输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
示例 4：
输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10000 <= matrix[i][j] <= 10^61 <= k <= m * n
思路
首先算出矩阵每一个前缀和异或值，这个可以类比二维前缀和。
sum[i][j]=val[i][j]^sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]。
然后用一个大小为k的堆维护第k大即可。
时间复杂度：
.
class Solution:
def check(self, x, y, n, m, val: List[List[int]]) -> int:
if x >= 0 and x < n and y >= 0 and y < m :
return val[x][y]
return 0
def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
m = len(matrix[0])
val = [[0 for i in range(m)] for i in range(n)]
tasks = []
for i in range(n):
for j in range(m):
val[i][j] = matrix[i][j] ^ self.check(i - 1, j, n, m, val) ^ self.check(i, j - 1, n, m, val) ^ self.check(i - 1, j - 1, n, m, val)
heapq.heappush(tasks, val[i][j])
if len(tasks) > k :
heapq.heappop(tasks)
return heapq.heappop(tasks)
5664. 放置盒子
有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：
- 你可以把盒子放在地板上的任何地方。
- 如果盒子
x需要放置在盒子y的顶部，那么盒子y竖直的四个侧面都 必须 与另一个盒子或墙相邻。
给你一个整数 n ，返回接触地面的盒子的 最少 可能数量*。*
示例 1：
img
输入：n = 3
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 2：
img
输入：n = 4
输出：3
解释：上图是 3 个盒子的摆放位置。
这些盒子放在房间的一角，对应左侧位置。
示例 3：
img
输入：n = 10
输出：6
解释：上图是 10 个盒子的摆放位置。
这些盒子放在房间的一角，对应后方位置。
提示：
1 <= n <= 10^9
思路
房间长宽高都是n不用担心会放不下。
观察得知一个较为完备的立体形状是底面是一个长宽相同的斜三角形。也就是实例2和实例3的样子。
首先算出每一个完备立体形状图形的大小。
找到底边长宽最大的且方块个数小于等于n的完备图形，假设底面是一个长宽为k的斜三角形。
然后尝试将其扩展补足n个方块，扩展方案：在一个侧面贴着放置一个长高为a的三角形。
代码有注释。
时间复杂度：
.
class Solution:
def minimumBoxes(self, n: int) -> int:
# 算出每一个完备图形的方块个数
val = [1]
i = 2
last = val[len(val) - 1]
while last < n :
last += i * (i + 1) // 2
val.append(last)
i += 1
# 二分k
l = 1
r = len(val)
ans = 1
while l <= r :
mid = (l + r) >> 1
if val[mid - 1] <= n :
ans = mid
l = mid + 1
else :
r = mid - 1
res = ans * (ans + 1) // 2
n -= val[ans - 1]
# 扩展侧面，放一个i*i的三角形，算出i最小是多少
i = 1
while n > 0 :
n -= i
i += 1
res += 1
return res腾讯云开发者
