不知道哪一天的
稳稳DP
def maxScoreSightseeingPair(self, values: List[int]) -> int:
ans, dp = -1, values[0]
for j in range(1, len(values)):
ans = max(dp+values[j]-j, ans)
dp = max(dp, values[j]+j)
return ans
不知道哪一天的
我写更新dict那里写了半小时
干你娘
白痴死了 我说我
连swap都不会...
def minimumOperations(self, root: Optional[TreeNode]) -> int:
def countswap(nums):
mp = {}
cnt = 0
for i in range(len(nums)):
mp[nums[i]] = i
for i, num in enumerate(sorted(nums)):
if num!=nums[i]:
a, b = num, nums[i]
a_idx, b_idx = mp[a], i
nums[a_idx], nums[b_idx] = nums[b_idx], nums[a_idx]
mp[a], mp[b] = b_idx, a_idx
cnt += 1
return cnt
q = deque()
ans = 0
q.append(root)
while q:
ans += countswap([node.val for node in q])
# print([node.val for node in q], countswap([node.val for node in q]))
for _ in range(len(q)):
cur_node = q.popleft()
if cur_node.left:
q.append(cur_node.left)
if cur_node.right:
q.append(cur_node.right)
return ans