笺札

3446. 按对角线进行矩阵排序 🎯 问题描述 描述： 给你一个大小为 n x m 的整数矩阵 grid。 请你返回一个经过调整的矩阵，调整规则如下： 左下角三角形（包括主对角线）：该区域内的每一条对角线（从左上到右下方向）按非递增（降序）顺序排序。 右上角三角形：该区域内的每一条对角线按非递减（升序）顺序排序。 说明： 这是一个坐标变换结合分组排序的问题。 核心策略： 利用数学公式将二维坐标映射到一维对角线索引。 通过枚举对角线标识符 k 来遍历所有副对角线。 提取对角线元素 -> 排序 -> 写回矩阵。 排序规则：根据对角线起始位置动态决定排序方向。 示例： 示例 1： 12345678输入：grid = 输出：解释：- 主对角线 [1,8,6] (i-j=0)：属于左下角区域（含主对角线），降序排序 -> [8,6,1]。- 对角线 [9,5] (i-j=1)：属于左下角，降序 -> [9,5] (不变)。- 对角线 [4] (i-j=2)：属于左下角，降序 -> [4] (不变)。- 对角线 [7,2] (i-j=-1)：...

3152. 特殊数组 II 🎯 问题描述 描述： 一个数组被称为特殊数组，如果它的每一对相邻元素的奇偶性都不同（即一个是奇数，一个是偶数）。 给你一个整数数组 nums 和一个二维整数数组 queries。 对于每个查询 queries[i] = [li, ri]，你需要判断子数组 nums[li...ri] 是否是特殊数组。 返回一个布尔数组 answer，其中 answer[i] 为 true 表示该子数组是特殊的，否则为 false。 说明： 这是一个区间查询问题，核心在于判断区间内的相邻元素性质。 核心策略： 直接对每个查询遍历区间检查相邻元素会导致 O(Q⋅N)O(Q \cdot N)O(Q⋅N) 的复杂度。 我们可以定义**“坏对”：指相邻两个元素奇偶性相同**的情况。 如果一个区间内“坏对”的数量为 0，则该区间是特殊的。 利用前缀和数组统计“坏对”的数量，实现 O(1)O(1)O(1) 的查询。 示例： 示例 1： 12345678910输入：nums = [3,4,1,2,6], queries = 输出：[false]解释：- 子...

2559. 统计范围内的元音字符串数目 🎯 问题描述 描述： 给你一个下标从 0 开始的字符串数组 words 和一个二维整数数组 queries。 对于每个查询 queries[i] = [li, ri]，请计算 words 中下标在 [li, ri] 范围内（包含两端）有多少个元音字符串。 元音字符串定义： 该字符串以元音字母开头 并且 以元音字母结尾。 元音字母包括：‘a’, ‘e’, ‘i’, ‘o’, ‘u’。 说明： 这是一个前缀和的经典应用场景。 核心策略： 题目涉及多次区间求和查询。 如果直接对每个查询遍历区间，时间复杂度为 O(Q⋅N)O(Q \cdot N)O(Q⋅N)，在数据量大时会超时。 利用前缀和数组，我们可以先预处理出每个位置之前有多少个元音字符串。 查询时，利用前缀和的差值在 O(1)O(1)O(1) 时间内得到结果。 示例： 示例 1： 12345678910111213输入：words = ["aba","bcb","ece","aa"...

456. 132 模式 🎯 问题描述 描述： 给你一个整数数组 nums，数组中共有 n 个整数。 132 模式的子序列由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足： i < j < k nums[i] < nums[k] < nums[j] 如果 nums 中存在 132 模式的子序列，返回 true；否则，返回 false。 说明： 这是一个枚举中间最大值结合有序集合维护后缀的问题。 核心策略： 我们要找 nums[i]<nums[k]<nums[j]nums[i] < nums[k] < nums[j]nums[i]<nums[k]<nums[j]。 我们可以枚举中间的元素 nums[j] 作为“3”（最大值）。 左侧 (1)：为了让 nums[i]<nums[k]nums[i] < nums[k]nums[i]<nums[k] 更容易满足，对于固定的 j，我们需要知道 j 左侧的最小值 min_left。 右侧 (2)：我们需要在 j 的右侧找到...

447. 回旋镖数量 🎯 问题描述 描述： 给定平面上 n 个点，其中每个点表示为 points[i] = [xi, yi]。 回旋镖是由三个点组成的元组 (i, j, k)，其中 i、j 和 k 是不同的点，且 i 到 j 的距离与 i 到 k 的距离相等。 计算并返回回旋镖的数量。 说明： 这是一个枚举中心点 + 哈希表计数的问题 核心策略：枚举每个点作为回旋镖的中心点，统计到其他点的距离频次 排列计算：对于距离相同的点，使用乘法原理计算排列数 示例： 示例 1： 12345输入：points = 输出：2解释：回旋镖为 和 即以 [1,0] 为中心，到 [0,0] 和 [2,0] 距离相等的两个排列 💻 解题思路 思路1：枚举中心点 + 动态计数 核心逻辑 枚举中心点： 遍历每个点作为回旋镖的中心点 i 计算距离频次： 对于每个中心点，计算它到其他所有点的距离平方 使用哈希表统计相同距离的点的个数 动态计算排列数： 关键技巧：在遍历过程中动态累加结果 当发现一个新的点与之前某些点距离相等时，立即计算新增的排列数 代码实现 1234...

2874. 有序三元组中的最大值II 🎯 问题描述 描述： 给你一个下标从 0 开始的整数数组 nums。 请你找出并返回满足以下条件的三元组 (i,j,k)(i, j, k)(i,j,k) 的最大值： 0≤i<j<k<n0 \le i < j < k < n0≤i<j<k<n 三元组的值定义为：(nums[i]−nums[j])×nums[k](nums[i] - nums[j]) \times nums[k](nums[i]−nums[j])×nums[k] 如果所有三元组的值都小于 0，则返回 0。 说明： 这是一个枚举中间点结合前后缀极值预处理的问题。 核心策略： 我们要最大化 (nums[i]−nums[j])×nums[k](nums[i] - nums[j]) \times nums[k](nums[i]−nums[j])×nums[k]。 我们可以枚举中间的下标 jjj。 当 jjj 固定时，为了使结果最大，我们需要： 在 jjj 的左侧（i<ji < ji<j）找到最大...

3128. 直角三角形 🎯 问题描述 描述： 给你一个二维 boolean 矩阵 grid。 请你返回使用 grid 中的 3 个元素可以构建的直角三角形数目，且满足 3 个元素值都为 1。 注意： 如果 grid 中 3 个元素满足：一个元素与另一个元素在同一行，同时与第三个元素在同一列，那么这 3 个元素称为一个直角三角形。 这 3 个元素互相之间不需要相邻。 直角顶点是那个既在行上又在列上的交点元素。 说明： 这是一个矩阵统计结合组合数学的问题。 核心策略： 直角三角形由三个点组成：直角顶点 (r, c)，同行点 (r, c2)，同列点 (r2, c)。 我们可以枚举每一个值为 1 的格子作为直角顶点。 对于每个直角顶点，它能形成的三角形数量 = (该行其他 1 的个数) × (该列其他 1 的个数)。 优化：为了避免重复计算每行每列的 1 的个数，我们可以先预处理统计出每一行和每一列的总和。 示例： 示例 1： 12345678输入：grid = [[0,1,0],[0,1,1],[0,1,0]]输出：2解释：- 只有 grid[1]...

1930. 长度为 3 的不同回文子序列 🎯 问题描述 描述： 给你一个字符串 s，返回 s 中长度为 3 的不同回文子序列的个数。 即便存在多种方法来构建相同的子序列，只要子序列的内容相同，就视为同一个。 回文串是正着读和反着读一样的字符串。 子序列是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。 例如，"aba" 是回文子序列，"abc" 不是。 说明： 这是一个枚举首尾字符结合集合去重的问题。 核心结构：长度为 3 的回文子序列形式必然是 A B A。 首字符和尾字符必须相同（都是 A）。 中间字符 B 可以是任意字符。 策略： 枚举所有可能的字符 A（从 ‘a’ 到 ‘z’）。 在字符串 s 中找到 A 第一次出现的位置 i 和 最后一次出现的位置 j。 任何在 i 和 j 之间出现的字符 B，都可以与首尾的 A 组成一个回文子序列 A B A。 统计 (i, j) 区间内有多少个不同的字符，就是以 A 为首尾的回文子序列的数量。 示例： 示例 1： ...

2909. 元素和最小的山形三元组II 🎯 问题描述 描述： 给你一个下标从 0 开始的整数数组 nums。 请你找出并返回满足以下条件的最小三元组和： 存在下标 i,j,ki, j, ki,j,k 满足 0≤i<j<k<n0 \le i < j < k < n0≤i<j<k<n。 满足“山形”条件：nums[i]<nums[j]nums[i] < nums[j]nums[i]<nums[j] 且 nums[k]<nums[j]nums[k] < nums[j]nums[k]<nums[j]。 目标是使 nums[i]+nums[j]+nums[k]nums[i] + nums[j] + nums[k]nums[i]+nums[j]+nums[k] 的值最小。 如果不存在这样的三元组，返回 -1。 说明： 这是一个前后缀分解（或预处理）的问题。 核心策略：我们可以枚举中间的元素 nums[j]nums[j]nums[j]。 为了使总和最小，对于固定的 jjj，我们需要在...

2001. 可互换矩形的组数 🎯 问题描述（来源于LeetCode） 描述： 给你一个二维整数数组 rectangles，其中 rectangles[i] = [width_i, height_i] 表示第 i 个矩形的宽度和高度。 如果两个矩形 i 和 j（i < j）的宽高比相同，则认为它们是可互换的。 具体来说，如果 width_i / height_i == width_j / height_j，则这两个矩形可互换。 请你返回可互换矩形的组数。 说明： 这是一个哈希表计数结合组合数学的问题。 核心逻辑是将矩形按照“宽高比”进行分组。 对于同一组内的 kkk 个矩形，它们可以组成的对数为 Ck2=k(k−1)2C_k^2 = \frac{k(k-1)}{2}Ck2​=2k(k−1)​。 代码采用了累加计数法，在遍历过程中直接计算新增的对数。 示例： 示例 1： 123456789输入：rectangles = [[4,8],[3,6],[10,20],[15,30]]输出：2解释：- [4,8] 的宽高比为 0.5。- [3,6] 的...