LeetCode笔记：Biweekly Contest 74
LeetCode笔记：Biweekly Contest 74
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题的思路还是很直接的，只需要对数组中的每一个元素的个数进行一下统计，要能够成功分组，当且仅当所有元素的个数均为偶数。
2. 代码实现
给出python代码实现如下：
class Solution:
def divideArray(self, nums: List[int]) -> bool:
cnt = Counter(nums)
return all(v % 2 == 0 for v in cnt.values())提交代码评测得到：耗时118ms，占用内存14.2MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题的思路其实也比较直接，显然，pattern中没有出现的字符对于结果是无用的，因此，我们首先可以对字符串进行简化，只保留pattern当中出现过的字符，然后，我们来考察如何获得最多的pattern。
在此之前，我们首先考察一种特殊情况，即pattern为两个相同字符的情况，此时根据排列组合，答案事实上是显见的，且字符增加方法也是无所谓的，只要随意增加一个字符即可。
如果pattern的字符不同，那么，增加字符的方式就一定是以下两者之一：
- 在字符串开头加上
pattern[0] - 在字符串尾部加上
pattern[1]
对于前者，增加的pattern数目为pattern[1]的数目，而对于后者，增加的pattern数目为pattern[0]的数目。
因此，剩下的我们只需要考察原始序列当中包含的pattern数目即可，这个问题只要对每一个pattern[0]字符后面的pattern[1]的数目进行一下求和即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
s = [ch for ch in text if ch in pattern]
n = len(s)
if pattern[0] == pattern[1]:
return n * (n+1) // 2
cnt = 0
res = 0
for ch in s[::-1]:
if ch == pattern[1]:
cnt += 1
else:
res += cnt
return res + max(cnt, n-cnt)提交代码评测得到：耗时169ms，占用内存16.4MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题我的思路其实挺简单的，不过相对的效率就不是很高……
我的思路就是不断地取最大的元素进行减半处理。
因此，我们就是直接对原数组进行一次排序，然后不断地pop，然后取半，最后二分插入即可。
不过直接这样的解法遇到了超时，因此我们稍微做了一点优化，即：
- 显然的，如果最大的元素减半之后不大于最小的元素，那么最优的解法必然是所有的元素减半，因此，我们返回数组长度即可。
另一方面，对于元素减半之后如果长度小于了最小的元素，那么我们事实上也不再需要将这个元素放回到数组当中了。
通过上述优化，代码不再遇到超时问题，不过还是感觉不太优雅……
anyway，先将就将就吧……
2. 代码实现
给出python代码实现如下：
class Solution:
def halveArray(self, nums: List[int]) -> int:
nums = sorted(nums)
if nums[-1] / 2 <= nums[0]:
return len(nums)
s = sum(nums) / 2
rm = 0
cnt = 0
while rm < s:
x = nums.pop() / 2
rm += x
cnt += 1
if rm < s and x > nums[0]:
bisect.insort(nums, x)
return cnt提交代码评测得到：耗时4188ms，占用内存28.8MB。
看了一下当前的最优解法，感觉也就是把二叉排序换成了堆排，没啥本质的区别……
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题感觉就是一个简单地动态规划的题目。
对每一个位置，如果该位置本来就是黑色的话，那么我们无需进行额外的操作，否则，我们可以有两种操作，要不就是铺上地毯，要不然就是不铺，然后继续考虑下一个位置，此时白色格子总数就会+1。
特殊的，如果剩下的地毯可以铺满所有的位置时，那么直接返回0即可；反之，如果地毯已经铺完了，那么只要返回剩下的所有的白色的格子数目即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
n = len(floor)
cnt = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
if floor[i] == "0":
cnt[i] = cnt[i+1]
else:
cnt[i] = cnt[i+1] + 1
@lru_cache(None)
def dp(idx, k):
if idx >= n:
return 0
elif k == 0:
return cnt[idx]
elif k * carpetLen >= n - idx:
return 0
elif floor[idx] == "0":
return dp(idx+1, k)
return min(1 + dp(idx+1, k), dp(idx+carpetLen, k-1))
return dp(0, numCarpets)提交代码评测得到：耗时2045ms，占用内存178.3MB。
腾讯云开发者
