4.1题目 954. 二倍数对数组

【哈希表 + 排序】用一个哈希表来统计ct，并将其键值按绝对值从小到大排序，然后模拟上述操作，去掉元素的操作可以改为从cnt中减去对应值。

4.2题目 420. 强密码检验器

【分类讨论】根据k mod 3 = 0/1/2分类讨论。

4.3题目 744. 寻找比目标字母大的最小字母

【线性查找】如果目标字母小于列表中的最后一个字母，则一定可以在列表中找到比目标字母大的最小字母。如果目标字母大于或等于列表中的最后一个字母，则列表中不存在比目标字母大的字母，根据循环出现的顺序，列表的首个字母是比目标字母大的最小字母。

4.4题目 307. 区域和检索 - 数组可修改

【分块处理】设数组大小为n，我们将数组nums分成多个块，每个块大小sze，最后一个块的大小为剩余的不超过sze的元素数目，那么块的总数为⌈n/size⌉，用一个数组sm保存每个块的元素和。

4.5题目 762. 二进制表示中质数个计算置位

【数学 + 位运算】枚举[left，right]范围内的每个整数，挨个判断是否满足题目要求。

4.6题目 310. 最小高度树

【BFS】只需要求出路径最长的两个叶子节点即可，并求出其路径的最中间的节点即为最小高度树的根节点。

4.7题目 796. 旋转字符串

【模拟】首先，如果s和goal的长度不一样，那么无论怎么旋转，s都不能得到goal，返回flse在长度一样（都为n）的前提下，假设s旋转i位，则与goal中的某一位字符goalj对应的原s中的字符应该为s[(i+j) mod n]。在固定i的情况下，遍历所有j，若对应字符都相同，则返回tru。否则，继续遍历其他候选的i。若所有的i都不能使s变成goal，则返回false。

4.8题目 429. N 叉树的层序遍历

【BFS】先把根节点oot放入队列中，随后在广度优先搜索的每一轮中，我们首先记录下当前队列中包含的节点个数（记为c），即表示上一层的节点个数。在这之后，我们从队列中依次取出节点，直到取出了上一层的全部ct个节点为止。当取出节点cur时，我们将cur的值放入一个临时列表，再将cur的所有子节点全部放入队列中。

4.9题目 780. 到达终点

【反向计算】可以从(tx, ty)开始反向计算，判断是否可以到达状态(sx,sy)。

4.10题目 804. 唯一摩尔斯密码词

【哈希表】我们将数组words中的每个单词按照莫尔斯密码表转换为摩尔斯码，并加入哈希集合中，最终的答案即为哈希集合中元素的个数。

4.11题目 357. 统计各位数字都不同的数字个数

【排列组合】考虑n = 0/1/2的情况，组合数学计算。

4.12题目 806. 写字符串需要的行数

【直接遍历】width + widths[c] ≤ 100更新时不变，width +  widths[c] > 100.

4.13题目 380. O(1) 时间插入、删除和获取随机元素

【变长数组 + 哈希表】插入操作时，首先判断val是否在哈希表中，如果已经存在则返回false，如果不存在则插入val，删除操作时，首先判断val是否在哈希表中，如果不存在则返回false，如果存在则删除val.

4.14题目 1672. 最富有客户的资产总量

【遍历】分别计算每位客户在各家银行托管的资产数量之和，返回这些资产总量的最大值。

4.15题目 385. 迷你语法分析器

【DFS】从左至右遍历s，如果第一位是‘[’字符，则表示待解析的是一个列表，从‘[’后面的字符开始又是一个新的NestedInteger实例，仍调用解析函数来解析列表的元素，调用结束后如果遇到的是，字符，表示列表仍有其他元素，需要继续调用。如果是‘]’字符，表示这个列表已经解析完毕，可以返回NestedInteger实例。否则，则表示待解析的NestedInteger只包含一个整数。我们可以从左至右解析这个整数，并注意是否是负数，直到遍历完或者遇到非数字字符（']’或‘，'），并返回NestedInteger实例。

4.16题目 479. 最大回文数乘积

【枚举】可以从大到小枚举回文数，由于确定了回文数的左半部分，其右半部分也就确定了，因此我们只需要枚举左半部分。

4.17题目 819. 最常见的单词

【哈希表 + 计数】遍历段落paragraph，得到段落中的所有单词，并对每个单词计数，使用哈希表记录每个单词的计数。由于每个单词由连续的字母组成，因此当遇到一个非字母的字符且该字符的前一个字符是字母时，即为一个单词的结束，如果该单词不是禁用单词，则将该单词的计数加1。如果段落的最后一个字符是字母，则当遍历结束时需要对段落中的最后一个单词判断是否为禁用单词，如果不是禁用单词则将次数加1。

4.18题目 386. 字典序排数

【DFS】尝试在number后面附加一个零，即number×10，如果number×10≤n，那么说明number×10是下一个字典序整数；如果number mod 10 = 9或number+1>n，那么说明未尾的数位已经搜索完成，退回上一位，即number = ⌊number /  10⌋然后继续判断直到number mod10≠9且number+1≤n为止，那么number+1是下一个字典序整数。

4.19题目 821. 字符的最短距离

【两次遍历】问题可以转换成，对s的每个下标i，求min(s[到其左侧最近的字符c的距离, s[到其右侧最近的字符c的距离)

4.20题目 388. 文件的最长绝对路径

【栈】文件系统中文件绝对路径的最大长度，可用栈保存当前已遍历路径的长度，栈中元素的个数即为当前路径的深度，栈顶元素即为当前路径的长度。

4.21题目 824. 山羊拉丁文

【模拟】一次遍历，按题意模拟。

4.22题目 396. 旋转函数

【迭代】F(k)=F(k-1)+numSum - n x nums[n - k] - k  (1 ≤ k < n)

4.23题目 587. 安装栅栏

【Jarvis 算法】经典求凸包。

4.24题目 868. 二进制间距

【位运算】我们可以使用一个循环从n二进制表示的低位开始进行遍历，并找出所有的1。我们用一个变量last记录上一个找到的1的位置。如果当前在第i位找到了1，那么就用i-last更新答案，再将last更新为i即可。

4.25题目 398. 随机数索引

【水塘采样】遍历nums，当我们第i次遇到值为target的元素时，随机选择区间「0，i）内的一个整数，如果其等于0，则将返回值置为该元素的下标，否则返回值不变。设nums中有k个值为target的元素，该算法会保证这k个元素的下标成为最终返回值的概率均为1/k。

4.26题目 883. 三维形体投影面积

【数学】根据题意，x轴对应行，y轴对应列，z轴对应网格的数值。xy平面的投影面积等于网格上非零数值的数目；yz平面的投影面积等于网格上每一列最大数值之和；zx平面的投影面积等于网格上每一行最大数值之和。

4.27题目 417. 太平洋大西洋水流问题

【DFS】使用深度优先搜索实现反向搜索，搜索过程中需要记录每个单元格是否可以从太平洋反向到达以及是否可以从大西洋反向到达。反向搜索结束之后，遍历每个网格，如果一个网格既可以从太平洋反向到达也可以从大西洋反向到达，则该网格满足太平洋和大西洋都可以到达，将该网格添加到答案中。

4.28题目 905. 按奇偶排序数组

【原地交换】记数组nums的长度为n。先从nums左侧开始遍历，如果遇到的是偶数，就表示这个元素已经排好序了，继续从左往右遍历，直到遇到一个奇数。然后从nums右侧开始遍历，如果遇到的是奇数，就表示这个元素已经排好序了，继续从右往左遍历，直到遇到一个偶数。交换这个奇数和偶数的位置，并且重复两边的遍历，直到在中间相遇，nums排序完毕。

4.29题目 427. 建立四叉树

【递归 + 二维前缀和优化】X可以与处理出数组gd的二维前缀和，这样一来，当我们需要判定某一部分是否均为0或1时，可以在O（1）的时间内得到这一部分的和，从而快速地进行判断。

4.30题目 908. 最小差值 I

【数学】更改后的整数数组nums的最低分数为maxNum-minNum-2k。