每日一题

2024.10.07 T871 . 最低加油次数

871. 最低加油次数 - 力扣（LeetCode）

871. 最低加油次数 - 汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。 沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。 假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。 为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。 注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。   示例 1： 输入：target = 1, startFuel = 1, stations = [] 输出：0 解释：可以在不加油的情况下到达目的地。 示例 2： 输入：target = 100, startFuel = 1, stations = [[10,100]] 输出：-1 解释：无法抵达目的地，甚至无法到达第一个加油站。 示例 3： 输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] 输出：2 解释： 出发时有 10 升燃料。 开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。 然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料）， 并将汽油从 10 升加到 50 升。然后开车抵达目的地。 沿途在两个加油站停靠，所以返回 2 。   提示： * 1 <= target, startFuel <= 109 * 0 <= stations.length <= 500 * 1 <= positioni < positioni+1 < target * 1 <= fueli < 109

https://leetcode.cn/problems/minimum-number-of-refueling-stops/

1. 问题描述
该代码解决了一个经典的动态规划问题，目标是计算在给定的加油站情况下，从起始位置到达目标所需的最少加油次数。如果无法到达目标，返回 -1。
• 目标距离 target: 我们希望从起点到达目标位置。
• 初始燃料 startFuel: 初始时拥有的燃料量。
• 加油站列表 stations: 每个加油站包含两个信息 [位置, 提供的燃料]。

2. 思路分析
1. 贪心算法：优先从能提供最多燃料的加油站加油，以确保在移动时能保持尽可能多的燃料。这是通过使用优先队列（大顶堆）来实现的。
2. 模拟行驶过程：
• 我们依次遍历每个加油站，计算从上一个位置移动到当前加油站所消耗的燃料。
• 如果燃料不足以到达当前加油站（或目标位置），我们需要从之前经过的加油站中选取燃料最多的站加油，直到有足够的燃料继续前进。
• 如果在选取加油站的过程中，仍然没有足够的燃料到达当前站或目标，则返回 -1 表示无法完成旅程。
3. 遍历所有加油站：
• 循环遍历加油站：在遍历加油站的过程中，将所有经过的加油站的可加燃料放入优先队列。
• 优先队列维护加油站的燃料值：优先队列（大顶堆）总是将最大的燃料值放在队列顶部，因此我们每次都可以从可加燃料最多的加油站加油。
4. 到达目标：
• 在遍历加油站的同时，还需要判断是否已经到达目标位置。如果到达了目标位置，则返回加油次数。

3. 代码实现

4. 复杂度分析

• 时间复杂度：每个加油站最多会进出优先队列一次，堆操作是对数级别的，因此总的时间复杂度为 ，其中 是加油站的数量。

• 空间复杂度：优先队列最多保存所有加油站的燃料，因此空间复杂度为 。

2024.10.08 T1436. 旅行终点站

1436. 旅行终点站 - 力扣（LeetCode）

1436. 旅行终点站 - 给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。 题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。   示例 1： 输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]] 输出："Sao Paulo" 解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。 示例 2： 输入：paths = [["B","C"],["D","B"],["C","A"]] 输出："A" 解释：所有可能的线路是： "D" -> "B" -> "C" -> "A".  "B" -> "C" -> "A".  "C" -> "A".  "A".  显然，旅行终点站是 "A" 。 示例 3： 输入：paths = [["A","Z"]] 输出："Z"   提示： * 1 <= paths.length <= 100 * paths[i].length == 2 * 1 <= cityAi.length, cityBi.length <= 10 * cityAi != cityBi * 所有字符串均由大小写英文字母和空格字符组成。

https://leetcode.cn/problems/destination-city/

1. 问题描述：
你有一份旅游线路图，其中每一条旅行线路使用一个数组表示，数组 paths 的每个元素是一个二元数组 paths[i] = [cityAi, cityBi]，表示从城市 cityAi 直接前往城市 cityBi。你的任务是找出这次旅行的终点站，即没有任何线路能够从该城市前往其他城市。
题目明确了以下几个条件：
• 数据保证恰好有一个终点站，即只有一个城市没有任何可以继续前往其他城市的线路。
• 旅行线路形成一条不含循环的路径，也就是说不存在从一个城市出发，经过多条线路最终又回到起点的情况。
具体要求是基于给定的 paths 数组，找出这个终点站。

2. 思路分析：
为了解决这个问题，我们可以把线路图看作是一个有向图，其中每一条线路 paths[i] = [cityAi, cityBi] 表示从城市 cityAi 到城市 cityBi 的一条有向边。
核心思路：
1. 终点站的定义：终点站是没有任何出边的城市，也就是说，没有任何线路从终点站继续前往其他城市。
2. 起点城市和终点城市的区分：我们可以将所有的城市分为两类：
• 起点城市：这些城市是路径中的 cityAi，它们可以到达其他城市。
• 终点城市：这些城市是路径中的 cityBi，但它们没有作为其他路径中的 cityAi 出现。
从这些城市的集合中，终点城市一定在 cityBi 列表中，但不会出现在 cityAi 列表中。

3. 实现步骤：
1. 使用两个集合：
• allCity：记录路径中所有出现过的城市（包括 cityAi 和 cityBi）。
• beginCity：记录所有的起点城市 cityAi。
2. 遍历 paths 数组，收集所有城市以及起点城市。
3. 最后，终点城市就是那些在 allCity 中出现，但不在 beginCity 集合中的城市。
通过这一步操作，我们可以找到唯一的终点城市。

4. 代码实现

5. 复杂度分析

• 时间复杂度：
• 遍历 paths 数组一次，处理每一条路径，收集所有的城市和起点城市。这一步需要遍历 paths 的所有元素，假设 paths 数组的长度为 n，每条路径包含两个城市，因此这一部分的时间复杂度是 。
• 遍历所有的城市，检查哪些城市不在起点城市集合 beginCity 中。由于我们使用哈希集合（C++ 中的 unordered_set），查找的时间复杂度是常数时间 ，因此这部分的时间复杂度也是 ，因为我们要对 allCity 中的每个城市进行查找。
• 总体时间复杂度为：
• ，其中 是 paths 数组的长度。

• 空间复杂度：
• 我们使用了两个集合 allCity 和 beginCity，它们最多会包含所有城市。由于每条路径包含两个城市，因此在最坏情况下，所有城市的数量不会超过 。因此，空间复杂度为 。
• 总体空间复杂度为：
• ，其中 是 paths 数组的长度。

• 结论：
• 时间复杂度：
• 空间复杂度：

2024.10.09 T3171. 找到按位或最接近K的子数组

3171. 找到按位或最接近 K 的子数组 - 力扣（LeetCode）

3171. 找到按位或最接近 K 的子数组 - 给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。 请你返回 最小 的绝对差值。 子数组 是数组中连续的 非空 元素序列。   示例 1： 输入：nums = [1,2,4,5], k = 3 输出：0 解释： 子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。 示例 2： 输入：nums = [1,3,1,3], k = 2 输出：1 解释： 子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。 示例 3： 输入：nums = [1], k = 10 输出：9 解释： 只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。   提示： * 1 <= nums.length <= 105 * 1 <= nums[i] <= 109 * 1 <= k <= 109

https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/

1. 问题描述：
给定一个数组 nums 和一个整数 k，需要找到 nums 中的一个子数组，使得这个子数组中所有元素的按位或运算的结果与 k 的绝对差值尽可能小。换句话说，寻找一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。需要返回这个最小的绝对差值。

2. 思路分析：
按位或运算（OR）是一个单调递增的操作，即如果你将一个新的元素加入到一个按位或结果中，最终的结果只会增加。因此，可以使用滑动窗口来逐步扩展子数组范围，并且动态计算按位或结果，直到找到与 k 差值最小的子数组。
核心思路：
1. 按位或运算的单调性：当子数组扩展时，按位或的结果只会增加，因此当按位或结果大于 k 时，需要通过缩小窗口来调整。
2. 双指针滑动窗口：通过滑动窗口法，维护窗口内的按位或结果，逐步扩展窗口的右边界，当按位或的结果与 k 的差值太大时，左边界收缩，缩小窗口。最终不断更新最小差值。
3. 最优策略：当按位或结果与 k 之间的绝对差值最小时，更新结果。如果发现按位或结果恰好等于 k，可以直接返回 0，因为这是最小可能的差值。

3. 实现步骤：
1. 初始化双指针 left 和 right 分别表示滑动窗口的左右边界，right_or 用于保存窗口内的按位或结果，ans 用于保存最小的绝对差值。
2. 外层循环遍历数组，用 right 指针扩展窗口。
3. 每次扩展窗口时，更新当前窗口的按位或结果，并根据当前的差值更新 ans。
4. 如果按位或结果大于 k，通过移动 left 指针缩小窗口，并且重构窗口内的按位或结果。
5. 最终返回最小的绝对差值。

4. 代码实现：

5. 复杂度分析：
• 时间复杂度：
• 外层循环遍历数组的每一个元素，即 right 指针向右扩展，最多移动 n 次。每次扩展时，内层的 while 循环通过移动 left 指针来缩小窗口。
• 最坏情况下，每个元素可能会被处理两次，分别由 left 和 right 指针移动导致。因此，整体的时间复杂度为 ，其中 n 是数组 nums 的长度。
• 空间复杂度：
• 只使用了几个常数级别的变量（如 right_or，ans），空间复杂度为 。
• 结论：
• 时间复杂度：
• 空间复杂度：

2024.10.10 T3162. 优质数对的总数 I

3162. 优质数对的总数 I - 力扣（LeetCode）

3162. 优质数对的总数 I - 给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。 如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。 返回 优质数对 的总数。   示例 1： 输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1 输出：5 解释： 5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。 示例 2： 输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3 输出：2 解释： 2个优质数对分别是 (3, 0) 和 (3, 1)。   提示： * 1 <= n, m <= 50 * 1 <= nums1[i], nums2[j] <= 50 * 1 <= k <= 50

https://leetcode.cn/problems/find-the-number-of-good-pairs-i/

1. 问题描述：
给定两个整数数组 nums1 和 nums2，其长度分别为 n 和 m，同时给定一个正整数 k。如果满足 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为优质数对（其中 0 <= i <= n - 1，0 <= j <= m - 1）。需要返回所有优质数对的总数。
题目要求：
对于每对数组元素，检查是否符合优质数对的条件，即 nums1[i] % (nums2[j] * k) == 0，并返回符合条件的数对总数。

2. 思路分析：
这个问题的核心是检查每对 (i, j) 是否满足 nums1[i] % (nums2[j] * k) == 0，这是一种枚举问题。为了确定每个数对是否是优质数对，我们可以遍历 nums1 和 nums2 的所有元素组合，检查其是否满足上述条件。
核心思路：
1. 双重循环遍历：通过双重循环遍历 nums1 和 nums2 中的每个元素组合，分别计算 nums1[i] 是否能被 nums2[j] * k 整除。如果是，则计数器加 1。
2. 暴力解法：由于没有给出明确的性能要求，我们可以通过暴力枚举所有数对并判断其是否是优质数对。这是一种直接且简单的思路。

3. 实现步骤：
1. 使用一个变量 count 来记录优质数对的数量。
2. 双重循环遍历 nums1 和 nums2，每次计算 nums1[i] % (nums2[j] * k) 是否等于 0，如果是，则将 count 加 1。
3. 返回最终的 count，即优质数对的总数。

4. 代码实现：

5. 复杂度分析：
• 时间复杂度：
• 外层循环遍历 nums1，内层循环遍历 nums2，每次检查一个数对是否符合条件。两层循环的时间复杂度为 ，其中 n 是 nums1 的长度，m 是 nums2 的长度。
• 每次判断 nums1[i] % (nums2[j] * k) 是否等于 0 是常数时间操作，因此整体的时间复杂度为 。
• 空间复杂度：
• 我们只使用了一个计数器 count 来记录优质数对的数量，除此之外没有使用额外的空间。因此，空间复杂度为 。
• 结论：
• 时间复杂度：
• 空间复杂度：

2024.10.11 T3164. 优质数对的总数 II

3164. 优质数对的总数 II - 力扣（LeetCode）

3164. 优质数对的总数 II - 给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。 如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。 返回 优质数对 的总数。   示例 1： 输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1 输出：5 解释： 5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。 示例 2： 输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3 输出：2 解释： 2个优质数对分别是 (3, 0) 和 (3, 1)。   提示： * 1 <= n, m <= 105 * 1 <= nums1[i], nums2[j] <= 106 * 1 <= k <= 103

https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/description/

1. 题目描述
给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。 如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（其中 0 <= i <= n - 1, 0 <= j <= m - 1）。 请返回 优质数对 的总数。

2. 思路分析
1. 问题分析：
• 我们需要遍历 nums1 和 nums2 中的每个元素组合，并判断 nums1[i] 是否能够被 nums2[j] * k 整除。
• 通过将 nums2[j] 先乘以 k，然后在 nums1 中找出与其满足倍数关系的数对，可以加速计算过程。
2. 优化方案：
• 预处理 nums2：将 nums2 中的每个元素乘以 k，存储在数组中，便于后续查找。
• 频率计数：使用频率计数数组 freqNums1 来记录 nums1 中每个元素的出现次数，这样可以直接在后续查找中利用倍数关系快速累加符合条件的数对。
• 倍数查找：利用 vis 数组标记处理后的 nums2 中每个元素乘以 k 后是否有效，并在 nums1 中寻找符合倍数关系的数。
3. 步骤细化：
• 遍历 nums2，将每个元素乘以 k 后存入 vis 数组。
• 遍历 nums1，通过频率计数记录每个元素的出现次数。
• 遍历 vis 中标记的数，通过倍数查找方法，在 nums1 中寻找满足条件的数对，累加符合条件的数对数量。

3. C++ 代码实现

4. 复杂度分析
• 时间复杂度：
• 预处理 nums1 和 nums2 的时间复杂度为 ，其中 n 是 nums1 的长度，m 是 nums2 的长度。
• 在处理完 nums2 后，我们会对 vis 数组进行查找，并遍历可能的倍数，查找的时间复杂度接近 ，但由于 k 的限制，实际复杂度会更低。
因此，综合时间复杂度为 。
• 空间复杂度：
• 需要存储 freqNums1 和 vis 数组，空间复杂度为 ，其中 n 是 nums1 中的最大值。

2024.10.12 T3158. 求出出现两次数字的 XOR 值

3158. 求出出现两次数字的 XOR 值 - 力扣（LeetCode）

3158. 求出出现两次数字的 XOR 值 - 给你一个数组 nums ，数组中的数字 要么 出现一次，要么 出现两次。 请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。   示例 1： 输入：nums = [1,2,1,3] 输出：1 解释： nums 中唯一出现过两次的数字是 1 。 示例 2： 输入：nums = [1,2,3] 输出：0 解释： nums 中没有数字出现两次。 示例 3： 输入：nums = [1,2,2,1] 输出：3 解释： 数字 1 和 2 出现过两次。1 XOR 2 == 3 。   提示： * 1 <= nums.length <= 50 * 1 <= nums[i] <= 50 * nums 中每个数字要么出现过一次，要么出现过两次。

https://leetcode.cn/problems/find-the-xor-of-numbers-which-appear-twice/

1. 问题描述
给定一个数组 nums，数组中的数字要么出现一次，要么出现两次。你的任务是返回数组中所有出现两次的数字的按位异或（XOR）值。如果没有数字出现过两次，则返回 0。

2. 问题具体要求：
1. 每个数字的出现次数要么是 1，要么是 2。
2. 返回所有出现两次的数字的异或值，如果没有这样的数字，返回 0。

3. 思路分析
该问题的核心是找到所有出现两次的数字并计算它们的异或值。可以通过以下步骤来实现：
• 记录每个数字的出现次数：可以使用一个计数器来统计数组中每个数字的出现次数。
• 筛选出现两次的数字：遍历计数器，找出所有出现两次的数字。
• 计算异或值：对于每个出现两次的数字，将它们依次进行按位异或运算，得到最终结果。
💡
异或运算的性质：
1. a ^ a = 0，同一个数异或两次会抵消。
2. 异或运算具有交换律和结合律，即 a ^ b ^ c == c ^ b ^ a，因此我们可以按任意顺序依次异或。

4. 实现步骤
1. 使用一个数组 cnt 来记录数字的出现次数。由于题目没有明确数字的范围，我们假设数字在 0 到 50 之间。
2. 遍历 nums 数组，统计每个数字的出现次数。
3. 对所有出现次数大于等于 2 的数字进行异或操作，计算它们的异或值。
4. 返回结果。

5. 代码实现

6. 复杂度分析
1. 时间复杂度：
• 我们需要遍历 nums 数组一次，统计数字的出现次数。这一步的时间复杂度是 ，其中 n 是 nums 数组的长度。
• 随后，我们遍历计数数组 cnt，这一部分的时间复杂度为 ，因为 cnt 的大小是固定的（长度为 51）。
• 因此，整体时间复杂度为 。
2. 空间复杂度：
• 我们使用了一个长度为 51 的计数数组 cnt，空间复杂度为 ，因为计数数组的大小是固定的。
• 整体空间复杂度为 。
3. 结论
• 时间复杂度：
• 空间复杂度：

2024.10.13 T1884. 鸡蛋掉落-两枚鸡蛋

1884. 鸡蛋掉落-两枚鸡蛋 - 力扣（LeetCode）

1884. 鸡蛋掉落-两枚鸡蛋 - 给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。 每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？   示例 1： 输入：n = 2 输出：2 解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。 如果第一枚鸡蛋碎了，可知 f = 0； 如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1； 否则，当两个鸡蛋都没碎时，可知 f = 2。 示例 2： 输入：n = 100 输出：14 解释： 一种最优的策略是： - 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。 - 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。 - 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。 不管结果如何，最多需要扔 14 次来确定 f 。   提示： * 1 <= n <= 1000

https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/

1. 问题描述
在这道“鸡蛋掉落”问题中，我们有两枚相同的鸡蛋和一栋有 层楼的建筑。已知存在一个临界楼层 ，满足：
• 从高于 的楼层扔下鸡蛋，鸡蛋会碎；
• 从 楼层或者低于 的楼层扔下鸡蛋，鸡蛋不会碎。
目标是通过最少的操作次数，确定这个临界楼层 的值。每次操作可以选择任意楼层扔下鸡蛋。扔鸡蛋后，如果鸡蛋没碎，可以继续使用这枚鸡蛋；如果碎了，鸡蛋就不能再使用了。最终需要确定出最少的操作次数来找到临界楼层。

2. 思路分析
本题可以用两种方法求解：动态规划法和数学推导法。
• 动态规划法
动态规划的核心思想是：逐步增加操作次数，通过最优选择确保找到临界楼层。设 表示用 枚鸡蛋在 次操作内最多可以测试的楼层数。那么问题可以转化为找到最少的操作次数 ，使得在两枚鸡蛋的条件下能够测试 层楼。
动态规划状态转移方程：
其中：
• ：表示鸡蛋碎了，接下来在剩下的 次操作中，使用剩下的 枚鸡蛋测试前面的楼层。
• ：表示鸡蛋没碎，接下来用 枚鸡蛋在剩余的楼层上继续测试。
通过状态转移，我们逐步增加操作次数 ，直到能测试所有 层楼。
• 数学推导法
数学推导法通过观察等差数列求和来解决问题。设 次操作为等差数列的和：
确定每次的楼层高度：
• 设我们第 1 次选择的楼层是 ，第 2 次选择的楼层是 ，依此类推，第 k 次选择的楼层是 。为了最小化最坏情况下的操作次数，我们希望每次扔鸡蛋后剩下的楼层数尽量减少，形成等差数列。
假设第一次从第 层扔鸡蛋，如果碎了，我们就有 层需要逐层测试；如果没碎，还剩下 层楼。这时我们从 层开始下一次测试。
为了平衡这两种情况的最坏情况次数，选择楼层应该满足如下条件：
• 第一次扔的楼层 ，应该满足剩余的楼层数在 次测试内也能覆盖。
所以楼层选择的策略是：
换句话说，等差数列的和至少要覆盖所有的楼层数 。

3. 实现步骤
• 动态规划法步骤：
1. 初始化一个二维动态规划数组 ，其中 记录在 枚鸡蛋、 次操作内能够测试的最大楼层数。
2. 设定最小的操作次数 ，逐步增加操作次数，直到找到能够测试所有楼层的最小操作次数。
3. 通过状态转移方程计算 ，直到满足 。
4. 返回操作次数 。
• 数学推导法步骤：
1. 设定初始操作次数 ，总楼层数和 。
2. 每次增加操作次数 ，更新总楼层数 ，直到 大于等于 。
3. 返回操作次数 。

4. 代码实现
• 动态规划法的 C++ 实现：
• 数学推导法的 C++ 实现：

5. 复杂度分析
• 动态规划法：
• 时间复杂度： 。由于我们逐步增加操作次数 ，并且在每次操作中更新 ，因此时间复杂度取决于楼层数 和操作次数的增。
• 空间复杂度： 。只需存储一个二维的动态规划数组
• 数学推导法：
• 时间复杂度： 。通过等差数列求和公式找到最小的 ，由于等差数列和与 的平方根有关，时间复杂度为
• 空间复杂度： 。只使用常数空间存储变量 和

2024.10.14 T887 . 鸡蛋掉落

887. 鸡蛋掉落 - 力扣（LeetCode）

887. 鸡蛋掉落 - 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？   示例 1： 输入：k = 1, n = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 如果它没碎，那么肯定能得出 f = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。 示例 2： 输入：k = 2, n = 6 输出：3 示例 3： 输入：k = 3, n = 14 输出：4   提示： * 1 <= k <= 100 * 1 <= n <= 104

https://leetcode.cn/problems/super-egg-drop/

1. 问题描述
给定 枚相同的鸡蛋，以及 层楼的建筑，已知存在一个临界楼层 ，满足：
• 当从高于 层的楼层扔下鸡蛋时，鸡蛋会碎。
• 当从 层或比 低的楼层扔下鸡蛋时，鸡蛋不会碎。
目标是找出这个临界楼层 ，并要求在最坏情况下找到 所需的最小操作次数。每次操作时，你可以选择一枚鸡蛋从某一楼层扔下，判断鸡蛋是否破碎，并继续根据结果进行接下来的操作。

2. 思路分析
这个问题的本质是一个递归问题。可以使用动态规划的方式来解，但递归本身也可以解决，只是效率较低。为了提升效率，可以结合记忆化搜索来减少重复计算。
• 递归公式分析：
设 表示在 个鸡蛋和最多 次操作下，能够检测的最大楼层数。根据以下两种情况进行递推：
• 如果鸡蛋碎了：问题转化为 个鸡蛋， 次操作的子问题。
• 如果鸡蛋没碎：问题转化为 个鸡蛋， 次操作的子问题。
于是有递推关系式：
• 终止条件：
• 当 或 时，无法检测任何楼层，返回 0。
• 使用记忆化缓存已经计算过的结果，避免重复计算。
• 判断操作次数 ：
通过不断增加操作次数 ，直到 能够检测的楼层数大于等于 ，即满足 ，得到最小的 值。

3. 实现步骤
递归定义： 定义 ，表示用 个鸡蛋在 次操作内可以检测的最大楼层数。
递推关系： 使用公式 计算不同 和 的值。
记忆化搜索： 采用一个二维数组 来保存已经计算过的结果，避免重复计算。
主函数： 定义 ，通过逐步增加操作次数 ，直到 能够检测到 层楼。
返回最小的操作次数： 当 达到或超过 时，返回当前的 值作为最小操作次数。

4. 代码实现

5. 复杂度分析
1. 时间复杂度：
• 由于使用了记忆化数组， 只会被计算一次。因此，每个 和 的组合最多被计算一次。
• 递归的最坏情况下，操作次数 大约是 ，所以总的时间复杂度是 ，即 个鸡蛋和 层楼的大小决定了总的计算次数。
2. 空间复杂度：
• 记忆化数组 的空间复杂度是 ，用于存储已经计算过的结果。

2024.10.15 T3200. 三角形的最大高度

3200. 三角形的最大高度 - 力扣（LeetCode）

3200. 三角形的最大高度 - 给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。 每一行的球必须是 相同 颜色，且相邻行的颜色必须 不同。 返回可以实现的三角形的 最大 高度。   示例 1： 输入： red = 2, blue = 4 输出： 3 解释： [https://assets.leetcode.com/uploads/2024/06/16/brb.png] 上图显示了唯一可能的排列方式。 示例 2： 输入： red = 2, blue = 1 输出： 2 解释： [https://assets.leetcode.com/uploads/2024/06/16/br.png] 上图显示了唯一可能的排列方式。 示例 3： 输入： red = 1, blue = 1 输出： 1 示例 4： 输入： red = 10, blue = 1 输出： 2 解释： [https://assets.leetcode.com/uploads/2024/06/16/br.png] 上图显示了唯一可能的排列方式。   提示： * 1 <= red, blue <= 100

https://leetcode.cn/problems/maximum-height-of-a-triangle/

1. 问题描述
给定两个整数 red 和 blue，分别表示红色球和蓝色球的数量。使用这些球可以构建一个三角形，三角形的第 1 行有 1 个球，第 2 行有 2 个球，依次类推，每一行的球都必须是相同颜色，相邻行的球颜色必须不同。任务是找到在满足上述条件的情况下，所能构建的三角形的最大高度。

2. 思路分析
• 方法一：模拟
1. 从第一行开始逐行填充球，每行的球数量等于行号，且每行球的颜色交替变化。
2. 每一行用红色球或蓝色球，具体取决于当前行是奇数行还是偶数行。
3. 分别计算当前使用的红色球和蓝色球的总数，并在超过总球数时停止，输出构建的最大高度。
• 方法二：数学方法
1. 奇数行球数公式推导
• 设奇数行有 行，每行的球数为 ，这是一个等差数列，首项为 1，公差为 2。根据等差数列的求和公式，奇数行球的总数为：
• 所以，如果我们有 个球用于奇数行，那么 应该满足：
• 解得：
• 因此，奇数行最多能够放 行。
2. 偶数行球数公式推导
• 设偶数行有 行，每行的球数为 ，这是一个等差数列，首项为 2，公差为 2。根据等差数列的求和公式，偶数行球的总数为：
• 所以，如果我们有 个球用于偶数行，那么 应该满足：
• 这个不等式的解可以通过近似公式推导出来。将其展开为二次方程：
• 解这个不等式，得到：
• 取整数部分，最终得：
• 因此，偶数行最多能够放 行。
3. 总行数计算
• 设 odd 为奇数行的最大行数，even 为偶数行的最大行数，那么三角形的总高度取决于以下两种情况：
• 如果 odd > even，那么最大的高度为 2 * even + 1，因为我们最多可以放下 even 行偶数行和 even + 1 行奇数行。
• 否则，最大的高度为 2 * odd，即 odd 行奇数行和 odd 行偶数行。
• 因此，最终公式为：

3. 实现步骤
1. 定义函数 maxHeightOfTriangle(red, blue)。
2. 使用模拟方法逐行计算球的数量，直到其中一种球数不足以支持下一行，返回当前行数减一作为最大高度。
3. 通过数学方法推导公式，计算最大可能的高度，并返回最终的结果。

4. 代码实现
• 方法一：模拟方法
• 方法二：数学方法

5. 复杂度分析
• 方法一：模拟方法
• 时间复杂度：，其中 为最大高度。每一行循环一次，直到球数不足为止。
• 空间复杂度：，只需常数空间存储当前行的球数。
• 方法二：数学方法
• 时间复杂度：，公式计算最大高度仅需常数次计算。
• 空间复杂度：，只需常数空间存储计算结果。

2024.10.16 T3194. 最小元素和最大元素的最小平均值

3194. 最小元素和最大元素的最小平均值 - 力扣（LeetCode）

3194. 最小元素和最大元素的最小平均值 - 你有一个初始为空的浮点数数组 averages。另给你一个包含 n 个整数的数组 nums，其中 n 为偶数。 你需要重复以下步骤 n / 2 次： * 从 nums 中移除 最小 的元素 minElement 和 最大 的元素 maxElement。 * 将 (minElement + maxElement) / 2 加入到 averages 中。 返回 averages 中的 最小 元素。   示例 1： 输入： nums = [7,8,3,4,15,13,4,1] 输出： 5.5 解释： 步骤 nums averages 0 [7,8,3,4,15,13,4,1] [] 1 [7,8,3,4,13,4] [8] 2 [7,8,4,4] [8,8] 3 [7,4] [8,8,6] 4 [] [8,8,6,5.5] 返回 averages 中最小的元素，即 5.5。 示例 2： 输入： nums = [1,9,8,3,10,5] 输出： 5.5 解释： 步骤 nums averages 0 [1,9,8,3,10,5] [] 1 [9,8,3,5] [5.5] 2 [8,5] [5.5,6] 3 [] [5.5,6,6.5] 示例 3： 输入： nums = [1,2,3,7,8,9] 输出： 5.0 解释： 步骤 nums averages 0 [1,2,3,7,8,9] [] 1 [2,3,7,8] [5] 2 [3,7] [5,5] 3 [] [5,5,5]   提示： * 2 <= n == nums.length <= 50 * n 为偶数。 * 1 <= nums[i] <= 50

https://leetcode.cn/problems/minimum-average-of-smallest-and-largest-elements/

1. 问题描述
给定一个初始为空的浮点数数组 averages，以及一个包含 n 个整数的数组 nums（其中 n 为偶数），需要进行以下步骤 n / 2 次：
• 从 nums 中移除最小的元素 minElement 和最大的元素 maxElement。
• 将 (minElement + maxElement) / 2 加入到 averages 中。
最终，返回 averages 数组中的最小元素。

2. 思路分析
本题的关键在于每次从 nums 中找到当前最小和最大元素，并计算它们的平均值，将结果存入 averages 数组，最终返回该数组中的最小值。
• 主要步骤：
1. 使用 min_element 和 max_element 分别找到 nums 中的最小值和最大值。
2. 将这两个元素从 nums 数组中移除。
3. 计算这两个元素的平均值，并将其加入 averages 数组。
4. 循环执行上述步骤，直到 nums 为空。
5. 最后，返回 averages 数组中的最小值。

3. 实现步骤
元素查找与移除：
• 使用 min_element 和 max_element 找到 nums 数组中的最小值和最大值，并分别从数组中删除它们。
平均值计算：
• 计算最小值和最大值的平均值，并将其存入 averages 数组。
返回结果：
• 在循环结束后，返回 averages 数组中的最小元素。

4. 代码实现

5. 复杂度分析
1. 时间复杂度：
• 每次操作都需要找到 nums 中的最小值和最大值，时间复杂度为 。在最坏情况下，n/2 次操作共计执行 次查找和移除操作。因此，总的时间复杂度为 ，其中 n 是数组 nums 的大小。
2. 空间复杂度：
• 由于需要存储 averages 数组，其大小为 n/2，因此空间复杂度为 。

6. 优化
1. 优化后的复杂度分析
1. 时间复杂度：
• 排序的时间复杂度是 。
• 双指针遍历的时间复杂度是 ，因为我们只需遍历一次数组。
• min_element 的时间复杂度是 。
• 因此，总的时间复杂度是 ，其中 n 是数组 nums 的大小。
2. 空间复杂度：
• 由于只使用了 averages 数组来存储结果，其大小为 n / 2，空间复杂度是 。

2024.10.17 T3193. 统计逆序对的数目

3193. 统计逆序对的数目 - 力扣（LeetCode）

3193. 统计逆序对的数目 - 给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。 整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ： * i < j 且 nums[i] > nums[j] 请你返回 [0, 1, 2, ..., n - 1] 的 排列 perm 的数目，满足对 所有 的 requirements[i] 都有 perm[0..endi] 恰好有 cnti 个逆序对。 由于答案可能会很大，将它对 109 + 7 取余 后返回。   示例 1： 输入：n = 3, requirements = [[2,2],[0,0]] 输出：2 解释： 两个排列为： * [2, 0, 1] * 前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。 * 前缀 [2] 的逆序对数目为 0 个。 * [1, 2, 0] * 前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。 * 前缀 [1] 的逆序对数目为 0 个。 示例 2： 输入：n = 3, requirements = [[2,2],[1,1],[0,0]] 输出：1 解释： 唯一满足要求的排列是 [2, 0, 1] ： * 前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。 * 前缀 [2, 0] 的逆序对为 (0, 1) 。 * 前缀 [2] 的逆序对数目为 0 。 示例 3： 输入：n = 2, requirements = [[0,0],[1,0]] 输出：1 解释： 唯一满足要求的排列为 [0, 1] ： * 前缀 [0] 的逆序对数目为 0 。 * 前缀 [0, 1] 的逆序对为 (0, 1) 。     提示： * 2 <= n <= 300 * 1 <= requirements.length <= n * requirements[i] = [endi, cnti] * 0 <= endi <= n - 1 * 0 <= cnti <= 400 * 输入保证至少有一个 i 满足 endi == n - 1 。 * 输入保证所有的 endi 互不相同。

https://leetcode.cn/problems/count-the-number-of-inversions/

1. 问题描述
给定一个整数 n 和一个二维数组 requirements，每个 requirements[i] = [endi, cnti] 表示要求在排列的前 endi+1 个元素中，恰好有 cnti 个逆序对。需要找到长度为 n 的排列 perm，使得它满足所有要求，并返回满足条件的排列的数量，答案需要对 10^9 + 7 取模。
逆序对的定义为：在一个数组中，若下标对 (i, j) 满足 i < j 且 nums[i] > nums[j]，则称该下标对为一个逆序对。

2. 思路分析
1. 逆序对的定义： 逆序对 (i, j) 的定义是 i < j 且 perm[i] > perm[j]。因此，在构造排列时，控制排列中的元素顺序决定了逆序对的数量。
2. 要求数组的处理：
• requirements[i] = [endi, cnti] 表示 perm[0..endi] 这段子数组中，必须恰好有 cnti 个逆序对。
• 需要处理多个这样的要求，且这些要求对不同位置的排列提出了限制。
3. 动态规划思路：
• 定义 dp[k] 表示排列中逆序对数为 k 的方案数。
• 对于每一个位置 i，通过调整当前位置的元素与前面元素的顺序，动态更新逆序对的数量。
• 如果某个位置 i 有特定的逆序对数量要求，那么该位置的逆序对数必须严格满足要求。
• 在不违反要求的情况下，通过累加不同逆序对数的方案数，来更新 dp 数组。
4. 前缀和优化： 为了加速逆序对数的累加，可以使用前缀和技巧，来快速计算子数组的逆序对数总和。

3. 实现步骤
1. 初始化逆序对要求数组：
• 初始化一个长度为 n 的数组 inversion_requirements，默认值为 1 表示没有限制。将 requirements 中的值填入对应位置。
• 特别处理第一个位置，若其要求不是 0，则直接返回 0，因为第一个位置不可能形成逆序对。
2. 动态规划数组初始化：
• 初始化一个 dp 数组，大小为最大逆序对数加 1，dp[0] 设为 1，表示没有元素时有且只有一种排列方式。
3. 更新动态规划数组：
• 遍历每个位置 i，根据当前的位置更新 dp 数组的值。
• 若当前位置有特定的逆序对要求，则只保留符合要求的值；若没有要求，利用前缀和技巧快速计算可行的逆序对数。
4. 返回结果：
• 返回最终排列的方案数，若最后一个位置有特定逆序对要求，则返回对应的 dp 值，否则返回所有可能的排列数总和。

4. 代码实现

5. 复杂度分析
• 时间复杂度：
• 遍历了所有 n 个位置，并且每次更新 dp 数组需要最多 次计算。因此，总的时间复杂度为 。
• 空间复杂度：
• 主要使用了一个长度为 max_inversions + 1 的 dp 数组，空间复杂度为 。

2024.10.18 T3191. 使二进制数组全部等于 1 的最少操作次数 I

3191. 使二进制数组全部等于 1 的最少操作次数 I - 力扣（LeetCode）

3191. 使二进制数组全部等于 1 的最少操作次数 I - 给你一个二进制数组 nums 。 你可以对数组执行以下操作 任意 次（也可以 0 次）： * 选择数组中 任意连续 3 个元素，并将它们 全部反转 。 反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。 请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。   示例 1： 输入：nums = [0,1,1,1,0,0] 输出：3 解释： 我们可以执行以下操作： * 选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1,0,0,1,0,0] 。 * 选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1,1,1,0,0,0] 。 * 选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1,1,1,1,1,1] 。 示例 2： 输入：nums = [0,1,1,1] 输出：-1 解释： 无法将所有元素都变为 1 。   提示： * 3 <= nums.length <= 105 * 0 <= nums[i] <= 1

https://leetcode.cn/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-i/

1. 问题描述
给定一个二进制数组 nums，你可以对该数组执行以下操作任意次：
• 选择数组中任意连续的 3 个元素，将它们全部反转（即将 0 变成 1，将 1 变成 0）。
你的目标是将数组中的所有元素都变为 1，求所需的最少操作次数。如果无法将所有元素变为 1，则返回 -1。

2. 思路分析
这个问题可以通过贪心算法来解决。我们需要从左到右遍历数组，当发现某个元素为 0 时，必须将其反转。由于可以对任意连续的 3 个元素进行操作，当我们遇到一个 0 时，可以将从该位置开始的接下来的 3 个元素反转，确保第一个元素变为 1。

3. 具体步骤：
1. 遍历数组：从左到右遍历，当遇到 nums[i] == 0 时，将 nums[i] 之后的两个元素反转（即 nums[i+1] 和 nums[i+2] ），这样可以确保当前位置的 0 被反转为 1。
2. 记录操作次数：每次反转操作之后，操作次数加 1。
3. 检查最后两个元素：当遍历结束时，如果最后两个元素不是 1，说明无法通过操作使所有元素变成 1，返回 1。否则，返回累积的操作次数。

4. 实现思路
1. 遍历数组：
• 遍历数组的前 n-2 个元素，若当前元素为 0，则反转接下来的 3 个元素，并记录操作次数。
2. 检查末尾元素：
• 遍历结束后，检查数组的最后两个元素，如果它们不全是 1，说明无解，返回 1。
3. 返回结果：
• 如果所有元素都能变为 1，则返回操作的总次数。

5. 代码实现

6. 复杂度分析
• 时间复杂度：
• 遍历一次长度为 n 的数组，时间复杂度为 。
• 空间复杂度：
• 使用了常数个额外变量，空间复杂度为 。

7. 贪心策略的解释
由于我们只能对连续的 3 个元素进行反转，因此每当遇到一个 0 时，最贪心的操作是将其立即反转，并反转其后的两个元素。这样，能够确保当前的 0 被翻转为 1，同时对后面的元素做出最小的影响。这种策略使得我们能够在局部最优的前提下，尽量减少整体的反转次数。

2024.10.19 T3192. 使二进制数组全部等于 1 的最少操作次数 II

3192. 使二进制数组全部等于 1 的最少操作次数 II - 力扣（LeetCode）

3192. 使二进制数组全部等于 1 的最少操作次数 II - 给你一个二进制数组 nums 。 你可以对数组执行以下操作 任意 次（也可以 0 次）： * 选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。 反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。 请你返回将 nums 中所有元素变为 1 的 最少 操作次数。   示例 1： 输入：nums = [0,1,1,0,1] 输出：4 解释： 我们可以执行以下操作： * 选择下标 i = 1 执行操作，得到 nums = [0,0,0,1,0] 。 * 选择下标 i = 0 执行操作，得到 nums = [1,1,1,0,1] 。 * 选择下标 i = 4 执行操作，得到 nums = [1,1,1,0,0] 。 * 选择下标 i = 3 执行操作，得到 nums = [1,1,1,1,1] 。 示例 2： 输入：nums = [1,0,0,0] 输出：1 解释： 我们可以执行以下操作： * 选择下标 i = 1 执行操作，得到 nums = [1,1,1,1] 。   提示： * 1 <= nums.length <= 105 * 0 <= nums[i] <= 1

https://leetcode.cn/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii/

1. 问题描述
给定一个二进制数组 nums，你可以对数组执行以下操作任意次（也可以为 0 次）：
• 选择数组中任意一个下标 i，并将从下标 i 开始到数组末尾的所有元素反转（将 0 变为 1，将 1 变为 0）。
你的目标是将数组 nums 中的所有元素都变为 1。你需要返回将数组变为全 1 的最少操作次数。

2. 思路分析
这个问题的核心在于观察到每次反转会影响从某个下标开始直到数组末尾的所有元素。因此，问题可以转化为检测数组的不同连续部分，因为我们每次反转都会使得这一段全部元素变化。为了最小化操作次数，我们应当尽量减少反转操作。
具体思路如下：
1. 反转段的标记：
• 从数组末尾向前遍历，如果两个相邻的元素不同（nums[i] != nums[i - 1]），意味着从 i 位置开始至末尾需要反转。
• 每当遇到一个这样的相邻变化，我们增加操作次数。
2. 处理第一个元素：
• 如果 nums[0] == 0，则需要再进行一次额外的反转操作，因为最终需要将 nums[0] 也变为 1。
3. 最少操作次数：
• 通过上述遍历数组，记录需要反转的次数，即为将整个数组变为全 1 的最少操作次数。

3. 实现步骤
1. 遍历数组：
• 从数组的末尾向前遍历，比较相邻元素是否相同。
• 如果两个相邻元素不同，则记录一次反转操作。
2. 处理数组起始位置：
• 如果数组的第一个元素为 0，需要额外加一次反转操作。
3. 返回结果：
• 返回累积的反转操作次数。

4. 代码实现

5. 复杂度分析
• 时间复杂度：
• 遍历一次长度为 n 的数组，因此时间复杂度为 。
• 空间复杂度：
• 只使用了常数个额外变量，因此空间复杂度为 。

6. 贪心策略的解释
这个问题可以通过贪心策略解决。由于每次操作都反转从某个位置到末尾的所有元素，因此最佳策略是每次只在需要的地方执行反转操作。具体地，每次遇到相邻的元素不相等时，就可以认为这一段需要反转，避免重复操作。
最后，如果数组的第一个元素为 0，我们必须要进行额外的一次反转操作才能确保第一个元素也变为 1。

2024.10.20 T908 . 最小差值 I

908. 最小差值 I - 力扣（LeetCode）

908. 最小差值 I - 给你一个整数数组 nums，和一个整数 k 。 在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。 nums 的 分数 是 nums 中最大和最小元素的差值。  在对  nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。   示例 1： 输入：nums = [1], k = 0 输出：0 解释：分数是 max(nums) - min(nums) = 1 - 1 = 0。 示例 2： 输入：nums = [0,10], k = 2 输出：6 解释：将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。 示例 3： 输入：nums = [1,3,6], k = 3 输出：0 解释：将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。   提示： * 1 <= nums.length <= 104 * 0 <= nums[i] <= 104 * 0 <= k <= 104

https://leetcode.cn/problems/smallest-range-i/

1. 问题描述
给定一个整数数组 nums 和一个整数 k。你可以对数组执行以下操作 任意次（每个索引最多执行一次）：
• 选择数组中任意一个索引 i（0 <= i < nums.length），并将 nums[i] 改为 nums[i] + x，其中 x 是一个范围在 [-k, k] 内的任意整数。
每个索引 i 最多只能执行一次上述操作。
数组 nums 的 分数 定义为数组中的最大元素和最小元素的差值。即：
 
你的任务是在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的 最低分数。如果无法通过任何操作使得所有元素变为 1，则返回相应的结果。

2. 思路分析
为了最小化数组 nums 的分数，即最大元素与最小元素的差值，我们需要通过调整每个元素来尽可能地降低最大值和提高最小值。由于每个元素可以增加或减少最多 k，我们可以得出以下结论：
1. 最大值的调整：
• 为了尽可能降低最大值，可以将数组中的最大元素减少 k。
2. 最小值的调整：
• 为了尽可能提高最小值，可以将数组中的最小元素增加 k。
综合以上两点，调整后的最大值为 max(nums) - k，调整后的最小值为 min(nums) + k。因此，调整后的分数为：
然而，这个结果可能为负数，表示通过调整操作，最大值已小于或等于最小值。由于分数不能为负数，因此我们需要取结果与 0 的最大值。
总结：
• 最低分数为 max(nums) - min(nums) - 2k，如果该值小于 0，则最低分数为 0。

3. 实现步骤
1. 找到数组中的最大值和最小值：
• 使用 max_element 和 min_element 函数分别找到 nums 数组的最大值和最小值。
2. 计算调整后的分数：
• 计算 max(nums) - min(nums) - 2 * k。
• 如果结果小于 0，则返回 0；否则，返回计算结果。
3. 返回结果：
• 返回计算得到的最低分数。

4. 代码实现

5. 复杂度分析
• 时间复杂度：
• 查找最大值和最小值各需 时间，总体时间复杂度为 ，其中 n 是数组 nums 的长度。
• 空间复杂度：
• 使用了常数个额外变量，空间复杂度为 。

2024.10.21 T910 . 最小差值 II

910. 最小差值 II - 力扣（LeetCode）

910. 最小差值 II - 给你一个整数数组 nums，和一个整数 k 。 对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。 nums 的 分数 是 nums 中最大元素和最小元素的差值。 在更改每个下标对应的值之后，返回 nums 的最小 分数 。   示例 1： 输入：nums = [1], k = 0 输出：0 解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。 示例 2： 输入：nums = [0,10], k = 2 输出：6 解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。 示例 3： 输入：nums = [1,3,6], k = 3 输出：3 解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。   提示： * 1 <= nums.length <= 104 * 0 <= nums[i] <= 104 * 0 <= k <= 104

https://leetcode.cn/problems/smallest-range-ii/

1. 问题描述
给定一个整数数组 nums 和一个整数 k，你可以对数组 nums 中的每个元素进行以下操作之一：
• 将 nums[i] 变为 nums[i] + k 或 nums[i] - k。
数组的 分数 定义为数组中最大元素和最小元素的差值。你的任务是在更改每个下标对应的值之后，返回 nums 的最小分数。

2. 思路分析
为了最小化数组的分数，即最大值与最小值的差值，我们需要找到一种方式将经过操作后的最大值和最小值尽量靠近。由于每个元素可以增加或减少 k，可以通过调整数组的极值（最大值和最小值）来实现分数的最小化。

3. 分析过程
1. 排序数组：
• 首先将数组 nums 排序，方便我们找到最大值和最小值。排序后，nums[0] 是数组的最小元素，nums[n-1] 是最大元素。
2. 操作的关键：
• 将 nums[0] 增加 k，将 nums[n-1] 减少 k，这可能缩小最大和最小值之间的差距。
• 我们可以对每一个位置 i 尝试操作，设定 nums[0] + k 和 nums[i + 1] - k 为新的最小值，同时设定 nums[n-1] - k 和 nums[i] + k 为新的最大值。通过在每一个可能的分割点计算新的最大值和最小值，我们可以找到最小分数。
3. 比较最小分数：
• 通过每次调整后的最大值与最小值的差，比较找到最优解。

4. 具体步骤
1. 将数组 nums 排序。
2. 初始化最小分数为 nums[n-1] - nums[0]，即排序后数组的原始最大值和最小值之差。
3. 遍历数组，针对每个下标 i，计算：
• 新的最大值：max(nums[n-1] - k, nums[i] + k)。
• 新的最小值：min(nums[0] + k, nums[i + 1] - k)。
• 更新最小分数。
4. 返回最小分数。

5. 代码实现

6. 复杂度分析
• 时间复杂度：
• 排序数组的时间复杂度为 ，其中 n 是数组的长度。
• 遍历数组计算新最大值和最小值的时间复杂度为 。
• 因此，总的时间复杂度为 。
• 空间复杂度：
• 只使用了常数个额外的变量，空间复杂度为 。

2024.10.22 T3184. 构成整天的下标对数目 I

3184. 构成整天的下标对数目 I - 力扣（LeetCode）

3184. 构成整天的下标对数目 I - 给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。 整天 定义为时间持续时间是 24 小时的 整数倍 。 例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。   示例 1： 输入： hours = [12,12,30,24,24] 输出： 2 解释： 构成整天的下标对分别是 (0, 1) 和 (3, 4)。 示例 2： 输入： hours = [72,48,24,3] 输出： 3 解释： 构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。   提示： * 1 <= hours.length <= 100 * 1 <= hours[i] <= 109

https://leetcode.cn/problems/count-pairs-that-form-a-complete-day-i/

1. 问题描述
给定一个整数数组 hours，表示以小时为单位的时间。需要找出数组中所有下标对 (i, j)，使得：
1. i < j，即下标 i 小于 j。
2. hours[i] + hours[j] 构成整天，即时间和是 24 的倍数。
整天的定义是指时间的持续时间是 24 小时的整数倍。例如：
• 1 天是 24 小时，
• 2 天是 48 小时，
• 3 天是 72 小时，
• 依此类推。
返回满足上述条件的下标对 (i, j) 的数目。

2. 思路分析
该问题的核心是找出满足 hours[i] + hours[j] 为 24 的倍数的下标对 (i, j)。暴力解法可以通过双重循环遍历数组中所有的下标对 (i, j)，检查它们的和是否为 24 的倍数。我们可以直接使用模运算 % 来检查是否满足条件 (hours[i] + hours[j]) % 24 == 0。
步骤解析：
1. 双重遍历：外层遍历数组的每个元素 hours[i]，内层遍历该元素之后的所有元素 hours[j]，即 j > i。
2. 检查条件：对于每一对 hours[i] 和 hours[j]，检查 (hours[i] + hours[j]) % 24 == 0 是否成立。
3. 计数：若条件成立，计数器加 1。

3. 实现步骤
1. 初始化一个计数器 cnt，用于记录满足条件的下标对数目。
2. 使用两个嵌套的循环来遍历数组 hours，外层循环变量 i 从 0 到 n-1，内层循环变量 j 从 i+1 到 n-1。
3. 对于每一对 (i, j)，判断 hours[i] + hours[j] 是否是 24 的倍数。如果是，则将计数器 cnt 加 1。
4. 返回最终的计数器值。

4. 代码实现

5. 复杂度分析
• 时间复杂度：。该算法使用了双重循环来遍历所有的下标对 (i, j)，其中 n 是数组 hours 的长度。
• 空间复杂度：。只使用了常数个额外变量来存储数组的大小和计数器。

2024.10.23 T3185. 构成整天的下标对数目 II

3185. 构成整天的下标对数目 II - 力扣（LeetCode）

3185. 构成整天的下标对数目 II - 给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。 整天 定义为时间持续时间是 24 小时的 整数倍 。 例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。   示例 1： 输入： hours = [12,12,30,24,24] 输出： 2 解释： 构成整天的下标对分别是 (0, 1) 和 (3, 4)。 示例 2： 输入： hours = [72,48,24,3] 输出： 3 解释： 构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。   提示： * 1 <= hours.length <= 5 * 105 * 1 <= hours[i] <= 109

https://leetcode.cn/problems/count-pairs-that-form-a-complete-day-ii/solutions/2928185/gou-cheng-zheng-tian-de-xia-biao-dui-shu-4ijs/

1. 问题描述
给定一个整数数组 hours，表示以小时为单位的时间。需要找出数组中所有下标对 (i, j)，使得：
1. i < j，即下标 i 小于 j。
2. hours[i] + hours[j] 构成整天，即时间和是 24 小时的倍数（如 24、48、72 等）。
返回满足上述条件的下标对 (i, j) 的数目。

2. 思路分析
要解决这个问题，关键在于找出满足 hours[i] + hours[j] 为 24 的倍数的下标对 (i, j)。为此，我们可以对每个 hours[i] 的值取模 24，并统计每个模值的频率。对于每个 hours[i]，我们可以寻找满足条件的 hours[j]，即 (hours[i] + hours[j]) % 24 == 0。
通过分析，这意味着对于每个 hours[i]，我们需要检查是否存在某个 hours[j] 使得 (hours[j] % 24) 等于 (24 - hours[i] % 24) % 24，即相加能整除 24。

3. 具体步骤
1. 使用一个长度为 24 的数组 freq 来统计每个模 24 值的频率。freq[r] 代表数组中模 24 余数为 r 的元素个数。
2. 遍历数组 hours，对于每个 hours[i]，我们需要找到 hours[j]，满足 (hours[i] + hours[j]) % 24 == 0，即 (24 - hours[i] % 24) % 24。通过 freq 数组记录的频率，可以直接得知有多少个之前的元素可以与 hours[i] 配对。
3. 记录每次的有效配对数，并更新 freq 数组以包含当前 hours[i] 的模 24 余数。
这种方法利用了频率数组优化了时间复杂度，从原来的 降低到 。

4. 代码实现

5. 复杂度分析
• 时间复杂度：
• 遍历数组 hours 的时间复杂度为 ，其中 n 是数组的长度。对于每个元素的模运算和频率数组的更新，都是常数时间操作。因此，总的时间复杂度为 。
• 空间复杂度：
• 使用了一个长度为 24 的频率数组 freq，因此空间复杂度为 ，即常数空间复杂度。

2024.10.24 T3175. 找到连续赢 K 场比赛的第一位玩家

3175. 找到连续赢 K 场比赛的第一位玩家 - 力扣（LeetCode）

3175. 找到连续赢 K 场比赛的第一位玩家 - 有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。 给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。 所有玩家从编号 0 到 n - 1 排成一列。 比赛进行方式如下： * 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。 * 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。 这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。 请你返回这个比赛的赢家编号。   示例 1： 输入：skills = [4,2,6,3,9], k = 2 输出：2 解释： 一开始，队列里的玩家为 [0,1,2,3,4] 。比赛过程如下： * 玩家 0 和 1 进行一场比赛，玩家 0 的技能等级高于玩家 1 ，玩家 0 胜出，队列变为 [0,2,3,4,1] 。 * 玩家 0 和 2 进行一场比赛，玩家 2 的技能等级高于玩家 0 ，玩家 2 胜出，队列变为 [2,3,4,1,0] 。 * 玩家 2 和 3 进行一场比赛，玩家 2 的技能等级高于玩家 3 ，玩家 2 胜出，队列变为 [2,4,1,0,3] 。 玩家 2 连续赢了 k = 2 场比赛，所以赢家是玩家 2 。 示例 2： 输入：skills = [2,5,4], k = 3 输出：1 解释： 一开始，队列里的玩家为 [0,1,2] 。比赛过程如下： * 玩家 0 和 1 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。 * 玩家 1 和 2 进行一场比赛，玩家 1 的技能等级高于玩家 2 ，玩家 1 胜出，队列变为 [1,0,2] 。 * 玩家 1 和 0 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为 [1,2,0] 。 玩家 1 连续赢了 k = 3 场比赛，所以赢家是玩家 1 。   提示： * n == skills.length * 2 <= n <= 105 * 1 <= k <= 109 * 1 <= skills[i] <= 106 * skills 中的整数互不相同。

https://leetcode.cn/problems/find-the-first-player-to-win-k-games-in-a-row/

1. 问题描述
有 n 位玩家正在进行一场比赛，玩家编号依次为 0 到 n-1。给定一个长度为 n 的整数数组 skills 和一个正整数 k，其中 skills[i] 表示第 i 位玩家的技能等级，并且所有玩家的技能等级互不相同。
比赛按照以下规则进行：
1. 队列最前面的两名玩家进行比赛，技能等级更高的玩家获胜。
2. 获胜者留在队列的开头，失败者排到队列的末尾。
3. 比赛的赢家是第一位连续赢下 k 场比赛的玩家。
要求返回这场比赛的赢家的编号。

2. 思路分析
比赛是基于技能等级的对抗，技能等级高的玩家总是胜利者。因此，只需要找到第一个连续赢下 k 场比赛的玩家即可。为了模拟比赛过程并找到赢家，可以采取如下步骤：
1. 初始化赢家：假设最开始第一个玩家为赢家，并记住当前赢家已经赢了多少场比赛。
2. 遍历队列：从第二个玩家开始，依次与当前的赢家对抗：
• 如果当前玩家的技能等级比赢家高，则当前玩家成为新的赢家，且他的连胜场数重置为 1。
• 如果当前玩家的技能等级比赢家低，则赢家的连胜场数增加 1。
3. 停止条件：当某个玩家连胜次数达到 k 时，比赛结束，该玩家就是赢家。
如果玩家的技能等级数组长度 m 比 k 小，那么最大的技能玩家就是赢家，因为技能最大的玩家最终总会获胜。

3. 具体步骤
1. 初始化赢家为第一个玩家，记录他的技能等级和当前连胜次数。
2. 从第二个玩家开始，与当前赢家进行对抗：
• 如果当前玩家的技能等级更高，则更新赢家，并重置连胜次数为 1。
• 否则，增加当前赢家的连胜次数。
3. 如果赢家的连胜次数达到 k，比赛结束，返回赢家编号。

4. 代码实现

5. 复杂度分析
• 时间复杂度：
• 该算法只需要遍历数组 skills 一次，时间复杂度为 ，其中 n 是数组 skills 的长度。
• 空间复杂度：
• 只使用了常数个额外变量，空间复杂度为 。

2024.10.25 T3180. 执行操作可获得的最大总奖励 I

3180. 执行操作可获得的最大总奖励 I - 力扣（LeetCode）

3180. 执行操作可获得的最大总奖励 I - 给你一个整数数组 rewardValues，长度为 n，代表奖励的值。 最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ： * 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。 * 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。 以整数形式返回执行最优操作能够获得的 最大 总奖励。   示例 1： 输入：rewardValues = [1,1,3,3] 输出：4 解释： 依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。 示例 2： 输入：rewardValues = [1,6,4,3,2] 输出：11 解释： 依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。   提示： * 1 <= rewardValues.length <= 2000 * 1 <= rewardValues[i] <= 2000

https://leetcode.cn/problems/maximum-total-reward-using-operations-i/

1. 问题描述
给定一个整数数组 rewardValues，表示每个下标对应的奖励值。最初你的总奖励为 x = 0，且所有下标都是未标记的。你可以执行以下操作任意次：
1. 从区间 [0, n-1] 中选择一个未标记的下标 i。
2. 如果 rewardValues[i] 大于你当前的总奖励 x，则将 rewardValues[i] 加到你的总奖励 x 上，并将该下标 i 标记。
你的任务是通过执行最优操作获得最大的总奖励。
目标：返回你通过执行最优操作能够获得的最大总奖励。

2. 思路分析
本题的关键是：每次只能选择一个 rewardValues[i] 大于当前总奖励 x 的值来增加奖励。因此我们要通过合理的操作顺序，尽量选择对当前总奖励有增量作用的值，以最大化最终结果。
要解决这个问题，可以采取以下思路：
1. 排序奖励值：
• 由于每次只能选择当前总奖励 x 小于的值，因此我们需要优先考虑小的奖励值，逐步提升总奖励，确保后续更大的奖励值可以被选择。
2. 贪心策略：
• 从最小的奖励值开始逐步累加，每次选择尽量满足条件的最小奖励值。通过贪心选择较小的值，不仅可以提升总奖励，还能为后续选择更大的奖励值打下基础。
3. 动态规划思想：
• 可以使用动态规划来记录每一个可能的总奖励 x，并逐步更新。每当可以选择某个 rewardValues[i] 时，尝试将其加入总奖励，更新当前奖励的最大值。

3. 实现步骤
1. 排序：首先将 rewardValues 按升序排序，这样可以确保每次尽量先选取较小的值，逐步增加总奖励。
2. 动态规划数组：
• 使用一个动态规划数组 dp，其中 dp[j] 表示在总奖励为 j 时，能够达到的最大奖励值。
3. 遍历更新：
• 遍历每一个奖励值 rewardValues[i]，更新 dp 数组。在每次遍历中，检查是否可以将该值加入当前总奖励，并更新最大值。
4. 返回结果：最终返回总奖励的最大值。

4. 代码实现

5. 复杂度分析
• 时间复杂度：
• 排序部分：对 rewardValues 进行排序的时间复杂度为 O(n log n)，其中 n 是数组 rewardValues 的长度。
• 动态规划部分：在遍历过程中，双重循环的复杂度为 O(n * maxValue)，其中 maxValue 是 rewardValues 中的最大值。
• 因此总的时间复杂度为 O(n * maxValue)。
• 空间复杂度：
• 使用了长度为 maxValue 的 dp 数组，空间复杂度为 O(maxValue)。

2024.10.26 T3181. 执行操作可获得的最大总奖励 II

ps:真的恶心这个题😅不用位运算死活都是超时

3181. 执行操作可获得的最大总奖励 II - 力扣（LeetCode）

3181. 执行操作可获得的最大总奖励 II - 给你一个整数数组 rewardValues，长度为 n，代表奖励的值。 最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ： * 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。 * 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。 以整数形式返回执行最优操作能够获得的 最大 总奖励。   示例 1： 输入：rewardValues = [1,1,3,3] 输出：4 解释： 依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。 示例 2： 输入：rewardValues = [1,6,4,3,2] 输出：11 解释： 依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。   提示： * 1 <= rewardValues.length <= 5 * 104 * 1 <= rewardValues[i] <= 5 * 104

https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/

1. 问题描述
给定一个整数数组 rewardValues，表示每个下标的奖励值。初始总奖励 x 为 0，并且所有下标都是未标记的。可以执行以下操作任意次：
1. 从数组中选择一个未标记的下标 i。
2. 如果 rewardValues[i] 大于当前总奖励 x，则将其加到总奖励 x 上，并将该下标标记。
目标是通过执行最优操作获得最大的总奖励。

2. 代码实现思路
本代码通过使用贪心和位运算来找到可以获得的最大总奖励。以下是实现细节的分析。
1. 预处理：
• 首先，找到数组中的最大奖励值 maxReward，这是所有奖励值中的上界，最终的总奖励不会超过 2 * maxReward - 1。
• 创建一个布尔数组 isRewardUsed，用于记录是否使用过某个奖励值。这一数组帮助我们避免重复计算和多次处理同一奖励值。
2. 快速检查特定条件：
• 遍历所有奖励值，如果当前奖励 reward 等于 maxReward，直接跳过，因为我们关心的是所有其他奖励值对最终总奖励的贡献。
• 如果 reward 为 maxReward - 1 或 maxReward - reward - 1，则直接返回 2 * maxReward - 1，因为可以通过选择这些奖励值直接得到接近上限的总奖励。
3. 构建可行的奖励状态：
• 使用位运算的 bitset，将 rewardStates 初始化为 1，表示当前的总奖励为 0。
• 遍历所有奖励值，如果某个奖励值 reward 已经被标记为可用，则通过位移将其值添加到当前的状态集合 rewardStates。
• 通过左移和右移的组合更新 rewardStates，表示所有可以通过累加奖励值而达到的状态。
4. 计算最大总奖励：
• 从 maxReward - 1 开始向下检查每一个可能的奖励状态，寻找最大可能的总奖励。如果 rewardStates 中某一位被置为 1，则表示我们可以达到的最大奖励为 maxReward + reward。
• 如果没有找到合适的奖励状态，默认返回 maxReward。

3. 代码实现细节
1. 找到最大值 maxReward：
• max_element 获取数组中的最大值，用于确定奖励上限，减少后续计算中的搜索空间。
2. 条件检查：
• 在遍历过程中，针对 maxReward - 1 和 maxReward - reward - 1 的检查可以提前终止循环并返回接近上限的值。
3. 构建状态集合 rewardStates：
• 通过 bitset 记录可以通过奖励组合达到的所有状态，这种位移操作可以高效表示所有可能的累加状态。
• 通过左移和右移动态调整 rewardStates，结合或运算将新的奖励状态累加进集合，保证所有可能的奖励值状态都被记录。
4. 确定最大总奖励：
• 从 maxReward - 1 开始，逐步向下检查 rewardStates 的可行状态，确定能够达到的最大奖励组合。

4. 代码实现

5. 复杂度分析

• 时间复杂度：代码的主要复杂度来自于遍历 rewardValues 数组的 处理，以及使用 bitset 来更新和检查状态，位移操作的复杂度为常数。因此总的时间复杂度为 。

• 空间复杂度：使用了大小为 maxReward 的布尔数组 isRewardUsed 和位宽为 50000 的 bitset，总的空间复杂度为 。

2024.10.27 T684 . 冗余连接

684. 冗余连接 - 力扣（LeetCode）

684. 冗余连接 - 树可以看成是一个连通且 无环 的 无向 图。 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。   示例 1： [https://pic.leetcode-cn.com/1626676174-hOEVUL-image.png] 输入: edges = [[1,2], [1,3], [2,3]] 输出: [2,3] 示例 2： [https://pic.leetcode-cn.com/1626676179-kGxcmu-image.png] 输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4]   提示: * n == edges.length * 3 <= n <= 1000 * edges[i].length == 2 * 1 <= ai < bi <= edges.length * ai != bi * edges 中无重复元素 * 给定的图是连通的

https://leetcode.cn/problems/redundant-connection/

1. 问题描述
给定一个有 n 个节点的树（节点值为 1 到 n），在树中添加一条额外的边，使得图变成了一个包含 n 个节点的无向图。这条额外的边连接了两个原本已经在树中的节点，因此它会引入一个环。
你需要找到这条可以删除的边，使得删除该边后，图中的剩余部分仍然是一棵有 n 个节点的树。如果有多个符合条件的答案，返回输入中最后出现的那条边。

2. 解决方案
该问题的本质是寻找添加到树中的冗余边，这条边会导致树中出现一个环。为了找出这条边，可以使用并查集（Union-Find）来检测环的出现。

3. 思路分析
1. 并查集简介：
• 并查集是一种数据结构，用于高效地解决集合的合并和查找问题。
• 并查集中的每个节点都指向它的父节点，通过路径压缩优化查找操作，使得查找操作的时间复杂度接近 O(1)。
• 合并操作则用于将两个集合合并在一起。
2. 检测环的出现：
• 初始化并查集，节点范围是 1 到 n。
• 遍历每条边 (u, v)：
• 使用 find 操作检查 u 和 v 是否已经在同一个集合中。
• 如果 u 和 v 已经在同一个集合中，则添加该边会导致环的出现，返回这条边。
• 否则，将 u 和 v 合并在一起。
• 若遍历完所有边都未找到重复边，则返回空数组（根据题意，实际上不会出现这种情况）。

4. 代码实现细节
1. 并查集类 UnionFind：
• find 方法：查找节点 x 的根节点，并在查找过程中进行路径压缩，将 x 直接连到它的根节点，减少查找路径长度。
• unite 方法：将 x 和 y 合并到同一个集合中，如果它们已经在同一个集合中，则返回 false，表示合并失败，说明当前边 u, v 会导致环的形成。
2. 主算法 findRedundantConnection：
• 初始化 UnionFind 对象 uf，并根据 edges 的数量设置并查集的大小。
• 遍历 edges，对每一条边进行 unite 操作：
• 如果 unite 返回 false，则说明这条边使得两个节点已经在同一个集合中，即添加这条边后形成了环，因此返回该边。

5. 代码实现

6. 复杂度分析
• 时间复杂度：
• 并查集的 find 和 unite 操作的时间复杂度接近 ，因为使用了路径压缩。遍历所有边的复杂度为 ，因此总的时间复杂度为 。
• 空间复杂度：
• 使用了一个大小为 n+1 的 parent 数组来记录每个节点的父节点，因此空间复杂度为 。

2024.10.28 T685 . 冗余连接 II

685. 冗余连接 II - 力扣（LeetCode）

685. 冗余连接 II - 在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。 输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。 返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。   示例 1： [https://assets.leetcode.com/uploads/2020/12/20/graph1.jpg] 输入：edges = [[1,2],[1,3],[2,3]] 输出：[2,3] 示例 2： [https://assets.leetcode.com/uploads/2020/12/20/graph2.jpg] 输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]] 输出：[4,1]   提示： * n == edges.length * 3 <= n <= 1000 * edges[i].length == 2 * 1 <= ui, vi <= n

https://leetcode.cn/problems/redundant-connection-ii/

1. 问题分析
给定的有向图中的多余边可能出现以下两种情况之一：
• 情况 1：某个节点有两个父节点（入度为 2）。在这种情况下，我们需要检查两条导致入度为 2 的边中，哪一条是冗余的。
• 情况 2：图中形成了一个环。在这种情况下，我们需要找到导致环的那条边，并将其删除。

2. 解题思路
• 查找入度为 2 的节点：首先，我们遍历所有边，记录每个节点的入度。如果发现某个节点有两个父节点，就记录这两条边。
• 构建并查集：使用并查集逐条添加边来检测环的存在。如果某条边导致了两个节点在同一个集合中，则说明这条边是导致环的边。
• 判断并删除多余边：
• 如果有一个节点有两个父节点，那么检查删除哪一条不会形成环。
• 如果没有入度为 2 的节点，只存在环，则删除导致环的边。

3. 代码解释
• 记录入度为 2 的情况：
• 使用 parent 数组记录每个节点的父节点。
• 如果发现某个节点的父节点已经存在，说明该节点有两个父节点，记录两条边 edge1 和 edge2。
• 环检测：
• 使用并查集逐条处理边，跳过 edge2（如果存在）。
• 如果发现无法合并（即两个节点已经在同一个集合中），说明存在环。
• 返回结果：
• 如果 edge2 存在且没有环，则返回 edge2。
• 如果 edge2 存在且有环，则返回 edge1。
• 如果 edge2 不存在但有环，则返回 lastEdge，即形成环的那条边。

4. 代码实现

5. 复杂度分析

• 时间复杂度：遍历每条边的时间为 ，并查集操作近似为常数时间，因此总体时间复杂度为 。

• 空间复杂度：使用了并查集和辅助数组，空间复杂度为 。

2024.10.29 T3211. 生成不含相邻零的二进制字符串

3211. 生成不含相邻零的二进制字符串 - 力扣（LeetCode）

3211. 生成不含相邻零的二进制字符串 - 给你一个正整数 n。 如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。 返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。   示例 1： 输入： n = 3 输出： ["010","011","101","110","111"] 解释： 长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。 示例 2： 输入： n = 1 输出： ["0","1"] 解释： 长度为 1 的有效字符串有："0" 和 "1"。   提示： * 1 <= n <= 18

https://leetcode.cn/problems/generate-binary-strings-without-adjacent-zeros/

1. 问题描述
给定一个正整数 n，我们需要生成所有长度为 n 的有效二进制字符串。
有效字符串的定义是：一个二进制字符串 x 的所有长度为 2 的子字符串中都包含至少一个 "1"。换句话说，不能有连续两个 "0" 出现。
目标是返回所有长度为 n 的有效二进制字符串，以任意顺序排列。

2. 解决方案
我们可以使用深度优先搜索 (DFS) 来生成所有满足条件的二进制字符串。DFS 可以帮助我们构建字符串的每一个位置，并在递归过程中生成所有可能的组合。

3. 实现思路
1. DFS 递归构建字符串：
• 使用 DFS 递归地构建二进制字符串。
• 在每一步中，我们可以选择添加 "0" 或 "1"，但要满足有效字符串的条件。
2. 有效性条件：
• 如果当前字符串的最后一个字符是 "1"，则可以添加 "0" 或 "1"（因为不会出现连续的 "0"）。
• 如果当前字符串的最后一个字符是 "0"，则只能添加 "1"（以避免连续出现两个 "0"）。
3. 终止条件：
• 当构建的字符串长度达到 n 时，将其加入结果集。
4. 回溯过程：
• 在递归过程中，通过回溯（即 pop_back）的方式来撤销上一步的选择，并继续探索其他可能的组合。

4. 代码实现细节
1. DFS 函数定义：
• 使用了 C++ 中的 lambda 函数来定义递归的 dfs，并通过引用捕获来支持递归调用。
2. 递归构建字符串：
• 每次递归调用中，根据字符串的末尾字符来决定是否可以添加 "0" 和 "1"。
• 使用 s.push_back() 添加字符，随后通过 s.pop_back() 进行回溯，撤销添加的字符。
3. 字符串保存与结果构建：
• 当字符串的长度达到 n 时，将其添加到结果向量 ans 中。

5. 代码实现

6. 复杂度分析
• 时间复杂度：。
• 由于每个位置最多有 2 种选择（在满足条件时可以选择 "0" 或 "1"），因此可能的组合数是指数级别的 。
• 不过，实际生成的字符串数量会少于 ，因为有部分字符串（包含连续 "0" 的）不符合条件。
• 空间复杂度：。
• 主要是递归调用栈的深度，以及构建字符串的存储。

2024.10.30 T3216. 交换后字典序最小的字符串

3216. 交换后字典序最小的字符串 - 力扣（LeetCode）

3216. 交换后字典序最小的字符串 - 给你一个仅由数字组成的字符串 s，在最多交换一次 相邻 且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。 如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。   示例 1： 输入： s = "45320" 输出： "43520" 解释： s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。 示例 2： 输入： s = "001" 输出： "001" 解释： 无需进行交换，因为 s 已经是字典序最小的。   提示： * 2 <= s.length <= 100 * s 仅由数字组成。

https://leetcode.cn/problems/lexicographically-smallest-string-after-a-swap/

1. 问题描述
给定一个仅由数字组成的字符串 s，要求通过至多一次交换相邻且具有相同奇偶性的数字，使得得到的字符串是字典序最小的字符串。
• 相同奇偶性：两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9 是奇数，2 和 4 是偶数。
• 字典序最小：希望结果字符串在字典序上尽可能小。

2. 思路分析
1. 逐对比较字符：
• 从字符串的左侧开始遍历每一对相邻字符 s[i] 和 s[i + 1]。
• 如果 s[i] > s[i + 1] 且 s[i] 和 s[i + 1] 具有相同奇偶性，则可以交换这两个字符，使得当前字符串更接近字典序最小。
2. 交换条件：
• 仅在满足 s[i] > s[i + 1] 且 s[i] 和 s[i + 1] 具有相同奇偶性时，执行交换。
• 由于只能交换一次相邻字符，因此找到第一次满足条件的相邻对并交换即可。
3. 提前结束：
• 在找到满足条件的第一对并完成交换后，可以立即结束循环并返回结果，因为题目只允许一次交换操作。

3. 代码实现细节
1. 遍历字符串：
• 使用 for 循环从 0 遍历到 len - 2，依次检查每对相邻字符 s[i] 和 s[i + 1]。
2. 检查交换条件：
• 通过条件 s[i] > s[i + 1] 确保字典序变小。
• 通过条件 (s[i] % 2 == s[i + 1] % 2) 确保两个数字具有相同奇偶性。
3. 执行交换：
• 满足条件时，执行 swap(s[i], s[i + 1]) 并立即跳出循环返回结果。

4. 代码实现

5. 复杂度分析
• 时间复杂度：，其中 n 是字符串的长度。最坏情况下，需要遍历整个字符串一次。
• 空间复杂度：，只修改输入字符串 s 并在原地操作，不需要额外空间。

2024.10.31 T3165. 不包含相邻元素的子序列的最大和

3165. 不包含相邻元素的子序列的最大和 - 力扣（LeetCode）

3165. 不包含相邻元素的子序列的最大和 - 给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi]。 对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素 的 子序列 的 最大 和。 返回所有查询的答案之和。 由于最终答案可能非常大，返回其对 109 + 7 取余 的结果。 子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。   示例 1： 输入：nums = [3,5,9], queries = [[1,-2],[0,-3]] 输出：21 解释： 执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。 执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。 示例 2： 输入：nums = [0,-1], queries = [[0,-5]] 输出：0 解释： 执行第 1 个查询后，nums = [-5,-1]，不包含相邻元素的子序列的最大和为 0（选择空子序列）。   提示： * 1 <= nums.length <= 5 * 104 * -105 <= nums[i] <= 105 * 1 <= queries.length <= 5 * 104 * queries[i] == [posi, xi] * 0 <= posi <= nums.length - 1 * -105 <= xi <= 105

https://leetcode.cn/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/

1. 问题描述
给定一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi] 表示一次查询操作。每次查询要求将 nums[posi] 更新为 xi，然后计算数组 nums 中不包含相邻元素的子序列的最大和。目标是返回所有查询的答案之和，并对 10^9 + 7 取余。

2. 解决方案
为了快速求解更新操作后数组中不包含相邻元素的最大子序列和，可以使用线段树和动态规划思想。线段树可以帮助我们高效地处理区间的更新和查询操作。下面是实现思路的详细分析。

3. 实现思路
1. 四种状态表示：
• 我们定义一个线段树节点结构体 SegmentNode，用来记录不同选择条件下的最大和。这些状态包括：
• maxBothEnds: 包含区间左右两端点的最大和。
• maxStartOnly: 只包含区间左端点的最大和。
• maxEndOnly: 只包含区间右端点的最大和。
• maxNoEnds: 不包含区间两端点的最大和。
2. 线段树构建：
• 初始化时构建一棵线段树，使得每个叶子节点对应 nums 的一个元素，非叶子节点存储子区间的最大和。
• 当构建叶子节点时，如果该位置的值为负数，取 0 来表示不选择该元素（避免负贡献）。
3. 更新线段树：
• 对于每个查询，先更新 nums 数组中的对应位置 posi，然后在线段树中进行更新。
• 更新过程需要递归更新自底向上的所有父节点。
4. 合并节点状态：
• 在每个节点更新或构建过程中，通过 pushUp 函数将左右子区间的状态合并，计算当前节点的四种状态的最大值。
• 例如，maxBothEnds 可以通过将左子节点的 maxBothEnds 与右子节点的 maxEndOnly 合并，或左子节点的 maxStartOnly 与右子节点的 maxBothEnds 合并得到。
5. 累积结果：
• 每次更新线段树后，将根节点 maxBothEnds 的值加到结果中，并对 10^9 + 7 取余。

4. 代码实现细节
1. 构建线段树：
• build 方法递归地构建线段树，将每个叶子节点的初始值设为元素值（若为负则取 0）。递归返回时使用 pushUp 方法合并子节点状态。
2. 更新操作：
• update 方法更新指定位置的值，然后向上更新整个树，使得每个父节点的状态都保持最新。
3. 计算最大和：
• 每次更新后，通过根节点的 maxBothEnds 获取当前不包含相邻元素的最大和，并累积到 result。

5. 代码实现

6. 复杂度分析
• 时间复杂度：
• 构建线段树的时间复杂度为 。
• 每次更新的时间复杂度为 。
• 总时间复杂度为 ，其中 为查询的数量。
• 空间复杂度：
• 线段树的存储复杂度为 ，因为我们存储了每个节点的四种状态信息。