笺札

冒泡排序 基本概念 冒泡排序（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_...

数组种的第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，并将对应指针后移一位。 重复上述操作，直到某一指针到达对应子数组末尾。 ...

希尔排序 基本概念 希尔排序（Shell Sort）基本思想： 通过设定不同的间隔（gap），将数组分组进行插入排序，然后逐步缩小间隔直至为 11，最终完成整个数组的排序。 算法实现步骤 假设数组长度为 n，算法步骤如下： 设定初始间隔 gap = n / 2。 按间隔将数组分组，对每组进行插入排序。 缩小间隔 gap = gap / 2。 重复步骤 2∼3，直到 gap = 1。 最后对整个数组进行一次插入排序。 费曼理解 内部实现： 12345678910111213141516class solution: def shellsort(self,nums:[int])->[int]: size=len(nums) gap=size//2 while gap>0: for i in range(gap,size): temp=nums[i] j=i while j>=gap and nums[j-gap]>temp: nums[j]=nums[j-gap] j-=gap nums[j]=t...

多数元素 🎯 问题描述（来源于LeetCode） 描述： 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 说明： n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109 输入保证数组中一定有一个多数元素。 示例： 示例 1： 12输入：nums = [3,2,3]输出：3 示例 2： 12输入：nums = [2,2,1,1,1,2,2]输出：2 💻 解题思路 思路1：快速排序 思路1：代码实现 1234class Solution: def majorityElement(self, nums: List[int]) -> int: nums.sort() return nums[len(nums)//2] 思路1：📊 性能分析 提交结果 运行时间：0ms击败100.00% 内存消耗：19.1...

计算右侧小于当前元素的个数 🎯 问题描述（来源于LeetCode） 描述： 给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。 说明： 1 <= nums.length <= 105 -104 <= nums[i] <= 104 示例： 示例 1： 1234567输入：nums = [5,2,6,1]输出：[2,1,1,0] 解释：5 的右侧有 2 个更小的元素 (2 和 1)2 的右侧仅有 1 个更小的元素 (1)6 的右侧有1个更小的元素 (1)1 的右侧有0个更小的元素 示例 2： 12输入：nums = [-1]输出：[0] 💻 解题思路 思路1：在归并过程中计数 思路1：代码实现 1234567891011121314151617181920212223242526272829303132333435class Solution: def countSmaller(sel...