6.1题目 2517. 礼盒的最大甜蜜度

【贪心 + 二分】由于随着甜蜜度的增大，能选择的糖果数量变小，有单调性，所以可以用二分答案来做。对price从小到大排序，二分答案d。最小的数x可以选，下一个可以选的数是第一个≥x+d的数，依此类推。如果可以选的数<k，说明d取大了，否则说明d取小了，根据这一点来二分。二分上界可以取(price[-1] - price[0]) // (k - 1) + 1（即⌊(max(price) - min(price)) / (k - 1)⌋）。

6.2题目 2559. 统计范围内的元音字符串数

【前缀和】创建一个长度为n+1的前缀和数组s，s[i]表示数组words的前i个字符串中以元音开头和结尾的字符串的数目。遍历words，如果当前字符串以元音开头和结尾，s[i+1] = s[i] + 1，否则s[i+1] = s[i]。

6.3题目 1156. 单字符重复子串的最大长度

【双指针】用哈希表统计字符串text每个字符出现的次数。定义一个指针i，每次将指针j指向i，并不断向右移动j，直到j指向的字符与i指向的字符不同，此时得到一个长度为l=j-i的字串text[i:j-1]，其余字符都相同。然后跳过指针j指向的字符，用指针k继续向右移动，知道k指向的字符与i指向的字符不同，此时得到一个长度为r = k - j - 1的字串text[j+1:k-1]，其中所有字符都相同，最多通过一次交换，可得最长单字符重复字串长度为min(l+r+1,cnt[text[i]])，接下来将指针i移动到j继续寻找下一个字串。

6.4题目 2465. 不同的平均值数目

【排序】排序后每次取数组守卫元素计算它们的和，用哈希表记录每个和出现的次数。

6.5题目 2460. 对数组执行操作

【模拟】遍历nums，对于任意相邻的两个元素nums[i]和nums[i+1]，如果nums[i]=nums[i+1]，那么将nums[i]的值变为原来的2倍，同时将nums[i+1]的值变为0。创建一个长度为n的答案数组ans，并将nums中所有非零元素按序放入ans中。

6.6题目 2352. 相等行列对

【模拟】将矩阵每一行和每一列进行比较，如果相等那么就是一对相等行列对。

6.7题目 2611. 老鼠和奶酪

【贪心 + 排序】将第i块奶酪从第二只老鼠分给第一只老鼠，得分的变化量为reward1[i] - reward2[i]，希望这个变化量尽可能大，才能使总得分最大。因此将奶酪按照reward1[i] - reward2[i]从大到小排序，前k块奶酪由第一只老鼠吃掉，剩下奶酪由第二只老鼠吃掉。

6.8题目 1240. 铺瓷砖

【递归回溯 + 状态压缩】按位置进行递归回溯，过程中我们用一个变量t记录当前使用的瓷砖数。如果j=m，第i行已经被完全填充，则递归到下一行，即(i+1,0)；如果i=n，则表示所有位置都已被填充，应该更新答案并返回；如果当前(i,j)已经被填充，递归到下一个位置(i,j+1)。否则枚举当前位置(i,j)可以填充的最大正方形边长w，并将当前位置(i,j)到(i+w-1,j+w-1)的位置全部填充，然后递归到下一个位置(i,j+w)。回溯时，要将当前位置(i,j)到(i+w-1,j+w-1)的位置全部清空。由于每个位置只有两种状态：填充或者未填充，因此我们可以使用一个整数来表示当前位置的状态。我们使用一个长度为n的整数数组filled，其中filled[1]表示第i行的状态。如果filled[i]的第j位为1，则表示第i行第j列已经被填充，否则表示未填充。

6.9题目 2699. 修改图中的边权

【两次Dijkstra】先把-1都修改成1，然后跑第一遍Dijkstra，设从source到点i的最短路长度为d_i，0。如果从起点到终点的最短路长度不超过target（否则无解，返回空数组），那我们就来尝试修改某些边权，使得从起点到终点的最短路长度恰好等于target。不妨再跑一遍Dijkstra，由于Dijkstra算法保证每次拿到的点的最短路就是最终的最短路，所以按照Dijkstra算法遍历点/边的顺序去修改，就不会对已确定的最短路产生影响。对于第二遍Dijkstra，设从source到点i的最短路长度为d_i，1。对于一条可以修改的边x-y，假设要把它的边权改为w，那么source-x-y-destination这条路径由三部分组成： 1.从source到x的最短路，这是第二遍Dijkstra算出来的，即d_x，1。 2.从x到y，即w。 3.从y到destination的最短路，由于后面的边还没有修改，这个最短路是第一遍Dijkstra算出来的，即d_destination，0-d_y，0。注意这个式子仅当y在从source到destination的最短路上才成立。不过，如果y不在最短路上，修改x-y并不会对最短路产生影响，所以代码中并没有判断y是否在最短路上。这三部分之和需要等于target，所以有dx，1+w+d_destination，0-d_y，0=target。解得w=target-d_destination，0+dy，0-d_x，1。如果第二遍Dijkstra跑完后，从起点到终点的最短路仍然小于target，那么就说明无法修改，返回空数组。否则，答案就是我们在第二遍Dijkstra中作出的修改。注意第二遍Dijkstra跑完后可能还有些边是-1（因为在w=1的时候没有修改，或者有些边不影响最短路），把这些边都改成1就行。代码实现时，为了修改边权，需要在邻接表中额外记录边的编号。此外，由于输入最坏是稠密图，可以用朴素版的Dijkstra算法。

6.10题目 1170. 比较字符串最小字母出现频次

【排序 + 二分】首先根据题目描述实现函数f——返回字典序最小的字母的出现次数。接下来将words中每个字符串w都计算出f(w)并排序。然后遍历queries，对于每个字符串q，在ws数组中二分查找第一个大于f(q)的位置i，则ws中下标i及后面的元素都满足f(q) < f(W)，当前查询答案就是n-i。

6.11题目 1171. 从链表中删去总和值为零的连续节点

【前缀和 + 哈希表】若链表节点的两个前缀和相等，说明两个前缀和之间的连续节点序列的和为0，可以消去这部分连续节点。第一次遍历链表，用哈希表last记录前缀和及对应链表节点，对于同一前缀和sm，后面出现的节点覆盖前面的节点。接下来遍历链表，若当前节点cur的前缀和sm在last中出现，说明cur与last[s]之间的所有节点和为0，我们直接修改cur的指向，即cur.next=last[s].next，这样就删去了这部分和为0的连续节点。继续往后遍历，删除所有和为0的连续节点。

6.12题目 1483. 树节点的第 K 个祖先

【树上倍增】预处理出每个节点的第2^i个祖先节点，由于任意k可以分解为不同的2的幂，如13=8+4+1。先枚举i，再枚举x，计算出所有爷爷节点，再算出所有爷爷的爷爷节点，pa[x] [0] = parent[x]，即父节点。pa[x] [1] = pa[pa[x]][0][0]，即爷爷节点。一般地，pa[x] [i+1] = pa[pa[x][i][i]][i]，如果pa[x] [i] == -1则pa[x] [i+1] = -1。需要找到k的二进制表示中的所有1，可以从小到大枚举i，如果k右移i位后的最低位为1，就说明k的二进制从低到高第i位是1。

6.13题目 2475. 数组中不等三元组的数目

【哈希表】用 Counter 统计每个数字出现的次数，然后依次遍历每个数字的出现次数，假设当前遍历到的数字为 x，出现次数为 c，那么在已经选择了 x 作为其中一个数字的情况下，剩下可以选择的数字个数为 n-c，而在选择 x 之前可以选择的数字个数为 a，因此选择 x 作为第二个数字的方案数为 a c，同时在已经选择了 x 和另外一个数字作为三元组的前两个数字的情况下，还需要选择一个与它们都不同的数字作为第三个数字，剩下可以选择的数字个数为 n-a-c，因此总的方案数为 a c * (n-a-c)，这些方案数累加起来就是最终的结果。

6.14题目 1375. 二进制字符串前缀一致的次数

【遍历】只有当前面所有的位都已经被翻转时，后面的位才可能成为前缀一致的一部分。在翻转过程中，mx 记录了当前已经翻转过的位中最大的位置，如果 mx 等于当前的下标 i，说明前 i 个位都已经被翻转，因此可以将答案加 1。

6.15题目 1177. 构建回文串检测

【前缀和】考虑一个字串能否在经过最多k次替换后变回回文串，需要统计字串中每个字符出现的次数，可以通过前缀和。对于出现偶数次数的字符，不需要替换，对于出现奇数次的字符，需要进行替换，替换次数为⌊x/2⌋，x为出现奇数次的字符个数，如果⌊x/2⌋ < k，可以变成回文串。预处理长为i的前缀中，每种字符各出现多少次，用n*26的二维数组sm存前缀和，其中sm[i + 1] [j]表示sm[0] 到sm[i]中，字母表的第j个小写字母的出现次数。对于queries[i]，利用前缀和计算每种字母出现次数，统计多少种字母出现奇数次，设为m，如果⌊m/2⌋ <= k，那么ans[i]为真。

6.16题目 1494. 并行课程 II

【子集状压 DP】将所有的课程抽象成一个有向无环图（DAG），其中每个节点表示一门课程，每条边表示一个先修课程的关系。用二进制数来表示当前已经选修的课程，其中二进制数的第 i 位为 1 表示已经选修第 i 门课程，为 0 则表示还未选修。用 f[S] 表示已经选修了集合 S 中的所有课程所需要的最少学期数。因为一共有 2^n 种选课状态，所以我们需要使用状态压缩的方式来存储和转移状态。枚举当前学期选修的课程集合 T，并将其与当前已经选修的课程集合 S 进行合并，得到一个新的选课状态 S' = S ∪ T。由于我们需要在当前学期内最多选修 k 门课程，因此 T 的大小不能超过 k。另外，为了保证先修课程的关系不被违反，我们需要保证 T 中的每个课程的先修课程都已经在 S 中选修过了。用一个二进制数 pre[i] 来表示第 i 门课程的先修课程集合。具体来说，pre[i] 的第 j 位为 1 表示第 j 门课程是第 i 门课程的先修课程。然后，我们可以使用位运算来判断 T 中的所有课程的先修课程是否都已经在 S 中选修过了。在枚举 T 的过程中，我们需要对所有合法的 T 进行转移。具体来说，我们可以将 f[S'] 更新为 f[S ∖ (S' \ T)] + 1，其中 S ∖ (S' \ T) 表示从 S 中去掉所有在 S' \ T 中的课程，即已经选修过但不在 T 中的课程。这个转移的含义是，我们先选修 S 中除了 T 中的课程之外的所有课程，然后在当前学期选择 T 中的课程。

6.17题目 2481. 分割圆的最少切割次数

【分类讨论】当n=1时无需切割；n为奇数时，不存在共线的情况，最少需要n次切割；n为偶数时，可以两两共线，最少需要n/2次切割。

6.18题目 1254. 统计封闭岛屿的数目

【DFS】从网格图的第一行、最后一行、第一列和最后一列的所有0出发，DFS访问四方向的0，并把这些0标记成访问过。代码实现时可以直接把0修改成1。然后从剩下的0出发，按照同样的方式DFS访问四方向的0，同时把0改成1。每次从一个新的0出发（起点），就意味着找到了一个新的封闭岛屿，答案加一。

6.19题目 1262. 可被三整除的最大和

【DP】定义dfs(i,j)为nums[0]到nums[i]中选数，后续还需选的数字之和sm满足sm mod 3 = j的前提下下，sm的最大值，设x = nums[i]：如果不选x，问题变成从nums[0]到nums[i-1]中选数，所选数字之和sm，满足sm mod 3 = j的前提下，sm的最大值，即dfs(i,j) = dfs(i-1,j)。如果选x，问题变成从nums[0]到nums[i-1]中选数，所选数字之和sm满足(sm + x) mod 3 = j，即sm mod 3 = (j - x) mod 3的前提下，sm的最大值，即dfs(i,j) = dfs(i - 1, (j - x) mod 3) + x。两种情况取最大值，有dfs(i,j) = max(dfs(i - 1, (j - x) mod 3) + x, dfs(i-1,j))，转换成f[i] [j] = max(f[i-1] [j], f[i-1] [(j+x) mod 3] + x)，最后用滚动数组优化。

6.20题目 1595. 连通两组点的最小成本

【状压DP】定义dfs(i,j)为第一组0~i和第二组0~m-1相连且第二组的集合j未被连接时，最小成本是多少。枚举第一组的点i和第二组的0~m-1其中一个点相连，取最小值，即dfs(i,j) = min(dfs(i-1, j \ {k}) + cost[i] [k])，改成递推，即f[i] [j] = min(f[i-1] [j \ {k}] + cost[i] [k])。

6.21题目 LCP 41. 黑白翻转棋

【BFS】题目中棋盘的大小最大为8×8，因此可以尝试枚举所有的空余位置作为下一步放置黑棋的位置，然后使用广度优先搜索的方法计算在该位置下可以翻转的白棋的数量，找出最大值即可。我们定义一个函数bfs(i,j)，表示在棋盘上放置黑棋在s(i,j)位置后，可以翻转的白棋的数量。在函数中，我们使用队列来进行广度优先搜索，初始时将s(i,j)放入队列中，然后不断取出队首位置，遍历棋盘的八个方向，如果该方向上是一段连续的白棋，且在末尾是黑棋，则将该黑棋之前的所有白棋都可以翻转，将这些白棋的位置放入队列中，继续进行广度优先搜索。最后，我们返回可以翻转的白棋的数量。

6.22题目 面试题 16.19. 水域大小

【DFS】从网格图的0出发，DFS访问八方向的0，并把这些0标记成“访问过”。代码实现时可以直接把0修改成1。DFS过程中，统计每个方向访问到的格子个数，累加个数得到池塘大小cnt。每次从一个新的0出发（起点），就意味着找到了一个新的池塘，把DFS得到的池塘大小加入答案。把答案排序后返回。

6.23题目 2496. 数组中字符串的最大值

【模拟】定义一个函数f(s)用于计算字符串s的值，如果s只包含数字，那么f(s)就是s在十进制下的值，否则f（s)就是s的长度，答案为max(f(s))。

6.24题目 1659. 最大化网格幸福感

【状压dp】每个网格只有三种状态：不分配人员、分配内向的人、分配外向的人，用012表示三种状态。定义dfs(i,pre,ic,ec)表示从第i行开始，且上一行的状态为pre，内向的人还剩ic个，外向的人还剩ec个，网格的最大幸福感。答案是dfs(0,0,introvertsCount,extrovertsCount)。如果i=m表示已经处理完了所有行返回0，如果ic=ec=0表示所有人已经分配玩了返回0，否则枚举当前行的状态cur，计算当前行的幸福感f[cur]，以及上一行的状态pre之间对幸福感的共线g[pre] [cu]，并递归计算dfs(i+1, cur, ic-ix[cur], ec-ex[cur])，最后dfs(i,pre,ic,ec) = max(f[cur] + g[pre] [cur] + dfs(i+1, cur, ic-ix[cur], ec-ex[cur]))。

6.25题目 1401. 圆和矩形是否有重叠

【数学】 (x,y)小于圆半径就在圆内，矩形内说明x1<=x<=x2，y1<=y<=y2，⚪和举行重叠相当于在举行内找到一个(x,y)使得a = |x-xCenter| 和b=|y-yCenter|都取到最小值，此时若a^2+b^2<=radius^2说明有重叠。对于x∈[x1,x2]和y∈[y1,y2]统一用f函数处理。

6.26题目 2485. 找出中枢整数

【公式】 (1+x) x = (x+n) (n - x + 1)，变形：n (n - 1) = 2 x^2，x = 根号(n * (n + 1) / 2)。

6.27题目 1186. 删除一次得到子数组最大和

【dp】定义f[i] [j]为子数组右端点是arr[i]，不能/必须删除数字的情况下，子数组元素和的最大值。f[i] [0] = max(f[i - 1] [0], 0) + arr[i]，f[i] [1] = max(f[i - 1] [1] + arr[i], f[i - 1] [0]) ，空间优化，在计算f[i+1]时，不会用到x下标<i的状态，状态转移方程改为f[1] = max(f[1] + arr[i], f[0]), f[0] = max(f[0], 0) + arr[i]。

6.28题目 1681. 最小不兼容性

【预处理 + 状压DP】设划分后每个子集大小为m，m=n/k，n为数组长度。枚举所有子集i（i∈[0,2^n]），如果子集i的二进制表示中有m个1，并且子集i中的元素没有重复，就可以计算出子集i的不兼容性，记为g[i]，即g[i] = max(min{num[j]})。定义f[i]为当前已经划分的子集状态为i时，子集的不兼容性和的最小值，对于状态i，找出所有未被划分且不重复的元素，用状态mask表示，如果状态mask中元素个数大于等于m，就枚举mask的所有子集j，f[i ∪ j] = min{f[i ∪ j], f[i] + g[j]}。

6.29题目 1253. 重构 2 行二进制矩阵

【贪心】创建ans[0]和ans[1]分别表示矩阵的第一和第二行，从左到右遍历数组colsum，对于遍历到的元素colsum[j]。如果colsum[j] = 2，将ans[0] [j] 和 ans[1] [j]都置为1，如果colsum[j] = 1，将ans[0] [j] 或 ans[1] [j]置为1，如果upper > lower，优先将ans[0] [j]置为1，否则优先将ans[1] [j]置为1，此时upper或lower减去1。如果colsum[j] = 0，将ans[0] [j] 和ans[1] [j]都置为0。如果upper<0或lower<0，说明无法构造出满足要求的矩阵，返回一个空数组，遍历结束，如果upper和lower都为0则返回ans，否则返回一个空数组。

6.30题目 2490. 回环句

【模拟】判断字符串的第一个字符和最后一个字符是否相等，如果不相等则返回false，否则遍历字符串，如果当前字符是空格，则判断前一个字符和后一个字符是否相等，如果不相等则返回false，否则遍历完所有字符后返回true。