复盘｜2022.9每日一题

9.1题目 1475. 商品折扣后的最终价格

【单调栈】单调栈预处理prices，使得查询prices中每个元素对应位置右边的第一个更小的元素值时不需要再遍历price。在每个位置维护一个其右边更小的元素列表。

9.2题目 687. 最长同值路径 

【DFS】类似求二叉树最大深度。

9.3题目 646. 最长数对链

【贪心】pre记录上一个pair[1]，下一个pair[0]得大于上一个pair[1]。

9.4题目 1582. 二进制矩阵中的特殊位置

【模拟】枚举每个位置判断是否满足，可以用原始矩阵的第一行来存减少空间消耗。

9.5题目 652. 寻找重复的子树

【使用序列化表示】用哈希表存子树，如果一局出现就把子树放进哈希表中。

9.6题目 828. 统计子串中的唯一字符

【一次遍历】从左向右遍历s的同时，对每个字母s[i]记录上一次出现的下标last_0[s[i]]和上上次出现的下标last_1[s[i]]，可以算出以s[i-1]结尾的字串到以s[i]结尾的字串，countUniqueChars值的变化量为i - 2last_0[s[i]] + last_1[s[i]]。

9.7题目 1592. 重新排列单词间的空格

【模拟】首先按照空格分割text，得到单词集合，并统计空格数。如果单词数为 1，则将全部空格拼接到这个单词后面，否则先计算出单词间的间隔，按照单词及间隔来进行拼接，若拼接后仍有多余的空格，则将剩下的空格拼接在末尾即可。

9.8题目 667. 优美的排列 II

【思维题】k=1时，1~n按照[1,2,…,n]的顺序排列，相邻的差均为1，满足k=1的要求。k = n -1时，将1~n按照[1,n,2,n-1,3,…]的顺序排列，相邻的差从n-1开始，依次减1，这样所有1到n-1的差值均出现一次，满足k=n-1。其他一般情况，将这两种情况合并，前半部分相邻差为1，后半部分相邻差从k开始递减到1，这样1到k的差值均出现一次，对应列表[1,2,…,n-k,n,n-k+1,n-1,n-k+2,..]

9.9题目 1598. 文件夹操作日志搜集器

【模拟】用depth记录当前目录的深度，../如果depth > 0则减1，./则depth不变，x/则depth加1.

9.10题目 669. 修剪二叉搜索树

【递归】一个节点的值如果没有落在[lo, hi]内，如果root.val < lo，则root和root的左子树都小于lo，都需要被剪掉；如果root.val > hi，则root和root的右子树都大于hi，都需要被剪掉。

9.11题目 857. 雇佣 K 名工人的最低成本

【贪心 + 最大堆】在最优发工资方案下，至少有一名工人，发给他的工资恰好等于他的最低期望工资。剩余工人可以按每单位工作质量的工资即r_i = wage_i / quality_i 升序排序，k名工人quality之和为sumQ，发工资总额为sumQ × r_i，所以sumQ越小发的工资总额就越小，所以需要从小到大枚举r_i。维护当前最小的k个quality值。代码中，可以用最大堆（优先队列）来维护，按照r_i从小到大的顺序遍历，当堆中有k个元素时，如果quality_i比堆顶小，可以弹出堆顶，将quality_i入堆，从而得到一个更小的sumQ，此时有可能找到一个更优解sumQ×r_i。

9.12题目 1608. 特殊数组的特征值

【降序排序 + 一次遍历】特征值x是在[1,n]范围内的一个整数，其中n是数组nums的长度，因此可以遍历[1,n]判断某个整数i是否是特征值，若i是特征值，那么nums中恰好有i个元素大于等于i，由于数组降序排序，说明nums[i - 1]必须大于等于i，nums[i]如果存在必须小于i。

9.13题目 670. 最大交换

【贪心】右边越大的数字与左边较小的数字进行交换，这样产生的整数才能保证越大。

9.14题目 1619. 删除某些元素后的数组均值

【排序】排序后，区间[n / 20, 19n/20)内的元素求和即为未删除元素，再除以0.9n即为均值。

9.15题目 672. 灯泡开关 Ⅱ

【二进制枚举】找规律，位置i与i + 6的灯泡的开关状态始终一致，所以只需考虑前n=6个灯泡的开关状态。对于每个按钮，若操作偶数次，相当于没执行，若操作奇数次，相当于操作1次，不同按钮操作的先后顺序不影响结果。共4个按钮，每个按钮有“操作偶数次”和“操作奇数次”两种状态，共有2^4种按钮状态，可以二进制枚举按钮的状态mask，若当前状态满足题目presses的限制，可以xor模拟，最终得到的状态t去重后即为答案。

9.16题目 850. 矩形面积 II

【离散化 + 线段树 + 扫描线】先将所有矩形的左右边界按照横坐标排序，确定扫描线扫描顺序，随后遍历左右边界，一次性处理掉一批横坐标相同的左右边界，对应增加或减少覆盖的长度，下一个没遍历到的左右边界横坐标就是扫描新水平方向移动过的距离，而覆盖的线段长度可以离散化。

9.17题目 1624. 两个相同字符之间的最长子字符串

【哈希表】类似两数之和的解法。

9.18题目 827. 最大人工岛

【DFS】统一岛屿中所有点都属于同一个集合，可用不同的mark值标识不同的岛屿，用p记录每个grid[i] [j]对应的mark值，用cnt记录每个岛屿的面积，遍历grid，对于每个0，统计相邻四个点中1所在的岛屿。

9.19题目 1636. 按照频率将数组升序排序

【哈希表】先算出数组nums中各元素的频率，然后按照元素频率和数值对数组进行排序即可。

9.20题目 698. 划分为k个相等的子集

【DFS + 剪枝】首先sum(nums)如果不能被k整除则肯定无法划分为k个子集，如果能被k整除，将每个子集的期望和记为s，创建长度为k的数组cur表示每个子集的和，对nums降序排序，尝试将每个元素加入cur的子集，如果子集的和超过s，则可以跳过，如果cur[j] == cur[j - 1]说明在之前已经完成搜索也可以跳过，如果所有元素都能加入cur中，则可以划分为k个子集。

9.21题目 854. 相似度为 K 的字符串

【DFS】每次碰到不同的s1[i] != s2[i]时，从s1[i + 1,…]中选择处于不同位置的字符s1[j] = s2[j]，将其与s1[i]进行交换，然后保持当前子状态，搜索下一个位置i+1，直到素有字符串s1全部与s2匹配完成，当前子状态搜索完成后，回复字符串，继续搜索下一个与s2[i]相等的字符，并进行替换。长度为n的两个相似字符串，n为偶数时，至少交换n/2次，n为奇数，至少交换(n+1)/2次。

9.22题目 1640. 能否连接形成数组

【哈希表】用一个哈希表记录pieces哥哥数组的首元素与下标的对应关系，将piece[j]与arr[i]及之后的整数进行比较，都相等就往后移直到所有pieces都匹配成功。

9.23题目 707. 设计链表

【指针引用实现单链表】单向链表的每个节点仅存储本身的值和后继节点，还需要一个哨兵节点作为头节点。

【静态数组实现单链表】指针引用每次动态创建一个链表节点，频繁new操作会增加耗时，可以使用静态数组来实现，预先申请一块略大于数据范围的内存空间，每次插入节点时，从数组中取出一个空闲的位置，将新节点插入到该位置，同时更新该位置的前驱和后继节点的指针引用。

9.24题目 1652. 拆炸弹

【前缀和】若 k 为 0，直接返回[0] * n。若 k为正数，那么 i 位置的值为 i 位置后 kk 个位置的值之和，若 k 为负数，那么 i 位置的值为 i  位置前 |k| 个位置的值之和。

9.25题目 788. 旋转数字

【枚举】按题意，2，5，6，9是合法的旋转后不同的数字，3，4，7是不合法的数字，0，1，8是合法的但旋转后相同的数字。所以该数字的数位中必须至少出现2，5，6，9中的一个，且不能出现3，4，7，而0，1，8出现与否都无所谓。用一个check数组存一下，依次判断。

9.26题目 面试题 17.19. 消失的两个数字

【位运算】xor初始化为0，缺两个数的[1,N] xor 完整[1,N]，xor的结果是缺的两个数的异或和。已知lowbit算法x & (-x)可以保留x最右边的1，其余位置置0。运用lowbit算法找到xor的最右边的1，表示在这一个二进制位上缺失的两个数一个是0一个是1，把该位当成mask过滤两遍（按0按1都行）得到其中一个数，用xor异或上这个数得到另一个数。(a ^ b ^ a = b)

9.27题目 面试题 01.02. 判定是否互为字符重排

【哈希表】用哈希表统计两个字符串每个字符出现次数，相等就行。

9.28题目 面试题 17.09. 第 k 个数

【平衡树/最小堆】每次把最小的3x,5x,7x存进去，第k次取到的数即为第k小的数。

【多路归并】第k位数可以由3x、5x、7x三种序列归并而来，用三个指针指向当前最小的那个数。

9.29题目 面试题 01.09. 字符串轮转

【模拟】需要满足长度相等，且把s2拼起来，s1一定在其中。

9.30题目 面试题 01.08. 零矩阵

【使用标记数组】遍历每一行每一列，如果有0，将整行置0.

【使用单个标记变量】先用一个遍历存第一列是否存在0，存在flag变量里，之后用第一行存每一列是否包含0，用第一列存每一行是否包含0，可以节约空间。倒序遍历是为了留着第一列最后再用flag变量更新。