3.1题目 2373. 矩阵中的局部最大值

【枚举】枚举每个3×3的矩阵，求出最大值，可以原地修改放入原矩阵中。

3.2题目 面试题 05.02. 二进制数转字符串

【模拟】十进制小数转二进制的方法是乘二取整，由于输入小数位数最多只有6位，可证其二进制小数位数至多，可优化最多循环6次。证明：num如果看表示为有限位二进制小数，那么可以表示为一个b/2^k的最简分数，b是整数且与2^k互质，num在(0,1)内时，k≥1，b与2^k互质，如0.625 = 5/8 = 5 / 2^3，对于一个十进制小数位最多6位的数num，可以表示为a/(2^5 × 2^6) = b/2^k，都×2^k得a·2^(k-6)/5^6 = b。b和2互质，等号左边不能有因子2，所以k≤6.代码中不断乘2减去b1,循环k次。

3.3题目 1487. 保证文件名唯一

【哈希表】用哈希表d记录每个文件夹的最小可用编号，其中d[name] = k表示文件夹name的最小可用编号为k，d中没有任何文件夹，d为空。遍历文件夹数组，对于每个文件名name，如果name在d中，不断尝试Name(k)，直到找到新文件夹名,将d[name]更新为k+1，如果不在d中，直接将name加入d，将d[name]更新为1。

3.4题目 982. 按位与为零的三元组

【枚举 + 常数优化】暴力三重循环枚举i,j,k的时间复杂度是O(n^3)，应该优化。对于nums[k]来说，只需要知道其and一个数的结果是否等于0，这个数具体是哪些nums[i] and nums[j]得到的不重要，所以可以写一个O(n^2)的枚举，预处理所有nums[i] and nums[j]的出现次数，存在一个哈希表或数组中，然后枚举Nums[k]和x，如果nums[k] and x = 0 就把cnt[x]加到答案中，用哈希表实现的枚举所有key，用数组实现的要枚举区间[0, 2^16]内的所有数。继续优化，如果吧二进制堪称集合，二进制从低到高第i位为1表示i在集合中，为0表示i不在集合中，如{0,2,3}可以表示为1101，a AND b相当于集合a和集合b没有交集，也相当于b是C_u A的子集，U = {0,1,...,15}，对应0xffff，一个数异或0xffff就得到这个数的补集，可以优化成枚举nums[k] ⊕ 0xffff的子集，可以从m不断减1，直到0，如果s and m = s就表示s是m的子集，也可以直接跳到下一个子集，即s更新为(s-1) and m，最后s=0时，(s-1) and m = m，继续优化，预处理每个Nums[k]的补集出现次数，最后累加cnt[nums[i] AND nums[j]]，继续优化，仔细计算cnt的大小u，相应的全集是u-1。

3.5题目 1599. 经营摩天轮的最大利润

【模拟】模拟摩天轮轮转过程，每次轮转时，累加等待的游客及新到达的游客，然后最多4个人上传，更新等待的游客数和利润，记录最大利润与其对应的轮转次数。

3.6题目 1653. 使字符串平衡的最少删除次数

【前后缀分解】平衡字符串的a和b之间有分割线，分割线之前要删b，分割线之后要删a，枚举所有分割线，计算删除次数的最小值。

【动态规划】s的最后一个字母如果是'b'，则无需删除，问题变为使s前n-1个字母平衡的最小删除次数，如果是'a'，有删和不删的选择，删问题变为使s前n-1个字母平衡的最小删除次数 + 1, 不删则前面所有b都得删。设cnt_b为前i个字母中'b'的个数，定义f[i]表示使s前i个字母平衡的最少删除次数，如果第i个字母是'b'，则f[i] = f[i - 1]，如果第i个字母是'a'，则f[i] =min(f[i - 1], cnt_b)，代码实现时只需要f一个变量。

3.7题目 1096. 花括号展开 II

【递归】用dfs(exp)处理表达式exp，将结果存入集合s中，首先找到第一个右花括号的位置j，如果找不到说明exp中没有右花括号，即exp为单一元素，直接将exp加入集合s中即可。否则，从位置j开始往左找到第一个左花括号位置i，此时exp[:i]和exp[j+1:]分别为exp的前后缀，而exp[i+!:j]为exp中花括号内的部分，即exp的子表达式，将其按逗号分割成多个字符串，将其和前后缀拼起来，递归调用即可，最后将集合s中的元素按字典序排序。

3.8题目 剑指 Offer 47. 礼物的最大价值

【DP】定义f[i] [j]为从棋盘左上角走到右下角 的礼物最大累计价值，f[i] [j] =max(f[i - 1] [j], f[i] [j - 1]) + grid[i - 1] [j - 1]，由于f[i + 1]只依赖于f[i]，那么考研只用两个滚动数组，而且f[1] [1]会用到f[0] [1]，直接把f[1] [1]填入f[0] [1]中，所以只需一个长为n+1的一维数组即可，再优化：直接用grid[0]当f数组，做到O(1)空间。

3.9题目 2379. 得到 K 个黑块的最少涂色次数

【滑动窗口】固定大小为k的滑动窗口，在向右移动过程中维护窗口中白色快数目，返回白色快数目最小值即需要至少出现一次连续k个黑色块最小操作次数。

3.10题目 1590. 使数组和能被 P 整除

【前缀和+哈希表】同余：如果(x - y) mod p = 0，则称x与y对模p同余，记作x ≡ y (mod p)，为了避免判断是否负数，可以写为(x mod p + p) mod p = y mod p （python会保证取模运算的结果非负）。举例，设总和为x，子数组和为y，去掉y后，x mod p = y mod p，等价于y ≡x (mod p)。通过前缀和，题目转化为：在前缀和数组sm上找到两个数sm[l]和sm[r]，满足r-l最小，且sm[r] - sm[l] = x (mod p)，移项的sm[r] - x = sm[l] (mod p)，变形为((sm[r] - x) mod p + p) mod p = sm[l] mod p，即(sm[r] mod p - x mod p + p) mod p = sm[l] mod p。遍历sm的同时，用哈希表记录sm[i] mod p最近一次出现的下标，如果哈希表中包含(sm[i] mod p - x mod p) mod p，设其下标为j，那么[j,i)是一个符合要求的子数组，枚举所有i计算所有符合要求的子数组长度的最小值。代码实现时，可以边遍历nums边计算前缀和。

3.11题目 面试题 17.05. 字母与数字

【前缀和+哈希表】字母和数字个数相同等价于字母的个数减去数字的个数等于0，可以把字母看作1，数字看作-1，即找到一个最长子数组其元素和等于0，用前缀和处理，元素和等于0等价于两个前缀和之差等于0，等于两个前缀和相同，即从前缀和中找到两个相同的sm[r]和sm[l]，计算r-l的最大值，遍历前缀和sm的同时，用一个数组或哈希表first记录sm[i]首次出现下标，计算i-first[sm[i]]的最大值。

3.12题目 1617. 统计子树中城市之间最大距离

【DFS+乘法原理】暴力枚举i和1作为直径的两个端点，那么从到j的这条简单路径是直径，这上面的每个点都必须选。设dis[i] [j]为i到j的距离，为了计算树上任意两点的距离ds，枚举i作为树的根，计算i到其余点的距离。通过n次DFS，就可以得到树上任意两点的距离了。

3.13题目 2383. 赢得比赛需要的最少训练时长

【贪心 + 模拟】开始时把精力补充到足够击败这n个对手，接下来考虑经验值，遍历n个对手，若经验不足以超过对手，就把经验补到刚好能超过该对手，击败对手后把对方的经验值加到自己身上，遍历结束后返回训练的小时数。

3.14题目 1605. 给定行和列的和求可行矩阵

【贪心 + 构造】以rowSum = [5,7,10], colSum = [8,6,8]为例，单独看左上角的格子，最小可以填0，最大可以填min(5,8)，按顺序给每个格子填最大值，取min的两个值哪个小，改行/该列剩下就全填0了。可以观察到需要填的格子（非零格）组成了一条向下或向右的路径，至多要填m+n-1个格子，其余格子全为0。

3.15题目 1615. 最大网络秩

【枚举 + 计数】用一维数组cnt记录每个城市的度，用二维数组g记录每对城市之间是否有道路相连，如果a和b之间有道路相连则g[a] [b]= 1，否则g[a] [b] = g[b] [a] = 1，枚举每对城市(a,b)，计算网络秩即cnt[a] + cnt[b] - g[a] [b]（减掉两者相连即中间重复计算的），其中最大值为答案。

3.16题目 2488. 统计中位数为 K 的子数组

【遍历 + 计数】前缀和思想，定义一个计数器 cnt，用于统计当前遍历过的数组中，「比 k大的元素的个数」与「比 k小的元素的个数」的差值的个数。由于nums中的整数互不相同，k是长为奇数的子数组的中位数等价于子数组中大于k的数的个数=小于k的数的个数。「左侧小于+右侧小于」 = 「左侧大于+右侧大于」，移项得左侧小于-左侧大于=右侧大于-右侧小于。把比k大的数视为1，比k小的数视为-1，k视为0。倒序枚举子数组左端点，计算「左侧小于 - 左侧大于」的值 x，然后正序枚举子数组右端点，计算「右侧大于 − 右侧小于」的值x，对每个右端点的x，看有多少个一样的左端点的x，子数组长为奇数时，子数组个数为cnt[0] + cnt[1] = 2，子数组长为偶数时，「左侧小于-左侧大于」= 「右侧大于 -右侧小于 - 1」，cnt[x-1]是该右端点对应的符合要求的长为偶数的子数组个数，累加这些cnt[x-1]就是子数组长为偶数时的答案，奇数和偶数个数相加就是答案。代码中，x的范围在[-(n-1), n -1]之间，所以可以用数组代替哈希表，考虑到要访问cnt[x-1]，实际范围是[-n,n-1]，需要一个长为2n的数组。

3.17题目 2389. 和有限的最长子序列

【排序 + 前缀和 + 二分】对于每个queries[i]，对在前缀和二分找到元素和不超过queries[i]的最小下标j。

3.18题目 1616. 分割两个字符串得到回文串

【双指针】a的前缀和b后缀匹配的字母越多，中间需要判断的回文串越短，a_prefix+b_suffix越可能构成回文串(b_prefix+a_suffix同理)。代码中，check函数：如果 a_prefix + b_suffix 可以构成回文串则返回 True，否则返回 False；相向双指针，如果两个指针指向字符相等就同时王中间移动，直到遇到不同的字母或两指针交叉。如果交叉，说明已经得到回文串，否则需要判断中间剩余字串是否是回文串。没交叉，则交换a和b重复一遍。

3.19题目 1625. 执行操作后字典序最小的字符串

【枚举】数据范围较小，可以枚举所有字符串状态，取字典序最小的状态。可以观察到，对于累加操作，数字最多累加10次就会回到原来的状态，对于轮转操作，字符串最多轮转n次，就会回到原来的状态，所以轮转操作最多产生n种状态，如果轮转位数b是偶数，累加操作只会对奇数位数字产生影响，共n×10种状态；如果轮转位数b是奇数，累加操作会对奇数位和偶数位数字都产生影响，共n×10×10种状态.

3.20题目 1012. 至少有 1 位重复的数字

【数位 DP】前置知识(位运算和集合论)：集合可以用二进制表示，二进制从低到高第i位为1表示i在集合中，为0表示i不在集合中。例如集合{0,2,3}对应的二进制数为1101(2)。设集合对应的二进制数为x。本题需要用到两个位运算操作：1.判断元素d是否在集合中：x>d&1可以取出x的第d个比特位，如果是1就说明d在集合中。2.把元素d添加到集合中：将x更新为x | (1<d)。思路：正难则反，转换成求无重复数字的个数。将n转换成字符串s，定义f(i, mask, isLimit, isNum)表示构造从高到低第i位及其之后数位的合法方案数，其余参数的含义为：·mask表示前面选过的数字集合，换句话说，第i位要选的数字不能在mask中。·isLimit表示当前是否受到了n的约束。若为真，则第i位填入的数字至多为s[i]，否则可以是9。如果在受到约束的情况下填了s[i]，那么后续填入的数字仍会受到的约束。·isNum表示i前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为1；若为真，则要填入的数字可以从0开始。代码中，递归入口：f(0,0,true,false)表示：从s[0]开始枚举：一开始集合中没有数字；一开始要受到n的约束（否则就可以随意填了，这肯定不行）；一开始没有填数字。递归中：如果isNum为假，说明前面没有填数字，那么当前也可以不填数字。一旦从这里递归下去，isLimit就可以置为fa1se了，这是因为s[0]必然是大于0的，后面就不受到n的约束了。或者说，最高位不填数字，后面无论怎么填都比n小。如果isNum为真，那么当前必须填一个数字。枚举填入的数字，根据isNum和isLimit来决定填入数字的范围。递归终点：当i等于s长度时，如果isNum为真，则表示得到了一个合法数字（因为不合法的不会继续递归下去），返回1，否则返回0。

3.21题目 2469. 温度转换

【模拟】按题意模拟。

3.22题目 1626. 无矛盾的最佳球队

【排序 + DP】将球员按照分数从小到大排序，如果分数相同则按照年龄从小到大排序，定义f[i]为排序后第i个球员的最大得分，枚举0≤j<i，如果第i个球员年龄大于等于第j个球员年龄，则f[i]可以由f[j]转移来，f[i] = max(f[i], f[j])。

3.23题目 1630. 等差子数组

【模拟 + 数学】定义一个check函数用于判断子数组是否能重排成等差数列，首先子数组长度n = r - l -1，并将子数组中元素放入集合st中，获取子数组中最大值an和最小值a1，如果an-a1不能被n-1整除，那么不能形成等差数列，否则计算公差d = (an-a1)/(n-1)，从a1开始依次计算第i项元素，如果第i项元素a1+(i-1)×d不在集合st中，那么不可能形成等差数列，否则遍历完所有元素。遍历所有查询，对每个查询调用check判断，将结果存入答案数组中。

3.24题目 1032. 字符流

【前缀树】根据初始化时的字符串数组words构建前缀树，前缀树的每个节点包含两个属性：children——指向26个字母的指针数组，用于存储当前节点的子节点，is_end——标记当前节点是否为某个字符串的结尾。构造函数中，遍历字符串数组words，对于每个字符串w，将其反转后逐个插入到前缀树中，插入结束后，将当前节点的is_end标记为true。在query函数中，将当前字符c加入到字符流中，从后往前遍历字符流，对于每个字符c，在前缀树中查找是否存在以c为结尾的字符串，如果存在返回true，否则返回false。

3.25题目 1574. 删除最短的子数组使剩余数组有序

【双指针】要找出数组的最长非递减前缀和最长非递减后缀，如果i≥j，说明数组本身就是非递减的，否则可以删右侧后缀或左侧前缀。枚举左侧前缀的最右端点l，对于每个l，直接用双指针找到第一个大于等于nums[l]的位置，记为r，此时可以删出nums[l+1,...r-1]，并更新答案，继续枚举l。

3.26题目 2395. 和相等的子数组

【哈希表】遍历数组，用哈希表记录两个相邻元素和，如果已经出现过返回true，否则将和加入哈希表。

3.27题目 1638. 统计只差一个字符的子串数目

【枚举】记k1为上一个不同字符的位置，记k0为上上一个不同字符的位置，枚举i，维护k0和k1，累加k1-k0到答案中由于一开始k0和k1不存在，对于j≠i的情况，枚举它俩的差值d=i-j，例如d=2时，枚举的是s[i]和t[i-2此时k0和k1应初始化为的初始值减一。

3.28题目 1092. 最短公共超序列

【DP】先用dp求出两个字符串的最长公共子序列，然后根据最长公共子序列构造出最短公共超序列，定义f[i] [j]为字符串str1的前i个字符和字符串str2的前j个字符的最长公共子序列的长度，状态转移方程是{f[i] [j] = 0; f[i - 1] [j - 1] + 1; max(f[i - 1] [j], f[i] [j -1])}。用双指针ij分别指向str1和str2的末尾，从后往前遍历，每次比较str1[i]和str2[j]，相等则将任意一个字符加入到答案序列，ij同时减一，不等则将f[i] [j]和f[i -1] [j]和f[i] [j -1]的最大值进行比较，如果f[i] [j] = f[i - 1] [j]则将str1[i]加入答案序列，i--，f[i] [j] = f[i] [j -1]则将str2[j]加入答案序列，j--。直到i = 0 或 j = 0，然后将剩余字符串加入到答案序列，最后将答案反转。

3.29题目 1641. 统计字典序元音字符串的数目

【数学】问题转化为n 个字符分配给五个元音所代表的盒子，盒子可以为空，一共有多少种方法。盒子不为空的情况：把 n 个小球分成了 m，放隔板的位置有 n - 1 个，我们要放 m - 1 个隔板。答案为 C(n - 1, m - 1)；盒子可以为空的情况：想成先把 n + m 个小球放到 m 个盒子里，盒子不能为空，然后再在每个盒子里拿走 1 个小球，总共拿走了 m 个小球，得到的结果，就是把 n 个小球放到 m 个盒子里，盒子可以为空的解，即C(n + m - 1, m - 1)。代入m=5，ans=C(n + 5 - 1, 5 - 1) = C(n + 4, 4)

3.30题目 1637. 两点之间不包含任何点的最宽垂直区域

【排序】对数组points按照x升序排序，获取相邻点之间x的差值的最大值。

3.31题目 2367. 算术三元组的数目

【三指针】由于nums是严格递增的，遍历k时，i和j只增不减，因此可以用类似同向双指针的做法来移动指针：枚举x=nums[i]；移动j直到nums[j]+diff≥x，如果nums[j]+d时=x，则移动i直到nums[i]+2·diff时≥x；如果nums[2+2·df=x，则找到了一对等差三元组。无需判断j<k和i<j，因为一旦j=k，numsj]+df≥x必然成立，所以万<k无需判断，i也同理。