type
status
date
slug
summary
tags
category
icon
password
comment
12月，冲冲冲！！！
每日一题2024.12.01 T51 . N 皇后2024.12.02 T52 . N 皇后 II2024.12.03 T3274. 检查棋盘方格颜色是否相同2024.12.04 T2056. 棋盘上有效移动组合的数目2024.12.05 T3001. 捕获黑皇后需要的最少移动次数2024.12.06 T999 . 可以被一步捕获的棋子数2024.12.07 T688 . 骑士在棋盘上的概率2024.12.08 T782 . 变为棋盘2024.12.09 T1812. 判断国际象棋棋盘中一个格子的颜色2024.12.10 T935 . 骑士拨号器2024.12.11 T2717. 半有序排列2024.12.12 T2931. 购买物品的最大开销2024.12.13 T3264. K 次乘运算后的最终数组 I2024.12.14 T3266. K 次乘运算后的最终数组 II2024.12.15 T1338. 数组大小减半2024.12.16 T1847. 最近的房间2024.12.17 T3291. 形成目标字符串需要的最少字符串数 I2024.12.18 T3292. 形成目标字符串需要的最少字符串数 II2024.12.19 T3285. 找到稳定山的下标2024.12.20 T3138. 同位字符串连接的最小长度2024.12.21 T2545. 根据第 K 场考试的分数排序2024.12.22 T1387. 将整数按权重排序2024.12.23 T855 . 考场就座2024.12.24 T1705. 吃苹果的最大数目2024.12.26 T3083. 字符串及其反转中是否存在同一子字符串2024.12.27 T3159. 查询数组中元素的出现位置2024.12.28 T3046. 分割数组2024.12.29 T1366. 通过投票对团队排名2024.12.30 T1367. 二叉树中的链表2024.12.31 T3219. 切蛋糕的最小总开销 II
每日一题
2024.12.01 T51 . N 皇后
2024.12.02 T52 . N 皇后 II
两个题思路一样，一起写了就
- 问题分析
- 皇后可以攻击同一行、同一列或同一斜线上的其他棋子。
- 对于给定的整数
n，要求返回所有可能的放置方式，其中每个解法表示为一个n × n的棋盘。 - 在棋盘中，
'Q'代表皇后，'.'代表空位。
本题是经典的 n 皇后问题，目标是在一个
n × n 的棋盘上放置 n 个皇后，使得它们互不攻击。- 解题思路
- 回溯法：
- 我们将从第
0行开始，尝试将皇后放在每一列上，递归地进行尝试。每当到达一行时，检查当前列和两个斜线是否能放置皇后，若可以则放置皇后并继续递归。 - 合法性检查：
- 对每一行的每一列，都需要检查皇后是否能安全放置。检查的条件是：
- 该列上是否已有皇后。
- 主对角线（左上到右下）是否已有皇后。
- 副对角线（右上到左下）是否已有皇后。
- 回溯过程：
- 如果某一行的某个位置可以放置皇后，则递归进入下一行。如果能成功放置到最后一行，说明找到了一个解，将该解保存下来。
- 若某一列不能放置皇后，则撤回上一步，继续尝试其他列。
- 返回所有解：
- 最终返回所有找到的解。
这道题可以通过回溯算法来求解，具体步骤如下：
- 代码实现
- 代码解释
- 回溯函数：
backtrack函数用于递归搜索每一行的所有可能放置皇后的位置，并检查是否合法。如果某个位置合法，则放置皇后并递归尝试下一行，最后将有效解保存到result中。- 合法性检查函数：
isValid函数用于检查在当前位置(row, col)放置皇后是否安全。检查条件包括列、主对角线和副对角线是否已经有皇后。- 主函数：
solveNQueens函数是主要入口，初始化棋盘并调用回溯算法来搜索所有解。- 结果存储：
- 每当找到一个解时，将棋盘状态（字符串形式）添加到
result中。
- 复杂度分析
- 时间复杂度：最坏情况下，算法需要尝试每个位置，因此时间复杂度为 ，因为每一行有
n种选择，而递归深度为n。 - 空间复杂度：空间复杂度主要来自于递归栈和保存结果的
result，因此空间复杂度为 。
2024.12.03 T3274. 检查棋盘方格颜色是否相同
- 这题太简单了懒得写解释了，直接上代码
2024.12.04 T2056. 棋盘上有效移动组合的数目
天天下棋，昨天下的还挺简单，今天就拉了坨大的，我服了
- 问题分析
- 车：可以水平或竖直移动。
- 后：可以水平、竖直或斜对角移动。
- 象：只能斜对角移动。
给定一个 8x8 的棋盘，包含
n 个棋子（车、后、象）。每个棋子都可以至多移动一次。棋子的移动遵循不同的规则，具体为：给定每个棋子的位置和类型，要求计算出所有有效的棋子移动组合数。一个有效的组合是指每个棋子按照其规则进行合法移动，且在某个时刻不会有两个棋子占据同一位置。
- 解题思路
- 预处理所有合法移动：
- 对于每个棋子，列出其可能的所有合法移动路径。车的路径包括上下左右，象的路径包括四个斜对角，后则包含所有方向。
- 每个棋子会有多个可能的移动，使用 DFS 遍历每个棋子的所有可能移动。
- 深度优先搜索 (DFS)：
- 从第一个棋子开始，尝试每个可能的移动，并递归地考虑后续棋子的移动组合。
- 对于每个棋子，检查它的移动是否与之前棋子的移动冲突（即是否会碰撞）。如果没有冲突，则继续递归。
- 判断合法性：
- 在每一秒，检查所有棋子的状态，确保没有两个棋子重叠。
- 如果有两个棋子会在某一时刻重叠，返回无效组合。
- 交换位置：
- 如果两个棋子直接相邻且会在同一时刻互相占据对方的位置，可以将它们交换位置。
- 代码实现
- 代码解释
generate_moves函数：- 为每个棋子计算其所有可能的合法移动，包含原地不动的情况以及其他可能的步数和方向。
is_valid函数：- 检查两个棋子是否会在某个时刻占据相同的位置，判断它们的移动是否会冲突。
- 深度优先搜索 (DFS)：
- 通过 DFS 枚举每个棋子的移动，确保没有棋子之间的冲突，并且计算所有合法的组合数。
- 主函数：
- 预处理每个棋子的合法移动，使用 DFS 遍历所有可能的合法组合，并返回有效的移动组合数。
- 复杂度分析
- 时间复杂度：，其中：
n是pieces数组的长度（即棋子的数量）。L = 8表示棋盘的大小。- 表示单个棋子的合法移动个数，最多为 8 种移动方向。
- 由于 DFS 搜索树的深度为
n，每个节点可能有M个分支，树的总节点数为 。每个节点需要时间O(n * L)来判断第i个棋子的合法移动是否有效。故总时间复杂度为 。
- 空间复杂度：，用于存储每个棋子的所有合法移动。每个棋子的合法移动数最多为
M，所以空间复杂度为 。
2024.12.05 T3001. 捕获黑皇后需要的最少移动次数
- 问题分析
- 白色车：可以向垂直或水平方向移动任意数量的格子，前提是没有其他棋子阻挡。
- 白色象：可以沿对角线方向移动任意数量的格子，前提是没有其他棋子阻挡。
- 黑色皇后：处于固定位置，不能移动。
在给定的 8x8 棋盘上，存在三个棋子：
任务是找到最少的移动次数，使得白色的车或象捕获到黑色皇后。如果棋子在直线或对角线方向上能到达皇后所在的位置，即可视为捕获。
- 解题思路
- 移动规则：
- 车的移动范围是整个水平方向和竖直方向。其捕获皇后的条件是车所在行或列与皇后一致，同时中间没有其他棋子阻挡。
- 象的移动范围是棋盘的对角线方向，其捕获皇后的条件是象和皇后在同一对角线上，且中间没有其他棋子阻挡。
- 捕获条件判断：
- 判断白色车是否能到达皇后位置，首先要满足车和皇后在同一行或列，然后需要检查中间是否存在其他棋子（即白色象）阻挡。
- 判断白色象是否能到达皇后位置，需要它们在同一对角线上，并且中间没有其他棋子（白色车）阻挡。
- 结果判定：
- 若任一棋子可以在一次移动中捕获皇后，返回
1。 - 否则返回
2，表示需要两步才能捕获皇后。
- 代码实现
- 代码解释
- 判断车能否捕获皇后：
- 如果车在与皇后相同的行，且白色象不在它们之间（即没有阻挡），则车可以一步捕获皇后。
- 如果车在与皇后相同的列，同样判断白色象是否阻挡。
- 判断象能否捕获皇后：
- 如果象和皇后在同一对角线上，且白色车不在它们之间（没有阻挡），象可以一步捕获皇后。
- 返回结果：
- 如果车或象可以在一步内捕获皇后，返回
1；否则返回2。
- 复杂度分析
- 时间复杂度：。代码中仅进行了常量次的判断和比较操作，因此时间复杂度为 。
- 空间复杂度：。只使用了常量级别的额外空间。
2024.12.06 T999 . 可以被一步捕获的棋子数
- 问题分析
- 白色的车
'R'，可以在水平方向或竖直方向移动。 - 白色的象
'B'，会阻挡车的路径。 - 黑色的卒
'p'，是车的目标。 - 水平或竖直方向移动，直到碰到边界或其他棋子。
- 遇到卒时，车可以吃掉卒，且停止移动。
- 遇到象时，车无法穿过象，停止移动。
给定一个
8 x 8 的棋盘，其中存在：车的移动规则：
任务是计算白车
'R' 能够吃掉的卒 'p' 的数量。- 解题思路
- 遍历棋盘，找到白车
'R'的位置(x, y)。 - 依次检查白车的四个方向（上、下、左、右）：
- 在每个方向中，移动并检查当前格子：
- 如果遇到
'B'，停止该方向的检查。 - 如果遇到
'p'，计数器加1，并停止该方向的检查。 - 如果是
'.'，继续移动。 - 将四个方向吃掉卒的数量累加并返回。
- 代码实现
- 代码解释
- 找到白车的位置：
- 遍历整个棋盘，记录车的坐标
(x, y)。 - 逐个方向移动：
- 每次移动一格，并检查格子的状态：
- 遇到象
'B'，停止该方向检查。 - 遇到卒
'p'，计数加1并停止该方向检查。 - 遇到空格
'.'，继续移动。 - 返回计数器：
- 将四个方向能吃到的卒数量累加返回。
- 复杂度分析
- 时间复杂度：
- 找到车的位置：，即遍历整个棋盘。
- 四个方向的检查：每个方向最多检查 步，总共 。
- 总复杂度：。
- 空间复杂度：
- 使用了常数级别的额外变量，空间复杂度为 。
2024.12.07 T688 . 骑士在棋盘上的概率
- 问题分析
在一个
n x n 的国际象棋棋盘上，有一个骑士（马）从位置 (row, column) 开始尝试进行 k 次移动。每次移动时，骑士从 8 种可能的方向中随机选择一种。如果骑士在任意时刻离开了棋盘，则停止移动。目标是计算骑士在进行
k 次移动之后，仍然留在棋盘上的概率。- 解题思路
- 骑士的移动方式：
- 骑士有 8 种可能的移动，每次走两个单元格，再走一个正交方向。
- 骑士可能会走出棋盘，因此需要判断每一步的合法性。
- 动态规划（DP）：
- 使用动态规划来解决这个问题。
- 定义
dp[step][row][col]表示从位置(row, col)出发，经过step步后，骑士留在棋盘上的概率。 - 状态转移：从当前位置
(row, col)，骑士可以移动到新的位置(newRow, newCol)，新位置的概率由之前的状态累加而来。 - 滚动数组优化：
- 在
k次移动中，实际上我们只需要维护当前步和上一步的状态。 - 因此，使用一个三维数组
dp[2][n][n]来存储两轮的状态，来减少空间复杂度。
- 代码实现
- 代码解释
- 初始化：
- 使用一个三维数组
dp[2][boardSize][boardSize]来保存两轮状态的概率。 - 初始化状态为
1，表示骑士在初始位置的概率为 1。 - 动态规划过程：
- 使用变量
currentState来指示当前的状态。 - 对于每一个
step，更新当前所有棋盘位置的概率。 - 骑士有 8 个可能的方向，从
(row, col)移动到(newRow, newCol)，每种可能的概率为1/8。 - 返回结果：
- 返回
dp[moves & 1][startRow][startColumn]，表示经过k次移动后，骑士留在初始位置的概率。
- 复杂度分析
- 时间复杂度：，其中
k为移动次数，n为棋盘的边长。我们需要遍历每一步的每个格子，并且对于每个格子，计算 8 个可能的移动方向。 - 空间复杂度：，我们只保存两轮状态，因此只需要 的空间。
2024.12.08 T782 . 变为棋盘
- 问题分析
给定一个
n x n 的矩阵 board，其中仅包含 0 和 1。通过交换任意两列或两行的位置，目标是将矩阵变成 “棋盘”。“棋盘”的定义是：任意格子的上下左右四个方向的值都与其本身不同。
- 解题思路
- 判断是否能变为棋盘：
- 任意行（或列）的二进制表示只能有两种互为相反的模式。例如，
rowMask和reverseRowMask。 - 如果某一行或列不符合上述规则，则无法将矩阵变为棋盘。
- 确定交换次数：
- 统计当前矩阵中行和列的分布，与理想的棋盘状态的匹配程度，计算最小交换次数。
- 处理特殊情况：
- 当矩阵的大小
n为奇数时，棋盘中的1和0的数量会相差1。 - 当
n为偶数时，棋盘中的1和0的数量应完全相等。 - 使用位运算简化：
- 通过
bitmask记录行或列的二进制状态。 - 通过按位异或计算互为反转的行或列状态。
- 代码实现
- 代码解释
- 核心函数
getMoves： - 使用
mask表示行或列的二进制状态。 - 计算当前行或列需要多少次交换才能符合棋盘模式。
- 当
n为奇数或偶数时，处理逻辑不同： - 奇数：
1和0的数量相差1。 - 偶数：
1和0的数量相等。 - 主函数
movesToChessboard： - 遍历矩阵的每一行和每一列，检查其是否符合棋盘模式。
- 如果任意一行或列无法与棋盘模式匹配，返回
1。 - 如果满足条件，则计算最小的交换次数。
- 复杂度分析
- 时间复杂度：
- ：需要遍历整个矩阵来检查行和列的状态，并计算最小交换次数。
- 空间复杂度：
- ：只使用了少量额外变量和位运算处理。
2024.12.09 T1812. 判断国际象棋棋盘中一个格子的颜色
- 问题分析
- 国际象棋棋盘是 8x8 的矩阵，其中：
- 左上角格子 (
a1) 是黑色。 - 格子的颜色交替变化（黑白相间）。
给定一个国际象棋棋盘上的坐标
coordinates（如 "a1" 或 "h8"），判断这个格子的颜色是否为白色：- 解题思路
- 坐标的表示：
- 字母部分（
a到h）表示列，对应的 ASCII 值可通过减去'a'转换为数字（0到7）。 - 数字部分（
1到8）表示行，可通过减去'1'转换为数字（0到7）。 - 颜色判断：
- 行列之和为奇数的格子是白色。
- 行列之和为偶数的格子是黑色。
- 位运算优化：
(row + col) & 1用于快速判断颜色：- 如果结果为
1，说明是白色。 - 如果结果为
0，说明是黑色。
- 代码实现
- 代码解释
- 转换行列索引：
coordinates[0] - 'a'：将字母部分转为 0 到 7 的列索引。coordinates[1] - '1'：将数字部分转为 0 到 7 的行索引。- 颜色判断：
(coordinates[0] - 'a' + coordinates[1] - '1') & 1：- 计算行列之和并取模 2（使用位运算），判断是奇数还是偶数。
- 返回值：
- 如果结果为
1，返回true（白色）。 - 如果结果为
0，返回false（黑色）。
- 复杂度分析
- 时间复杂度：
- 仅涉及常量次的字符操作和简单计算。
- 空间复杂度：
- 仅使用了少量的局部变量，无额外空间开销。
2024.12.10 T935 . 骑士拨号器
- 问题分析
象棋骑士在电话拨号盘上的独特跳跃规则，要求计算长度为
n 的电话号码的数量。骑士可以从任何数字单元格开始，通过有效的骑士跳跃生成一系列号码。- 解题思路
- 骑士的移动规则：
- 骑士可以从一个数字单元格跳到其他数字单元格。以下是电话拨号盘的跳跃规则：
0: 可以跳到4, 6。1: 可以跳到6, 8。2: 可以跳到7, 9。3: 可以跳到4, 8。4: 可以跳到3, 9, 0。5: 无法跳跃。6: 可以跳到1, 7, 0。7: 可以跳到2, 6。8: 可以跳到1, 3。9: 可以跳到2, 4。- 动态规划 (DP)：
- 使用
dp[step][i]表示从数字i开始，经过step步后可以到达的路径数量。 - 状态转移公式：
其中，
moves[i]表示从数字i可以跳到的所有目标数字。 - 状态压缩优化：
- 由于计算时只需要当前步和上一步的状态，使用滚动数组优化空间复杂度。
- 初始状态：
- 第
0步时，每个数字都可以作为起始点，因此路径数量为 1。 - 结果计算：
- 从所有起始数字的路径数量累加得到最终结果。
- 代码实现
- 代码解释
- 定义跳跃规则：
- 使用二维数组
moves定义每个数字的跳跃目标。 - 动态规划：
dpPrev保存上一步的状态。dpCurr保存当前步的状态。- 对于每个数字，计算其跳跃目标数字的路径数量并累加。
- 结果计算：
- 最后一步的所有数字路径数量的总和就是最终结果。
- 模运算：
- 每次累加时都对结果取模，防止溢出。
- 复杂度分析
- 时间复杂度：
- 总共
n步，每步需要遍历 10 个数字，每个数字的跳跃目标最多为 3 个。 - 空间复杂度：
- 只需存储当前步和上一步的状态，空间复杂度为常数级别。
2024.12.11 T2717. 半有序排列
- 问题分析
nums[0] == 1（第一个元素为 1）nums[n-1] == n（最后一个元素为n）
给定一个排列
nums（包含从 1 到 n 的每个数字且每个数字恰好出现一次），要求通过交换相邻的两个元素，使得：我们需要计算将
nums 转变为 半有序排列 所需的最小交换次数。- 解题思路
- 找到
1的位置： - 遍历数组找到
1的索引pos1。 - 计算将
1移动到nums[0]所需的交换次数pos1。 - 将
1移到首位： - 从
pos1开始，将1向左逐步交换，直到移动到第一个位置。 - 找到
n的位置： - 再次遍历数组，找到
n的索引posN。 - 计算将
n移动到nums[n-1]所需的交换次数n - posN - 1。 - 返回结果：
- 两次移动的总和就是最终的最小交换次数。
- 代码实现
- 代码解释
- 找到
1的位置： - 遍历数组，找到
1的索引pos1。 - 索引
pos1表示1到达nums[0]所需的交换次数。 - 将
1移动到首位： - 从
pos1开始，将1向左逐步移动，同时调整其右侧的元素位置。 - 找到
n的位置： - 遍历数组，找到
n的索引posN。 - 索引
posN表示n到达nums[n-1]所需的交换次数。 - 返回最小交换次数：
- 将两次操作的交换次数累加得到结果。
- 复杂度分析
- 时间复杂度：
- 找到
1和n的位置需要两次线性扫描，总时间复杂度为 。 - 空间复杂度：
- 只使用了常量空间，空间复杂度为 。
2024.12.12 T2931. 购买物品的最大开销
- 问题分析
- 第
d天购买的物品的开销为values[i][j] * d。 - 最大化总开销需要优先购买价值最高的物品，并且越晚购买价值越高的物品越好。
给定一个
m x n 的矩阵 values，每一行代表一个商店的物品价值，所有物品的价值已经按非递增顺序排列。每天可以选择一个商店购买其当前价值最高的未购买物品。目标是通过尽可能高的开销完成所有物品的购买。开销计算规则：
- 解题思路
- 收集所有物品：
- 将矩阵
values展平为一维数组，并按降序排序。 - 逐天购买：
- 第
i天购买第i-1个最大价值的物品，计算开销。 - 计算总开销：
- 根据排序后的物品价值和购买天数，累积总开销。
- 排序：
- 计算开销：
方法一：直接排序法（略讲）
代码实现：
时间复杂度：
空间复杂度：
方法二：优先队列法（推荐）
核心思路：
- 使用优先队列（最小堆）动态维护当前所有商店中价值最高的物品。
- 每天从堆中取出当前价值最高的物品进行购买，同时将该商店的下一个最高价值物品加入堆中。
- 按购买天数和物品价值累积开销。
具体步骤：
- 初始化堆：
- 每个商店的价值最高的物品（最右边物品）加入优先队列。
- 逐天购买：
- 每天从堆中取出当前价值最高的物品，计算开销。
- 将对应商店的下一个最高价值物品加入堆中。
- 终止条件：
- 当所有物品都购买完（堆为空）。
代码实现：
复杂度分析
时间复杂度：
- 堆操作：每次取堆顶和插入的时间复杂度为 ，共进行
m * n次操作，因此时间复杂度为 。
空间复杂度：
- 优先队列：需要存储最多
m个商店的当前物品，空间复杂度为 。
2024.12.13 T3264. K 次乘运算后的最终数组 I
2024.12.14 T3266. K 次乘运算后的最终数组 II
方法一：
- 问题分析
- 每次找到数组中最小的值（如果存在多个最小值，选择最前面的一个）。
- 将找到的最小值替换为其值乘以
multiplier。
给定一个整数数组
nums，一个整数 k，以及一个整数 multiplier。需要对数组执行 k 次操作：最终返回经过
k 次操作后的数组。- 解题思路
- 找到最小值：
- 使用
std::min_element函数，找到数组中当前的最小值。如果有多个最小值，std::min_element会返回最前面的位置。 - 更新最小值：
- 将找到的最小值乘以
multiplier，更新数组。 - 重复操作：
- 执行上述步骤
k次。 - 返回结果：
- 最终的
nums数组即为结果。
- 代码实现
- 代码解释
min_element函数：std::min_element(nums.begin(), nums.end())用于找到数组中最小值的迭代器。- 如果有多个相等的最小值，它会返回最前面的一个。
- 更新最小值：
- 使用
iter直接访问最小值，将其更新为iter * multiplier。 - 循环操作：
- 重复执行
k次，每次都找到当前最小值并更新。 - 返回结果：
- 返回更新后的数组。
- 复杂度分析
- 时间复杂度：
- 找最小值的时间复杂度是 （
n是数组长度）。 - 重复操作
k次，总时间复杂度为 。 - 空间复杂度：
- 只使用了常量级别的额外空间，空间复杂度为
O(1)。
方法二：
- 问题分析
- 找到数组中最小值
x（若有多个最小值，选择最前面的一个）。 - 将该值替换为
x * multiplier。 - 最终对数组中每个值取模
10^9 + 7。
给定整数数组
nums，一个整数 k 和一个整数 multiplier。需要对数组进行以下操作 k 次：要求返回经过所有操作后，数组的最终状态。
- 解题思路
- 快速幂计算：
- 利用快速幂算法计算
multiplier^e % MOD，可以高效处理多次乘法操作。 - 这避免了直接对每个元素逐次相乘，从而提升效率。
- 提前计算所需倍数：
- 如果
multiplier足够大，每次乘以multiplier后的结果可能很快超出数组中最大值。 - 使用预处理方法，提前计算使每个元素增长到超过数组最大值所需的最小倍数及相应的幂次。
- 直接暴力模拟：
- 若剩余操作数
k较小，直接使用最小堆找到当前最小值并更新其值。 - 每次操作后，重新维护最小堆。
- 批量处理剩余操作：
- 若剩余操作数较多，利用数学公式计算结果：
- 将剩余的
k次操作按均匀分布应用到所有元素，减少逐次计算的复杂度。
优化操作次数
两种处理方式
- 代码实现
- 代码解释
- 快速幂：
- 使用快速幂计算乘法结果，避免逐次乘法导致的高时间复杂度。
- 预处理：
- 计算将每个元素提升到超过当前最大值所需的最小幂次和倍数。
- 暴力模拟：
- 若剩余操作较少，直接使用最小堆依次更新最小值。
- 批量处理：
- 若剩余操作较多，利用数学公式直接计算每个元素最终值，避免逐次更新。
- 复杂度分析
- 时间复杂度：
- 暴力模拟：（每次维护最小堆的时间复杂度）。
- 数学公式处理：。
- 预处理：。
- 总体时间复杂度为 。
- 空间复杂度：
- 使用最小堆和预处理表，空间复杂度为 。
2024.12.15 T1338. 数组大小减半
- 问题分析
给定一个整数数组
arr，要求从数组中选出一个整数集合，并删除这些整数在数组中的所有出现。目标是通过删除这些数字，使得剩余数组中的元素个数至少为原数组的一半。我们需要计算最小的整数集合大小，使得删除这些整数后，数组中剩下的元素个数不超过原数组的一半。
- 解题思路
- 统计元素出现频率：
- 使用哈希表
unordered_map来统计每个整数在数组中出现的次数。 - 将出现频率排序：
- 将所有数字的频率按降序排列，这样可以优先选择删除频率高的元素，从而更高效地减少数组的元素个数。
- 累积删除：
- 从频率数组中开始，逐步删除出现次数最多的数字，直到删除的元素总数超过数组的一半。记录删除数字的集合大小。
- 返回结果：
- 最终的结果即为删除数字的集合大小。
- 代码实现
- 代码解释
- 统计元素频率：
- 遍历数组
arr，用哈希表mp记录每个数字出现的次数。每个数字作为mp的键，出现次数作为值。 - 构建频率数组：
- 将所有数字的出现次数提取到
freq数组中。 - 降序排序：
- 使用
std::sort对freq数组按降序进行排序，这样频率高的数字排在前面。 - 删除数字并累加：
- 从
freq数组中逐个累加，删除频率最多的数字，直到删除的元素个数达到或超过数组长度的一半。 - 每次删除一个数字时，累加
sum（即已删除元素的个数），并通过i记录删除的数字集合的大小。 - 返回结果：
- 最终返回集合大小，即需要删除的数字的数量。
- 复杂度分析
- 时间复杂度：
- 统计频率的时间复杂度是 ，其中 n 是数组的长度。
- 将频率数组进行排序的时间复杂度是 ，其中 k 是不同元素的个数，最多为 n。
- 因此，总的时间复杂度是 ，在最坏情况下 k 接近 n，所以整体时间复杂度是 。
- 空间复杂度：
- 使用了一个哈希表
mp来存储元素及其频率，空间复杂度为 ，其中 k 是不同元素的个数，最多为 n。
2024.12.16 T1847. 最近的房间
- 问题分析
preferred: 目标房间号minSize: 最小面积要求- 房间面积大于等于
minSize。 - 房间号与
preferred的差的绝对值最小。 - 如果差值相等，选择房间号较小的。
给定一个二维数组
rooms 和二维数组 queries，每个房间都有唯一的房间号和面积。我们需要针对每一个查询，在符合条件的房间中找到最合适的房间。每个查询包含两个信息：对于每个查询，我们需要找到一个满足以下条件的房间：
如果没有满足条件的房间，返回 -1。
- 解题思路
- 排序
- 对房间
rooms按照面积从大到小排序，这样可以在处理查询时，逐步加入符合面积要求的房间。 - 对查询
queries按照最小面积minSize从大到小排序，这样可以在处理查询时，优先处理面积大的房间。 - 使用双指针和集合
- 使用一个指针
j遍历rooms数组，将符合最小面积要求的房间加入集合room_ids。 - 对于每个查询，通过集合
room_ids找到一个房间，其房间号与preferred的差的绝对值最小。 - 可以通过
lower_bound查找集合中第一个大于等于preferred的房间号。 - 检查集合中该位置及其前一个位置的差值，选择最合适的房间。
首先，我们需要根据房间的面积和查询的最小面积进行排序：
c. 计算最小差值
对于每个查询，使用集合中的房间号，找出与
preferred 的差值最小的房间号。d. 返回结果
将结果按照查询的顺序保存，最后返回答案。
- 代码实现
- 代码解释
- 排序房间：
- 使用
ranges::sort(rooms, {}, [](auto& a) { return -a[1]; });对房间按面积降序排序，确保面积大或相等的房间会在前面。 - 排序查询：
- 使用
ranges::sort(query_ids, {}, [&](int i) { return -queries[i][1]; });对查询按照minSize降序排序。query_ids数组保存了查询的索引，排序后方便逐个查询。 - 房间的加入：
- 使用
set<int> room_ids;来存储符合查询条件的房间号。set保证了房间号的有序性。 - 在处理每个查询时，首先将所有符合
minSize的房间号加入room_ids。 - 查找最合适的房间：
- 使用
lower_bound查找最接近preferred_id的房间号。 - 如果
it指向的房间号比preferred_id小，还需要检查前一个房间号。 - 比较差值，选择最小的差值对应的房间号。
- 答案保存：
- 将每个查询的结果保存到
ans数组，最终返回。
- 复杂度分析
- 时间复杂度：
- 排序：房间排序的时间复杂度是 ，查询排序的时间复杂度是 ，其中
n是房间数量，k是查询数量。 - 查询处理：对于每个查询，我们最多遍历一次房间数组和集合，查询部分的复杂度是 。
- 空间复杂度：
- 使用了一个
set来存储房间号，其空间复杂度是O(n)，此外还使用了O(k)的空间存储查询结果。因此，空间复杂度是 。
因此，总的时间复杂度是 。
2024.12.17 T3291. 形成目标字符串需要的最少字符串数 I
2024.12.18 T3292. 形成目标字符串需要的最少字符串数 II
- 问题分析
- 需要判断
target的子串是否是words中任意字符串的前缀。 - 使用高效的数据结构处理频繁的前缀查找。
- 通过有限的字符串拼接
target，确保字符串数量最少。
给定字符串数组
words 和目标字符串 target，每个 words[i] 都可以作为目标字符串的前缀。需要计算出通过连接这些前缀字符串形成目标字符串 target 所需的最少字符串数量。如果无法实现目标字符串，返回 -1。- 解题思路
- 使用 Aho-Corasick 自动机构建前缀树
- 构建前缀树（Trie），存储所有模式字符串（
words）。 - 为每个节点添加失败指针（
fail），使得匹配失败时能够高效跳转到下一个可能的匹配节点。
Aho-Corasick 自动机是一种高效的多模式字符串匹配算法，支持：
- 动态规划
- 定义
f[i]为构造target[0..i-1]所需的最少有效字符串数量。 - 遍历
target，在每个位置动态更新f，以记录通过前缀树的匹配状态。
利用自动机处理
target：- 算法步骤
- 构建
words的前缀树。 - 为前缀树构造失配指针（
fail）。 - 使用动态规划，通过前缀树匹配
target，最小化字符串连接次数。
- 代码实现
- 复杂度分析
- 时间复杂度：，其中 n 是 target 的长度，L 是 words 中所有字符串的长度之和。
- 空间复杂度：。
2024.12.19 T3285. 找到稳定山的下标
这个题太easy了，懒得写了，期末了尽量保证做题不保证题解了～
2024.12.20 T3138. 同位字符串连接的最小长度
- 问题分析
给定一个字符串
s，它由若干个相同的子字符串 t 和这些子字符串的同位字符串连接而成。我们需要找出字符串 t 的最小可能长度。所谓同位字符串，是指两个字符串由相同的字符组成，但字符的排列顺序可能不同。例如，“abc”和“bca”是同位字符串。- 解题思路
- 子串长度的选择：
- 如果
n（字符串s的长度）能被k整除，那么就可以尝试长度为k的子串。 - 否则，跳过当前长度。
- 验证同位字符串：
- 对于每个可能的长度
k，我们检查从第一个子串开始，后续的每一个子串是否都是同位字符串。 - 如果某个子串不是同位字符串，就跳过该长度，尝试更大的长度。
- 返回最小长度：
- 一旦找到一个合法的
k，就返回这个长度。
我们可以从小到大尝试每个可能的长度
k，看是否可以将字符串 s 划分为若干个长度为 k 的子串，这些子串要么相同，要么是同位字符串。- 代码实现
- 代码解释
- 遍历每个可能的子串长度：
- 代码从
k = 1开始遍历每个可能的子串长度，直到k = n / 2。如果n % k != 0，就跳过这个长度，因为无法将s平均分割为k长度的子串。 - 验证每个长度的子串是否是同位字符串：
- 首先，统计字符串
s中第一个长度为k的子串的字符频次（cnt0）。 - 然后，依次检查后续的每个长度为
k的子串的字符频次。如果某个子串的字符频次与cnt0不同，则说明这不是一个合法的同位字符串，跳出循环，尝试更大的k。 - 返回最小的有效长度：
- 如果找到了一个长度
k，使得所有子串都是同位字符串，就返回该长度。 - 如果没有找到合法的
k，则返回n，表示最小的子串长度为整个字符串s的长度。
- 复杂度分析
- 时间复杂度：
- 外层循环遍历
k从 1 到n / 2，因此有最多n / 2次迭代。 - 对于每个
k，我们检查每个长度为k的子串，共需要遍历n / k个子串。每个子串的检查需要O(k)的时间（因为要统计k个字符的频次）。 - 总的时间复杂度为：
- 这里的复杂度是平方级别的，因为我们在最坏情况下需要遍历
n次，每次遍历都进行最多O(n)的操作。 - 空间复杂度：
- 使用了固定大小的数组
cnt来存储每个子串的字符频次，数组大小为 26（即字母表大小），因此空间复杂度是 （常数空间）。
2024.12.21 T2545. 根据第 K 场考试的分数排序
- 问题分析
- 的整数矩阵
score，每行表示一个学生的成绩。 - 整数 ，表示要按第 场考试的分数排序。
- 排序后的矩阵，行按照第 列分数从高到低排序。
我们需要对一个矩阵进行排序，其中每行表示一个学生的成绩，每列表示一场考试的分数。要求按照某一场考试（第 kk 场考试）的分数从高到低对矩阵的行进行排序，返回排序后的矩阵。
输入：
输出：
- 解题思路
- 问题分解：
- 我们需要根据第 列的值排序矩阵的行。
- 排序规则为降序排序。
- 实现方法：
- 使用 C++ 的
std::sort，通过传入自定义排序函数对score按行排序。 - 自定义排序函数比较每一行的第 列值，确保按降序排列。
- 返回结果：
- 排序后的矩阵直接返回。
- 代码实现
- 代码解释
- 函数定义：
vector<vector<int>> sortTheStudents(vector<vector<int>>& score, int k)：- 输入参数
score是成绩矩阵。 - 输入参数 表示按第 列排序。
- 返回排序后的矩阵。
- 排序逻辑：
sort(score.begin(), score.end(), ...)：sort对score的行（向量）排序。- 自定义排序函数
[](const vector<int>& u, const vector<int>& v)比较两行： u[k] > v[k]实现降序排序。- 返回结果：
- 排序后的矩阵
score。
- 复杂度分析
- 时间复杂度：
- 排序的时间复杂度为 ，其中 是矩阵的行数。
- 每次比较的时间复杂度为 （比较第 列的值）。
- 空间复杂度：
- 使用原地排序，不需要额外空间。空间复杂度为：
综合时间复杂度为：
2024.12.22 T1387. 将整数按权重排序
- 问题分析
- 如果是偶数，则
x = x / 2。 - 如果是奇数，则
x = 3 * x + 1。
题目要求我们根据整数的“权重”对区间
[lo, hi] 之间的整数进行排序，然后返回排序后的第 k 个数。整数的“权重”是指根据以下规则将该整数变成 1 所需要的步数：我们需要计算每个整数的权重并根据权重排序，若权重相同，则按数值升序排序。
- 解题思路
- 权重计算：首先，我们需要为每个整数计算其权重。计算权重的过程遵循题目给出的规则，这可以通过递归实现。为了提高效率，我们使用一个
unordered_map来记忆化已计算的结果，避免重复计算。 - 排序：对于区间
[lo, hi]内的所有整数，我们计算每个整数的权重，并将其存入一个数组。然后根据权重进行升序排序，若权重相同，则按数值升序排序。 - 返回第 k 个数：排序完成后，直接返回排序后的第
k个数。
- 代码实现
- 代码解释
- unordered_map<int, int> mp：这个哈希表用于缓存已计算的整数权重。每当计算一个整数的权重时，我们首先检查该整数的权重是否已经计算过，避免重复计算。
- dfs(int i)：这是一个递归函数，计算整数
i的权重。如果i等于 1，则返回 0，表示权重为 0；否则，根据i是奇数还是偶数，递归计算其权重并返回。计算过程中使用了记忆化优化，避免重复计算。 - getKth(int lo, int hi, int k)：此函数的目标是返回区间
[lo, hi]中的第k个数。首先，通过iota函数生成区间[lo, hi]内的数字列表。然后，使用ranges::sort对这些数字按照它们的权重升序排序，若权重相同则按数值升序排序。最后，返回排序后的第k个数字。
- 复杂度分析
- 计算权重的时间复杂度：每个整数的权重计算最多进行 32 步，因为题目保证了整数变成 1 所需的步数是一个 32 位有符号整数，因此单次权重计算的复杂度是 ，其中 x 是整数的大小。由于使用了记忆化优化，每个整数的权重最多计算一次。
- 排序的时间复杂度：我们需要对
[lo, hi]区间内的所有整数进行排序。排序的时间复杂度是 ，其中n是区间[lo, hi]中整数的个数。 - 总体时间复杂度：整体时间复杂度为 ，其中
n是区间[lo, hi]中的整数个数。每次计算整数的权重的复杂度是 ，但在排序过程中整体的时间复杂度会被排序的 主导。 - 空间复杂度：空间复杂度为 ，用于存储区间中的整数列表。由于我们使用了记忆化，存储已计算权重的
unordered_map的空间复杂度为 ，其中n是区间[lo, hi]内整数的数量。
2024.12.23 T855 . 考场就座
- 问题分析
- 入座：学生进入考场时，他们必须选择距离其他学生最远的座位。如果有多个座位符合条件，他们会选择编号最小的座位。
- 离开：某个学生离开座位后，该座位变为空，系统需要更新座位信息。
需要设计一个模拟考场座位分配的类
ExamRoom，该类的功能主要有两个：- 解题思路
- 数据结构设计：
- 使用
set<int>来维护已经占用的座位，保证所有座位按升序排列，并且可以快速地检查某个座位是否已被占用。 - 使用
priority_queue<pair<int, int>>（最大堆）来存储空座位区间，便于快速选择距离其他学生最远的座位。队列中的每个元素表示一对座位区间(start, end)，即从start到end的连续空座位区间。 - 入座逻辑：
- 如果考场为空（即没有学生），则学生直接坐在第一个座位（座位编号为 0）。
- 否则，我们需要选择一个距离其他学生最远的座位。这可以通过查看最大堆中的区间来实现。区间的计算方式是：对于每个空座位区间，计算其最远座位距离，选择距离最大的位置，若多个座位距离相同，选择编号最小的座位。
- 离开逻辑：
- 学生离开后，原本的座位成为空座位，更新空座位区间，并将新的空座位区间加入最大堆。
- 代码实现
- 代码解释
- Comp 结构体：
- 该结构体定义了
priority_queue的比较规则，用来根据区间的大小和起始位置排序。优先级队列会根据区间长度降序排序，如果长度相同，则优先选择起始位置较小的区间。 - ExamRoom 类的成员函数：
ExamRoom(int n)：初始化函数，n为座位总数。初始化时，我们将整个座位区间[0, n-1]放入最大堆。seat()：当有学生进来时，我们从最大堆中取出最远的座位区间，计算出最优座位（最远座位），然后更新seats集合，最后将新产生的空座位区间推入最大堆。leave(int p)：当学生离开时，我们首先从seats集合中删除该座位，然后计算出新的空座位区间，并将该区间重新放入最大堆。
- 复杂度分析
seat()函数：- 最坏情况下，我们需要从
priority_queue中提取最大元素并插入新的元素。priority_queue的操作复杂度是 ，插入和提取操作都需要 时间，因此seat()的时间复杂度为 。 leave()函数：- 删除一个元素的复杂度为 ，然后插入新生成的空区间同样是 。因此
leave()的时间复杂度也是 。 - 总体时间复杂度：
- 总体空间复杂度：
- 主要是由
set<int>和priority_queue<pair<int, int>>组成。set存储已经占用的座位，priority_queue存储空座位区间，因此空间复杂度为 。
2024.12.24 T1705. 吃苹果的最大数目
- 问题分析
在这道题目中，我们有一棵特殊的苹果树，在每个给定的
n 天中，树上会长出不同数量的苹果，并且每种苹果都有它的腐烂时间。每天你最多能吃掉一个苹果，目的是计算出你能吃掉的苹果的最大数目。对于第
i 天，apples[i] 表示树上长出的苹果的数量，而 days[i] 表示这些苹果在多少天后会腐烂。我们的目标是设计一个高效的算法来模拟这个过程，尽可能多地吃掉苹果。- 解题思路
- 优先队列：我们使用一个优先队列来存储腐烂日期和苹果数量的对
(腐烂时间, 苹果数量)。优先队列会根据腐烂时间（最小的腐烂时间优先）排序，这样我们就可以在每一天挑选出最早腐烂的苹果。 - 遍历天数：从第 0 天开始，我们逐天检查苹果树上的苹果。每一天，我们将腐烂时间到当前日期的苹果移除（因为它们已经腐烂）。然后，如果当天有新苹果长出来（即
apples[i] > 0），我们将这些苹果加入优先队列。 - 吃苹果：如果优先队列不为空，我们从中取出最早腐烂的苹果，并将其数量减 1，表示我们吃掉了一个苹果。如果该类型的苹果还有剩余，则将其重新放入优先队列中，继续等待下一次食用。
- 终止条件：当我们遍历完所有天数并且优先队列为空时，停止。
我们可以通过一个优先队列（最小堆）来模拟这个过程。最小堆将帮助我们在每一天尽量选择腐烂时间最早的苹果来食用。具体步骤如下：
- 代码实现
- 代码解释
- 变量初始化：
ans：用来记录我们吃掉的苹果数。n：苹果树的天数。pq：一个最小堆，用来存储腐烂时间和苹果数量。- 循环逻辑：
- 遍历每一天，检查是否有苹果腐烂（通过
while (!pq.empty() && pq.top().first == i)来移除腐烂的苹果）。 - 如果当天有新的苹果（
apples[i] > 0），就将它们加入到优先队列，腐烂时间为i + days[i]。 - 如果优先队列不为空，意味着我们可以吃掉一个苹果，就从堆中取出最早腐烂的苹果，并更新苹果数量。如果该种苹果数量不为 1，继续将它放回优先队列。
- 返回结果：
- 最后返回
ans，即我们能吃掉的苹果数量。
- 复杂度分析
- 时间复杂度：
- 我们遍历了每一天，对于每一天，可能有一个苹果被加入到优先队列中，也可能有一个苹果从优先队列中被移除。每个操作的时间复杂度是 ，因此，总的时间复杂度是 ，其中 是苹果树的天数。
- 空间复杂度：
- 使用了一个优先队列来存储苹果的腐烂时间和数量。最坏情况下，所有的苹果都不会腐烂（即每一天都有新的苹果），此时空间复杂度为 。
- 问题分析
我们需要将一个大小为 的矩形蛋糕切成 的小块。切割的操作开销不相同，对于每一条水平切割线和垂直切割线，有给定的切割开销数组
horizontalCut 和 verticalCut。每次切割会增加一块小蛋糕，我们的目标是以最小的总开销将蛋糕切成 的小块。- 解题思路
- 排序切割线的开销：首先，按切割开销从大到小对水平切割线
horizontalCut和垂直切割线verticalCut进行排序。这样可以保证我们每次选择开销最大的切割线。 - 模拟切割过程：
- 初始化水平和垂直的分块数（初始时整个蛋糕就是一个大块，即水平和垂直方向上分别只有1块）。
- 每次选择切割开销较大的切割线进行切割，并根据当前分块数计算切割的成本。
- 对于每次切割，无论是水平切割还是垂直切割，切割的成本都等于当前切割线的开销乘以当前水平和垂直块数。
- 更新切割方向的分块数。
- 边界条件：
- 如果水平切割线用完了，则只能进行垂直切割；反之亦然。
- 每次选择较大的切割线，直到所有切割都完成。
要解决这个问题，我们可以使用贪心算法。由于每次切割都会将蛋糕切成两个部分，并且切割操作的开销是根据每个部分的数量来计算的，因此我们应该优先选择开销较大的切割线，以便在切割的过程中减少对后续操作的影响。
具体思路如下：
- 代码实现
- 代码解释
- 排序：
- 我们首先对
horizontalCut和verticalCut数组进行排序，使用greater<long long>()保证它们按降序排列。这样可以确保我们每次选择开销最大的切割操作。 - 贪心选择切割操作：
- 使用两个指针
i和j分别指向horizontalCut和verticalCut数组的当前位置。初始化时，水平和垂直方向上的切割块数分别为 1。 - 在每次循环中，我们比较当前
i和j指向的切割开销，选择开销较大的切割线。 - 每次切割操作都会增加分块数并更新总开销。
- 处理边界条件：
- 如果某一方向的切割已经完成（即指针
i或j超过了数组的大小），我们只能选择另一方向的切割。 - 返回结果：
- 最后，返回
totalCost，即最小的总切割开销。
- 复杂度分析
- 时间复杂度：
- 排序
horizontalCut和verticalCut的时间复杂度是 ，其中m和n分别是水平和垂直切割线的数量。 - 计算总开销的过程中，每次操作的时间复杂度为 ，总共进行
m + n - 2次操作，因此总时间复杂度为 。 - 空间复杂度：
- 由于我们只使用了常量额外空间来存储变量，空间复杂度是 。
2024.12.26 T3083. 字符串及其反转中是否存在同一子字符串
- 问题分析
题目要求我们检查字符串中是否存在一个长度为 2 的子字符串，其反转后的字符串也在原字符串中出现。具体来说，如果字符串
s 中存在子字符串 ab，并且反转后的 ba 也存在，则返回 true；否则返回 false。- 解题思路
- 位运算压缩状态：
- 我们可以利用一个二维布尔矩阵来表示每对字符是否曾作为长度为 2 的子字符串出现过。由于字符是小写英文字母，范围是
a到z，共有 26 个字符，因此矩阵的大小为 。 - 为了节省空间，可以将二维矩阵用一个大小为 26 的整数数组代替，每个整数用 26 位的二进制表示每个字符的状态。
- 子字符串的记录：
- 遍历字符串
s，对于每个长度为 2 的子字符串s[i]s[i+1]： - 记录子字符串的状态：将
s[i+1]对应的位设置为 1，表示s[i]后可以接s[i+1]。 - 检查反转后的子字符串是否已出现：如果
s[i+1]的记录中包含s[i]，即h[s[i+1]]的s[i]位为 1，则说明反转后的子字符串存在，返回true。 - 快速返回：
- 一旦发现某个反转的子字符串存在，可以立即返回
true，无需继续遍历。
- 代码实现
- 代码解释
- 状态记录：
h|= (1 << y)表示字符x后可以接字符y。通过位操作，利用1 << y将y的位置标记为 1。- 检查反转状态：
h[y] & (1 << x)检查字符y后是否接过字符x。如果结果不为 0，说明反转的子字符串yx存在。- 效率：
- 由于字符范围是固定的（26 个小写字母），使用位运算的方式能够高效地检查和记录子字符串状态，且内存占用低。
- 复杂度分析
- 时间复杂度：
- 遍历字符串一次，复杂度为 ，其中 是字符串的长度。
- 空间复杂度：
- 使用一个大小为 26 的整数数组，每个整数用 26 位记录状态，空间复杂度为 。
2024.12.27 T3159. 查询数组中元素的出现位置
- 问题分析
题目要求我们对于每个查询，找到整数数组
nums 中指定次数 queries[i] 的整数 x 出现的位置，如果 x 出现的次数少于查询次数，则返回 -1。- 解题思路
- 查找所有
x的位置： - 遍历
nums数组，记录所有x出现的位置。 - 使用一个数组
idx来存储这些位置。具体来说，当nums[i] == x时，将i添加到idx中。 - 处理查询：
- 对于每个查询
queries[i]，我们检查idx数组的长度。如果queries[i]小于等于idx的大小，则返回idx[queries[i] - 1]，即查询指定的第queries[i]个位置（注意查询是 1-indexed，因此需要减 1）。 - 如果
queries[i]超出了idx数组的范围，则返回1。
- 代码实现
- 代码解释
- 找到所有
x的位置： for (int i = 0; i < nums.size(); i++)遍历数组nums，如果nums[i] == x，就将索引i添加到idx中，表示x在nums中的出现位置。- 处理查询：
- 对于每个查询
queries[i]，首先检查queries[i]是否小于等于idx的大小。 - 如果小于等于，则返回
idx[queries[i] - 1]（因为查询是 1-indexed，需要减 1）。 - 如果大于，则返回
1，表示该查询的x出现次数不足。 - 返回结果：
- 将每个查询的结果保存在
ans数组中，最后返回该数组。
- 复杂度分析
- 时间复杂度：
- 遍历
nums数组的时间复杂度为 ，其中 是数组nums的长度。 - 遍历
queries数组的时间复杂度为 ，其中 是数组queries的长度。 - 总的时间复杂度为 。
- 空间复杂度：
- 存储
x所有出现位置的数组idx的大小为 ，其中 是x出现的次数（最多为 ）。 - 存储查询结果的数组
ans的大小为 。 - 总的空间复杂度为 。
2024.12.28 T3046. 分割数组
- 问题分析
nums1和nums2的长度相等，且均为数组的一半长度。nums1中的元素必须互不相同。nums2中的元素必须互不相同。- 如果能够找到符合条件的分割方式，返回
true，否则返回false。
题目要求我们将一个偶数长度的整数数组
nums 分割成两个长度相等的子数组 nums1 和 nums2，并且满足以下条件：- 解题思路
- 频次统计：
- 对于一个合法的分割，数组中的每个元素最多只能出现 2 次。因为如果某个元素出现超过 2 次，那么它就无法被分配到两个互不相同的子数组中。
- 我们可以利用一个哈希表
mp来记录每个数字的出现次数。如果某个数字的出现次数超过了 2 次，直接返回false，因为无法满足要求。 - 分割检查：
- 如果所有元素的出现次数不超过 2 次，数组就可能分割成符合条件的两个子数组。具体来说：
- 每个元素出现 2 次时，必须将它均匀分配到两个子数组中。
- 每个元素出现 1 次时，可以任意分配到
nums1或nums2。 - 返回结果：
- 如果没有任何元素的出现次数超过 2 次，就返回
true，否则返回false。
- 代码实现
- 代码解释
- 频次统计：
unordered_map<int, int> mp用来存储每个元素的出现次数。if (++mp[num] > 2)这一行在遇到某个元素时，首先将该元素的出现次数加 1，如果该元素的次数超过了 2 次，直接返回false，因为这不满足条件。- 返回结果：
- 如果所有元素的出现次数都不超过 2 次，则说明可以找到一种合法的分割方式，返回
true。
- 复杂度分析
- 时间复杂度：
- 遍历数组
nums一次，时间复杂度为 ，其中 是数组的长度。 - 空间复杂度：
- 使用哈希表存储每个元素的频次，空间复杂度为 ，其中 是数组的长度。
2024.12.29 T1366. 通过投票对团队排名
- 问题分析
- 根据每个团队获得的 排位第一 的票数排序；如果并列，则比较 排位第二 的票数，依次类推。
- 如果团队的所有排名票数都相等，则按字母顺序排序。
本题的目标是通过投票排序一个团队列表，依据团队的排名票数以及字母顺序来决定最终顺序。具体规则如下：
- 解题思路
- 统计排名票数：
- 使用一个
map，其中键是团队名称（字符），值是一个长度为n的数组，记录每个团队在每个排位上获得的票数。例如，mp['A'][0]表示团队A在 第一名 的票数，mp['A'][1]表示团队A在 第二名 的票数。 - 自定义排序：
- 对团队按上述规则进行排序。
- 首先比较每个团队的票数数组，从第一名到最后一名依次比较票数，票数多的排前面。
- 如果所有排名票数都相等，则按字母顺序排序。
- 生成结果：
- 将排序后的团队字符依次拼接成字符串，作为最终结果返回。
- 代码实现
- 代码解释
- 统计排名票数：
- 遍历每个投票字符串
v，对于每个字符v[i]，将其在i名次上的票数加 1。 - 确保
mp[v[i]]的大小为团队数量（v.size()），避免数组越界。 - 排序规则：
- 使用
std::sort按照自定义规则对团队排序。 - 比较
mp[a]和mp[b]，即从第一名到最后一名的票数逐一比较。如果票数不同，则票数多的优先；如果票数相同，则按字母顺序排序。 - 生成结果：
- 排序后，将结果存储到字符串
res中并返回。
- 复杂度分析
- 时间复杂度：
- 统计票数：遍历所有投票字符串，每个字符串长度为
n，投票人数为m，时间复杂度为 。 - 排序：对
n个团队按票数排序，排序复杂度为 。 - 总时间复杂度为 。
- 空间复杂度：
mp的大小为 ，因为每个团队对应一个长度为n的数组。- 总空间复杂度为 。
2024.12.30 T1367. 二叉树中的链表
- 问题分析
- 关键点：
- 二叉树：从某个节点向下，可能是左子树或右子树。
- 链表：每个节点值要与树中的一个节点值一一匹配。
本题要求判断在给定的二叉树中是否存在一条从某个节点开始的路径，且路径的节点值依次与给定的链表的节点值一一对应。路径必须是从树的根节点开始并向下延伸的连续路径。
- 解决思路：
- 深度优先搜索（DFS）：
- 对每一个树的节点，我们尝试匹配链表中的第一个节点。
- 如果当前树的节点值与链表的第一个节点匹配，则递归地检查左子树和右子树，继续匹配链表的下一个节点。
- 如果树的某个路径能够完全匹配链表，则返回
True；否则返回False。 - 递归调用：
- 在每个节点上，我们都检查是否从当前节点开始存在符合条件的路径。
- 如果当前节点值和链表当前节点值匹配，则递归去检查左子树或右子树。
- 如果路径不匹配，则直接返回
False。 - 返回条件：
- 如果链表的所有节点都匹配完毕，则返回
True。 - 如果树的节点遍历完了还没有找到匹配路径，则返回
False。
- 代码实现
- 代码解释
- DFS函数：
- 如果链表已经为空 (
head == nullptr)，说明所有节点都匹配成功，返回true。 - 如果树为空 (
root == nullptr)，说明当前路径无法匹配链表，返回false。 - 如果当前树节点的值与链表的当前节点值相等，则继续向下匹配，分别递归检查左子树和右子树。
- 如果当前树节点的值与链表的当前节点值不相等，则返回
false。 - isSubPath函数：
- 如果链表为空，直接返回
true。 - 如果树为空，且链表不为空，返回
false。 - 从根节点开始，递归地检查树的每个节点，看是否存在一条路径与链表匹配。如果存在匹配的路径，则返回
true。 - 递归调用：
- 首先在当前树的节点上执行 DFS，检查从当前节点开始是否存在匹配的路径。
- 然后递归检查左子树和右子树，看是否有其他节点能作为链表匹配的起点。
- 复杂度分析
- 时间复杂度：
- 每个节点和每个链表节点只会被访问一次，因此最坏的情况下时间复杂度为 ，其中 是二叉树中的节点数， 是链表的长度。
- 对于每个树节点，我们最多需要执行一次链表的递归匹配。
- 空间复杂度：
- 递归的深度是二叉树的最大深度 ，其中 是树的高度.
- 总空间复杂度为 ，其中 是树的高度， 是链表的长度。
2024.12.31 T3219. 切蛋糕的最小总开销 II
见2024.12.25 T3219.切蛋糕的最小总开销 I
- 作者:小H狂炫香菜
- 链接:https://hjwvip.top/14d01f2a87be80898800d59375f90537
- 声明:本文采用 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)
