子序列首尾元素的最大乘积-LeetCode
3584.子序列首尾元素的最大乘积 🎯 问题描述（来源于LeetCode） 描述： 给你一个整数数组 nums 和一个整数 m。 返回任意大小为 m 的 子序列 中首尾元素乘积的最大值。 子序列 是可以通过删除原数组中的一些元素（或不删除任何元素），且不改变剩余元素顺序而得到的数组。 说明： 1 <= nums.length <= 105 -105 <= nums[i] <= 105 1 <= m <= nums.length 示例： 示例 1： 1234输入： nums = [-1,-9,2,3,-2,-3,1], m = 1输出： 81解释：子序列[-9]的首尾元素乘积最大：-9 * -9 = 81。因此，答案是 81。 示例 2： 1234输入： nums = [1,3,-5,5,6,-4], m = 3输出： 20解释：子序列 [-5, 6, -4]的首尾元素乘积最大。 💻 解题思路 思路1：枚举右，维护左 思路1：代码实现 123456789101112class Solution: def...
必须拿起的最小连续卡牌数-LeetCode
2260. 必须拿起的最小连续卡牌数 🎯 问题描述（来源于LeetCode） 描述： 给你一个整数数组 cards，其中 cards[i] 表示第 i 张卡牌的值。 如果两张卡牌的值相同，则认为这一对卡牌是匹配的。 请你找出必须拿起的最小连续卡牌数目，使得其中包含一对匹配的卡牌。 如果无法找到匹配的一对卡牌，返回 -1。 说明： 这是一个哈希表结合贪心算法的问题。 核心逻辑是：对于每个数字，记录它最后一次出现的位置。 当再次遇到该数字时，计算当前位置与上次出现位置之间的距离，并更新最小距离。 通过一次遍历即可完成查找。 示例： 示例 1： 123456输入：cards = [3,4,2,3,4,7]输出：4解释：- 拿起 [3,4,2,3] 包含一对匹配的 3，长度为 4。- 拿起 [4,2,3,4] 包含一对匹配的 4，长度为 4。- 最小长度为 4。 示例 2： 1234输入：cards = [1,0,5,3]输出：-1解释：- 没有匹配的卡牌对。 💻 解题思路 思路1：哈希表记录最后出现位置 思路1：代码实现 123456789...
找出满足差值条件的下标II-LeetCode
2905. 找出满足差值条件的下标II 🎯 问题描述 描述： 给你一个下标从 0 开始的整数数组 nums，另给你两个整数 indexDifference 和 valueDifference。 你的任务是找出两个下标 i 和 j，使得满足以下条件： |i - j| >= indexDifference |nums[i] - nums[j]| >= valueDifference 如果存在多个满足条件的下标对，返回任意一个即可。如果不存在这样的下标对，返回 [-1, -1]。 说明： 这是一个数组遍历结合动态维护极值的问题。 核心策略：我们不需要双重循环去枚举所有 (i, j) 对。 我们可以固定右边的下标 j，然后在左边合法的范围内（即 i <= j - indexDifference）寻找最优的 i。 为了使差值 |nums[i] - nums[j]| 最大，i 对应的值应该是左边范围内的最大值或最小值。 示例： 示例 1： 1234567891011输入：nums = [5,1,4,1], indexDifference...
数组中的最大数对和-LeetCode
2815.数组中的最大数对和 🎯 问题描述 描述： 给定一个整数数组 nums，找出两个下标 i 和 j（i < j），使得 nums[i] 和 nums[j] 的最大数位相同，并且 nums[i] + nums[j] 的值最大。 如果不存在这样的数对，返回 -1。 说明： 这是对“数位和”问题的变体。 分组依据从“数位之和”变成了“数位最大值”。 例如：129 的最大数位是 9，901 的最大数位也是 9，它们可以配对。 示例： 示例 1： 12345678输入：nums = [129, 901, 55, 34]输出：1030解释：- 129 的最大数位是 9。- 901 的最大数位是 9。- 它们可以配对，和为 129 + 901 = 1030。- 55 的最大数位是 5，没有其他数最大数位是 5。- 34 的最大数位是 4，没有其他数最大数位是 4。 💻 解题思路 思路1：哈希表 + 贪心 思路1：代码实现 1234567891011121314151617181920212223class Solution: def ma...
最佳观光组合-LeetCode
1014. 最佳观光组合 🎯 问题描述 描述： 给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分。 两个景点 i 和 j（i < j）组成的观光组合的得分为： values[i]+values[j]+i−jvalues[i] + values[j] + i - j values[i]+values[j]+i−j 即：两个景点的评分之和减去它们之间的距离。 请你返回一对观光景点能取得的最高分。 说明： 这是一个线性扫描结合拆分项维护的问题。 直接暴力枚举所有 i,ji, ji,j 对需要 O(N2)O(N^2)O(N2) 时间。 核心优化逻辑：将公式拆分为 (values[i]+i)+(values[j]−j)(values[i] + i) + (values[j] - j)(values[i]+i)+(values[j]−j)。 当我们遍历到 jjj 时，只需要知道在 jjj 之前，(values[i]+i)(values[i] + i)(values[i]+i) 的最大值是多少。 示例： 示例 1： ...
统计一个数组中好对子的个数-LeetCode
1814. 统计一个数组中好对子的个数 🎯 问题描述 描述： 给你一个非负整数数组 nums。 如果满足 0 <= i < j < nums.length 且： nums[i]+rev(nums[j])==nums[j]+rev(nums[i])nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) nums[i]+rev(nums[j])==nums[j]+rev(nums[i]) 那么我们称 (i, j) 是一个好对子。 其中 rev(x) 表示将整数 x 的各位数字反转（例如 rev(123) = 321，rev(120) = 21）。 请你返回好对子的数目。由于答案可能很大，请返回它对 109+710^9 + 7109+7 取余的结果。 说明： 这是一个哈希表计数结合数学恒等变形的问题。 核心难点：直接暴力枚举所有 (i, j) 对需要 O(N2)O(N^2)O(N2) 时间，效率太低。 策略：通过移项变形，将涉及 i 和 j 的项分离，找到每个元素独立的特征值（差值），将问题转化为“寻找具有相...
统计凯撒加密对数目-LeetCode
3805. 统计凯撒加密对数目 🎯 问题描述（来源于LeetCode） 描述： 给你一个字符串数组 words，所有字符串长度相同且仅包含小写英文字母。 如果一个字符串可以通过另一个字符串进行凯撒加密（即每个字符都向后移动相同的位数，例如 ‘a’ -> ‘c’, ‘b’ -> ‘d’）得到，则称这两个字符串是相似的。 请你返回 words 中相似字符串对的数量。 说明： 这是一个哈希表计数结合差分特征提取的问题。 核心洞察：如果字符串 AAA 和 BBB 是凯撒加密关系（即 B[i]=A[i]+kB[i] = A[i] + kB[i]=A[i]+k），那么它们相邻字符之间的差值是恒定不变的。 B[i]−B[i−1]=(A[i]+k)−(A[i−1]+k)=A[i]−A[i−1]B[i] - B[i-1] = (A[i] + k) - (A[i-1] + k) = A[i] - A[i-1]B[i]−B[i−1]=(A[i]+k)−(A[i−1]+k)=A[i]−A[i−1]。 因此，我们可以将每个字符串转换为其“差分序列”作为特征指纹。指纹相同的...
统计坏数对的数目-LeetCode
2364. 统计坏数对数目 🎯 问题描述（来源于LeetCode） 描述： 给你一个下标从 0 开始的整数数组 nums。 如果 i < j 且 j - i != nums[j] - nums[i]，那么我们称 (i, j) 是一个坏数对。 请你返回 nums 中坏数对的总数目。 说明： 这是一个哈希表计数结合补集思想的问题。 直接思考：判断 j - i != nums[j] - nums[i] 比较麻烦。 转换思考： 不等式 j - i != nums[j] - nums[i] 等价于 nums[i] - i != nums[j] - j。 反之，好数对满足 j - i == nums[j] - nums[i]，即 nums[i] - i == nums[j] - j。 策略： 计算所有可能的数对总数 TotalTotalTotal。 计算满足 nums[i] - i == nums[j] - j 的好数对数量 GoodGoodGood。 答案即为 Total−GoodTotal - GoodTotal−Good。 示例： 示例 1：...
统计梯形的数目I-LeetCode
3623.统计梯形的数目I 🎯 问题描述 描述： 给定平面上的 NNN 个点 points，其中 points[i] = [x_i, y_i]。 请你统计这些点能组成多少个梯形。 梯形的定义是：至少有一组对边平行，且另一组对边不平行（或者简单定义为有一组对边平行）。 在本题的特定语境下（基于代码逻辑推断），通常指上下底平行于 x 轴的梯形。 即：我们需要选择两条不同的水平线（y 坐标不同），每条线上至少选两个点，从而构成一个梯形。 说明： 这是一个组合数学结合哈希表计数的问题。 核心逻辑是：梯形由两条平行的底边组成。 如果一条水平线上有 kkk 个点，那么这条线上可以形成 Ck2=k(k−1)2C_k^2 = \frac{k(k-1)}{2}Ck2=2k(k−1) 条线段。 任意两条不同高度的线段都可以组成一个梯形。 利用前缀和思想优化计算过程。 示例： 示例 1： 123456输入：points = [[0,0],[1,0],[0,1],[1,1],[2,1]]输出：3解释：- y=0 的线有 2 个点：[0,0], [1,0] -&g...
统计特殊三元组-LeetCode
3583.统计特殊三元组 🎯 问题描述 描述： 给你一个整数数组 nums。 如果三元组 (i, j, k) 满足以下条件，我们称之为特殊三元组： 0 <= i < j < k < n nums[i] == 2 * nums[j] nums[k] == 2 * nums[j] 换句话说，中间元素 nums[j] 的两倍必须等于左边元素 nums[i] 和右边元素 nums[k]。 请你返回特殊三元组的数目。由于答案可能很大，请返回它对 109+710^9 + 7109+7 取余的结果。 说明： 这是一个枚举中间点结合**动态计数（滑动窗口）**的问题。 核心策略：固定中间下标 j，我们需要快速知道 j 左侧有多少个 2 * nums[j]，以及 j 右侧有多少个 2 * nums[j]。 优化点：不需要每次都重新遍历左右子数组。随着 j 向右移动，我们只需要将元素从“右侧计数器”移动到“左侧计数器”即可。 示例： 示例 1： 1234567891011输入：nums = [2, 1, 4, 1, 2]输出：4解释：- 目标...
