LeetCode 课程 Task03 学习打卡（2021年11月18日~11月21日）

LeetCode 课程 Task03 学习打卡（2021年11月18日~11月21日）

第 04 天题目

剑指 Offer 45. 把数组排成最小的数

标签：贪心、字符串、排序难度：中等

题目大意

给定一个非负整数数组 ​​nums​​。

要求：将数组中的数字拼接起来排成一个数，打印能拼接出的所有数字中的最小的一个。

解题思路

本质上是给数组进行排序。假设 ​​x​​​、​​y​​​ 是数组 ​​nums​​​ 中的两个元素。如果拼接字符串 ​​x + y > y + x​​​，则 ​​x < y​​​。​​x​​​ 应该排在 ​​y​​​ 前面。反之，则 ​​x > y​​。

按照上述规则，对原数组进行排序。这里使用了 ​​functools.cmp_to_key​​ 自定义排序函数。

代码

import functoolsclass Solution: def minNumber(self, nums: List[int]) -> str: def cmp(a, b): if a + b == b + a: return 0 elif a + b > b + a: return 1 else: return -1 nums_s = list(map(str, nums)) nums_s.sort(key=functools.cmp_to_key(cmp)) return ''.join(nums_s)

0283. 移动零

标签：数组、双指针难度：简单

题目大意

给你一个数组，将所有 0 移动到末尾，并保持原有的非 0 数字的相对顺序。要求只能在原数组上进行操作。

解题思路

使用两个指针 left，right。left 指向处理好的非 0 数字数组的尾部，right 指针指向当前待处理元素。

不断向右移动 right 指针，每次移动到非零数，则将左右指针对应的数交换，交换同时将 left 右移。

此时，left 指针左边均为处理好的非零数，而从 left 指针指向的位置开始， right 指针左边都为 0。

遍历结束之后，则所有 0 都移动到了右侧，且保持了非零数的相对位置。

代码

class Solution: def moveZeroes(self, nums: List[int]) -> None: left = 0 right = 0 while right < len(nums): if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1 right += 1

0912. 排序数组

标签：数组、分治、桶排序、计数排序、基数排序、排序、堆（优先队列）难度：中等

题目大意

给你一个整数数组 ​​nums​​。

要求：将该数组升序排列。

解题思路

这道题是一道用来复习排序算法，测试算法时间复杂度的好题。我试过了十种排序算法。得到了如下结论：

下面给出这十种排序算法相关的代码。

代码

1. 冒泡排序

class Solution: def bubbleSort(self, arr): for i in range(len(arr)): for j in range(len(arr) - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr def sortArray(self, nums: List[int]) -> List[int]: return self.bubbleSort(nums)

2. 选择排序

class Solution: def selectionSort(self, arr): for i in range(len(arr) - 1): # 记录未排序序列中最小数的索引 min_i = i for j in range(i + 1, len(arr)): if arr[j] < arr[min_i]: min_i = j # 如果找到最小数，将 i 位置上元素与最小数位置上元素进行交换 if i != min_i: arr[i], arr[min_i] = arr[min_i], arr[i] return arr def sortArray(self, nums: List[int]) -> List[int]: return self.selectionSort(nums)

3. 插入排序

class Solution: def insertionSort(self, arr): for i in range(1, len(arr)): temp = arr[i] j = i while j > 0 and arr[j - 1] > temp: arr[j] = arr[j - 1] j -= 1 arr[j] = temp return arr def sortArray(self, nums: List[int]) -> List[int]: return self.insertionSort(nums)

4. 希尔排序

class Solution: def shellSort(self, arr): size = len(arr) gap = size // 2 while gap > 0: for i in range(gap, size): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp gap = gap // 2 return arr def sortArray(self, nums: List[int]) -> List[int]: return self.shellSort(nums)

5. 归并排序

class Solution: def merge(self, left_arr, right_arr): arr = [] while left_arr and right_arr: if left_arr[0] <= right_arr[0]: arr.append(left_arr.pop(0)) else: arr.append(right_arr.pop(0)) while left_arr: arr.append(left_arr.pop(0)) while right_arr: arr.append(right_arr.pop(0)) return arr def mergeSort(self, arr): size = len(arr) if size < 2: return arr mid = len(arr) // 2 left_arr, right_arr = arr[0: mid], arr[mid:] return self.merge(self.mergeSort(left_arr), self.mergeSort(right_arr)) def sortArray(self, nums: List[int]) -> List[int]: return self.mergeSort(nums)

6. 快速排序

import random class Solution: def randomPartition(self, arr, low, high): i = random.randint(low, high) arr[i], arr[high] = arr[high], arr[i] return self.partition(arr, low, high) def partition(self, arr, low, high): x = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= arr[high]: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 def quickDivideSort(self, arr, low, high): n = len(arr) if low < high: pi = self.randomPartition(arr, low, high) self.quickDivideSort(arr, low, pi - 1) self.quickDivideSort(arr, pi + 1, high) return arr def quickSort(self, arr): low, high = 0, len(arr) - 1 return self.quickDivideSort(arr, low, high)

7. 堆排序

class Solution: # 调整为大顶堆 def heapify(self, arr, index, end): left = index * 2 + 1 right = left + 1 while left <= end: # 当前节点为非叶子结点 max_index = index if arr[left] > arr[max_index]: max_index = left if right <= end and arr[right] > arr[max_index]: max_index = right if index == max_index: # 如果不用交换，则说明已经交换结束 break arr[index], arr[max_index] = arr[max_index], arr[index] # 继续调整子树 index = max_index left = index * 2 + 1 right = left + 1 # 初始化大顶堆 def buildMaxHeap(self, arr): size = len(arr) # (size-2) // 2 是最后一个非叶节点，叶节点不用调整 for i in range((size - 2) // 2, -1, -1): self.heapify(arr, i, size - 1) return arr # 升序堆排序，思路如下： # 1. 先建立大顶堆 # 2. 让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值 # 3. 再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值 # 4. 以此类推，直到最后一个元素交换之后完毕。 def maxHeapSort(self, arr): self.buildMaxHeap(arr) size = len(arr) for i in range(size): arr[0], arr[size-i-1] = arr[size-i-1], arr[0] self.heapify(arr, 0, size-i-2) return arr def sortArray(self, nums: List[int]) -> List[int]: return self.maxHeapSort(nums)

8. 计数排序

class Solution: def countingSort(self, arr): arr_min, arr_max = min(arr), max(arr) size = arr_max - arr_min + 1 counts = [0 for _ in range(size)] for num in arr: counts[num - arr_min] += 1 for j in range(1, size): counts[j] += counts[j - 1] res = [0 for _ in range(len(arr))] for i in range(len(arr) - 1, -1, -1): res[counts[arr[i] - arr_min] - 1] = arr[i] counts[arr[i] - arr_min] -= 1 return res def sortArray(self, nums: List[int]) -> List[int]: return self.countingSort(nums)

9. 桶排序

class Solution: def insertionSort(self, arr): for i in range(1, len(arr)): temp = arr[i] j = i while j > 0 and arr[j - 1] > temp: arr[j] = arr[j - 1] j -= 1 arr[j] = temp return arr def bucketSort(self, arr, bucket_size = 5): arr_min, arr_max = min(arr), max(arr) bucket_count = (arr_max - arr_min) // bucket_size + 1 buckets = [[] for _ in range(bucket_count)] for num in arr: buckets[(num - arr_min) // bucket_size].append(num) res = [] for bucket in buckets: self.insertionSort(bucket) res.extend(bucket) return res def sortArray(self, nums: List[int]) -> List[int]: return self.bucketSort(nums)

10. 基数排序

class Solution: def radixSort(self, arr): size = len(str(max(arr))) for i in range(size): buckets = [[] for _ in range(10)] for num in arr: buckets[num // (10**i) % 10].append(num) arr.clear() for bucket in buckets: for num in bucket: arr.append(num) return arr def sortArray(self, nums: List[int]) -> List[int]: return self.radixSort(nums)

第 05 天题目

0506. 相对名次

标签：数组、排序、堆（优先队列）难度：简单

题目大意

给出 ​​n​​​ 名运动员的成绩，用数组 ​​score​​ 表示。

要求：找出他们的相对名次，并授予前三名对应的奖牌。前三名运动员将会被分别授予「金牌」，「银牌」和「铜牌」（​​Gold Medal​​​, ​​Silver Medal​​​, ​​Bronze Medal​​）。

解题思路

先对数组 ​​score​​​ 进行排序，再将对应前三个位置上的元素替换成对应的字符串：​​Gold Medal​​​, ​​Silver Medal​​​, ​​Bronze Medal​​。

代码

class Solution: def shellSort(self, arr): size = len(arr) gap = size // 2 while gap > 0: for i in range(gap, size): temp = arr[i] j = i while j >= gap and arr[j - gap] < temp: arr[j] = arr[j - gap] j -= gap arr[j] = temp gap = gap // 2 return arr def findRelativeRanks(self, score: List[int]) -> List[str]: nums = score.copy() nums = self.shellSort(nums) score_map = dict() for i in range(len(nums)): score_map[nums[i]] = i + 1 res = [] for i in range(len(score)): if score[i] == nums[0]: res.append("Gold Medal") elif score[i] == nums[1]: res.append("Silver Medal") elif score[i] == nums[2]: res.append("Bronze Medal") else: res.append(str(score_map[score[i]])) return res

面试题 10.01. 合并排序的数组

标签：数组、双指针、排序难度：简单

题目大意

给定两个排序后的数组 ​​A​​​ 和 ​​B​​​，以及 ​​A​​​ 的元素数量 ​​m​​​ 和 ​​B​​​ 的元素数量 ​​n​​​。 ​​A​​​ 的末端有足够的缓冲空间容纳 ​​B​​​。 要求：编写一个方法，将 ​​​B​​​ 合并入 ​​A​​ 并排序。

解题思路

双指针，归并排序。

使用两个指针分别表示​​A​​​、​​B​​​ 正在处理的元素下标。对 ​​A​​​、​​B​​​ 进行归并操作，将结果存入新数组中。归并之后，再将所有元素赋值到数组 ​​A​​ 中。

代码

class Solution: def merge(self, A: List[int], m: int, B: List[int], n: int) -> None: """ Do not return anything, modify A in-place instead. """ arr = [] index_A, index_B = 0, 0 while index_A < m and index_B < n: if A[index_A] <= B[index_B]: arr.append(A[index_A]) index_A += 1 else: arr.append(B[index_B]) index_B += 1 while index_A < m: arr.append(A[index_A]) index_A += 1 while index_B < n: arr.append(B[index_B]) index_B += 1 for i in range(m + n): A[i] = arr[i]

剑指 Offer 51. 数组中的逆序对

标签：树状数组、线段树、数组、二分查找、分治、有序集合、归并排序难度：困难

题目大意

给定一个数组 ​​nums​​。

要求：计算出数组中的逆序对的总数。

解题思路

可以用树状数组解决。

数组 ​​tree[i]​​​ 表示数字 ​​i​​​ 是否在序列中出现过，如果数字 ​​i​​​ 已经存在于序列中，​​tree[i] = 1​​​，否则 ​​tree[i] = 0​​​。按序列从左到右将值为 ​​nums[i]​​​ 的元素当作下标为​​nums[i]​​​，赋值为 ​​1​​​ 插入树状数组里，这时，比 ​​nums[i]​​​ 大的数个数就是 ​​i + 1 - query(a)​​。将全部结果累加起来就是逆序数了。

代码

import bisectclass BinaryIndexTree: def __init__(self, n): self.size = n self.tree = [0 for _ in range(n + 1)] def lowbit(self, index): return index & (-index) def update(self, index, delta): while index <= self.size: self.tree[index] += delta index += self.lowbit(index) def query(self, index): res = 0 while index > 0: res += self.tree[index] index -= self.lowbit(index) return resclass Solution: def reversePairs(self, nums: List[int]) -> int: size = len(nums) sort_nums = sorted(nums) for i in range(size): nums[i] = bisect.bisect_left(sort_nums, nums[i]) + 1 bit = BinaryIndexTree(size) ans = 0 for i in range(size): bit.update(nums[i], 1) ans += (i + 1 - bit.query(nums[i])) return ans

第 06 天题目

0075. 颜色分类

标签：数组、排序、双指针难度：中等

题目大意

给定一个数组 nums，元素值只有 0、1、2，分别代表红色、白色、蓝色。将数组进行排序，使得 红色在前，白色在中间，蓝色在最后。

要求不使用标准库函数，同时仅用常数空间，一趟扫描解决。

解题思路

使用两个指针 left，right，分别指向数组的头尾。left 表示当前处理好红色元素的尾部，right 表示当前处理好蓝色的头部。

再使用一个下标 index 遍历数组，如果遇到 nums[index] == 0，就交换 nums[index] 和 nums[left]，同时将 left 右移。如果遇到 nums[index] == 2，就交换 nums[index] 和 nums[right]，同时将 right 左移。

直到 index 移动到 right 位置之后，停止遍历。遍历结束之后，此时 left 左侧都是红色，right 右侧都是蓝色。

注意：移动的时候需要判断 index 和 left 的位置，因为 left 左侧是已经处理好的数组，所以需要判断 index 的位置是否小于 left，小于的话，需要更新 index 位置。

代码

class Solution: def sortColors(self, nums: List[int]) -> None: left = 0 right = len(nums) - 1 index = 0 while index <= right: if index < left: index += 1 elif nums[index] == 0: nums[index], nums[left] = nums[left], nums[index] left += 1 elif nums[index] == 2: nums[index], nums[right] = nums[right], nums[index] right -= 1 else: index += 1

0215. 数组中的第K个最大元素

标签：数组、堆排序难度：中等

题目大意

给定一个未排序的数组 nums，从中找到第 k 个最大的元素。

解题思路

很不错的一道题，面试常考。

直接可以想到的思路是：排序后输出数组上对应第 k 位大的数。所以问题关键在于排序方法的复杂度。

可考虑堆排序、归并排序、快速排序。

这道题的要求是找到第 k 大的元素，使用归并排序只有到最后排序完毕才能返回第 k 大的数。而堆排序每次排序之后，就会确定一个元素的准确排名，同理快速排序也是如此。

1. 堆排序

升序堆排序的思路如下：

先建立大顶堆让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值以此类推，直到最后一个元素交换之后完毕。

这道题我们只需进行 1 次建立大顶堆， k-1 次调整即可得到第 k 大的数。

2. 快速排序

快速排序每次调整，都会确定一个元素的最终位置，且以该元素为界限，将数组分成了两个数组，前一个数组元素都比该元素小，后一个元素都比该元素大。

这样，只要某次划分的元素恰好是第 k 个下标就找到了答案。并且我们只需关注 k 元素所在区间的排序情况，与 k 元素无关的区间排序都可以忽略。这样进一步减少了执行步骤。

3. 借用标准库（不建议）

提交代码中的最快代码是调用了 Python 的 heapq 库，或者 sort 方法。 这样的确可以通过，但是不建议这样做。借用标准库实现，只能说对这个库的 API 和相关数据结构的用途相对熟悉，而不代表着掌握了这个数据结构。可以问问自己，如果换一种语言，自己还能不能实现对应的数据结构？刷题的本质目的是为了把算法学会学透，而不仅仅是调 API。

代码

堆排序

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # 调整为大顶堆 def heapify(nums, index, end): left = index * 2 + 1 right = left + 1 while left <= end: # 当前节点为非叶子节点 max_index = index if nums[left] > nums[max_index]: max_index = left if right <= end and nums[right] > nums[max_index]: max_index = right if index == max_index: # 如果不用交换，则说明已经交换结束 break nums[index], nums[max_index] = nums[max_index], nums[index] # 继续调整子树 index = max_index left = index * 2 + 1 right = left + 1 # 初始化大顶堆 def buildMaxHeap(nums): size = len(nums) # (size-2) // 2 是最后一个非叶节点，叶节点不用调整 for i in range((size - 2) // 2, -1, -1): heapify(nums, i, size - 1) return nums buildMaxHeap(nums) size = len(nums) for i in range(k-1): nums[0], nums[size-i-1] = nums[size-i-1], nums[0] heapify(nums, 0, size-i-2) return nums[0]

快速排序

import randomclass Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def randomPartition(nums, low, high): i = random.randint(low, high) nums[i], nums[high] = nums[high], nums[i] return partition(nums, low, high) def partition(nums, low, high): x = nums[high] i = low-1 for j in range(low, high): if nums[j] <= nums[high]: i += 1 nums[i], nums[j] = nums[j], nums[i] nums[i+1], nums[high] = nums[high], nums[i+1] return i+1 def quickSort(nums, low, high, k): n = len(nums) if low < high: pi = randomPartition(nums, low, high) if pi == n-k: return nums[len(nums)-k] if pi > n-k: quickSort(nums, low, pi-1, k) if pi < n-k: quickSort(nums, pi+1, high, k) return nums[len(nums)-k] return quickSort(nums, 0, len(nums)-1, k)

借用标准库

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: nums.sort() return nums[len(nums)-k]

import heapqclass Solution: def findKthLargest(self, nums: List[int], k: int) -> int: res = [] for n in nums: if len(res) < k: heapq.heappush(res, n) elif n > res[0]: heapq.heappop(res) heapq.heappush(res, n) return heapq.heappop(res)

剑指 Offer 40. 最小的k个数

标签：数组、分治、快速选择、排序、堆（优先队列）难度：简单

题目大意

给定整数数组 ​​arr​​​，再给定一个整数 ​​k​​。

要求：返回数组 ​​arr​​​ 中最小的 ​​k​​ 个数。

解题思路

直接可以想到的思路是：排序后输出数组上对应的最小的 k 个数。所以问题关键在于排序方法的复杂度。

可考虑堆排序、归并排序、快速排序。本题使用堆排序。具体做法如下：

利用数组前​​k​​​ 个元素，建立大小为​​k​​ 的大顶堆。遍历数组​​[k, size - 1]​​ 的元素，判断其与堆顶元素关系，如果比堆顶元素小，则将其赋值给堆顶元素，再对大顶堆进行调整。最后输出前调整过后的大顶堆的前​​k​​ 个元素。

代码

class Solution: def heapify(self, nums: [int], index: int, end: int): left = index * 2 + 1 right = left + 1 while left <= end: # 当前节点为非叶子节点 max_index = index if nums[left] > nums[max_index]: max_index = left if right <= end and nums[right] > nums[max_index]: max_index = right if index == max_index: # 如果不用交换，则说明已经交换结束 break nums[index], nums[max_index] = nums[max_index], nums[index] # 继续调整子树 index = max_index left = index * 2 + 1 right = left + 1 # 初始化大顶堆 def buildMaxHeap(self, nums: [int], k: int): # (k-2) // 2 是最后一个非叶节点，叶节点不用调整 for i in range((k - 2) // 2, -1, -1): self.heapify(nums, i, k - 1) return nums def getLeastNumbers(self, arr: List[int], k: int) -> List[int]: size = len(arr) if k <= 0 or not arr: return [] if size <= k: return arr self.buildMaxHeap(arr, k) for i in range(k, size): if arr[i] < arr[0]: arr[i], arr[0] = arr[0], arr[i] self.heapify(arr, 0, k - 1) return arr[:k]

第 07 天题目

​​1122. 数组的相对排序​​

标签：数组、哈希表、计数排序、排序难度：简单

题目大意

给定两个数组，​​arr1​​​ 和 ​​arr2​​​，其中 ​​arr2​​​ 中的元素各不相同，​​arr2​​​ 中的每个元素都出现在 ​​arr1​​ 中。

要求：对 ​​arr1​​​ 中的元素进行排序，使 ​​arr1​​​ 中项的相对顺序和 ​​arr2​​​ 中的相对顺序相同。未在 ​​arr2​​​ 中出现过的元素需要按照升序放在 ​​arr1​​ 的末尾。

注意：

​​1 <= arr1.length, arr2.length <= 1000​​。​​0 <= arr1[i], arr2[i] <= 1000​​。

解题思路

因为元素值范围在 ​​[0, 1000]​​，所以可以使用计数排序的思路来解题。

使用数组 ​​count​​​ 统计 ​​arr1​​ 各个元素个数。

遍历 ​​arr2​​​ 数组，将对应元素​​num2​​​ 按照个数 ​​count[num2]​​​ 添加到答案数组 ​​ans​​​ 中，同时在 ​​count​​ 数组中减去对应个数。

然后在处理 ​​count​​​ 中剩余元素，将 ​​count​​​ 中大于 ​​0​​​ 的元素下标依次添加到答案数组 ​​ans​​ 中。

代码

class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: count = [0 for _ in range(1010)] for num1 in arr1: count[num1] += 1 res = [] for num2 in arr2: while count[num2] > 0: res.append(num2) count[num2] -= 1 for num in range(len(count)): while count[num] > 0: res.append(num) count[num] -= 1 return res

​​0908. 最小差值 I​​

标签：数组、数学难度：简单

题目大意

给你一个整数数组 ​​nums​​​，和一个整数 ​​k​​​。给数组中的每个元素 ​​nums[i]​​​ 都加上一个任意数字 ​​x​​​ （​​-k <= x <= k​​​），从而得到一个新数组 ​​result​​。

要求：返回数组 ​​result​​ 的最大值和最小值之间可能存在的最小差值。

解题思路

​​nums​​​ 中的每个元素可以波动 ​​[-k, k]​​​。最小的差值就是「最大值 - k」和「最小值 + k」的差值。而如果差值小于 ​​0​​​，则说明每个数字都可以波动成相等的数字，此时直接返回 ​​0​​ 即可。

代码

class Solution: def smallestRangeI(self, nums: List[int], k: int) -> int: return max(0, max(nums) - min(nums) - 2*k)

​​0164. 最大间距​​

标签：数组、桶排序、基数排序、排序难度：困难

题目大意

给定一个无序数组 ​​nums​​。

要求：找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 ​​2​​​，则返回 ​​0​​。

注意：

所有元素都是非负整数，且数值在 32 位有符号整数范围内。请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

解题思路

这道题分为两步：

数组排序。计算相邻元素之间的差值。

遍历数组元素，获取数组最大值元素，并取得位数。以个位元素为索引，对数组元素排序。合并数组。之后依次以十位，百位，…，直到最大值元素的最高位处值为索引，进行排序，并合并数组，最终完成排序。

最后，还要注意数组元素个数小于 2 的情况需要特别判断一下。

代码

class Solution: def radixSort(self, arr): size = len(str(max(arr))) for i in range(size): buckets = [[] for _ in range(10)] for num in arr: buckets[num // (10 ** i) % 10].append(num) arr.clear() for bucket in buckets: for num in bucket: arr.append(num) return arr def maximumGap(self, nums: List[int]) -> int: if len(nums) < 2: return 0 arr = self.radixSort(nums) return max(arr[i] - arr[i-1] for i in range(1, len(arr)))

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。