LeetCode 周赛 339（2023/04/02）解题思路与代码实现

首先，我们来简要概述一下这周的题目：

1. 第一题是一个关于贪心算法的问题，要求我们设计一个函数来生成最小的排列。这需要我们使用贪心策略，每次选择当前未使用的最小数字。
2. 第二题是一个排序问题，要求我们对一组整数进行排序，并返回排序后的数组。这个问题可以使用各种排序算法来解决，如冒泡排序、选择排序或快速排序。
3. 第三题涉及到拓扑排序的概念，要求我们使用深度优先搜索（DFS）对有向无环图（DAG）进行拓扑排序。拓扑排序的目的是对图中的节点进行线性排序，使得对于每一条有向边 (u, v)，u 在排序中都出现在 v 之前。
4. 最后一题是关于平衡二叉树的问题，要求我们判断给定的二叉树是否是平衡的。平衡二叉树是指任意节点的左右子树的高度差不超过 1。
   接下来，我们将详细分析每道题目的解题思路和代码实现。
   第一题：贪心算法
   题目描述：给定一个由 n 个非负整数组成的数组 nums，设计一个函数来生成最小的排列。
   解题思路：我们可以使用贪心算法来解决这个问题。首先，我们需要一个辅助数组 used 来记录每个数字是否已经被使用。然后，我们从左到右遍历 nums 数组，对于每个数字 num，我们检查它是否已经被使用过（即 used[num] 为 true）。如果 num 未被使用过，我们将其添加到结果数组中，并将其标记为已使用（即 used[num] = true）。接着，我们通过将结果数组中的元素按照从小到大的顺序排列，得到最小的排列。
   代码实现：

   def minimumSwaps(nums):
   n = len(nums)
   used = [False] * (max(nums) + 1)
   result = []
   for num in nums:
   if not used[num]:
   used[num] = True
   result.append(num)
   return result[::-1]  # 反转数组以得到升序排列

   第二题：排序算法
   题目描述：给定一个包含 n 个整数的数组 nums，将其按照升序排序并返回排序后的数组。可以使用任何排序算法实现。
   解题思路：我们可以使用快速排序算法来解决这个问题。快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分继续进行排序，以达到整个序列有序。在本题中，我们可以选择第一个元素作为基准值，并将数组分为两部分：一部分是小于基准值的元素，另一部分是大于基准值的元素。然后递归地对这两部分进行快速排序。
   代码实现：

   def sortArray(nums):
   if len(nums) <= 1:
   return nums
   pivot = nums[0]
   less = [x for x in nums[1:] if x <= pivot]
   greater = [x for x in nums[1:] if x > pivot]
   return sortArray(less) + [pivot] + sortArray(greater)

   第三题：拓扑排序
   题目描述：给定一个有向无环图（DAG），使用深度优先搜索（DFS）对其进行拓扑排序。拓扑排序的输出应该是所有节点的线性序列，满足对于每一条有向边 (u, v)，u 在排序中都出现在 v 之前。如果存在多个有效的拓扑排序，你可以返回其中任意一个。
   解题思路：拓扑排序可以通过深度优先搜索来实现。首先，我们需要创建一个辅助数组 inDegree 来记录每个节点的入度。入度为 0 的节点是可访问的，我们将它们加入到结果数组中，并递归地对其邻居节点进行深度优先搜索