第61场双周赛
总的来说，这周的题目算是比较水吧。
a.差的绝对值为K的数对数目
注意到数据量1 <= nums.length <= 200，于是果断暴力
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
ans = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if abs(nums[i] - nums[j]) == k:
ans += 1
return ansb.从双倍数组中还原数组
一种朴素的思路就是从小开始枚举changed数组中的元素，假设当前挑选
的数据为a
1.如果2 * a在changed中，就把a当作是原数组的元素，同时删除2 * a
2.如果2 * a不在changed中，说明不是一个双倍数组
为什么上面这种方法是可以的，因为只要changed是个双倍数组，且a是当
前的最小值，那么a一定是在原数组中的。
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
s = {}
changed.sort()
for a in changed:
if a in s:
s[a] += 1
else:
s[a] = 1
ans = []
for a in changed:
if a in s:
if 2 * a in s:
ans.append(a)
s[a] -= 1
s[a * 2] -= 1
if s[a] == 0:
del s[a]
if 2*a in s and s[2 * a] == 0:
del s[a * 2]
if a in s and s[a] < 0:
return []
else:
return []
return ans c.出租车的最大盈利
这种题不知道为什么第一个想到的就是动态规划：
用dp[i]表示车到达i点时可以获得的最大利益,dp[i] = max (dp[i-1], dp[i])，还有一种情况是对于终点不大于i的订单，如果接了这个单子可以获取的利益。
class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
dp = [0] * (n + 1)
rides.sort(key=lambda x: x[1])
i = 0
for pos in range(1, n + 1):
dp[pos] = dp[pos-1]
while i < len(rides) and pos >= rides[i][1]:
s, t, e = rides[i]
dp[pos] = max(dp[pos], dp[s] + t - s + e)
i += 1
return dp[n]d.使得数组连续的最少操作
双指针, 首先我们将数组排序，然后我们用i表示第一个指针，表示nums[i]是我们变化数组后最小的数。
同时用j表示nums[j] > nums[i] + n - 1，其中j > i，
那么需要的操作就是将小于nums[i]的数，共有i个，还有就是大于等于'nums[j]'的个数，共有n-j个，同时不要忘记在[i, j)这些数中可能有一些数是重复的，我在程序中用cur来记录重复的个数，
那么对于[i,j)，需要的操作数就是i+cur+n-j，移动i,j就可以了，时间复杂度O(N)。
class Solution:
def minOperations(self, nums: List[int]) -> int:
nums.sort()
dp = collections.Counter(nums)
def next(i: int) -> int:
nonlocal nums
j = i
while j < n and nums[j] == nums[i]:
j += 1
return j
n = len(nums)
ans = n
i = j = 0
cur = 0
while i < n:
nxt = nums[i] + n - 1
while j < n and nums[j] <= nxt:
cur += dp[nums[j]] - 1
j = next(j)
ans = min(ans, i + cur + n - j)
cur -= dp[nums[i]] - 1
i = next(i)
return ans评论 (8)
