LeetCode笔记：Biweekly Contest 49 比赛记录
LeetCode笔记：Biweekly Contest 49 比赛记录
- LeetCode笔记：Biweekly Contest 49
- 0. 赛后总结
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
- 3. 算法优化
0. 赛后总结
表示人果然来是老了，中午和同学聚餐，跑去吃日料自助，兴致所至畅饮3大杯梅酒，然后直接就给跪了，当时没啥反应，吃完回来之后发现头晕脑涨，一觉睡到晚上快8点，回去之后还是晕乎乎的，饭都不怎么吃得下，硬塞了一碗泡面之后躺在床上瞬间就觉得天旋地转，最终还是放弃了做比赛，估计周日的比赛也是呵呵了……
得亏是清明假期的第一天，要是第二天或者第三天搞这么一出我估计上班就挂了……
老年人了，还是得好好养生啊！
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题没啥好说的，就是根据行列关系给出格点是否为白色格点的判断即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def squareIsWhite(self, coordinates: str) -> bool:
col, row = coordinates[0], coordinates[1]
return (row in "1357" and col in "bdfh") or (row in "2468" and col in "aceg")提交代码评测得到：耗时28ms，占用内存14.2MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题思路其实也挺直接的，不妨设句子A长于句子B，则两者相似的充要条件为B可以通过插入一个小句来构成A。
换言之，只要不断删除头尾部分AB两个句子完全相同的部分，就可以将B完全删除。
2. 代码实现
给出python代码实现如下：
class Solution:
def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
s1 = sentence1.strip().split()
s2 = sentence2.strip().split()
while s1 != [] and s2 != [] and s1[0] == s2[0]:
s1.pop(0)
s2.pop(0)
while s1 != [] and s2 != [] and s1[-1] == s2[-1]:
s1.pop()
s2.pop()
return s1 == [] or s2 == []提交代码评测得到：耗时28ms，占用内存14.4MB。
当前最优的代码实现耗时24ms，其算法思路与我们是相似的，就不过多展开了。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
nice pair的定义为：
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
变换公式可以得到：
nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
因此，我们只需要记录下nums[i] - rev(nums[i])的值，即可在 O(N)的时间复杂度内完成统计。
2. 代码实现
给出python代码实现如下：
class Solution:
def countNicePairs(self, nums: List[int]) -> int:
MOD = 10**9 + 7
def rev(n):
res = 0
while n != 0:
res = res * 10 + n % 10
n = n // 10
return res
counter = defaultdict(int)
for n in nums:
counter[n - rev(n)] += 1
res = 0
for n in counter.values():
res += n*(n-1)//2
return res % MOD提交代码评测得到：耗时680ms，占用内存24.6MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题最后还是采用暴力的方式解决的。
就是考察所有的取用情况，然后将最优解进行输出，我们采用cache进行状态记录之后，整体的解法还是比较直接的。
2. 代码实现
直接给出python代码实现如下：
class Solution:
def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
cnt = [0 for _ in range(batchSize)]
for g in groups:
cnt[g % batchSize] += 1
@lru_cache(None)
def dp(status, remain):
if all(x == 0 for x in status[1:]):
return 0
nxt = list(status)
res = 0
for i in range(1, batchSize):
if status[i] == 0:
continue
nxt[i] -= 1
res = max(res, dp(tuple(nxt), (remain+i)%batchSize))
nxt[i] += 1
return res if remain != 0 else res + 1
return cnt[0] + dp(tuple(cnt), 0)提交代码评测得到：耗时1200ms，占用内存48.4MB。
但是当前最优的算法耗时仅24ms，是我们效率的50倍，这就很悲伤了……
3. 算法优化
细看了一下他的代码，发现他们的核心思路和我们是一样的，不过他们在我们的代码基础上做了剪枝，首先，当然余数为0的部分可以直接去掉，这部分我们也做了，此外，他们还考察了余数互补的部分，即直接将 n−k进行了配对消耗，从而大幅缩减了整体需要考察的余量的比例。
给出其代码实现如下：
class Solution:
def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
cnt = [0 for _ in range(batchSize)]
for g in groups:
cnt[g % batchSize] += 1
ans = cnt[0]
cnt[0] = 0
for i in range(1, batchSize // 2):
pair = min(cnt[i], cnt[batchSize-i])
ans += pair
cnt[i] -= pair
cnt[batchSize-i] -= pair
if batchSize % 2 == 0:
pair = cnt[batchSize//2] // 2
ans += pair
cnt[batchSize//2] -= 2*pair
@lru_cache(None)
def dp(status, remain):
if all(x == 0 for x in status):
return 0
nxt = list(status)
res = 0
for i in range(1, batchSize):
if status[i] == 0:
continue
nxt[i] -= 1
res = max(res, dp(tuple(nxt), (remain+i)%batchSize))
nxt[i] += 1
return res if remain != 0 else res + 1
return ans + dp(tuple(cnt), 0)提交代码评测得到：耗时64ms，占用内存15.3MB。
虽然没有达到最优的24ms，但是基本处于同一个量级了。
腾讯云开发者
