LeetCode笔记：Biweekly Contest 62
LeetCode笔记：Biweekly Contest 62
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题还是比较简单的，首先看元素总数是否一致，然后直接按照顺序进行一下切分即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
if len(original) != n * m:
return []
res = [original[i:i+n] for i in range(0, n*m, n)]
return res提交代码评测得到：耗时956ms，占用内存21.6MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题我们首先对原数组进行一下统计，然后对每一个元素进行考察，如果该元素刚好为target的开头，那么我们需要考虑以下两种情况：
- 如果剩余字符串和当前字符串相同，则可以带来 A n 2 A_n^2 An2个pair对；
- 如果剩余字符串与当前字符串不同，则可以带来 n ⋅ m n\cdot m n⋅m个pair对；
我们对总量进行相加即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def numOfPairs(self, nums: List[str], target: str) -> int:
cnt = Counter(nums)
res = 0
for s1 in cnt:
if not target.startswith(s1):
continue
s2 = target[len(s1):]
if s1 != s2:
res += cnt[s1] * cnt[s2]
else:
res += cnt[s1] * (cnt[s1]-1)
return res提交代码评测得到：耗时40ms，占用内存14.2MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题就是分别考虑一下连续的T与连续的F能够组成的最大长度。
而对于上述的任意一种情况，我们可以使用滑动窗口的方式进行考察，即可得到最终的结果。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
n = len(answerKey)
def count_max_len(ch):
res = 0
i, j, cnt, rep = 0, 0, 0, 0
while j < n:
cnt += 1
if answerKey[j] == ch:
rep += 1
j += 1
while rep > k:
cnt -= 1
if answerKey[i] == ch:
rep -= 1
i += 1
res = max(res, cnt)
return res
return max(count_max_len("T"), count_max_len("F"))提交代码评测得到：耗时540ms，占用内存14.3MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
我们首先来考虑完全不进行元素变幻的话可以得到的分割方式，这个我们只需要求取元素的总和s，那么前缀和为 s 2 \frac{s}{2} 2s的位置均可作为分割点（结尾需要刨除，因为至少需要保证两侧均有一个元素）。
下面，我们考虑对某一个位置的元素i进行置换后会带来的影响，此时元素总和就修正为 s − x i + k s - x_i + k s−xi+k，此时，如果分隔点在前方，那么我们就要找在该元素之前的前序和为 s − x i + k 2 \frac{s-x_i+k}{2} 2s−xi+k的位置数目，如果分隔点在该元素后方，那么我们就要找该元素之后的后序和为 s − x i + k 2 \frac{s-x_i+k}{2} 2s−xi+k的位置数目，两者相加即为修改了该位置上的元素之后重新得到的数组的分割点个数。
2. 代码实现
给出python代码实现如下：
class Solution:
def waysToPartition(self, nums: List[int], k: int) -> int:
n, s = len(nums), sum(nums)
res = [0 for _ in range(n)]
cnt = defaultdict(int)
pre = nums[0]
cnt[pre] += 1
for i in range(1, n):
s_prime = s - nums[i] + k
res[i] += cnt[s_prime/2]
pre += nums[i]
cnt[pre] += 1
cnt = defaultdict(int)
post = nums[-1]
cnt[post] += 1
for i in range(n-2, -1, -1):
s_prime = s - nums[i] + k
res[i] += cnt[s_prime/2]
post += nums[i]
cnt[post] += 1
cnt[s] -= 1
res.append(cnt[s/2])
return max(res)提交代码评测得到：耗时3533ms，占用内存36.5MB。