笺札

选择排序 基本概念 选择排序（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...

冒泡排序 基本概念 冒泡排序（Bubble Sort）基本思想： 通过相邻元素的比较与交换，将较大的元素逐步「冒泡」到数组末尾，较小的元素自然「下沉」到数组开头。 算法步骤 对于长度为 n 的数组，冒泡排序的步骤如下： 第1趟冒泡：对前n个元素依次比较相邻元素，将较大的元素向右交换，最终使最大值移动到数组末尾（第n个位置）。 比较第1个和第2个元素，如果前者大于后者则交换。 比较第 2 个和第 3 个元素，如果前者大于后者则交换。 以此类推，直到比较第 n−1 个和第 n 个元素。 完成后，最大元素已位于末尾。 第 2 趟冒泡：对前 n−1 个元素重复上述过程，将次大值移动到倒数第二个位置（第 n−1 个位置）。 比较第1个和第 2 个元素，如果前者大于后者则交换。 比较第 2 个和第 3 个元素，如果前者大于后者则交换。 以此类推，直到比较第 n−2 个和第 n−1 个元素。 完成后，次大元素已位于倒数第二位。 持续进行上述冒泡过程，每一趟比较的元素个数递减，直到某一趟未发生任何交换，说明数组已完全有序，排序结束。 内部实现： 1234567891011...

库存管理III 🎯 问题描述（来源于LeetCode） 描述： 仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。 说明： 0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000 示例： 示例 1： 12输入：stock = [2,5,7,4], cnt = 1输出：[2] 示例 2： 12输入：stock = [0,2,3,6], cnt = 2输出：[0,2] 或 [2,0] 💻 解题思路 思路1：最小堆排序 思路1：代码实现 1234567891011121314151617181920212223242526272829303132class Solution: def maxHeap(self,nums:[int],i:int,heap_size:int): while 1: l_i=2*i+1 ...

数组种的第k个最大元素 🎯 问题描述（来源于LeetCode） 描述： 给定整数数组 nums 和整数 k，请返回数组中第 k个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 说明： 1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104 示例： 示例 1： 12输入: [3,2,1,5,6,4], k = 2输出: 5 示例 2： 12输入:[3,2,3,1,2,4,5,5,6],k = 4输出: 4 💻 解题思路 思路1：堆排序 思路1：代码实现 1234567891011121314151617181920212223242526class Solution: def maxHeap(self,nums:[int],i:int,heap_size:int): while 1: l_i=2*i+1 r_...

链栈 基本概念 数据结构的三要素 逻辑结构 线性结构 存储结构 链式存储 数据的运算 费曼理解 12栈结构：头指针L → [栈顶节点] → [节点2] → ... → [栈底节点] → NULL 就像编绳结一样，一个节点一个结从右往左遍就得从左往右解 内部实现： 1234typedef struct Linknode{ ElemType data; struct Linknode *next;}*LiStack 复杂度分析： 初始化 1234bool InitStack(LiStack &L){ L= new Linknode; L->next=NULL;} 判断栈空 12345678bool isEmpty(LiStack &L){ if(L-next==NULL){ return true; } else{ return false; }} 入栈 1234567void Push(LiStack &L,Elem...

快速排序 基本概念 快速排序（Quick Sort）基本思想： 采用分治策略，选择一个基准元素，将数组分为两部分：小于基准的元素放在左侧，大于基准的元素放在右侧。然后递归地对左右两部分进行排序，最终得到有序数组。 算法步骤 快速排序的核心是 分区操作，具体步骤如下： 选择基准：从数组中选择一个元素作为基准值（通常选择第一个元素） 分区操作： 使用双指针法，左指针从数组开始，右指针从数组末尾 右指针向左移动，找到第一个小于基准值的元素 左指针向右移动，找到第一个大于基准值的元素 交换这两个元素 重复上述过程，直到左右指针相遇 将基准值放到正确位置（左右指针相遇处） 递归排序：对基准值左右的两个子数组分别进行快速排序 内部实现： 12345678910111213141516171819202122232425import randomclass Solution: def randomPartition(self,nums:[int],low:int,high:int)->int: i=random.randint(low,high) nums[low]...

归并排序 基本概念 归并排序（Merge Sort）基本思想： 利用分治法，将数组递归地一分为二，直至每个子数组只包含一个元素。随后，将这些有序子数组两两合并，最终得到一个整体有序的数组。 算法步骤 假设数组的元素个数为 n 个，则归并排序的算法步骤如下： 分解过程：递归地将当前数组平分为两部分，直到每个子数组只包含一个元素为止。 找到数组的中间位置 mid，将数组划分为左、右两个子数组left_nums 和 right_nums。 分别对 left_nums 和 right_numsr递归执行分解操作。 最终将原数组拆分为 n 个长度为 1 的有序子数组。 归并过程：从长度为 1 的有序子数组开始，逐步将相邻的有序子数组两两合并，最终合并为一个长度为 n 的有序数组。 新建数组 nums 用于存放合并后的有序结果。 设置两个指针 left_i 和 right_i，分别指向 left_nums 和 right_nums的起始位置。 比较两个指针所指元素，将较小者加入结果数组 numsnums，并将对应指针后移一位。 重复上述操作，直到某一指针到达对应子数组末尾。 ...