LeetCode笔记：Biweekly Contest 61
LeetCode笔记：Biweekly Contest 61
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题很简单，最暴力的方式就是二重循环，不过我们的解法是先统计每个元素出现的个数，然后对每一个出现的元素考察与其绝对值为k的数据的个数相乘。
2. 代码实现
给出python代码实现如下：
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
cnt = Counter(nums)
_min, _max = min(nums), max(nums)
res = 0
for i in range(_min, _max-k+1):
res += cnt[i] * cnt[i+k]
return res提交代码评测得到：耗时64ms，占用内存14.3MB。
2. 题目二
给出题目二的试题链接如下:
1. 解题思路
这一题的思路也很直接，我们首先用一个counter记录下所有出现的元素以及其出现的次数，然后我们从小到大开始考察，对于最小的元素，其必然为原始的元素，那么如果可以构造，那么其两倍的元素必然存在且其个数不少于当前元素的个数。
我们重复上述过程，如果最终恰好可以完全分配完原始数组中的元素，那么我们就可以获得结果，反之无法成功构造。
唯一需要特殊考虑一下的就是0的情况，但是整体上没啥影响。
2. 代码实现
给出python代码实现如下：
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
cnt = Counter(changed)
keys = sorted(cnt.keys())
res = []
for k in keys:
if k == 0:
if cnt[k] % 2 != 0:
return []
res.extend([k] * (cnt[k] // 2))
continue
if cnt[k] == 0:
continue
if cnt[2*k] < cnt[k]:
return []
res.extend([k] * cnt[k])
cnt[2*k] -= cnt[k]
cnt[k] = 0
return res提交代码评测得到：耗时1372ms，占用内存31.7MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题思路也很暴力，就是用一个动态规划直接暴力求解……
整个的算法复杂度在 O ( N ⋅ l o g N ) O(N \cdot logN) O(N⋅logN)。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
rides = sorted(rides)
m = len(rides)
@lru_cache(None)
def dp(idx):
if idx >= m:
return 0
st, ed, tip = rides[idx]
fee = ed-st+tip
nxt = bisect.bisect_left(rides, [ed, ed, 0])
return max(fee + dp(nxt), dp(idx+1))
return dp(0)提交代码评测得到：1884ms，占用内存72.9MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题的思路其实也挺简单的。
首先，对于最终的结果，必然是连续的n个数，且我们总可以使第一个数是原始数组当中的数。
如此一来，我们只需要将原始的数据去重之后进行排序，然后考察每一个数x作为首元素时需要额外调整到范围内的数据的数目，然后获取其最小值即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minOperations(self, nums: List[int]) -> int:
n = len(nums)
nums = sorted(list(set(nums)))
i, j, m = 0, 0, len(nums)
res = n
while i < m:
while j < m and nums[j] < nums[i] + n:
j += 1
res = min(res, n - (j-i))
i += 1
return res提交代码评测得到：耗时824ms，占用内存33.2MB。
腾讯云开发者
