LeetCode笔记：Weekly Contest 313
LeetCode笔记：Weekly Contest 313
codename_cys
发布于 2022-10-04 19:12:35
发布于 2022-10-04 19:12:35
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题思路上很直接，就是直接计算两个数字的最大公约数，然后看一下这个最大公约数有多少个约数即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def commonFactors(self, a: int, b: int) -> int:
x = math.gcd(a, b)
t = int(math.sqrt(x))
if t*t == x:
res = 1
else:
res, t = 0, t+1
for i in range(1, t):
if x % i == 0:
res += 2
return res提交代码评测得到：耗时37ms，占用内存13.9MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题其实还是一个二维累积数组的问题。
我们首先计算一下二维累积数组，然后就可以快速地得到每一个
方阵的和，然后我们再扣去其中两个数即可得到没有给目标图像的和，求出其中的最大值即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxSum(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
s = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
s[i][j] = grid[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
def get_sum(i, j):
return s[i+3][j+3] - s[i][j+3] - s[i+3][j] + s[i][j] - grid[i+1][j] - grid[i+1][j+2]
return max([get_sum(i, j) for i in range(n-2) for j in range(m-2)])提交代码评测得到：耗时899ms，占用内存17.3MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题要获得最小的xor结果，那么我们首先计算出来num1中的1的位置与个数，然后用num2当中的1依次从大到小去填充这些数字。
在填充完成之后，如果1依然有剩余，那么我们只能够从小到大到那些原本为0的值上面重新补上1，直到所有的1都被用完。
由此，我们即可得到最小的xor结果。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimizeXor(self, num1: int, num2: int) -> int:
s = bin(num1)[2:].rjust(32, "0")
cnt = Counter(bin(num2))["1"]
digits = [0 for _ in range(32)]
for i in range(32):
if s[i] == "1" and cnt > 0:
digits[i] = 1
cnt -= 1
for i in range(31, -1, -1):
if cnt > 0 and s[i] == "0":
digits[i] = 1
cnt -= 1
res = 0
for i in range(32):
res = res * 2 + digits[i]
return res提交代码评测得到：耗时68ms，占用内存13.8MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题我的思路比较粗暴，就是一个动态规划 + 剪枝的思路，所以这里就不多做展开了。
2. 代码实现
给出python代码实现如下：
class Solution:
def deleteString(self, s: str) -> int:
n = len(s)
@lru_cache(None)
def dp(idx):
m = (n - idx) // 2
res = 1
for i in range(1, m+1):
if res >= 1 + (n-idx-i):
break
if s[idx+i:].startswith(s[idx:idx+i]):
res = max(res, 1 + dp(idx+i))
return res
return dp(0)提交代码评测得到：耗时2443ms，占用内存21.2MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录