type
status
date
slug
summary
tags
category
icon
password
comment
2024.11.30 十一月，完结撒花🎉🎉🎉！！！
每日一题2024.11.01 T3259. 超级饮料的最大强化能量2024.11.02 T3226. 使两个整数相等的位更改次数2024.11.03 T638 . 大礼包2024.11.04 T633 . 平方数之和2024.11.05 T3222. 求出硬币游戏的赢家2024.11.06 T3254. 长度为 K 的子数组的能量值 I2024.11.07 T3255. 长度为 K 的子数组的能量值 II2024.11.08 T3235. 判断矩形的两个角落是否可达2024.11.09 T3242. 设计相邻元素求和服务2024.11.10 T540 . 有序数组中的单一元素2024.11.11 T1547. 切棍子的最小成本2024.11.12 T3258. 统计满足 K 约束的子字符串数量 I2024.11.13 T3261. 统计满足 K 约束的子字符串数量 II2024.11.14 T3249. 统计好节点的数目2024.11.15 T3239. 最少翻转次数使二进制矩阵回文 I2024.11.16 T3240. 最少翻转次数使二进制矩阵回文 II2024.11.17 T825 . 适龄的朋友2024.11.18 T661 . 图片平滑器2024.11.19 T3243. 新增道路查询后的最短距离 I2024.11.20 T3244. 新增道路查询后的最短距离 II2024.11.21 T3248. 矩阵中的蛇2024.11.22 T3233. 统计不是特殊数字的数字数量2024.11.23 T3238. 求出胜利玩家的数目2024.11.24 T632 . 最小区间2024.11.25 T743 . 网络延迟时间2024.11.26 T3206. 交替组 I2024.11.27 T3208. 交替组 II2024.11.28 T3250. 单调数组对的数目 I2024.11.29 T3251. 单调数组对的数目 II2024.11.30 T3232. 判断是否可以赢得数字游戏
每日一题
2024.11.01 T3259. 超级饮料的最大强化能量
- 问题描述
- 如果从一种饮料切换到另一种饮料，需要等待一个小时来适应，这个小时将不提供任何强化能量。
- 可以选择从任意一种能量饮料开始饮用。
给定两个整数数组
energyDrinkA 和 energyDrinkB，它们的长度均为 n，分别表示每小时饮用 A、B 两种不同能量饮料所能提供的强化能量。你需要在每个小时选择饮用其中一种饮料，以最大化在 n 小时内的总强化能量。限制条件：
- 解决方案
为了解决这个问题，可以使用动态规划来计算在每个小时选择不同饮料类型所能获得的最大强化能量。关键在于合理地记录和更新不同情况下的选择：是否切换饮料，或者保持不变。
- 实现思路
- 状态定义：
- 定义
dp[0][i]表示在第i小时选择饮用能量饮料 A 的情况下，能够获得的最大强化能量。 - 定义
dp[1][i]表示在第i小时选择饮用能量饮料 B 的情况下，能够获得的最大强化能量。 - 状态转移：
- 在第
i小时选择饮料 A，有两种情况： - 在第
i-1小时选择了饮料 A，则dp[0][i] = dp[0][i-1] + energyDrinkA[i-1]。 - 在第
i-2小时选择了饮料 B，则dp[0][i] = dp[1][i-2] + energyDrinkA[i-1]。 - 因此，
dp[0][i] = max(dp[0][i-1] + energyDrinkA[i-1], dp[1][i-2] + energyDrinkA[i-1])。 - 同理，在第
i小时选择饮料 B： - 在第
i-1小时选择了饮料 B，则dp[1][i] = dp[1][i-1] + energyDrinkB[i-1]。 - 在第
i-2小时选择了饮料 A，则dp[1][i] = dp[0][i-2] + energyDrinkB[i-1]。 - 因此，
dp[1][i] = max(dp[1][i-1] + energyDrinkB[i-1], dp[0][i-2] + energyDrinkB[i-1])。 - 初始条件：
dp[0][1] = energyDrinkA[0]：如果从第一个小时选择饮料 A，获得的能量为energyDrinkA[0]。dp[1][1] = energyDrinkB[0]：如果从第一个小时选择饮料 B，获得的能量为energyDrinkB[0]。- 结果：
- 计算完
n小时的最大强化能量后，结果为max(dp[0][n], dp[1][n])
- 代码实现细节
- 初始化状态：
- 初始化
dp[0][1]和dp[1][1]表示在第一小时选择饮料 A 或饮料 B 时的能量值。 - 状态转移方程：
dp[0][i]和dp[1][i]的值通过前面两种可能的选择转移而来，即维持相同饮料或切换饮料。- 结果返回：
- 最后返回
max(dp[0][n], dp[1][n])，表示在n小时结束时，选择任意饮料的最大强化能量。
- 代码实现
- 复杂度分析
- 时间复杂度：，因为需要遍历每个小时 次，并在每次遍历时进行常数操作。
- 空间复杂度：，使用了一个大小为 的二维数组存储每小时的状态。
2024.11.02 T3226. 使两个整数相等的位更改次数
- 问题描述
给定两个正整数
n 和 k。可以选择 n 的二进制表示中任意一个值为 1 的位，将其改为 0。返回将 n 变成 k 所需要的最少更改次数。如果无法实现，返回 -1。- 问题分析
- 判断是否可以实现：
- 要将
n变为k，k的每一位1只能来自n中已有的1。换句话说，k中的所有1位必须出现在n中的1位位置上。 - 通过位运算
(n | k) == n可以判断是否可以实现： - 如果
n的每个1位能完全覆盖k中的所有1位，则(n | k) == n。否则，返回1。 - 计算更改次数：
- 如果
(n | k) == n，说明可以将n变为k。 - 计算
n和k的不同位位置，即n和k的异或结果xorResult = n ^ k。 - 对
xorResult的每一位检查：每个1位表示n中一个需要更改的1位。 - 统计
xorResult中的1位数量即可得到最小更改次数。
- 代码实现细节
- 判断是否可以实现：
- 使用
(n | k) != n判断是否可以实现，如果k有n无法覆盖的1位，则直接返回1。 - 异或运算计算不同位：
xorResult = n ^ k将n和k不同的位标记为1，即需要更改的位。- 逐位检查
xorResult中的1，计数得到需要更改的位数。 - 右移检查每位：
- 使用
while (xorResult > 0)循环，将xorResult每次右移一位，并检查当前位是否为1，若是则计数。
- 代码实现
- 复杂度分析
- 时间复杂度：，因为整数
n的二进制表示长度为 ，逐位检查异或结果的时间复杂度为 。
- 空间复杂度：，只使用了常数个额外变量。
2024.11.03 T638 . 大礼包
- 问题描述
在 LeetCode 商店中，有
n 件商品，每件商品都有对应的价格。同时，有一些大礼包以优惠价格捆绑销售一组商品。给定商品的单价数组 price、购物清单数组 needs 和大礼包数组 special，需要返回满足购物清单所需的最低花费，允许无限次使用大礼包。- 解决思路
- 状态定义：
- 用
needs数组表示当前需要购买的商品数量。 - 用
currentCost表示当前已花费的金额。 - 递归与深度优先搜索：
- 使用深度优先搜索（DFS）来探索所有可能的购买组合。
- 每次递归时，首先检查当前花费是否已经超过已知的最低花费，若超过则剪枝。
- 计算单独购买剩余商品的花费，并更新最低花费。
- 考虑礼包购买：
- 对于每个大礼包，减少
needs中对应商品的数量，并增加礼包的价格到currentCost，然后进行递归。 - 递归结束后恢复
needs和currentCost，以便尝试其他礼包。 - 剪枝优化：
- 如果在计算过程中发现某种商品的需求量小于 0，则直接返回，避免无效的递归。
- 在每次递归时检查总花费是否变化，若没有变化则返回，减少不必要的计算。
- 代码实现细节
- 状态管理：
- 使用
std::vector<int> singleItemPrices存储商品价格。 - 使用
std::vector<std::vector<int>> bundleOffers存储大礼包的组成和价格。 - DFS 函数：
dfs(int currentCost, std::vector<int>& needs)实现了深度优先搜索逻辑。- 首先判断当前花费是否超过最低花费，进行剪枝。
- 计算当前
needs数组中所有未满足需求的商品的花费，并更新最低花费。 - 礼包处理：
- 通过递归尝试每种礼包的购买组合。
- 使用循环遍历每个礼包，更新需求并计算新的总花费，递归调用
dfs。 - 剪枝优化：
- 如果在某次递归中发现
needs中某个商品的数量为负，则直接返回以避免继续无效计算。 - 计算总花费后，如果未发生变化，则可以返回，进一步减少不必要的递归深度。
- 代码实现
- 复杂度分析
- 时间复杂度：最坏情况下，DFS 会遍历所有组合，复杂度为 ，其中
m是礼包的数量，n是商品的数量。实际运行时会由于剪枝显著降低复杂度。 - 空间复杂度：递归栈的深度为 ，需要存储每次递归的
needs状态和当前花费，额外的空间复杂度为 。
2024.11.04 T633 . 平方数之和
- 问题描述
给定一个非负整数
c，需要判断是否存在两个非负整数 a 和 b，使得 。- 解决思路
- 双指针方法：
- 设定两个指针
l和r，分别从 0 和 开始。 - 通过计算 与
c的比较来调整指针： - 如果 ，说明
r需要减小，以减小总和。 - 如果 ，说明
l需要增大，以增大总和。 - 如果 ，则找到了满足条件的
a和b。 - 结束条件：
- 当
l超过r时，遍历结束。
- 代码实现
- 代码详解
- 数据类型：使用
long long类型来避免在计算平方时溢出。 - 指针初始化：
l从 0 开始，r从 开始。- 主循环：使用
while循环，检查指针是否相交。 - 条件判断：
- 计算
sum = l * l + r * r。 - 根据
sum与c的比较，调整指针位置。
- 复杂度分析
- 时间复杂度：，因为
l和r的最大值均为 。 - 空间复杂度：，只使用了常量空间来存储指针和中间变量。
2024.11.05 T3222. 求出硬币游戏的赢家
- 问题描述
给定两个正整数
x 和 y，分别表示价值为 75 和 10 的硬币的数量。Alice 和 Bob 玩一个游戏，每轮游戏中玩家需要拿出硬币，总价值为 115。如果玩家无法做到这一点，他们将输掉游戏。Alice 先手，Bob 后手。两名玩家都采取最优策略，要求判断游戏的赢家。- 思路分析
- 游戏逻辑：
- 每轮游戏中，玩家需要组合出总价值为 115 的硬币。可以用硬币的组合如下：
- 1 个 75 的硬币和 4 个 10 的硬币。
- 玩家需要在每轮消耗 1 个 75 的硬币和 4 个 10 的硬币。
- 胜负判断：
- 游戏进行到某一轮时，如果当前玩家无法拿出总价值为 115 的硬币，则该玩家输掉游戏。
- Alice 先手，Bob 后手，轮流进行游戏。
- 最优策略：
- 两个玩家都采取最优策略，即尽可能多次使用组合
(1 * 75 + 4 * 10)直到无法进行时。
- 实现思路
- 计数循环：
- 初始化一个标记
tag，用于跟踪当前轮到的玩家。 - 每轮消耗
x和y，即x--和y -= 4。 - 轮流切换玩家，直到其中一个玩家无法满足条件（
x < 0或y < 0）。 - 返回结果：
- 如果
tag为true，表示最后一轮是 Bob 操作时无法进行，返回"Bob"输掉游戏。 - 如果
tag为false，表示 Alice 操作时无法进行，返回"Alice"输掉游戏。
- 代码实现
- 代码实现细节
- 变量初始化：
bool tag = 0，表示当前是 Alice 的回合。- 游戏循环：
- 每次循环中，消耗
1个 75 的硬币和4个 10 的硬币，并切换玩家。 - 循环条件是
x >= 1 && y >= 4，因为每轮需要满足该条件才能继续。 - 判断输赢：
- 当循环结束时，根据
tag的值返回输家。
- 复杂度分析
- 时间复杂度：，每次循环减少一个 75 的硬币和四个 10 的硬币，因此时间复杂度是线性的。
- 空间复杂度：，只使用了常数空间。
2024.11.06 T3254. 长度为 K 的子数组的能量值 I
2024.11.07 T3255. 长度为 K 的子数组的能量值 II
- 问题描述
- 如果该子数组中的元素是连续且严格递增的，那么能量值为该子数组中的最大元素。
- 如果不是严格递增的，则能量值为 -1。
给定一个整数数组
nums 和一个正整数 k，你需要计算所有长度为 k 的子数组的能量值。子数组的能量值定义如下：最终需要返回一个包含所有长度为
k 子数组的能量值的数组。- 解决思路
- 遍历每个子数组：对于每个长度为
k的子数组，我们需要判断它是否是严格递增的。如果是递增的，返回该子数组中的最大元素；如果不是递增的，返回 -1。 - 递增判断：为了判断一个子数组是否严格递增，可以遍历该子数组并确保每个元素都比前一个元素大。如果存在任何元素不满足这一条件，则认为该子数组不是递增的。
- 效率考虑：遍历每个子数组并检查是否递增，时间复杂度是
O(k)，而有n - k + 1个子数组需要检查。因此，总体的时间复杂度是O(k * (n - k + 1))，即O(n * k)。 - 返回结果：对于每个子数组，满足条件的情况下，返回该子数组的最大值，否则返回 -1。
- 代码实现
- 代码解释
- 遍历所有长度为
k的子数组： - 从索引
i = 0到i = n - k，依次考虑每个长度为k的子数组。 - 递增判断：
- 对于每个子数组，我们检查从
nums[i]到nums[i + k - 1]是否是严格递增的。 - 如果发现任意一对相邻元素
nums[j]和nums[j+1]不是递增的（即nums[j] + 1 != nums[j+1]），则设置isIncreasing为false，并跳出循环。 - 计算能量值：
- 如果子数组是递增的，能量值是该子数组的最大值
nums[i + k - 1]（即子数组的最后一个元素，因为它是最大元素）。 - 如果子数组不是递增的，能量值为 -1。
- 返回结果：
- 最终返回一个包含所有子数组能量值的数组
res。
- 复杂度分析
- 时间复杂度：，即对于每个长度为
k的子数组，我们需要检查其是否递增，且此操作在每个子数组上需要O(k)的时间。因此总的时间复杂度是 。 - 空间复杂度：，即需要一个数组
res来存储所有子数组的能量值，长度为 。
2024.11.08 T3235. 判断矩形的两个角落是否可达
- 问题描述
给定一个二维矩形，其左下角在原点
(0, 0)，右上角在 (xCorner, yCorner)，并且有多个圆，定义在 circles 数组中，每个圆的表示为 [xi, yi, ri]，表示圆心在 (xi, yi)，半径为 ri。需要判断是否存在一条从矩形的左下角到右上角的路径，这条路径完全在矩形内部，不会触碰或经过任何圆的内部和边界，仅在起点 (0, 0) 和终点 (xCorner, yCorner) 接触矩形边界。如果存在这样的路径，则返回
true，否则返回 false。- 解决思路
本问题要求在考虑多个圆障碍的情况下，确定是否可以找到一条从矩形左下角到右上角的路径。可以将此问题视为路径查找和碰撞检测问题。需要确保路径不接触或穿越任何圆的边界或内部，同时满足到达终点的条件。
- 具体步骤
- 判断矩形边界与圆的碰撞：
- 首先检查每个圆是否覆盖了矩形的左下角
(0, 0)或右上角(xCorner, yCorner)，如果有任何圆覆盖了这些点，则说明从起点或终点出发就不可行，直接返回false。 - 然后检查每个圆是否接触到矩形的左边界、下边界、上边界或右边界，以确定它们是否阻挡了路径。
- 深度优先搜索 (DFS) 检查圆的连接性：
- 使用 DFS 检查是否存在连接到矩形内部的圆群。
- 对于每一个圆，如果它连接到另一个圆，检查其距离和路径是否相交，如果相连，则继续进行递归。
- 如果在递归过程中发现某个圆接触到矩形边界或矩形的内部，则路径被阻断。
- 路径搜索的剪枝：
- 若当前圆无法从一个圆直接穿越到矩形的另一边，则返回
false。 - DFS 过程中，若某个圆已经被访问过，则跳过，以减少不必要的重复计算。
- 代码实现
- 代码解释
- 辅助函数
isPointInCircle： - 判断一个点
(x, y)是否位于圆(centerX, centerY, radius)的内部或边界上。 - DFS 函数
dfs： - 递归地检查圆与圆之间的连接性。
- 判断当前圆是否接触到矩形的边界或内部。如果接触则返回
true，表示路径被阻断。 - 主循环：
- 遍历每个圆，检查它是否覆盖了矩形的起点或终点。如果覆盖，则直接返回
false。 - 使用 DFS 检查当前圆是否与其他圆连接并穿越矩形的内部。如果存在这样的一组圆，则返回
false。
- 复杂度分析
- 时间复杂度：，其中
n是圆的数量。DFS 中对于每个圆需要检查其他圆，导致平方级别的时间复杂度。 - 空间复杂度：，递归深度和访问数组的存储空间。
2024.11.09 T3242. 设计相邻元素求和服务
- 问题描述
int adjacentSum(int value)：返回在grid中与value上、下、左、右相邻的元素之和。int diagonalSum(int value)：返回在grid中与value在对角线位置（左上、右上、左下、右下）相邻的元素之和。
给定一个
n x n 的二维数组 grid，其中包含从 0 到 n^2 - 1 的不重复整数。要求实现 NeighborSum 类，包括以下两个功能：- 解决思路
- 方向数组：
- 定义一个方向数组
dirs，表示四个正交相邻方向和四个对角线相邻方向： - 正交方向（上、下、左、右）：
{-1, 0},{1, 0},{0, -1},{0, 1} - 对角线方向（左上、右上、左下、右下）：
{-1, -1},{1, 1},{-1, 1},{1, -1} - 预处理：
- 使用一个一维数组
s来存储每个value的相邻元素和。 - 遍历
grid中的每个元素，根据其value和dirs数组，计算其四个正交相邻方向的和（存储在s[value][0]）以及四个对角线相邻方向的和（存储在s[value][1]）。 - 查询：
adjacentSum(int value)直接返回s[value][0]。diagonalSum(int value)直接返回s[value][1]。
- 代码实现
- 代码解释
- 构造函数
NeighborSum： - 使用方向数组
dirs遍历grid中的每个元素，并计算其正交相邻和对角线相邻元素之和。 s[v][0]保存值v的正交相邻之和，s[v][1]保存值v的对角线相邻之和。adjacentSum和diagonalSum：- 直接从
s数组中读取已计算的结果，分别返回正交相邻之和和对角线相邻之和。
- 复杂度分析
- 时间复杂度：。构造函数遍历整个
n x n的grid并计算相邻元素之和，复杂度为 。
- 空间复杂度：。存储每个元素的正交相邻和对角线相邻元素之和，使用了
s数组，空间复杂度为 。
2024.11.10 T540 . 有序数组中的单一元素
- 问题描述
给定一个仅由整数组成的有序数组
nums，其中每个元素都会出现两次，唯有一个数只会出现一次。要求找出并返回只出现一次的那个数。设计的解决方案需要满足 时间复杂度和 空间复杂度。- 思路分析
- 特征分析：
- 假设
nums中的元素除了唯一的单个元素外，都成对出现。 - 每对元素的第一个出现的位置是偶数索引，第二个出现的位置是奇数索引。
- 在唯一元素之前的索引对会满足该特性，而在唯一元素之后的索引对会被错位（即成对元素的第一个出现的位置为奇数，第二个位置为偶数）。
- 二分查找：
- 通过二分查找的思想来缩小范围，使用中点
mid来划分数组。 - 如果
mid与mid ^ 1相等（异或操作：将mid的最后一位从偶数变为奇数或从奇数变为偶数），则说明唯一元素在mid之后，可以移动左指针l = mid + 1。 - 如果
mid与mid ^ 1不相等，则说明唯一元素在mid之前，可以移动右指针r = mid。 - 终止条件：
- 当
l == r时，找到唯一的元素，返回nums[l]。
由于数组是有序的且每个元素都出现两次（除了那个唯一的元素），可以利用二分查找来达到 的时间复杂度。以下是具体的分析步骤：
3. 代码实现
- 代码详解
- 指针初始化：
l = 0，r = n - 1，用于二分查找范围。- 二分查找循环：
- 计算
mid为当前查找范围的中点。 - 使用
mid ^ 1进行奇偶位置的判断。 - 根据结果更新
l或r，缩小查找范围。 - 返回结果：
- 最后
l == r时，返回nums[l]，即为唯一的非重复元素。
- 复杂度分析
- 时间复杂度：，二分查找每次将范围缩小一半。
- 空间复杂度：，没有使用额外空间。
2024.11.11 T1547. 切棍子的最小成本
- 问题描述
给定一根长度为
n 的木棍和一个整数数组 cuts，表示需要切割的位置，要求最小化木棍的总切割成本。每次切割的成本是当前木棍的长度。切割后，木棍会分成两段，接下来的切割成本依赖于剩余的木棍长度。返回最小总成本。- 问题解析
- 排序切割点：
- 将切割点排序是因为每次切割的成本与木棍的长度有关，木棍的长度不断变化，因此我们需要知道每一段木棍的长度。
- 动态规划数组：
- 定义
dp[i][j]为在cuts[i]到cuts[j]之间切割的最小成本。 - 状态转移：
- 对于每一段区间
[i, j]，我们尝试选择一个中间点k作为切割点，将问题分解为dp[i][k]和dp[k][j]两个子问题，最终的成本是：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + (cuts[j] - cuts[i]))。 - 边界条件：
- 当区间的长度为 2（即没有中间切割点时），
dp[i][i+1] = 0，因为不需要再切割了。
核心思想是通过合理的选择切割顺序来最小化总成本。
关键点：
- 动态规划的实现
- 初始化：
- 将所有切割点（包括木棍的两端）保存在
positions数组中，positions[0]为木棍的起点，positions[numCuts+1]为木棍的终点。 - 状态转移：
- 遍历所有的区间长度，从
len = 3到len = numCuts + 2，对于每个区间[i, j]，尝试在区间内选择一个k，计算最小切割成本。 - 最终结果：
- 最终的最小成本存储在
dp[0][numCuts + 1]中。
- 代码实现
- 代码解释
- 初始化和排序：
positions[0] = 0和positions[numCuts + 1] = n，分别表示木棍的起始和结束位置。- 将
cuts数组排序，然后将每个切割点填入positions数组。 - 动态规划填表：
- 对于每个长度为
len的子区间[i, j]，尝试所有的切割点k，更新dp[i][j]为最小成本。 dp[i][j]表示从positions[i]到positions[j]区间的最小切割成本。我们计算所有可能的k（中间的切割点），选择最小的切割成本。- 返回最小成本：
- 最终答案为
dp[0][numCuts + 1]，即从0到n范围内最小的切割成本。
- 复杂度分析
- 时间复杂度：
- ，因为我们有 的区间需要处理，对于每个区间，我们需要检查 个切割点。
- 空间复杂度：
- ，存储
dp数组和positions数组。
2024.11.12 T3258. 统计满足 K 约束的子字符串数量 I
1. 问题描述
给定一个二进制字符串
s 和一个整数 k。我们需要计算 s 中所有满足以下条件的子字符串数量：- 子字符串中
0的数量不超过k。
- 子字符串中
1的数量不超过k。
返回符合条件的子字符串数量。
- 解决思路
- 滑动窗口初始化：
- 维护两个计数器
count0和count1，分别记录窗口内0和1的数量。 - 设定左边界
left和结果计数器result。 - 滑动窗口右移：
- 遍历字符串的每个字符，并将其加入窗口中。如果字符为
0，增加count0；如果为1，增加count1。 - 调整窗口：
- 如果
count0和count1都大于k，则当前窗口不满足k约束。移动左边界left，逐步缩小窗口，直到满足k约束。 - 计算子字符串数量：
- 对于每个右边界
right，满足条件的子字符串数量等于当前窗口的长度(right - left + 1)。 - 累积到
result中。 - 返回结果：
- 最终返回所有满足条件的子字符串数量。
这是一个滑动窗口问题，目的是找出满足特定条件的子字符串的数量。通过维护一个窗口并在满足约束时扩大窗口，不满足时缩小窗口，可以高效地计算出满足条件的子字符串数量。
- 代码实现
- 代码详解
- 窗口更新：
- 通过
count0++和count1++来更新窗口内的0和1的数量。 - 窗口收缩：
- 如果窗口内的
0和1的数量都大于k，则收缩窗口（即增大left），同时减少相应的计数器。 - 子字符串计数：
- 对于每个右边界
right，窗口的长度为(right - left + 1)，表示所有从left到right的子字符串都满足k约束。
- 复杂度分析
- 时间复杂度：
O(n)，每个字符最多只会被左右指针访问一次。 - 空间复杂度：
O(1)，只需几个额外的变量用于计数和索引。
2024.11.13 T3261. 统计满足 K 约束的子字符串数量 II
- 问题分析
- 子字符串中
0的数量不超过k。 - 子字符串中
1的数量不超过k。
给定一个二进制字符串
s 和一个整数 k，我们需要计算 s 中满足以下条件的子字符串数量：对于一系列查询，每个查询给定一个区间
[li, ri]，要求计算该区间内所有满足 k 约束的子字符串数量。- 解题思路
- 滑动窗口处理：
- 我们通过滑动窗口来遍历字符串，维护一个窗口内的
0和1的数量。 - 使用两个指针
i和j来表示窗口的左右边界，确保窗口内的0和1的数量都不超过k。 - 前缀和计算：
prefix[j]表示从位置 0 到位置 j 的子字符串数量，所有满足k约束的子字符串数量。- 使用
right[i]数组来记录每个位置i的右边界，即最大的位置j，使得从位置i到j之间的子字符串满足约束。 - 计算查询结果：
- 对于每个查询
[li, ri]，我们可以通过prefix数组快速计算该区间的子字符串数量。通过计算区间内满足条件的子字符串数量，我们利用right数组来确定每个位置可以扩展到的最远位置。
这是一个滑动窗口问题，通过使用前缀和数组和维护一个右边界数组来快速计算满足条件的子字符串数量。具体思路如下：
- 代码实现
- 代码解释
- 前缀和数组：
prefix[j + 1] = prefix[j] + (j - i + 1)计算从i到j的子字符串数量并加到prefix数组中。- 右边界计算：
right[i] = j表示从位置i到位置j之间的子字符串满足k约束。在每次扩展窗口时，维护这个右边界信息。- 处理查询：
- 对每个查询
[l, r]，我们可以通过prefix数组和right数组来高效地计算该区间的符合条件的子字符串数量。 part1和part2分别表示从l到i的子字符串数量和从i到r的子字符串数量。- 返回结果：
- 最终返回所有查询的结果。
- 复杂度分析
- 时间复杂度：所以总的时间复杂度是 ，其中
q是查询的数量。 - 空间复杂度：
prefix和right数组的大小是 ，因此空间复杂度是 。
2024.11.14 T3249. 统计好节点的数目
- 问题分析
给定一棵树，树中有
n 个节点，节点的编号为从 0 到 n - 1，根节点是节点 0。树的结构通过一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] 表示节点 ai 和节点 bi 之间存在一条无向边。我们需要判断树中哪些节点是“好节点”。如果一个节点的所有子节点为根的子树包含的节点数相同，那么该节点被认为是一个“好节点”。
- 解题思路
- 树的表示：使用邻接表表示树的结构，其中每个节点存储它相邻的节点。
- DFS遍历：从根节点开始进行深度优先遍历 (DFS)，在遍历过程中计算每个节点的子树大小，并检查该节点的所有子树是否大小相同。
- 判断好节点：如果某个节点的所有子树大小相同，则该节点是好节点。
要找到“好节点”的数量，我们需要计算树中每个节点的子树的大小，并检查每个节点的所有子树大小是否相同。
关键步骤：
- 具体步骤
- 构建树的邻接表：将
edges数组转换为树的邻接表。 - 深度优先搜索 (DFS)：从根节点开始遍历树，对于每个节点，递归计算其子树的大小，并检查该节点的所有子树大小是否一致。
- 统计好节点：如果当前节点的所有子树大小一致，增加好节点的计数。
- 代码实现
- 代码解析
- 初始化：
goodNodesCount用于记录“好节点”的数量。graph是一个邻接表，用于存储树的结构。- 构建邻接表：
- 遍历
edges数组，将每一条边edges[i] = [ai, bi]转换为邻接表的形式，表示节点ai和bi之间有一条边。 - DFS遍历：
dfs函数采用递归方式，计算每个节点的子树大小，并检查该节点的所有子树是否大小一致。firstSubtreeSize用于记录第一个子树的大小，如果后续的子树大小与第一个子树不同，则说明当前节点不是“好节点”。- 递归计算时，如果发现当前节点的所有子树大小一致，则将
goodNodesCount加 1。 - 返回结果：
- 最终返回
goodNodesCount，即所有“好节点”的数量。
- 复杂度分析
- 时间复杂度：
- 邻接表构建：
O(n)，其中n是树的节点数，遍历edges数组构建邻接表需要 的时间。 - DFS遍历：
O(n)，因为树中有n个节点，DFS 遍历每个节点一次，时间复杂度是 。
因此，总时间复杂度是 。
- 空间复杂度
- 邻接表：，需要存储树的结构。
- DFS递归栈：最深递归的深度为树的高度，最坏情况下高度为 。
因此，总空间复杂度是 。
2024.11.15 T3239. 最少翻转次数使二进制矩阵回文 I
- 问题分析
给定一个 m x n 的二进制矩阵
grid，我们需要使矩阵的所有行或者所有列成为回文。回文是指某一行或列从前往后读和从后往前读是相同的。为了达到这个目标，我们可以翻转任意一个格子的值，将其从 0 变为 1 或者从 1 变为 0，求最少翻转次数。问题的要求是：返回使矩阵中的所有行或者所有列成为回文所需的最少翻转次数。
- 解题思路
- 行翻转处理：
- 对于每一行，检查其是否是回文。如果不是回文，我们需要计算最小的翻转次数，使其成为回文。
- 计算所有行需要翻转的总次数。
- 列翻转处理：
- 对于每一列，检查其是否是回文。如果不是回文，同样需要计算最小的翻转次数。
- 计算所有列需要翻转的总次数。
- 选择最少翻转次数：
- 最终，返回行翻转次数和列翻转次数的最小值，即为答案。
我们需要通过两种方式来解决这个问题，分别是：
为了检查一行或者一列是否为回文，我们使用双指针方法。通过比较左端和右端的元素，如果不同，则需要进行翻转。
- 代码实现
- 代码解释
minFlipsToMakePalindrome：- 这个函数用于判断一个数组（即一行）是否是回文，并计算将其变为回文所需的最小翻转次数。
- 使用两个指针
left和right，分别从两端向中间遍历，如果arr[left] != arr[right]，则需要一次翻转。 - 返回需要的翻转次数。
minFlipsToMakeColumnPalindrome：- 这个函数用于判断一列是否是回文，并计算将其变为回文所需的最小翻转次数。
- 同样使用双指针
top和bottom来遍历列中的元素，判断是否需要翻转。 - 返回需要的翻转次数。
minFlips：- 主函数
minFlips计算所有行和列的翻转次数，分别调用minFlipsToMakePalindrome处理每一行和minFlipsToMakeColumnPalindrome处理每一列。 - 最终返回行翻转和列翻转次数中的最小值，即为结果。
- 复杂度分析
- 时间复杂度：
- 对每一行，我们需要遍历整个行的元素，计算最小翻转次数，时间复杂度为 ，其中
m是行数，n是列数。 - 对每一列，我们同样需要遍历该列的元素，时间复杂度为 。
- 总的时间复杂度为 。
- 空间复杂度：
- 主要使用了额外的空间来存储结果，空间复杂度为 ，因为没有额外开辟大的存储空间，除了输入矩阵外。
2024.11.16 T3240. 最少翻转次数使二进制矩阵回文 II
1. 问题分析
我们需要处理一个 m x n 的二进制矩阵
grid，目标是通过最少的翻转次数满足以下两个条件：- 行和列为回文：
- 每一行和每一列从前往后与从后往前读是一样的。
- 1 的数量能被 4 整除：
- 矩阵中所有
1的个数最终必须是 4 的倍数。
为了达成目标，需要合理安排翻转策略，优先处理矩阵的对称性，同时关注
1 的数量调整。2. 解题思路
解决问题可以分为以下几步：
- 处理矩阵的对称性：
- 将矩阵分为四分之一区域，每次处理对称的四个格子，即
(r, c)、(r, n-1-c)、(m-1-r, c)、(m-1-r, n-1-c)。 - 对于每组对称的四个格子，计算
1的数量oneCount，翻转最少的格子即可满足回文。
- 处理中间行和列：
- 如果行数或列数是奇数，需要单独处理矩阵的中间行或列，确保其回文性。
- 处理矩阵中心点：
- 如果矩阵行列均为奇数，需要处理矩阵的正中心点，决定是否翻转它以满足目标条件。
- 调整
1的数量： - 在满足矩阵对称性后，根据
1的总数量是否是 4 的倍数，进行进一步调整： - 如果
1的数量多了，需要通过适当翻转减少1。 - 如果
1的数量少了，需要通过适当翻转增加1。
3. 代码实现
4. 代码解释
- 矩阵对称性处理：
- 遍历矩阵的左上四分之一部分，通过四个对称位置计算
1的数量oneCount。 - 如果
oneCount > 2，需要翻转4 - oneCount个格子；否则翻转oneCount个格子。
- 中间行和列的处理：
- 通过
(rows + 1) / 2和(cols + 1) / 2，有效处理了奇数行和奇数列的情况。
- 调整
1的总数量： - 在翻转的基础上，检查
1的数量是否是 4 的倍数。 - 如果不是，进一步翻转使其满足条件。
5. 复杂度分析
- 时间复杂度：
- 遍历矩阵的四分之一部分，每次操作最多涉及 4 个元素，时间复杂度为 。
- 空间复杂度：
- 只使用了常数额外空间，空间复杂度为 。
2024.11.17 T825 . 适龄的朋友
1. 问题分析
我们需要计算一个社交媒体平台上用户间发送好友请求的总数。好友请求的规则是：
- 用户
x不会向用户y发送请求，若满足以下条件之一：
- 用户
x不会向自己发送请求。
目标：返回符合条件的好友请求总数。
2. 解题思路
为高效计算好友请求，我们采用如下方法：
- 排序数组：
- 将数组
ages按照年龄从小到大排序，便于使用双指针计算满足条件的用户对。
- 双指针遍历：
- 对于每个用户
i，使用双指针维护范围[l, r]，表示能接收来自用户i的好友请求的用户范围。 - 左边界
l：用户ages[l]必须满足 。 - 右边界
r：用户ages[r]必须满足 。
- 计算好友请求：
- 对于每个用户
i，满足条件的好友请求数量为r - l。 - 排除自己发送给自己的情况，因此不加
i。
3. 代码实现
4. 代码解释
- 排序数组：
- 使用
sort(ages.begin(), ages.end());将年龄从小到大排序。
- 双指针范围更新：
l：维护左边界，保证好友请求的接收者满足。r：维护右边界，保证好友请求的接收者满足 。
- 计算好友请求：
ans += r - l：在每个用户i发送好友请求时，范围[l, r]内的用户是有效的接收者。
- 特殊处理：
- 如果用户年龄小于 15，跳过该用户，因为其不会发送好友请求。
5. 复杂度分析
- 时间复杂度：
- 排序的时间复杂度为 。
- 双指针遍历整个数组一次，时间复杂度为 。
- 总时间复杂度为 。
- 空间复杂度：
- 排序操作为原地操作，不使用额外空间，空间复杂度为 。
2024.11.18 T661 . 图片平滑器
1. 问题分析
给定一个表示图像灰度的 矩阵
img，需要对矩阵的每个单元格进行平滑处理。每个单元格的新值为该单元格及其周围最多 8 个单元格的灰度平均值（向下取整）。- 如果某个单元格位于边界或角落，缺失的邻域单元格不参与计算。
- 需要返回经过平滑处理后的矩阵。
2. 解题思路
为实现图像平滑处理，我们可以采用以下步骤：
- 偏移量数组：
- 用一个固定的方向数组来表示当前单元格的 3x3 邻域，包括 8 个方向及自身的位置。
- 遍历每个单元格：
- 使用双重循环依次遍历矩阵中的每个单元格。
- 处理每个单元格的邻域：
- 使用方向数组，根据当前单元格的位置，确定其 3x3 邻域的有效单元格。
- 对有效的邻域单元格，累加灰度值，同时统计邻域单元格的数量。
- 更新结果矩阵：
- 对于每个单元格，计算灰度平均值，向下取整，并存储在结果矩阵中。
- 返回结果矩阵：
- 最终返回包含平滑处理后值的结果矩阵。
3. 代码实现
4. 代码解释
- 方向数组：
- 定义了 9 个方向的偏移量（包括当前单元格本身），用于定位邻域单元格。
- 遍历矩阵：
- 外层循环遍历每一行，内层循环遍历每一列，从而遍历整个矩阵。
- 处理邻域单元格：
- 对于每个单元格，计算其周围最多 8 个邻域单元格的灰度值总和。
- 检查邻域单元格是否在矩阵范围内，确保不越界。
- 更新结果矩阵：
- 将灰度平均值向下取整后存储到结果矩阵中。
- 返回结果：
- 返回完整处理后的矩阵。
5. 复杂度分析
- 时间复杂度：
- 遍历每个单元格（外层 ，内层 ）。
- 对于每个单元格，检查其 3x3 邻域的 9 个方向（常数次操作）。
- 总时间复杂度为 。
- 空间复杂度：
- 结果矩阵占用 的额外空间。
- 方向数组为常量，额外空间复杂度为 。
2024.11.19 T3243. 新增道路查询后的最短距离 I
1. 问题分析
给定一个有 城市的图，初始时每个城市 都有一条单向道路通往城市 。通过若干查询
queries[i] = []，动态地在图中增加从城市 到城市 的单向道路。目标是在每次查询后，找到从城市 0 到城市 的最短路径长度。返回一个数组
answer，其中 answer[i] 表示处理完第 个查询后，从城市 0 到城市 的最短路径长度。2. 解题思路
- 初始化图和路径：
- 初始情况下，每个城市 到城市 有一条单向道路，路径长度为 。
- 用数组 记录从城市 到每个城市的最短路径长度，初始化为 。
- 用邻接表 记录每个城市可以通过哪些前驱城市到达。
- 处理查询：
- 对于每个查询
queries[i] = [u, v]，添加从城市 u 到城市 v 的单向道路。 - 更新从 0 到 的最短路径长度。
- 遍历所有可能到达的城市，使用前驱城市的最短路径动态更新当前城市的最短路径。
- 动态更新最短路径：
- 每次查询添加一条新道路后，利用邻接表和
dp数组更新所有受影响的节点的最短路径长度。
- 返回结果：
- 每次查询结束后，将从 0 到 n-1 的最短路径长度记录到结果数组中。
3. 代码实现
4. 代码解释
- 初始化：
prev[i]用于存储城市 i 的前驱城市。dp[i]表示从城市 0 到城市 i 的最短路径长度。- 初始情况下，城市 i 只能通过 i-1 到达，路径长度为 i 。
- 查询处理：
- 每次新增一条 的道路后，更新 的值。
- 遍历从 v 开始的所有城市，利用前驱城市动态更新最短路径长度。
- 结果存储：
- 每次查询结束后，将 的值加入结果数组
res。
5. 复杂度分析
- 时间复杂度：
- 初始构造 和 的时间为 。
- 每次查询中，更新从 v 开始的所有节点，最坏情况遍历 个节点，每个节点访问其所有前驱城市，时间为 ，其中 m 是前驱城市的平均数量。
- 总时间复杂度为 ，其中 q 是查询的数量。
- 空间复杂度：
dp和prev的空间复杂度为 。- 总空间复杂度为 。
2024.11.20 T3244. 新增道路查询后的最短距离 II
1. 问题分析
给定 个城市，初始时每个城市 都有一条单向道路连接到 。对于每个查询 ，新增一条从城市 到城市 的单向道路。我们需要在处理每个查询后，计算从城市 0 到城市 n-1 的最短路径长度。
特殊约束：查询保证不出现嵌套范围，即不存在
。
2. 解题思路
利用并查集处理动态连通性问题：
- 初始化并查集，记录每个节点的父节点，并将每个节点指向自身。
- 对于每个查询
queries[i] = [u, v]，将 u 到 v-1 的所有节点合并到同一连通块。
- 使用并查集的
find操作定位节点的根节点，并通过路径压缩优化合并操作。
- 每次查询完成后，记录连通块的数量作为结果。
3. 代码实现
4. 代码解释
并查集初始化：
fa[i] 用于记录节点 i 的父节点，初始时每个节点的父节点为自身。find 函数：实现路径压缩功能，快速找到节点的根节点，减少树的高度。
查询处理：
对于查询
queries[i] = [u, v]，合并 u 到 v-1 范围内的所有节点到 v-1 的连通块。结果记录：
每次查询后，将当前连通块数量保存到结果数组中。
5. 复杂度分析
时间复杂度：
- 并查集操作的均摊时间复杂度为 ，其中 是反阿克曼函数，几乎为常数。
- 每次查询遍历并合并范围内的节点，最坏情况为 。
- 总时间复杂度为 ，其中 q 是查询数量。
空间复杂度：
- 并查集数组
fa和结果数组ans的空间复杂度为 。
- 总空间复杂度为 。
2024.11.21 T3248. 矩阵中的蛇
1. 问题分析
在一个大小为 的矩阵中，蛇从位置 0（即左上角）开始，根据一系列命令移动。矩阵中的每个单元格由编号 唯一标识。
移动的规则如下：
- "UP"：向上移动一行。
- "DOWN"：向下移动一行。
- "LEFT"：向左移动一列。
- "RIGHT"：向右移动一列。
题目保证蛇在整个移动过程中不会超出矩阵的边界，因此不需要额外处理越界情况。
目标：根据所有的命令，返回蛇最终所在单元格的位置。
2. 解题思路
- 初始化蛇的位置：
- 初始位置为左上角，即 (0, 0)。
- 遍历命令数组：
- 根据命令调整当前的位置 ()：
- "UP"：行数减 1。
- "DOWN"：行数加 1。
- "LEFT"：列数减 1。
- "RIGHT"：列数加 1。
- 计算最终位置：
- 根据矩阵的编号规则，最终位置为 。
3. 代码实现
4. 代码解释
- 初始化：
row和col分别表示蛇在矩阵中的行号和列号，初始为 0。
- 遍历命令：
- 对于每个命令，根据其类型调整行号或列号。
- 计算结果：
- 根据 规则，计算蛇最终所在单元格的位置。
5. 复杂度分析
时间复杂度：
- 遍历所有命令，时间复杂度为 ，其中 是命令的数量。
空间复杂度：
- 常量空间用于存储行号和列号，空间复杂度为 。
2024.11.22 T3233. 统计不是特殊数字的数字数量
1. 问题分析
我们需要找出区间 内不是特殊数字的数字数量。
特殊数字的定义：
- 一个数字是特殊数字，如果它的真因数只有两个。换句话说，特殊数字是一个质数的平方
问题可以转化为：
- 计算区间内的特殊数字数量。
- 用区间总数减去特殊数字的数量，得到非特殊数字的数量。
2. 解题思路
- 特殊数字的平方根必须是质数，因此需要一个函数
isPrime(n)来判断一个数字是否是质数。
3. 代码实现
- 复杂度分析
- 时间复杂度
- 检查质数的复杂度为 ，因为对于每个可能的质数 p ，质数检测的时间复杂度为 。
- 遍历的范围限制在 ，所以总体时间复杂度近似为 。
- 空间复杂度
- 算法仅使用了常量级的额外空间，没有使用动态分配的数组或其他数据结构。
- 因此，空间复杂度为 。
2024.11.23 T3238. 求出胜利玩家的数目
- 问题分析
- 如果玩家获得了某种颜色球的数量严格大于
i的话，那么称玩家i为胜利玩家。 - 例如：
- 玩家 0 只要获得了任意球就是胜利玩家。
- 玩家 1 需要获得至少 2 个相同颜色的球才能成为胜利玩家。
- 玩家
i需要获得至少i + 1个相同颜色的球才能成为胜利玩家。
给定一个整数
n 表示玩家的数量，以及一个二维数组 pick，其中 表示玩家 获得了一个颜色为 的球。对于每个玩家
i：目标：计算游戏中胜利玩家的数量。
2. 解题思路
- 使用哈希表统计每个玩家的球数量：
- 使用一个大小为
n的数组colorCount，每个元素是一个哈希表，用于存储每个玩家各颜色球的数量。
- 遍历
pick数组，统计球数量： - 遍历
pick，对每个玩家的球颜色进行计数。
- 判断胜利玩家：
- 遍历每个玩家，检查每种颜色的球数量是否满足条件，如果满足即认为是胜利玩家。
- 计数胜利玩家：
- 统计满足条件的玩家数量。
3. 代码实现
4. 代码解释
- 数据结构选择：
- 使用一个大小为
n的数组colorCount，其中每个元素是一个unordered_map，用于记录每个玩家的各颜色球的数量。
- 遍历
pick数组： - 对于每个
pick[i]，将相应的玩家和球的颜色存储到colorCount中，更新计数。
- 判断胜利玩家：
- 对每个玩家
i，遍历其所有颜色的球数量，如果某种颜色的球数量严格大于i，则该玩家为胜利玩家，直接跳出检查。
- 返回结果：
- 统计所有满足条件的玩家数量并返回。
5. 复杂度分析
- 时间复杂度
- 遍历
pick数组的时间复杂度为 ，其中 m 是pick数组的长度。 - 遍历每个玩家及其颜色球的哈希表的时间复杂度在最坏情况下接近 。
- 总时间复杂度为 。
- 空间复杂度
- 使用了大小为
n的数组，每个元素是一个哈希表，哈希表的大小取决于pick中颜色的种类。 - 最坏情况下，空间复杂度为 。
2024.11.24 T632 . 最小区间
1. 问题分析
给定 个非递减排列的整数列表，需要找到一个最小区间，使得 个列表中的每个列表至少有一个数包含在区间内。
规则：
- 区间的大小由 决定。
- 如果多个区间大小相同，则选择起点较小的区间。
2. 解题思路
- 展开和排序：
- 将所有列表的元素展开到一个数组中，记录每个元素的值和它所属的列表编号。
- 对这个数组按值排序，以便后续使用滑动窗口处理。
- 滑动窗口：
- 使用双指针（即滑动窗口）遍历排序后的数组。
- 窗口的目标是覆盖 个列表中的所有列表。
- 每次窗口包含所有列表时，计算当前区间的大小并更新结果。
- 窗口收缩：
- 当窗口满足条件时，尝试收缩窗口以寻找更小的区间。
- 移动左指针，同时维护窗口内包含的列表数量。
3. 代码实现
4. 代码解释
- 展开和排序：
- 将所有列表的元素连同其所属的组号存入数组
ordered，并按值排序。这样可以按照数值大小处理所有元素，同时追踪其来源。
- 滑动窗口：
- 使用
groupCount记录窗口中每个列表的覆盖情况。 - 每当窗口覆盖了 个列表后，尝试更新最小区间。
- 区间更新条件：
- 优先选择更小的区间（
currentRange更小）。 - 如果区间大小相同，选择起点较小的区间。
- 窗口收缩：
- 左指针右移，移出窗口的组若在窗口内不再出现，减少覆盖的列表数量。
5. 复杂度分析
- 时间复杂度：
- 展开和排序：，其中 是所有列表元素的总数。
- 滑动窗口：每个元素至多进出窗口一次，时间复杂度为 。
- 总时间复杂度：
- 空间复杂度：
- 使用了额外的数组
ordered和哈希表groupCount，空间复杂度为 ，其中 是列表的数量。
2024.11.25 T743 . 网络延迟时间
1. 问题分析
我们需要找到从某个节点 发出的信号传播到所有其他节点所需的最短时间。如果某些节点无法收到信号，则返回 -1。
输入：
times：表示有向边的传递时间，格式为 ，其中：- 是源节点。
- 是目标节点。
- 是传递时间。
- ：节点的总数。
- ：信号发出的起始节点。
输出：
- 返回信号传播到所有节点的最短时间，如果无法到达所有节点，返回 -1。
2. 解题思路
- 构建图的邻接表：
- 将有向边存储为邻接表结构，便于快速查询每个节点的邻居和边权。
- Dijkstra 算法求最短路径：
- 使用优先队列（最小堆）维护未访问节点的最短路径。
- 每次从优先队列中取出当前距离最短的节点进行松弛操作，更新其邻居的最短路径。
- 检查结果：
- 如果最终某些节点的最短距离仍为无穷大，表示这些节点无法到达，返回 -1。
- 否则，返回所有节点中最远的最短路径。
3. 代码实现
4. 代码解释
- 构建邻接表：
- 将输入的边信息存储为邻接表，
graph[u]存储从节点 出发的所有邻居及其边权。
- 初始化：
distances数组存储从起点 到各节点的最短距离，初始值为无穷大，起点 的距离为 0。- 使用最小堆
minHeap优化 Dijkstra 算法。
- Dijkstra 算法：
- 每次从堆中取出当前最短距离的节点。
- 遍历其邻居，更新未访问节点的最短距离，并将更新后的节点重新加入堆。
- 结果检查：
- 如果某些节点的距离仍为无穷大，表示它们无法到达，返回 -1。
- 否则，返回
distances数组中的最大值。
5. 复杂度分析
- 时间复杂度：
- 构建图的时间复杂度为 ，其中 是边的数量。
- Dijkstra 算法的时间复杂度为 ，其中 是节点的数量。
总时间复杂度为 。
- 空间复杂度：
- 邻接表的空间复杂度为 。
distances数组的空间复杂度为 。- 优先队列的空间复杂度为 。
总空间复杂度为 。
2024.11.26 T3206. 交替组 I
2024.11.27 T3208. 交替组 II
两道题一个思路，放在一起说了就
- 问题分析
给定一个由红色和蓝色瓷砖组成的环，环中的每一块瓷砖由数组 表示， 为 0 或 1，分别代表红色和蓝色。我们的任务是找到环中长度为 且瓷砖颜色交替的连续子序列的个数。环的特点意味着数组的头尾相连，这为交替组的查找带来了额外的复杂性。
- 解题思路
- 通过遍历数组的两倍长度来模拟环的结构。
- 在每次遍历时，检查当前瓷砖是否与前一块的颜色相同。如果相同，重置当前交替组长度计数。
- 如果当前计数大于或等于
k，并且已经遍历到大于等于n的位置，则可以增加交替组的数量。
为了解决这个问题，我们需要遍历整个环，找到所有满足条件的交替组。由于数组是环状的，我们可以将数组模拟成长度为
2 * n 的数组，其中 n 为 colors 的长度，这样可以处理好首尾相连的问题。具体思路如下：
- 代码实现
- 代码解释
n = colors.size();- 获取瓷砖的总数量。int ans = 0, cnt = 0;- 初始化交替组的数量ans和当前计数cnt。for (int i = 0; i < n * 2; i++)- 遍历整个环的两倍长度，以处理首尾相连。if (i > 0 && colors[i % n] == colors[(i - 1) % n])- 如果当前瓷砖和前一块颜色相同，重置当前计数。cnt++- 否则增加当前计数。ans += i >= n && cnt >= k;- 如果已经遍历到长度n以上并且当前计数大于等于k，增加交替组的数量。return ans;- 返回交替组的总数量。
- 复杂度分析
- 时间复杂度：，其中
n为瓷砖的数量。由于我们遍历了 的长度，因此时间复杂度仍然是线性。 - 空间复杂度：，只使用了常数个额外的变量，空间复杂度为常数。
2024.11.28 T3250. 单调数组对的数目 I
2024.11.29 T3251. 单调数组对的数目 II
两个题只有数据范围不一样，一起写了
- 问题分析
arr1是单调非递减数组，即arr1[0] <= arr1[1] <= ... <= arr1[n - 1]。arr2是单调非递增数组，即arr2[0] >= arr2[1] >= ... >= arr2[n - 1]。- 对于所有
0 <= i <= n - 1，满足arr1[i] + arr2[i] == nums[i]。
给定一个长度为
n 的正整数数组 nums，要求找到所有满足条件的单调数组对 (arr1, arr2) 的数目。由于答案可能很大，最后需要返回答案对
10^9 + 7 取余后的结果。- 解题思路
- 动态规划思路：
- 使用一个
dp数组记录当前能够形成有效解的组合数。 - 初始时，可以通过遍历
nums[0]来确定初始的可能组合数量。 - 前缀和优化：
- 使用前缀和计算方式快速更新
dp数组，避免逐个累加导致的复杂度过高。 - 滑动窗口：
- 每次迭代时，更新
dp数组中的有效部分，并将无效部分清零，保持dp数组的有效性。
这道题涉及动态规划和前缀和的技巧。
- 代码实现
- 代码解释
- 初始化部分：
MOD是取余数的模数，防止结果溢出。maxValue是数组nums中的最大值，用于定义dp数组的大小。- 初始化
dp数组，使得dp[i]表示第i个位置上可能的组合数。 - 动态规划迭代：
- 对于每一个
nums[i]，根据上一个位置的dp值来更新当前可能的组合数。 - 使用前缀和的方式来高效地计算新的
dp值，减少时间复杂度。 - 滑动窗口更新
dp数组： - 更新
dp中有效的部分，并将不需要的部分清零，以保证在下一轮迭代时不受干扰。 - 返回结果：
- 最终返回
dp数组中所有元素的和，并对MOD取余。
- 复杂度分析
- 时间复杂度：假设
maxValue为数组中的最大值，时间复杂度约为O(n * maxValue)，其中n为数组的长度。代码中主要开销来自于遍历和前缀和计算。 - 空间复杂度：空间复杂度为
O(maxValue)，用于存储动态规划的dp数组。
2024.11.30 T3232. 判断是否可以赢得数字游戏
- 问题分析
- Alice 可以从
nums中选择所有个位数或所有两位数，剩余的数字归 Bob 所有。 - 如果 Alice 所选数字之和严格大于 Bob 的数字之和，则 Alice 获胜。
给定一个正整数数组
nums，Alice 和 Bob 正在玩一个游戏。游戏规则如下：我们的目标是判断 Alice 是否能赢得这场游戏，如果 Alice 能赢，返回
true，否则返回 false。- 解题思路
- 分配数字的原则：
- 由于 Alice 只能选择所有个位数或所有两位数，而我们希望 Alice 获胜，所以需要尽量让 Alice 获得和更大的数字。
- 思路分析：
- 将数组
nums排序后，Alice 选择所有个位数（即小于 10 的数字），Bob 选择剩余的数字。 - Alice 获胜的条件是 Alice 的选择数字之和严格大于 Bob 的选择数字之和。
- 判断条件：
- 如果 Alice 和 Bob 的和不同，则 Alice 赢得比赛；如果 Alice 和 Bob 的和相等，则 Alice 不能获胜。
这道题主要考察如何分配数字，确保 Alice 获胜。
- 代码实现
- 代码解释
- 排序：
- 首先对
nums数组进行升序排序，目的是方便后续区分 Alice 和 Bob 的选择。 - 遍历数组并分配数字：
- 遍历排序后的
nums数组，对于每个小于 10 的数字，添加到sum1（Alice 的得分）；其余的数字添加到sum2（Bob 的得分）。 - 判断 Alice 是否获胜：
- 最后比较
sum1和sum2的值，如果sum1大于sum2，则 Alice 获胜，返回true；否则，返回false。
- 复杂度分析
- 时间复杂度：，其中
n为数组nums的长度，主要的时间复杂度来源于排序操作。 - 空间复杂度：，只使用了常数级的额外空间。
- 作者:小H狂炫香菜
- 链接:https://hjwvip.top/technology/leetcode-November
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
.jpg?table=block&id=11101f2a-87be-8043-b90f-f8651aec7f03&t=11101f2a-87be-8043-b90f-f8651aec7f03&width=800&cache=v2)
.jpg?table=block&id=11201f2a-87be-80ed-8d70-fbdda0e7235f&t=11201f2a-87be-80ed-8d70-fbdda0e7235f&width=800&cache=v2)
