笺札

数组拆分 🎯 问题描述（来源于LeetCode） 描述： 给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。 返回该 最大总和 。 说明： 1 <= n <= 104 nums.length == 2 * n -104 <= nums[i] <= 104 示例： 示例 1： 1234567输入：nums = [1,4,3,2]输出：4解释：所有可能的分法（忽略元素顺序）为：1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 32. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 33. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4所以最大总和为 4 示例 2： 123输入：nums = [6...

桶排序 基本概念 桶排序（Bucket Sort）： 将待排序元素分散到多个桶中，对每个桶单独排序后合并。 算法步骤 确定桶的数量：根据待排序数组的数值范围，将其划分为 k 个桶，每个桶对应一个特定的区间。 元素分配：遍历数组，将每个元素根据其数值映射到所属的桶中。 桶内排序：对每个非空桶分别进行排序（可选用插入排序、归并排序、快速排序等算法）。 合并结果：按桶的顺序依次合并所有已排序的桶，得到最终有序数组。 内部实现： 1234567891011121314151617181920212223class Solution: def insertionSort(self,nums:[int])->[int]: for i in range(1,len(nums)): temp = nums[i] j=i while j>0 and nums[j-1]>temp: nums[j]=nums[j-1] j-=1 nums[j]=temp return nums def bucketSort(self,nums:[int],...

存在重复元素III 🎯 问题描述（来源于LeetCode） 描述： 给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。 找出满足下述条件的下标对 (i, j)： i != j, abs(i - j) <= indexDiff abs(nums[i] - nums[j]) <= valueDiff 如果存在，返回 true _；_否则，返回 false 。 说明： 2 <= nums.length <= 105 -109 <= nums[i] <= 109 1 <= indexDiff <= nums.length 0 <= valueDiff <= 109 示例： 示例 1： 1234567输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0输出：true解释：可以找出 (i, j) = (0, 3) 。满足下述 3 个条件：i != j --> 0 != 3abs(i - j) <= indexDiff --&g...

最大间距 🎯 问题描述（来源于LeetCode） 描述： 给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。 说明： 1 <= nums.length <= 105 0 <= nums[i] <= 109 示例： 示例 1： 123输入:nums = [3,6,9,1]输出: 3解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 示例 2： 123输入: nums = [10]输出: 0解释: 数组元素个数小于 2，因此返回 0。 💻 解题思路 思路1：桶排序 思路1：代码实现 12345678910111213141516171819202122232425262728293031323334353637383940class Solution: def maximumGap(self, nums: List[int]) ->...

计数排序 基本概念 计数排序（Counting Sort）基本思想： 统计数组中每个元素出现的次数，然后根据统计信息将元素按顺序放置到正确位置，实现排序。 算法步骤： 确定数值范围：找出数组中的最大值和最小值，计算数值范围。 创建计数数组：创建一个大小为数值范围的数组，用于统计每个元素出现的次数。 统计元素频次：遍历原数组，统计每个元素出现的次数。 计算累积频次：将计数数组转换为累积频次数组，表示每个元素在排序后数组中的位置。 逆序填充结果：逆序遍历原数组，根据累积频次将元素放入正确位置。 内部实现： 12345678910111213141516171819202122class Solution: def countingSort(self,nums;[int])->[int]: nums_min,nums_max=min(nums),max(nums) #1. 确定数值范围 size = nums_max-nums_min+1 #2. 创建计数数组 counts=[0 for _ in range(size)] #3. 统计元素频次 for ...

数组的相对排序 🎯 问题描述（来源于LeetCode） 描述： 给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。 说明： 1 <= arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 arr2 中的元素 arr2[i]  各不相同 arr2 中的每个元素 arr2[i] 都出现在 arr1 中 示例： 示例 1： 12输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]输出：[2,2,2,1,4,3,3,9,6,7,19] 示例 2： 12输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]输出：[22,28,8,6,17,44]...

选择排序 基本概念 选择排序（Selection Sort）基本思想： 将数组分为两个区间：左侧为已排序区间，右侧为未排序区间。每趟从未排序区间中选择最小的元素，放到已排序区间的末尾。 算法步骤 假设数组长度为n，选择排序的算法步骤如下： 初始状态：已排序区间为空，未排序区间为[0,n−1][0,n−1][0,n−1]。 第i趟选择（i从1开始）： 在未排序区间 [i−1,n−1][i−1,n−1][i−1,n−1]中找到最小元素的位置 minimin_imini​。 将位置i−1的元素与位置minimin_imini​的元素交换。 此时[0,i−1][0,i−1][0,i−1]为已排序区间，[i,n−1][i,n−1][i,n−1]为未排序区间。 重复步骤 2，直到未排序区间为空，排序完成。 内部实现： 1234567891011121314class Solution: def selectionSort(self,nums:[int])->[int]: n=len(nums) for i in range(n-1): min_i=i fo...

插入排序 基本概念 插入排序（Insertion Sort）基本思想： 将数组分为有序区间和无序区间，每次从无序区间取出一个元素插入到有序区间的正确位置。 算法步骤 假设数组长度为 n，算法步骤如下： 初始化：有序区间为 [0,0][0,0][0,0]，无序区间为 [1,n−1][1,n−1][1,n−1] 第i趟插入（i 从 11 到 n−1）： 取出无序区间第一个元素 nums[i]nums[i]nums[i] 从右到左遍历有序区间，将大于 nums[i]nums[i]nums[i]的元素右移一位 找到合适位置后插入 nums[i]nums[i]nums[i] 有序区间扩展为 [0,i][0,i][0,i]，无序区间变为[i+1,n−1][i+1,n−1][i+1,n−1] 内部实现： 123456789101112class Solution: def insertionSort(self,nums:[int])->[int]: for i in range(i,len(nums)): temp=nums[i] j=i while j&...

堆 基本概念 堆（Heap）：一种特殊的完全二叉树，具有以下性质之一： 大顶堆（Max Heap）：任意节点值 ≥ 其子节点值 小顶堆（Min Heap）：任意节点值 ≤ 其子节点值 数据结构的三要素 逻辑结构 树形结构 存储结构 顺序存储 父节点索引：(i - 1) // 2 左子节点：2*i + 1 右子节点：2*i + 2 数据的运算 费曼理解 堆就像是一个按优先级排队的队伍，队首总是优先级最高（最大或最小）的元素，你随时可以拿走它，也可以插入新人，队伍会自动调整顺序。 内部实现： python 创建空堆 123class MaxHeap: def _int_(self): self.max_heap=[] 访问堆顶元素 1234def peek(self)-> int: if not self.max_heap: return None return self.max_heap[0] 向堆种插入元素 向堆中插入元素需要两个步骤： 添加元素：将新元素添加到堆的末尾，保持完全二叉树的结构 上移调整：从新元素开始向上调整，...

堆排序 基本概念 堆排序（Heap sort）基本思想： 利用堆的特性，将数组构建成大顶堆，然后重复取出堆顶元素（最大值）并调整堆结构，最终得到有序数组。 算法步骤 堆排序分为两个主要阶段： 第一阶段：构建初始大顶堆 将原始数组视为完全二叉树 从最后一个非叶子节点开始，自底向上进行下移调整 将数组转换为大顶堆 第二阶段：重复提取最大值 交换堆顶元素与当前末尾元素 堆长度减 1，末尾元素已排好序 对新的堆顶元素进行下移调整，恢复堆的性质 重复步骤 1∼3，直到堆的大小为 1 内部实现： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class MaxHeap: def __init__(self): self.max_heap = [] def __buildMaxHeap(self, nums: [int]): # 将数组元素复制到堆中 self.max...