12.1题目 1779. 找到最近的有相同 X 或 Y 坐标的点

【枚举】直接枚举所有点。

12.2题目 1769. 移动所有球到每个盒子所需的最小操作数

【预处理 + 枚举】根据前一个盒子的操作数得到下一个盒子的操作数。预处理出每个位置i左边的小球移动到i的操作数left[i]，每个位置i右边的小球移动到i的操作数right[i]，ans[i] = left[i] + right[i]。

12.3题目 1796. 字符串中第二大的数字

【直接遍历】记录第一大和第二大，只对s[i]为数字生效。

【位运算】整数mask标识字符串中出现的数字，从高位到低位遍历mask，找到第二个为1的二进制位，其对应的数字即为第二大数字。

12.4题目 1774. 最接近目标价格的甜点成本

【回溯】回溯过程中总开销不增不减，当总开销大于target时，停止搜索。

【DP】某一个开销是否存在甜品制作方案，问题转化为01背包问题，设最小基料开销x，x≥target直接返回最小基料开销，x<target对超过target的保存一份最小的方案。

【枚举子集和 + 排序 + 二分查找】复制一份配料，dfs枚举子集和，代码中可以枚举一半配料的所有子集和，在另一半配料中，二分最接近的配料。

12.5题目 1687. 从仓库到码头运输箱子

【动态规划 + 单调队列】定义f[i]表示把前i个箱子从仓库运送到相应码头的最少行程数，ans = f[n]。从f[j]转移过来的时候，卡车上的箱子数量不能超过maxBoxes从；从f[j]转移过来的时候，卡车上的箱子总重量不能超过maxWeight。可以通过前缀和，计算出码头之间的行程数，再加上首尾两趟行程。实际上我们是要在[i-max Boxes，，…i-1]这个窗口内找到一个j，使得f[j]-cs[j]的值最小，求滑动窗口的最小值，一般用单调队列。

12.6题目 1805. 字符串中不同整数的数目

【双指针 + 模拟】找到每个整数的起始位置和结束位置，截取出这一个字串，存入哈希表，最后返回哈希表大小。

【正则】

12.7题目 1775. 通过最少操作次数使数组的和相等

【贪心 + 哈希表】设d = sum(nums2) - sum(nums1)，对于每个i，nums1[i]的最大变化量为6 - nums[i]，nums2[i]的最小变化量为nums2[i] - 1。统计变化量的个数，记到长为6的cnt数组中，有cnt[i]个数可以使d减少i，从大到小枚举i = 5,4,3,2,1。如果d > i cnt[i]，那么应该把这cnt[i]个数的变化量拉满，并更新d为d - i cnt[i]，否则通过修改⌈d/i⌉个数，使d恰好为0，退出循环，ans = Σ（需要修改的数的个数）。可以优化，如何把nums1全改成6仍小于nums2全改成1（互换同理），那么无法相等。

12.8题目 1812. 判断国际象棋棋盘中一个格子的颜色

【找规律】颜色相同的两个格子（x1,y1）和（x2,y2）满足x1+y1和x2+y2同奇偶，奇白偶黑。

12.9题目 1780. 判断一个数字是否可以表示成三的幂的和

【进制转换】一个数n可以表示位若干个不同的三的幂之和，那么n的三进制表示中，每一位的数字只能是0或1，将n转换为三进制判断。

12.10题目 1691. 堆叠长方体的最大高度

【排序 + 动态规划】把所有长方体的边长进行排序，使每个长方体满足 长 <= 宽 <= 高，定义f[i]表示以长方体i位最底部长方体时的最大高度，枚举每个长方体i的上方的长方体j，其中0≤j<i，j可以放在i上方时，有f[i] = max(f[j] + h[i])。h[i]是长方体i的高度，ans = max(f[i])。

12.11题目 1827. 最少操作使数组递增

【遍历】用变量mx记录当前严格递增数组的最大值，每个遍历到的元素给他set到至少mx+1，统计ans。

12.12题目 1781. 所有子字符串美丽值之和

【枚举】O(n^2)枚举每个字串的起始位置i，找到以该起点位置的字符为左端点的所有字串，计算每个子串的美丽值，累加到答案中。

12.13题目 1832. 判断句子是否为全字母句

【位运算】用一个整数mask记录出现过的字母，其中mask的第i位表示第i个字母是否出现过，最后判断mask的二进制表示中是否有26个1，即mask 是否等于2^26-1.

12.14题目 1697. 检查边长度限制的路径是否存在

【离线查询 + 并查集】给定一个查询时，遍历edgeList里的所有边，依次将长度小于limit的边加入并查集，使用并查集查询p和q是否属于同一个集合，如果p和q属于同一个集合，说明存在p到q的路径，且这条路径上每一条边的长度都严格小于limit，查询返回true，否则false。如果queries的limit是非递减的，说明上一次查询的并查集里的边都满足当前查询的limit要求，只需将剩余的长度小于limit的边加入并查集中。首先将edgeList按边长度从小到大排序，将queries按limit从小到大排序，用k指向上一次查询中不满足limit的长度最小的边。依次遍历queries，k指向的边的长度小于对应查询的limit，则将该边加入并查集中，然后将k加1，直到k指向的边不满足要求，最后根据并查集查询p和q是否属于同一集合。

12.15题目 1945. 字符串转化后的各位数字之和

【模拟】按题意模拟。

12.16题目 1785. 构成特定和需要添加的最少元素

【数学】需要使用多少个不超过limit的数组凑齐abs(sum-goal)，limit整除diff，答案就是⌊diff/limit⌋，若limit不整除，答案是⌊diff/limit⌋ + 1，以上两种情况可以统一为⌊(diff+limit−1)/limit⌋。

12.17题目 1764. 通过连接另一个数组的子数组得到一个数组

【双指针】变量i指向group[i]。遍历第k个元素，最后都找到了i=n就true。

12.18题目 1703. 得到连续 K 个 1 的最少相邻交换次数

【贪心 + 前缀和】可证明移动到x（x为qi-i的中位数p⌊k/2⌋是最优的），枚举第i个1是连续1的最左边的，前缀和求。

12.19题目 1971. 寻找图中是否存在路径

【DFS】建图，dfs图，用vis数组记录vistied的顶点，判断是否存在从source到destination的路径。

【并查集】构建并查集，将每条边的两个节点合并，最后查询source和destination的祖先节点是否相同，相同则说明两个节点连通。

12.20题目 1760. 袋子里最少数目的球

【二分】题目转换为对于某个开销值看它能否在maxOperations次操作内得到，二分枚举开销。假设最大值不超过y，二分查找到 y时，对于第 i 个袋子，其中有 nums[i] 个球，那么需要的操作次数为⌊(nums[i] - 1)/y⌋。总操作数P= Σ⌊(nums[i] - 1)/y⌋，P≤maxOperations时，调整二分上界，否则调整二分下界。

12.21题目 1753. 移除石子的最大得分

【模拟 + 贪心】每次从最大的两堆石头里取石头，直到至少两堆石头为空。

【数学】设a≤b≤c，那么当a+b≤c时，先从a,c两堆中取石头得分x，再从b,c两堆中取石头得分y，总分数x+y。a+b>c时，从c及a和b中较大的那一堆取石头，最终将c取空。

12.22题目 1799. N 次操作后的最大分数和

【状压DP】预处理Nums中任意两个数的最大公约数，其中 g[i]表示 nums[i]和nums[j] 的最大公约数，从小到大枚举状态。

12.23题目 2011. 执行操作后的变量值

【模拟】注意到每个字符串的第二个位置一定是符号。

12.24题目 1754. 构造字典序最大的合并字符串

【贪心 + 双指针】对于word1[i]和word2[j]，谁字典序大添加谁。word1[i] = word2[j]时，看word1[i:]和word[j:]的字典序大小（后缀字典序），自身字典序和后缀字典序均相等则任选一个即可。

本题也可以用后缀数组来做。

12.25题目 1739. 放置盒子

【数学】接触地面的盒子 = 1 + 2 + ... + i = i(i + 1) / 2，对应盒子上限maxN = 1 + (1 + 2) + (1 + 2 + 3) + ... + i(i + 1)/ 2 = i(i + 1)(i + 2)/6，在i(i + 1)(i + 2)/6的基础上，接触地面的盒子再增加j个，盒子上限增加1+2+..+j = j(j+1)/2。

12.26题目 1759. 统计同构子字符串的数目

【数学】同构子字符串为一个连续的字符序列且需要序列中的字符都相同，首先按照连续相同的字符来对字符串s进行分组，对于一个组中字符串的任意子字符串都为同构子字符串，而一个长度为m的字符串的子字符串的数目为m(m+1)/2。对于每一个组来统计其贡献的同构子字符串数目并求和即可。

12.27题目 2027. 转换字符串的最少操作次数

【贪心】遍历字符串 s，只要遇到 X，指针i就往后移动三格，并且答案加 1；否则指针 i往后移动一格。

12.28题目 1750. 删除字符串两端相同字符后的最短长度

【双指针】定义两个指针i和j指向字符串s的头部和尾部，然后相中间移动，直至i和j指向的字符不相等。

12.29题目 2032. 至少在两个数组中出现的值

【数组 + 枚举】将每个数组中的元素放入对应的数组（或哈希表）中，然后枚举1到100中的每个数i，判断i是否在至少两个数组中出现过。若是，则将加入答案数组中。

12.30题目 855. 考场就座

【有序集合 + 哈希表】假设两个人位置分别为l和r，区间[l, r]表示之间的空闲作为区间，选中点m = l + ⌊(r-l) / 2⌋能使距离最大化。题意需要实时维护这些区间顺序关系，并实时获取这些区间中的最优区间。可以用有序集合保存座位区间，有序集合的每个元素为一个二元组(l, r)，表示(l, r)能坐学生，用left,right两个哈希表维护每个学生左右邻居。

12.31题目 2037. 使每位学生都有座位的最少移动次数

【排序】将两个数组分别排序，然后遍历两个数组，计算每个学生的座位与其实际座位的距离，将所有距离相加即为答案。