1
![]()
思路：首先想到的就是暴力枚举，不出所料超时了。然后就没有思路了。查看官方解释，发现归并算法还有这个效果。两个分别有序的子数组，在经过归并排序的过程中，每一步中如果是后面的元素比较小，则将后面的元素排序并统计前一个子数组中的剩余元素个数并累计。最后得到的就是逆序对总数，并且还能得到排序后的有序数组。
时间复杂度是O(n*logn)
class Solution:
def __init__(self):
self.count = 0
def merge(self,nums1,nums2):
nums3 = []
while nums1 and nums2:
if nums1[0] <= nums2[0]:
nums3.append(nums1.pop(0))
else:
nums3.append(nums2.pop(0))
self.count += len(nums1)
if nums1:
nums3 += nums1
if nums2:
nums3 += nums2
return nums3
def merge_sort(self,nums3):
if len(nums3) <= 1:
return nums3
else:
nums1 = nums3[:len(nums3) // 2]
nums2 = nums3[len(nums3) // 2:]
nums1 = self.merge_sort(nums1)
nums2 = self.merge_sort(nums2)
nums3 = self.merge(nums1,nums2)
return nums3
def reversePairs(self, nums: List[int]) -> int:
if len(nums) <= 1:
return 0
else:
self.merge_sort(nums)
return self.count
2
![]()
思路：这题是真的一点思路都没有，题目都没看懂。后来看完题解之后有了一点思路，可以用递归，先找到最左边的左子节点，它就是最后的根节点然后从左下角，左子节点变为根节点，根节点变为右子节点，右节点变为左子节点。
class Solution:
def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
if root is None or root.left is None and root.right is None:
return root
newroot = self.upsideDownBinaryTree(root.left)
root.left.left = root.right
root.left.right = root
root.left = None
root.right = None
return newroot
