2.1题目 2325. 解密消息

【哈希表】用哈希表存对照表，遍历每个字符，替换为对应字符。

2.2题目 1129. 颜色交替的最短路径

【BFS】最短路问题，先对所有边进行预处理，将所有边按照颜色分类，存储到多维数组g中，g[0]存红色边，g[1]存蓝色边。q存搜索到的节点和当前边的颜色，vis存已经搜索过的节点和当前边的颜色，d存搜索层数即节点到起点的距离，ans存每个节点到起点的最短距离。先将起点0和起点边颜色0或1入堆，表示从起点出发且当时是红色或蓝色边，开始BFS，每次取出一个节点(i,c)，当前节点答案未更新就将当前节点的答案更新为当前层数d，然后将颜色c取反。

2.3题目 1145. 二叉树着色游戏

【DFS】贪心，哪颗子树最大，二号玩家就选哪颗，设n2为二号玩家最多可以染的节点个数，左子树大小为l_size，右子树大小为r_size。父节点子树大小为n-1-l_size-r_size，n2 = max(l_size, r_size, n-1-l_size-r_size)。

2.4题目 1798. 你能构造出连续值的最大数目

【排序+贪心】先排序，遍历数组，对于当前遍历到的元素v，如果v>ans，说明无法构造出ans+1个连续的整数，直接跳出循环，否则说明可以构造出ans+v个连续整数。

2.5题目 1210. 穿过迷宫的最少移动次数

【BFS】相当于网格图上求起点到重点的最短路长度，但多一个水平/垂直条件，可以添加一个维度解决，用（x,y,s）表示蛇尾在第x行y列，s=0表示水平状态，s=1表示垂直状态，则初始位置为(0, 0, 0)， 最终位置为(n - 1, n - 2, 0)。用三元组表示(x,y,s)的变化量，状态变换可以用异或运算解决。最后需要判断：移动后蛇身不能出界，移动后蛇身不能在障碍物上，旋转需要保证(x+1, y + 1)没有障碍物。蛇尾在(x,y)，如果s=0，则蛇头在(x, y + 1)，如果s = 1， 蛇头在(x + 1, y)，合并成一个公式表示蛇头：(x+s, y + s ⊕ 1)。

2.6题目 2331. 计算布尔二叉树的值

【递归】要计算当前节点node的值，首先需计算出两个叶子节点组成的子树的值，再计算出当前节点组成的子树的值。

2.7题目 1604. 警告一小时内使用相同员工卡大于等于三次的人

【哈希表 + 排序】同一个员工使用卡的时间顺序是按照h和min递增的，遍历数组keyname和keytime，哈希表记录事件列表。

2.8题目 1233. 删除子文件夹

【排序】将folder按照字典序排序，遍历数组，对于当前遍历到的文件夹f，如果长度大于等于最后一个文件夹的长度，并且它的前缀包含答案数组的最后一个文件夹再加上一个“/”，说明f是答案数组中最后一个文件夹的子文件夹。

2.9题目 1797. 设计一个验证系统

【哈希表】维护一个哈希表，键是tokenId，值是过期时间，generate操作时，将tokenId作为键，currentTime + timeToLive作为值存入哈希表中；renew操作时，如果tokenId不在哈希表中，或者currentTime≥d[tokenId]，则忽略当前操作否则更新为currentTime + timeToLive，countUnexpiredTokens操作时，遍历哈希表统计未过期的tokenId个数。

2.10题目 1223. 掷骰子模拟

【DP】定义f[i] [j] [x]为投掷前i次骰子，且第i次投掷的点数为j，连续投掷点数j的次数为x的方案数，初始时f[1] [j] [1] = 1，(1≤j≤6)，答案是ΣΣf[n] [j] [x]。

2.11题目 2335. 装满杯子需要的最短总时长

【贪心 + 分类讨论】设a b c为数组amount中的三个数，有以下两种情况：如果a+b≤c，只需要c次操作可将所有数变为0，答案为c；如果a+b>c，每次操作都可以将其中两个数减1，最后会剩下一个数（取决与总和是偶数还是奇数），ans = ⌊(a+b+c+1)/2⌋

2.12题目 1138. 字母板上的路径

【模拟】从起点(0,0)出发，模拟每一步的移动，将每一步的移动结果拼接到答案中，移动方向遵循左上右下的顺序。

2.13题目 1234. 替换子串得到平衡字符串

【同向双指针】如果待替换字串之外任意字符出现次数都>n/4，那么无论怎么替换都无法使这个字符的出现次数=n/4。如果待替换字串之外任意字符出现次数都不超过n/4，那么可以通过替换把s变成平衡字符串。用双指针，设字串左右端点为l和r，枚举r，如果字串外任意字符出现次数都不超过n/4，则说明l到r这段字串可以是待替换字串，用其长度r-l+1更新答案的最小值。

2.14题目 1124. 表现良好的最长时间段

【前缀和 + 哈希表】维护一个变量s，表示从下标0到当前下标的这一段，劳累天数与不劳累天数的差值，如果s>0，说明从下标到当前下标这一段满足“表现良好”。用pos记录每个s第一次出现的下标。遍历hours，对于每个i，如果hous[i]>8，就让s+1，否则-1。如果s>0，说明从下标0到当前下标这一段满足“表现良好”，否则，如果s-1在哈希表中，记j=pos[s-1]，说明从下标j+1到当前下标i这一段，满足“表现良好”，更新ans，如果s不在哈希表中，记录pos[s] = i。

2.15题目 1250. 检查「好数组」

【数学】数论中的“裴蜀定理”——对于不全为0的任意整数a和b，记g=gcd(a,b)，则对于任意整数x和y都满足ax+by是g的倍数，特别地，存在整数x和y满足ax+by=g。也可以推广到多个整数的情况，对于不全为0的任意n个整数a1,a2,...an，记n个数的gcd为g，则对于任意n个整数x1,x2,...xn，都满足求和ai×xi是g的倍数。正整数a1-an的最大公约数是1的充分必要条件是存在n个整数x1-xn满足求和ai×xi = 1。由裴蜀定理，题目等价于求nums中全部数字的最大公约数是否是1.

2.16题目 2341. 数组能形成多少数对

【哈希表】统计数组nums中每个数字x出现的次数，记录在哈希表或数组cnt中，遍历cnt，对于每个数字x，如果x出现的次数v>1，则可以从数组选中两个x形成一个数对，将v除以2向下取整，可得到当前数字x可以形成的数对数目，最后剩余的个数为nums的长度减去可以形成的数对数目×2。

2.17题目 1139. 最大的以 1 为边界的正方形

【前缀和 + 枚举】枚举正方形边长d和左上角坐标(i,j)，四条边全为1等价于1的个数都等于d，用前缀和快速计算1的数量。

2.18题目 1237. 找出给定方程的正整数解

【相向双指针】由于f是单调递增函数，可以从x=1，y=1000开始，表示在横坐标为x，1000以及纵坐标为[1，y]矩形范围内搜索答案。分类讨论：1.如果f（x，y）2，那对于任意x>x，都有f（x'，y)>f（x，y）>z，这说明固定y枚举其余x无法找到答案，那么将刘减一，缩小搜索范围。3.如果f（x，y）=z，那么记录答案，同情况1一样，将x加一。由于f（x+1，y）>f（x，y）=z，根据情况2，可以同时将y减一。不断循环直到x>1000或y<1为止，此时搜索范围为空。

2.19题目 1792. 最大平均通过率

【优先队列（增量大根堆）】假设一个班级当前通过率为a/b，将一个聪明学生安排到此班级后，班级通过率变成(a+1)/(b+1)，通过率增量为(a+1)/(b+1) - a/b。维护一个大根堆（优先选择通过率增加量最大的班级），堆中存储每个班级的通过率增量，进行extraStudents次操作，每次从堆顶取出一个班级，将这个班级的人数和通过人数都+1，然后将这个班级通过率增量重新计算并放回堆中，重复这个过程直到所有学生都分配完毕，最后将所有班级的通过率求和，然后除以班级数目即为答案。

2.20题目 2347. 最好的扑克手牌

【哈希表 + 计数】按题意求解。

2.21题目 1326. 灌溉花园的最少水龙头数目

【贪心】对于能覆盖某个左端点的水龙头，选择能覆盖最远右端点的水龙头是最优的，所以，先预处理数组ranges，对于第i个水龙头，它能覆盖的左端点l=max(0, i - ranges[i])，右端点r = i + ranges[i]，算出所有能覆盖左端点l的水龙头中，右端点最大的那个位置，记录在数组last[i]中。定义mx为当前能覆盖的最远右端点，pre为上一个水龙头覆盖的最远右端点。在[0,....,n-1]范围内遍历所有位置，对于当前位置i，用last[i]更新mx，即mx=max(mx, last[i])，如果mx<i，说明无法覆盖下一个位置，返回-1；如果pre=i，说明需要使用一个新的子区间，更新pre=mx。

2.22题目 1140. 石子游戏 II

【DP + 后缀和】定义f[i] [m]表示从piles[i]开始拿石子，可得到的最大石子数。定义后缀和s[i] = Σpiles[j]，有f[i] = s[i] - min(f[i + x], max(m, x))，ans= f[0] [1]。

2.23题目 1238. 循环码排列

【位运算】“在一组数的编码中，若任意两个相邻（包括首尾）的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）”。二进制码转换成二进制格雷码，其法则是保留二进制码，其法是保留二进制码的最高位作为格雷码的最高位，次高位格雷码为二进制码的高位和次高位相异或，格雷码其余各位与次高位的求法类似。对整数x，x ^ (x >> 1)可以得到其格雷码。gray(0) = 0，那么gray(0) ⊕ start = start，gray(i)与gray(i - 1)只有一个二进制位不同，所以gray(i) ⊕ start 与 gray(i - 1) ⊕ start也只有一个二进制位不同，所以可以直接将[]0,...,2^n-1]这些整数转换成对应的gray(i) ⊕ start，可以得到首项位start的格雷码排列。

2.24题目 2357. 使数组中所有元素都等于零

【哈希集合】贪心策略，观察可知，操作数数组中不同非零元素个数。

2.25题目 1247. 交换字符使得字符串相同

【哈希表 + 贪心】s1[i] = s2[i]的位置不用处理，s1[i]!=s2[i]的个数记作d，d为奇数 奇数不能均分所以不可能，d为偶数，则不同的情况为s1[i] = 'x'，s2[i] = 'y'或s1[i] = 'y'，s2[i] = 'x',通过一次交换最多使d-2（贪心），如果不同的x个数为偶数，则每次都d-2，总次数d/2，不同的x为奇数，则每次d-2，最后还剩一对不同要通过两次交换，所以是(d - 2)/2 + 2即d/2 + 1

2.26题目 1255. 得分最高的单词集合

【二进制枚举】由于数据范围不大可以二进制枚举出所有的单词组合，判断每个单词组合是否满足要求，满足则积分，然后取得分最大的单词组合，首先用哈希表或数组cnt记录字母表letters中每个字母出现次数，然后枚举所有单词组合，二进制的每一位表示单词表中每一个单词是否被选中，第i位为1表示选中，然后统计当前单词组合中每个字母出现的次数，记录在哈希表中，如果每个字母出现次数都不大于cnt中对应字母出现次数，说明满足要求。

2.27题目 1144. 递减元素使数组呈锯齿状

【枚举 + 贪心】为了使操作次数尽量少，nums[i]需要不断减小到比左右相邻数字都小，就立刻停止，所以nums[i]修改成m = min(nums[i-1], nums[i + 1]) - 1，修改次数为max(nums[i] - m, 0)，如果i-1或i+1的下标越界，则对应的数字为无穷大，最后把奇偶下标对应的修改次数分别累加，结果为min(奇修改次数，偶修改次数)。

2.28题目 2363. 合并相似的物品

【哈希表】用哈希表统计items1和items2的总重量然后从小到大遍历即可。（注意：itertools.chain是合并两个可迭代对象，比items1+items2的性能更好——items1+items2是用一个新建的list对象作为中间变量，时空间有额外的开销，chain知识把两个迭代器合成了，计算过程是lazy的，不存储中间变量，这样除了构建管道的成本和捕获异常的成本之外不会有额外的时空开销，在两个大items的情景下性能会更好）