10.1题目 1694. 重新格式化电话号码

【模拟】按题意模拟即可。

10.2题目 777. 在LR字符串中交换相邻字符

【双指针】思路：X是空地，L是向左移，L是向右移，L不能穿过R，R不能穿过X。代码：首先start和end里L和R的相对顺序必须一致（因为LR不能互相穿越），双指针遍历start和end，如果当前字符是L，但i<j 由于L无法向右移 false，R i>j false。

10.3题目 1784. 检查二进制字符串字段

【模拟】由于没有前导零，避免01串就行。

10.4题目 921. 使括号有效的最少添加

【贪心】left、right分别记录左右括号需求，碰到一个左括号说明需求一个右括号，碰到一个右括号，右括号需求减一，如果右括号又缺一个，左括号需求加一。

10.5题目 811. 子域名访问计数

【哈希表】用哈希表记录每个子域名的访问次数（为了避免子域名重复），最后将计数和子域名拼接。

10.6题目 927. 三等分

【三指针】首先，需要能够三等分，数组中1的数量必须是3的倍数。其次，由于第三组0的数量是确定的，用第三组的大小去确定前两组（find函数找到每组的第一个1来划分组）。满足三组每组1的数量相同后，从前往后检查每组的二进制值是否相等。

10.7题目 1800. 最大升序子数组和

【模拟】按题意模拟，用sm记录升序子数组的和，ans记录其中最大值。

10.8题目 870. 优势洗牌

思路：田忌赛马，打得过直接打，打不过派最烂的打。

【有序数 + 二分】用比nums2[i]稍大的去打nums2[i]，要是nums1里最大的都打不过就用num1最小的打。

【排序 + 双指针】对于增序的两个数组nums1和nums2，如果nums1[i] ≤ nums2[i]，说明nums[i] ≤ nums2的任意元素，剩着最后再匹配。（此题可以用nums2原地排序节约ans的空间）

10.9题目 856. 括号的分数

题意：( ) 1分.（ () () () ）2×(1+1+1)分

【字符串处理】按题意，()一分，左括号加，右括号结算两倍分数。

【计数】记（的个数为exp，每多一个得分倍数×2，每次碰到右括号结算得分2^exp。

10.10题目 801. 使序列递增的最小交换次数

【dp】用一个维度的状态表示交换与否，设dp[i] [0]表示到位置i为止nums1和nums2都严格递增所需的最小操作数且不对位置i进行交换，dp[i] [1]就是满足递增但对位置i进行交换。记a1 = nums1[i - 1], a2 = nums1[i], b1 = nums2[i - 1], b2 = nums2[i], 若a1 < a2且b1 < b2时，位置i可换可不换，有dp[i] [0] = dp[i - 1] [0]；dp[i] [1] = dp[i - 1] [1] +1；若a2 > b1且 b2 > a1，可以交换a2和b2 或a1和b1（选次数少的换），有dp[i] [0] = min(dp[i] [0], dp[i - 1] [1])，dp[i] [1] = min(dp[i] [1], dp[i - 1] [0] + 1)。

10.11题目 1790. 仅执行一次字符串交换能否使两个字符串相等

【计数】两个字符串至多只存在两个位置i,j处字符不相等，交换i,j处字符即可。如果s1==s2不需要交换，若s1!=s2，必须要满足s1[i] = s2[j],s1[j] = s2[i]，两个字符中只存在1个或大于2个位置的字符不相等，则无法通过一次交换使之相等。

10.12题目 817. 链表组件

【模拟】题意是找“一维连通块”的数量，即以head中节点值不在nums的节点作为分割，能分割出来子链数量。

10.13题目 769. 最多能完成排序的块

【贪心】arr是[0~n-1]的排列，记一个块[0,i]内最大值为mx，如果mx>i，则在[i+1,n-1]区间内必定存在一个值小于mx，这个值必然属于前一个块（否则块分别排序完这个值将在mx之后），所以可知对于每个i==mx为块的分割点。

10.14题目 940. 不同的子序列 II

【DP】定义dp[i]为以s[i]结尾的不同子序列的个数，遍历字符串s，更新dp[i] = Σdp[j] + 1。（Σdp[j]是之前求的不同子序列的个数，+1是指s[i]本身作为一个子序列）

10.15题目 1441. 用栈操作构建数组

【模拟】cur对应从list里取的1~n，遍历target的每个num，如果cur < num，说明应该先push再pop cur这个数，直到cur = num那么只push不pop。

10.16题目 886. 可能的二分法

【DFS】染色法判定二分图模板题，先把题中给的边数组改成邻接表，然后判断是否为二分图。两种染色标记为1和-1。遍历每个节点，把该点染成c，然后遍历这个点的邻近节点，不能出现颜色同样为c，也不能出现没染过色但是染-c失败的点。(color[x] = 0表示未访问节点)

【BFS】上述操作也用队列来实现.(q就是visited)

【并查集】遍历每个人，这个人和他讨厌的人不该在同一个集合中。

10.17题目 904. 水果成篮

【滑动窗口 + 哈希表】题意是求找到一段区间内不超过两种类型的最长子数组的长度。右边界每次都右移，用哈希表统计滑动窗口内的种类数，如果超过2种就需要将左边界右移，每次遍历更新一次答案。

10.18题目 902. 最大为 N 的数字组合

【记忆化搜索】题意是求给定区间内，由digits中数字构成的正整数个数，可以用记忆化搜索来实现数位 DP，定义dfs(i, is_limit, is_num)，i表示数字位数，is_num表示第i位前是否填了数字，is_limit表示可填数字是否有限制。

10.19题目 1700. 无法吃午餐的学生数量

【模拟】遍历每个三明治，如果某个三明治所有学生都不喜欢，那么这个三明治及之后的都无法被拿走了，返回剩余学生数量。

10.20题目 779. 第K个语法符号

【位运算 + 递归】写几行找规律，可以发现每一层的前半部分和上一层完全一致，后半部分是上一层的01反转。那么如果k在前半部分，第k个字符就是上一层的第k个字符，递归kthGrammar(n -1 ,k)，若k在后半部分，k就是上一层第k - 2^n - 2个字符的01反转，即kthGrammar(n -1 , k - 2^n - 2) xor 1。

【位运算 + 找规律】找规律，反转奇数次，相当于反转1次，反转偶数次，字符不变，所以只需要看k整个数字的累计反转次数，等价于求 k的二进制表示中，有多少位是 1。

10.21题目 901. 股票价格跨度

【单调栈】经典单调栈模型，找出左侧第一个比当前元素大的元素。从当天price往前找到第一个比该price大的价格，两个元素的下标之差即为跨度。需要维护一个栈底岛栈顶单调递减的栈，栈中每个元素存放(price, idx)数据对。

10.22题目 1235. 规划兼职工作

【dp + 二分】先按结束时间排序，定义dp[i]为前i个工作的最大报酬，对于第i个工作要么选要么不选，dp[i] = max(dp[i - 1], dp[j] + profit[j])，j是最大的满足endtime[j] ≤ starttime[i]的j，不存在时为-1，为了避免处理-1，可以改为dp[i + 1] = max(dp[i], dp[j] + profit[i])，初始f[0] = 0, ans = f[n]。由于结束时间有序，j可以用二分查找到。

【记忆化搜索 + 二分】定义dfs(i)为从第i份工作开始,可获最大报酬,ans = dfs(0). dfs(i) = max(dfs(i + 1), dfs(j) + profit[i]).

10.23题目 1768. 交替合并字符串

【双指针】按题意模拟，使用两个指针i 、j，分别指向两个字符串的起始，如果i没超过范围就加入word[i]，j同理，i、j都超出范围就return.

【调库】itertools.zip_longest和zip的区别——zip匹配短的那个，zip_longest匹配长的那个。

10.24题目 915. 分割数组

【一次遍历】left中每个元素都≤right中的每个元素，等价于left中最大值≤right中的最小值。从左向右遍历，left_max记录left数组最大值，如过有效，则右侧从partition + 1开始的每个元素值都应该大于left_max，如果右侧找到一个left_max小的元素，合并到左侧区间，否则记录一个cur_max，一旦右侧数组再次比left_max小，left_max = cur_max。

10.25题目 934. 最短的桥

【DFS + BFS】求最小反转次数使得两个岛屿连接，实际上是求连个岛屿之间的最短距离，可以用DFS将其实一个岛屿的所有点都找出来放到队列里，然后通过BFS一层层向外扩展，直至碰到另一个岛屿，当前扩展层数即为答案。搜索过程中，可以将已访问过的点标记为-1避免重复访问。

10.26题目 862. 和至少为 K 的最短子数组

【前缀和 + 单调队列】子数组的和可以转换为2个前缀和的差，可以暴力枚举所有i > j且presum[i] - presum[j] ≥ k的子数组[j, i)，找到最小的i-j就是答案。也可以用单调队列维护遍历过的presum[i]，如果presum[i] - presum[j] ≥ k，可以把presum[j]弹出，如果presum[i] < presum[j]，后续有presum[u]使得presum[u] - presum[i]  ≥ k,也可以弹出presum[j]，保证presum[j]单调递增。优化：可以在计算前缀和的同时计算答案。

10.27题目 1822. 数组元素积的符号

【遍历】元素值乘积的正负与正负元素的数量奇偶有关，初始sign = 1，碰到整数sign不变，如果碰到负数符号反转。

10.28题目 907. 子数组的最小值之和

【单调栈】对每个数，算出它是哪些子数组的最小值，可以用单调栈维护arr[i]的左右边界，可以直接在出栈的时候计算贡献。

10.29题目 1773. 统计匹配检索规则的物品数量

【模拟】用哈希表把输入key转为value下标，再遍历统计value相等的数量。

10.30题目 784. 字母大小写全排列

【暴搜】依次遍历s的每个字母，将其转换为小写和大写两种字母。

【BFS】遍历下一个字符c，如果是数字，将所有序列的末尾都加上c，如果是字母，加上c和swapcase(c)，放入队列，队列长度==长度则说明搜索完成。

【回溯】搜索到字符串s的第i个字符c时，若c为数字继续检测下一个字符，若c为字母，swapcase之后继续搜索，搜索完后恢复c继续搜索。

【位掩码】字符串s有m个字母，全排列有2^m个字符串序列，用bits唯一地表示一个字符串，bits的第i为0表示s从左往右第i个字母为小写，1为大写。位掩码计算字母，数字就跳过，依次检测字符串第i个字符串c，c为数字直接添加，c为字母，根据掩码bits判断添加大小写。

10.31题目 481. 神奇字符串

【构造】1、2交替出现，根据现在的数字确定接下来生成几个1or2。1和2的转换可以用3 - cur 或 xor3（1^3=2, 2^3=1）。也可以提前构造好数组，直接查询。