LeetCode笔记：Weekly Contest 298
LeetCode笔记：Weekly Contest 298
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题的思路还是比较简单的，只要先记录一下字符串当中的所有字符，然后按照字典序大小倒序遍历一下字符，看一下第一个大小写同时存在于字符串中的结果即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def greatestLetter(self, s: str) -> str:
cnt = Counter(s)
for i in range(26):
l, u = chr(ord('a') + 25 - i), chr(ord('A') + 25 - i)
if l in cnt and u in cnt:
return u
return ""提交代码评测得到：耗时64ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题要使得n个尾数为k的数之和要恰好等于num，那么必然有n*k与num有相同的尾数，且前者不大于后者。
此外，如果满足上述条件，那么我们总能够构造一组长度为n的数使得所有的数字尾数均为k，且总和为num。
事实上，只需要将余数适当分配到这n个数上即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumNumbers(self, num: int, k: int) -> int:
if num == 0:
return 0
for i in range(1, 11):
a = i * k
if a <= num and a % 10 == num % 10:
return i
return -1提交代码评测得到：耗时75ms，占用内存13.8MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题结果思路上前置的0可以有任意多个，但是一旦取了一个1之后，那么后续可能的排列就至多只能组成一个k，即是说，假设k的二进制一共是m位，那么后续能够使用的位数至多只能有m位。
因此，综上，我们就是要遍历一下所有的位置作为真实的有效开头，在这种情况下，每一个位置上的结果就是其前面的0的个数和后续能够构成的不大于k的二级制数最大位数。
然后，我们来看如何来找某一个位置起能够构成二进制数的最大位数，这个其实也简单，显然，如果总的位数小于m，那么全部取用就行了，如果位数大于m，还需要进行分类讨论一下，如果能找到n个数构成的子串小于k，那么结果为k，反之，结果就是m-1。
2. 代码实现
给出python代码实现如下：
class Solution:
def longestSubsequence(self, s: str, k: int) -> int:
n = len(s)
kd = []
while k != 0:
kd.insert(0, k % 2)
k = k // 2
m = len(kd)
def get_max(idx):
if n - idx < m:
return n-idx
sub = s[idx:]
less, j = False, 0
for i, ch in enumerate(sub):
if j >= m:
break
if not less:
if int(sub[i]) > kd[j]:
continue
elif int(sub[i]) < kd[j]:
less = True
j += 1
return m if j >= m else m-1
res, cnt = 0, 0
for i, ch in enumerate(s):
if ch == "0":
cnt += 1
res = max(res, cnt)
else:
res = max(res, cnt + get_max(i))
return res提交代码评测得到：耗时429ms，占用内存14MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题我的基本思路就是greedy的填充，首先，我们按照单位方格的价值把prices进行排序，然后greedy的使用方格进行填充。
填充方式是说，我们先用当前最大的prices进行填充主体的矩形，然后考察剩余的边角料的填充。
上述解法可以实现我们所需的功能，但是不加处理的话会出现超时，因此我们还需要在上述基础上进行一下剪枝。
剪枝的思路也相对简单，首先，如果行或者列上面能够直接被当前最大的price矩形完全覆盖，那么我们直接取用就行了，只有在无法完全覆盖的情况下，才可能出现其他矩形进行填充产生更大的总price的情况。
因此，我们基于此进行剪枝就能够减少算法复杂度，通过最后的测试。
2. 代码实现
给出python代码实现如下：
class Solution:
def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
prices = sorted(prices, key=lambda x: -x[2] / (x[0] * x[1]))
@lru_cache(None)
def dp(w, h, idx):
res = 0
for x, y, p in prices[idx:]:
if x > w or y > h:
continue
if p / (x * y) * (w * h) <= res:
break
if w % x == 0 and h % y == 0:
res = max(res, (w//x) * (h//y)*p)
break
elif w % x == 0:
i = w // x
for j in range(h//y, 0, -1):
s = i * j * p
wr, hr = w - x*i, h - y*j
res = max(res, s + dp(wr, h, idx+1) + dp(w-wr, hr, idx+1), s + dp(wr, h-hr, idx+1) + dp(w, hr, idx+1))
elif h % y == 0:
j = h // y
for i in range(w//x, 0, -1):
s = i * j * p
wr, hr = w - x*i, h - y*j
res = max(res, s + dp(wr, h, idx+1) + dp(w-wr, hr, idx+1), s + dp(wr, h-hr, idx+1) + dp(w, hr, idx+1))
else:
for i in range(w//x, 0, -1):
for j in range(h//y, 0, -1):
s = i * j * p
wr, hr = w - x*i, h - y*j
res = max(res, s + dp(wr, h, idx+1) + dp(w-wr, hr, idx+1), s + dp(wr, h-hr, idx+1) + dp(w, hr, idx+1))
return res
return dp(m, n, 0)提交代码评测得到：耗时1049ms，占用内存22MB。
腾讯云开发者
