笺札

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

交易逆序对的总数 🎯 问题描述（来源于LeetCode） 描述： 在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。 说明： 0 <= record.length <= 50000 示例： 示例 1： 123输入：record = [9, 7, 5, 4, 6]输出：8解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。 💻 解题思路 思路1：暴力破解 思路1：代码实现 123456789class Solution:    def reversePairs(self, record: List[int]) -> int:        i=count=0        while i<len(record):            for d in range(i,len(record)):           ...

合并两个有序数组 🎯 问题描述（来源于LeetCode） 描述： 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 说明： nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109 示例： 示例 1： 1234输入：nums1 = [1], m = 1, nums2 = [], n = 0输出：[1]解释：需要合并 [1] 和 [] 。合并结果是 [1] 。 示例 2：...

对角线遍历 🎯 问题描述（来源于LeetCode） 描述： 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。 说明： m == mat.length n == mat[i].length 1 <= m, n <= 104 1 <= m * n <= 104 -105 <= mat[i][j] <= 105 示例： 示例 1： 12输入：mat = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,4,7,5,3,6,8,9] 示例 2： 12输入：mat = [[1,2],[3,4]]输出：[1,2,3,4] 💻 解题思路 思路1：遍历 思路1：代码实现 1234567891011121314151617181920212223242526272829303132class Solution: def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]...

排序数组 🎯 问题描述（来源于LeetCode） 描述： 给你一个整数数组 nums，请你将该数组升序排列。 你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。 说明： 1 <= nums.length <= 5 * 104 -5 * 104 <= nums[i] <= 5 * 104 示例： 示例 1： 123输入：nums = [5,2,3,1]输出：[1,2,3,5]解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。 示例 2： 123输入：nums = [5,1,1,2,0,0]输出：[0,0,1,1,2,5]解释：请注意，nums 的值不一定唯一。 💻 解题思路 思路1：希尔排序 思路1：代码实现 1234567891011121314class Solution: def sortArray(self, nums: List[int]) -> List[int]: size=l...

相对名次 🎯 问题描述（来源于LeetCode） 描述： 给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。 运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况： 名次第 1 的运动员获金牌 "Gold Medal" 。 名次第 2 的运动员获银牌 "Silver Medal" 。 名次第 3 的运动员获铜牌 "Bronze Medal" 。 从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。 使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。 说明： n == score.length 1 <= n <= 104 0 <= score[i] <= 106 score 中的所有值 互不相同 示例：...

加一 🎯 问题描述（来源于LeetCode） 描述： 给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。 将大整数加 1，并返回结果的数字数组。 说明： 1 <= digits.length <= 100 0 <= digits[i] <= 9 digits 不包含任何前导 0。 示例： 示例 1： 12345输入：digits = [1,2,3]输出：[1,2,4]解释：输入数组表示数字 123。加 1 后得到 123 + 1 = 124。因此，结果应该是 [1,2,4]。 示例 2： 12345输入：digits = [9]输出：[1,0]解释：输入数组表示数字 9。加 1 得到了 9 + 1 = 10。因此，结果应该是 [1,0]。 💻 解题思路 思路1：反向遍历 思路1：代码实现 12345678910111213141516171819class Solution: def plusO...

各赛事的注册率 🎯 问题描述（来源于LeetCode） 描述： 用户表： Users ±------------±--------+ | Column Name | Type | ±------------±--------+ | user_id | int | | user_name | varchar | ±------------±--------+ user_id 是该表的主键(具有唯一值的列)。 该表中的每行包括用户 ID 和用户名。 注册表： Register ±------------±--------+ | Column Name | Type | ±------------±--------+ | contest_id | int | | user_id | int | ±------------±--------+ (contest_id, user_id) 是该表的主键(具有唯一值的列的组合)。 该表中的每行包含用户的 ID 和他们注册的赛事。 编写解决方案统计出各赛事的用户注册百分率，保留两位...