-
LeetCode 3296 & 3297 - 统计重新排列后包含另一个字符串的子字符串数目
-
典型滑动窗口题目，统计
word2的字符出现频次，以及word1当前窗口的字符出现频次，如果word1当前窗口每个字符的出现频次均大于等于word2的频次，则说明可以通过重新排列word1的滑动窗口内的字串得到word2，以及固定窗口左侧，一直延伸到word1的末尾的所有子串都满足题目要求。II属于困难题，上述的做法会超时。改进点可以使用一个变量
diff记录word1当前窗口还需要多少个字符才能通过重新排列得到word2，然后在滑动窗口的过程中，根据diff的值来判断是否需要移动窗口左侧或者右侧。diff值可以在窗口变化时更新，判断当前滑走/滑入的字符是否会影响diff的值来采取递增或者递减。 - LC 题目链接
-
-
LeetCode 198 & 213 - 打家劫舍I、II
-
这两道题目是LeetCode上的经典动态规划题目，都是关于打家劫舍的问题。对于第一道题目，可以定义一个数组
dp，其中dp[i]表示在前i个房子中能偷到的最大金额。对于第i个房子，有两种选择：偷或者不偷。如果偷第i个房子，那么第i - 1个房子就不能偷，因此最大金额为dp[i - 2] + nums[i]；如果不偷第i个房子，那么最大金额取决于前i - 1个房子的结果，即dp[i - 1]。因此，状态转移方程为dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。最后，返回dp[n - 1]和dp[n - 2]中的较大值即可。而对于第二道题目，由于房子是环形的，因此可以分两种情况讨论：偷第一个房子和不偷第一个房子。对于第一种情况，
dp[0] = nums[0]，第1到第n - 2个房子的偷法采用第一题的做法，而最后一个房子不能偷，即dp[n - 1] = dp[n - 2]；对于第二种情况，第一个房子不能偷，即dp[0] = 0，第1到第n - 1个房子的偷法采用第一题的做法，而最后一个房子可以偷，即dp[n - 1] = dp[n - 2]。最后，返回这两种情况的较大值即可。 - LC 题目链接
-
-
LeetCode 1444 - 切披萨的方案数
-
一开始想复杂了，以为切后的两片都能再切，其实只能继续切右边/下边的那块(这意味着不用记录剩下的长宽，只要记录下一切的起始点就行，因为能继续切的部分处于原披萨的右下角)，另一块则需要保证有苹果。因此可以使用递归+记忆化搜索解决：记
dp(r, c, remain)为从(r, c)开始，剩余remain次切割的方案数：-
如果
remain == 0，则只需判断剩下的那块有没有苹果即可，如果有则返回1，否则返回0 -
如果
remain > 0，但是剩下的切数过多，也就是说，即便切成1x1, 还是多余的切数，直接返回0 -
否则，分别考虑横向切和纵向切的情况，如果从某一行/列切下去后，前面的行/列有苹果，则后面的切法都能保证切出来的那块有苹果，此时将
remain减一，从新的起始点递归调用dp函数，累加结果即可。
-
- LC 题目链接
-
-
LeetCode 3133 - 数组最后一个元素的最小值
-
一个想起来挺复杂，但想出来后实现挺简单的题目。由于要求数组内所有元素按位AND之后的值为
x，这意味着，x每个为1的位，数组中每个元素的对应位也都要为1。因此，我们可以按照以下方式构造一个递增数组：第一个元素除了x中为1的位之外，其他位都为0，第二个元素其他位中后两位为10，第三个元素其他位中后两位为11，第四个元素其他位中后三位为100，以此类推。这样构造的数组，其最后一个元素的值就是返回值。因此，题目就可以转化为：满足x中为1的位，对应位也都要为1的(for all b, if x[b] == 1 then elem[b] == 1)，第n个元素的值。。换句话说，本质就是将n转化为二进制，然后插入到x中为0的位。 - LC 题目链接
-
-
LeetCode 1442 - 形成两个异或相等数组的三元组数目
-
不难得知，对于满足条件的三元组
(i,j,k)，由于arr[i..j-1]的异或结果a等于arr[j..k]的异或结果a，那么a和b的异或结果为0，换句话说，子数组arr[i..k]所有的元素异或结果为0。反过来思考，如果某个长度为l的子数组中，所有元素异或的结果为0，那么该子数组中可以构造l - 1个满足条件的三元组。因此，题目转化为寻找所有元素异或结果为0的子数组，并计算其长度l，然后累加l - 1的和。怎么寻找这些子数组呢？我们可以使用一个数组
prev_xor，其中prev_xor[i]表示第i个元素到当前元素的异或结果。那么可从左到右遍历数组arr，更新prev_xor，如果更新后某个prev_xor[i]的结果为0，那么从i到j的子数组满足条件，此时可以构造j - i个三元组。 - LC 题目链接
-
-
LeetCode 3192 - 使二进制数组全部等于 1 的最少操作次数 II
-
有两种做法：第一种则是动态规划，记
dp[i][j](其中j = 0, 1)为数组后i个元素构成的子数组(只考虑这i个元素，不考虑前面的翻转影响)翻转为j的最少次数，则如果nums[i] == j，则dp[i][j] = dp[i - 1][j]；否则dp[i][j] = dp[i - 1][1 - j] + 1。最后返回min(dp[n][0], dp[n][1])。第二种做法，则是基于上一个问题3191：先考虑第一个元素，如果其为
0，则只能通过翻转arr[0..n]将其翻转为1；随后，如果第二个元素此时为0，则只能翻转arr[1..n](因为如果翻转arr[0..n]，则第一个元素又会变为0)；以此类推。那么如何判断第i个元素此时应该为0还是1呢？我们将翻转次数记为k，此时arr[i] = (arr[i] + k) % 2。 - LC 题目链接
-
-
LeetCode 3206 & 3208 - 交替组
-
交替组I由于只需求连续3块瓷砖的交替，做法很简单，直接枚举模拟判断
colors[i] == colors[(i + 2) % n] and colors[i] != colors[(i + 1) % n]即可；交替组II将瓷砖组的数量泛化为任意数量
k，则需要考虑双指针的方法：left指针指向当前组的起始位置，right指针指向当前组的下一个比较位置。如果colors[right] != colors[(right - 1) % n]，意味着交替继续，right指针继续向右移动；否则，left指针指向right(快速移动，left只往右移动一位该组还是不会交替的，直接跳到right即可)，right指针指向下一个位置。当right == (left + k) % n时，意味着找到了一个交替组，ans += 1。 - LC 题目链接
-
-
LeetCode 2940 - 找到 Alice 和 Bob 可以相遇的建筑
-
一开始自然地想到了单调栈：先假定
bi > ai(如果bi == ai，已经相遇，则直接返回ai即可)，如果bi比ai高，则Alice直接走到bi即可；否则，Bob需要找到第一个比ai高的建筑。此类找到右侧第一个比当前位置高的建筑的问题，可以使用单调栈解决: 如果第一个比bi高的建筑(即为ci)也比ai高，则Alice可以直接走到这个建筑；否则，Bob需要继续找到右侧第一个比ai高的建筑: 类似于链表的形式，Bob继续跳到比ci高的第一个建筑，直到找到比ai高的建筑。这样的时间复杂度为O(n2)。且链表状的查找过程，无法使用二分查找优化。因此，我们需要使用ST表/线段树/树状数组来优化此类的区间查询问题: 即在区间
[bi, n-1]中找到第一个比ai高的建筑。这样的时间复杂度可降为O(nlogn)。 - LC 题目链接
-
-
LeetCode 3240 - 最少翻转次数使二进制矩阵回文 II
-
在3239的基础上，条件升级为行回文且列回文，且
1的次数必须被4整除。分析可知，由于两种方向都对称，每个元素都可能会有3个镜像位置，也就是题目中为什么要求能被4整除: 无论该位置是0还是1，通过翻转满足题目要求后，这四个位置要么全0，要么全1，1的个数都会被4整除。这样就解决了吗？并不是！我们还需要考虑奇数行和奇数列的情况：-
如果行数和列数都是奇数，那么中心位置必须为
0，否则1的个数不可能被4整除。 -
如果行或列为奇数，我们需要考虑中心行和中心列: 在中心行/列中，除了最中央的元素(只有行和列都为奇数的时候，才会有这个元素)外，每个元素有
1个镜像位置。我们可以统计中央行和列的1的个数，以及不对称的位置对个数。然后使用贪心的方法计算最少翻转次数: 首先考虑保证对称的情况，此时需要翻转的次数为不对称位置对的个数；然后再考虑能被4整除的情况，此时需要翻转的次数为min(4, 4 - (1的个数 % 4))。我们需取两种情况的最大值即可保证两种情况都能满足！
-
- LC 题目链接
-
-
LeetCode 3218 & 3219 - 切蛋糕的最小总开销
-
问题I可以直接记忆化搜索/动态规划解决，即遍历所有可能的切法，递归计算各种切法的总开销，取最小值即可。即对于一个初始位置为
(begin_r, begin_c)，大小为(width, height)的矩形，最小的开销记为dp(begin_r, begin_c, width, height), 则有如下递归关系：-
如果
width == 1或height == 1，则返回0； -
如果
height > 1，则可以在height - 1个位置切开，对于每个位置1 <= i < height，计算dp(begin_r, begin_c, width, i) + dp(begin_r, begin_c + i, width, height - i)的最小值； -
如果
width > 1，则可以在width - 1个位置切开，对于每个位置1 <= j < width，计算dp(begin_r, begin_c, j, height) + dp(begin_r + j, begin_c, width - j, height)的最小值。 -
最终结果即为上述两种情况的最小值。
问题II由于数据量很大(
1 <= m, n <= 10^5)，无法穷举所有的切法，我们需要通过观察下是否可以采取贪心的策略：-
做法1: 不必遍历所有的横切/竖切方法，每个方向只取开销最大的切法即可(否则，如果开销最大的切法放在后面切，因为另一个方向的蛋糕可能会变多，可能会使得开销变大(
方向1切法开销 * 方向2切片数量)) -
改进做法1: 由于需要找到开销最大的切法，在每一次递归中每个方向都需要遍历一次，重复计算了很多次，不妨使用ST表来预处理每个区间的最大值，这样可以在
O(1)时间内找到每个区间的最大值。 -
进一步改进：递归的开销同样巨大，由于做法1已经不是穷举所有的切法，可以转为队列的方式，每次取出开销最大的切法，然后将其切开，将新的切法加入队列中，直到队列为空。
-
做法2: 上述做法还是会超时…不妨进一步将贪心用到极致，结合归并的思想：首先对两种切法的开销进行排序，然后候选的切法为开销最大的横切、竖切，然后评估上述两种切法中，能够使得开销最小的切法，重复上述过程，直到候选切法为空。详细的贪心做法见详情。
-
- LC 题目链接
-
-
LeetCode 699 - 掉落的方块
-
线段树的应用题，由于之前没系统实现过线段树，所以这次从头学了一遍线段树的简单实现和应用。该题目就是在一个二维的坐标轴上，不断添加方块，并将每次添加后所有方块的最大高度添加到结果中。本质上，每次添加边长为
sideLength的方块时，首先需要找到该方块所在x轴区间[left, left + sideLength - 1]的最大高度h，然后将该区间的最大高度更新为h + sideLength。不难得知此类区间更新+查询类型题目可使用线段树解决，每个节点维护一个区间的最大高度，在每次添加方块的时候，首先查询该区间的最大高度，然后更新该区间的最大高度，并将总的最大高度添加到结果中。 - LC 题目链接
-
-
LeetCode 2959 - 访问消失节点的最少时间
-
多源最短路径问题的变种，可使用Floyd算法解决。题意要求求解的是去掉某些节点后，所有节点之间的最短路径都不超过
maxDistance的方案数。可以逆向思考，求解子集中所有节点之间的最短路径都不超过maxDistance的子集数量。因此，我们可以使用回溯法枚举所有子集，然后使用Floyd算法求解子集中所有节点之间的最短路径，最后统计满足条件的子集数量。需要注意的是，如果在每个枚举中都重新来一遍Floyd算法，时间开销会特别巨大。我们可以回顾下Floyd算法的原理，本质是动态规划，在每次迭代中，我们只需要关注新增的节点(允许经过该节点)对所有节点间的最短路径的影响。对于本题目，我们可以在参数中传递前面的节点集合中的最短路径矩阵，然后在本次枚举中，只需要关注新增的节点对前面节点间的最短路径的影响即可。
- LC 题目链接
-
-
LeetCode 1267 - 统计参与通信的服务器
-
本质就是找到一组服务器，其中每个服务器至少和另一个服务器处在同一行或同一列中。一开始想用的是并查集，但不用那么复杂。有两种方法，第一种也是官解的做法，即两次遍历+哈希表的做法，首先第一次遍历用于统计每一行和每一列的服务器数量，第二次遍历则检查服务器对应的行和列是否有其他服务器，如果有，则计数；
第二种方法也是遍历两次，但第二次遍历仅需遍历行即可，使用的是逆向思维：统计落单的服务器个数，最后结果即为总服务器数减去落单的服务器数。首先第一次遍历统计所有的服务器数量、每一列的服务器数量以及每一行中仅有一个服务器的情况下，该服务器的所在列，第二次则遍历每一行，如果该行中仅有一个服务器，且该服务器所在列的服务器数量为
1，则该服务器为落单服务器。 - LC 题目链接
-
-
LeetCode 1262 - 可被三整除的最大和
-
比较容易想到使用动态规划的方法，定义
dp[j][i](其中0 <= i < 3)表示数组前j个元素中，模3余数为i的最大和。遍历数组，对于每一个nums[j]，更新dp[j][(i + nums[j]) % 3] = max(dp[j - 1][(i + nums[j]) % 3], dp[j - 1][i] + nums[j])。最终的答案就是dp[len(nums) - 1][0]。需要注意的是，由于dp元素的初始值为0，如果在更新数组的过程中，发现上一个状态dp[j - 1][i]为0，且i != nums[j] % 3，则直接跳过，因为为0意味着前面数组中完全找不到模3余数为i的和。如果dp[j - 1][i]为0，且i == nums[j] % 3，则直接更新dp[j][i] = nums[j]，意味着当前元素就是模3为i最大和。 - LC 题目链接
-
-
LeetCode 1247 - 交换字符使得字符串相同
-
需要一些观察和分析，首先，在同一个下标
i下，如果s1[i]为x，而s2[i]为y，将其记为xy对；如果s1[i]为y，而s2[i]为x，将其记为yx对。那么，如果存在两个相同的xy对(或者两个相同的yx对)，那么可以通过一次交换将这两个对应的下标变为相同的字符；而如果仅有一个xy对以及一个yx对，那么需要两次交换才能将其变为相同的字符。对于整个字符串而言，如果xy对和yx对的个数总和为奇数，那么无法将其变为相同的字符串(不难证明，上述情况下，两个字符串的x个数为奇数，y个数，不可能能做到两个字符串相等)。如果为偶数，则存在可行解，且最优解可通过贪心的做法，尽量先同类对交换(只需要一次交换操作)(即xy对内部两两匹配，yx对内部两两匹配)，如果最后剩下一个xy对和一个yx对，那么需要两次交换。 - LC 题目链接
-
-
LeetCode 3011 - 判断一个数组是否可以变为有序
-
题目中的交换操作以实现排序，本质就是冒泡排序的做法。因此，我们可以模拟冒泡排序的过程，如果在交换过程中发现需要交换的相邻两个元素的二进制数位
1不同，那么就无法通过交换操作实现排序，返回False；否则，返回True。上述的模拟冒泡排序做法的时间复杂度为
O(n^2)，其实还有一种不用排序，且仅需一次遍历的做法。通过观察发现，某个元素能交换的位置范围是有限的，即该范围内所有的元素都具有相同的二进制数位1(即只能彼此交换，不能逾越到1计数不一样的元素那里)。我们可以将数组切分成若干个这样的区间，然后将每个区间的元素进行排序，最后观察整个数组是否有序即可。该做法还有个trick，而无需对区间进行排序：只要数组每个区间的最小值都大于其左边区间的最大值，那么就可以认为整个数组可以通过交换操作变为有序。 - LC 题目链接
-
-
LeetCode 3102 - 最小化曼哈顿距离
-
两个点
p0(x1, y1)和p1(x2, y2)的曼哈顿距离为|x1 - x2| + |y1 - y2|。不妨将绝对值分情况讨论，即有四种情况：-
x1 >= x2，y1 >= y2，有x1 - x2 + y1 - y2 = (x1 + y1) - (x2 + y2)； -
x1 >= x2，y1 < y2，有x1 - x2 + y2 - y1 = (x1 - y1) - (x2 - y2)； -
x1 < x2，y1 >= y2，有x2 - x1 + y1 - y2 = (y1 - x1) - (y2 - x2)； -
x1 < x2，y1 < y2，有x2 - x1 + y2 - y1 = (x2 + y2) - (x1 + y1)。
不难得知，最大曼哈顿距离的点对，要么是
x + y中最大和最小的两个点，要么是x - y中最大和最小的两个点(直观地讲，可以看成是两个对角线)。因此，要想移除某个点后任意两点间最大曼哈顿距离最小，要移除的点必然出自上述两个点对(4个点)中的某个点(不难证明，如果移除上述点对外的点，最大曼哈顿距离没有变化)。因此，我们可以先将所有点按照x + y和x - y的值排序以取得上述的点对，然后枚举这四个点，计算移除该点后的最大曼哈顿距离，取最小值即可。 -
- LC 题目链接
-
-
LeetCode 1222 - 可以攻击国王的皇后
-
类似于1958-检查操作是否合法，枚举八个方向，如果有一个方向具有皇后，则将该皇后坐标添加到结果数组中(后续该方向不用寻找了，只关注该方向的第一个皇后)，然后转向下一个方向继续寻找。
- LC 题目链接
-
-
LeetCode 1186 - 删除一次得到子数组最大和
-
最大和子数组的变种题目，新增了一个允许删除一个元素的条件。对于最大和子数组，其中以第
i个元素结尾的子数组最大和为dp[i] = max(dp[i-1] + nums[i], nums[i])。对于本题，我们可以使用二维n * 2的dp数组，其中dp[i][0]和dp[i][1]分别表示以第i个元素结尾的非空子数组，不删除元素和删除一个元素的情况下的最大和。对于不删除元素的情况，dp[i][0] = max(dp[i-1][0] + nums[i], nums[i])；对于删除一个元素的情况，dp[i][1] = max(dp[i - 1][0], dp2[i-1] + nums[i])(即要么是删除本元素，要么就是不删除本元素，删除的操作在前面的元素)。最终结果即为上述循环中最大的数组值，注意不能取dp[0][1]，因为题目要求子数组非空的。(2024-07-21更新实际上，dp[0][1]是不符合上述的非空子数组要求的，只不过这里为了方便计算，将dp[0][1]设置为初始值0，但不计入结果) - LC 题目链接
-
-
LeetCode 2786 - 访问数组中的位置使分数最大
-
此类单向转移+寻找分数最大化的问题可以考虑使用动态规划做法。最朴素的dp是定义
dp[i]为转移到第i个元素的最大分数，其中dp[i] = max(dp[j] + nums[i] - (x if nums[i] % 2 != nums[j] % 2 else 0))，j < i，这样需要双重循环，需要考虑优化：仅使用两个变量odd_max和even_max表示已遍历的数组元素中，转移到奇数和偶数的最大分数，这样可以将遍历压到一重。其中遍历到偶数元素时，更新even_max = max(even_max + nums[i], odd_max + nums[i] - x)，遍历到奇数元素时，更新odd_max = max(odd_max + nums[i], even_max + nums[i] - x)。最后返回max(odd_max, even_max)即可。 - LC 题目链接
-
-
LeetCode 1105 - 填充书架
-
放置/分类且求某最小值的题目，可以考虑动态规划。本题中使用
dp[i]表示放置前i本书所需的最小高度。在遍历书i时，需要考虑最后一层 + 前面层的最小值，可以遍历书i放在最后一层的所有可能情况，计算当前情况的总高度(最后一层高度+前面层次的高度，后者可以直接取上一层最后一本书的dp结果)，取其中的最优解(因此就满足了最优子结构)。状态转移方程为dp[i] = min(dp[j] + line_height)，其中j为上一层最后一本书的编号(j < i)，且sum(width[j+1..i]) <= shelf_width，line_height为最后一层的高度(j+1到i之间的最大值)。 - LC 题目链接
-
-
LeetCode 1094 - 拼车
-
一开始以为这种区间查询和更新问题需要使用线段树or树状数组的结构，没想到可以利用前缀和的逆形式 - 差分数组来解决，差分数组本质也是个前缀和，但区别在于其维护的是元素间的差值，而不是元素本身。这样，对于区间
[l, r]的更新操作add(l, r, val)可以转化为diff[l] += val和diff[r + 1] -= val，而每个元素本身的值可以累加前面的差分值得到。这样，对于add(l, r, val)此类的更新操作操作，只需要O(1)的时间复杂度即可完成。差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。而前缀和主要适用原始数组不会被修改的情况下，频繁查询某个区间的累加和。 - LC 题目链接
-
-
LeetCode 1061 - 按列翻转得到最大值等行数
-
不妨取个例子：如果通过多次列翻转后，数组
[0, 0, 1]变为全0或者全1，那么通过相同的列翻转操作，数组[1, 1, 0](注意，110和011异或后为0)也可以变为全1或者全0，而其他排列的数组则不会变为全0或者全1(具有互斥性)。我们将这些两两异或后为0的行放在一个集合内，该问题本质就是求解最大的集合，其中集合内的行通过相同的列翻转操作可以变为全0或者全1。我们可以使用哈希表进行集合计数，而下一步就是如何表示这些集合：不难得知，每个集合内仅有两种可能的数字（如上述例子的001和100），其互为对方的反码，我们将有前导0的数字作为计数哈希表的键，而遇到前导1的数字时，我们将其反码作为键，这样就可以保证集合的唯一性。最后，我们只需要返回最大的集合的计数即可。 - LC 题目链接
-
-
LeetCode 937 - 重新排列日志文件
-
简单的字符串处理题，首先按第一个空格分割每个日志，取出标识符和内容，然后检查内容是否全为数字或空格判断是否为数字日志：如果是，则按序加入到数字日志列表中，否则，加入
(内容, 日志全文)到字母日志列表中(如果内容相同，进而比对日志全文，实际上就是在比对标识符了，没必要单独放标识符在元组里面)。最后，对字母日志列表进行排序，然后按序取出日志全文并追加数字日志组成即可。官解的答案也非常简洁：自定义排序逻辑(直接编写排序函数里面的
key逻辑即可)，每个元素用于比较的信息为(0,内容,标识符)(如果是字母日志)或(1,)(如果是数字日志)，由于是稳定排序，所以数字日志的顺序不会被打乱。 - LC 题目链接
-
-
LeetCode 1673 - 找出最具竞争力的子序列
-
由题目得知，如果子序列前面的值越小，则越具竞争力，即尽可能找到较小的值放在前面。本质就是找到一个子数组，其中第一个元素为
nums[0..n-k]中的最小值，第二个元素为nums[第一个元素位置+1..min(n-1, n-k+1)]中的最小值，第三个元素及后面亦然(注意区间的右侧，我们不能直接取最小值，否则即便追加后面所有的元素都无法构成长度为k的结果)。朴素的想法可以使用一个堆，先维护nums[0..n-k]中的元素，然后开始循环，取出栈顶(当前最小值)，如果栈顶的位置位于结果数组最后一个元素的右边，则加入到结果数组中，并将原数组未加入到堆中的最左边元素放进堆里面，直至结果数组填充完毕。更高效的方式是使用单调栈(并不一定单调，只是处理的方式同单调栈，尽可能将较小的元素放在最前面)来充当当前循环的最优解：如果当前元素小于栈顶，且栈顶弹出后不影响结果的长度等于
k(所谓的影响即，弹出后再加入该元素，并将该元素后所有元素添加上去，长度都小于k)。 - LC 题目链接
-
-
LeetCode 889- 根据前序和后序遍历构造二叉树
-
类似于根据前序+中序遍历构造二叉树，不同之处在于仅根据前序和后序则不能构建一棵唯一的二叉树，即如果只有一个孩子的情况下，仅根据前序和后序遍历是无法得知其为左孩子还是右孩子。在每次递归下，如果当前子数组的长度为1，则此时子树仅只有一个节点，直接返回该节点即可；否则，该子树的根的值为前序遍历子数组的第一个元素，亦是后序遍历子数组的最后一个元素；而其第一个孩子(左孩子)的值为前序遍历子数组的第2个元素，而最后一个孩子(不一定是右孩子，可能还是左孩子)的值为后序遍历子数组的倒数第2个元素。如果第一个孩子的值等于最后一个孩子的值，则说明该节点仅有一个孩子。否则，根据上述信息，进一步切分成两个子数组继续递归下去。
- LC 题目链接
-
-
LeetCode 1542 - 找出最长的超赞字符串
-
相当有挑战性的题目。朴素的前缀和做法是使用一个数组
pre，其中pre[i] = (c0, ..., c9)是指数组arr前i个元素中，0-9的计数，所以子数组arr[i..j]的计数信息可通过pre[j + 1] - pre[i + 1]计算可得。若子数组满足超赞字符串(重排后满足回文)，则计数信息需要满足仅存在零个或一个奇数计数位。因此，遍历所有的位次，计算前缀信息后再遍历以该元素结尾的子数组，校验是否为超赞字符串，不断更新超赞字符串的最长长度。但这样会发生超时，我们可以将计数信息压缩到一个
int，其中第i个二进制位表示数字i的计数的奇偶性。其中pre[j] - pre[i]可以表示为pre[j] ^ pre[i](使用异或来表示奇偶相减)，然后判断为1的位个数是否小于等于1即可。但还是会超时…需要再通过逆向思维来挖掘可以优化的地方：在前面的做法中，每遍历一个位次时，均需要通过双重循环，计算以该位次元素结尾的子数组中满足要求(即两个前缀信息异或后得到子数组计数信息，判断
1的个数小于等于1)的最长长度，复杂度为O(n^2)。不难得知，可能的前缀信息共有1024个，其中满足和当前前缀异或后的结果中。1的个数小于等于1的前缀信息共11个(即和本身异或，得到全0比特串，或者和0000000001，0000000010直至100000000异或，得到只有一个1的比特串)。我们可以使用哈希表记录这些前缀信息第一次出现的位置(后面出现的位置拿来比较没意义了，只有和第一次出现的位置比较才会得到比较长的子数组)，然后反向推导，根据当前位次的前缀信息比特串来得到异或后满足要求的这11个比特串，然后查哈希表得到它们第一次出现的位置，更新结果即可！ - LC 题目链接
-
-
LeetCode 851 - 喧闹和富有
-
首先使用图论将问题抽象出来，将人视作为节点。可以采用DFS的方法解决问题：首先如果
a比b富有，则添加有向边b -> a(注意是指向更富的人)，然后通过DFS的方法，求解节点a中，比a富有的人中，quiet值最小的人：首先初始化quiet最小者为自己，然后遍历子节点中quiet值最小者，更新自身的最优解，直至所有节点处理完毕。同样，此类涉及入度出度的问题可以转化为拓扑排序：如果
a比b富有，则添加有向边a -> b(注意这里是指向更穷的人)。不难得知，入度为0的节点意味着没有人比他富有，即属于最富的一批人。但不能使用前缀和的思路解决，因为最富的一批人中，我们不知道他们内部谁比谁有钱(没有边连接他们)。所以，我们可以在拓扑排序的过程中，当处理入度已为0的节点u时，减少其子节点v的入度过程中，顺带更新v中quiet值最小者的数据。这种本质就是从富有到贫穷的顺序开始处理，不断更新穷人(子节点)的数据。 - LC 题目链接
-
-
LeetCode 849 - 到最近的人的最大距离
-
一般这种考虑左右两侧的数组题目(如845)，都可以通过两次遍历(从左，从右)+前缀和思路维护局部数据，然后再遍历一次数组以组成结果。在这个题目中，这个局部数据就是左侧/右侧连续为0的个数，最后再遍历数组，其中第
i个座位距离最近有人座位的距离为min(左侧连续为0的个数, 右侧连续为0的个数)。需要注意左/右侧没人的情况。此外，这种双侧题目，可以使用双指针+贪心的方式以减少空间开销。使用
left和right从左到右分别指向有人座位，其中right为left右侧的第一个有人座位(即left下一次会指向right)。因此，这两个有人座位的空隙中，最大的距离为(right - left) // 2。不断移动两个指针，直至right滑出数组即可。同样需要留意数组边缘左右侧没人的情况。 - LC 题目链接
-
-
LeetCode 2589 - 完成所有任务的最少时间
-
对于任务规划题目，一般都可以采取按结束时间排序 + 贪心的方法解决。在这个问题里，同样可以先按
end排序，然后遍历所有的任务，首先优先寻找能够复用的时间段，即使用start对已经使用的时间occupied(离散时间点，如[1,2,3,5,6,7]表示时间[1-3]和[5-7]被使用，且可以复用)进行二分搜索，寻找大于等于start的元素下标位置i，此时可以复用的时间段数量为occupied.length() - i(即右侧的所有时间都可以复用)；对于剩下的、无法复用的时间，则将其依次添加到occupied中（新建使用时间），直至所有任务处理完毕，返回occupied的长度即可。 - LC 题目链接
-
-
LeetCode 845 - 数组中的最长山脉
-
这种涉及两侧计算的数组问题一般都可以考虑使用双侧前/后缀和的思想来维护阶段信息，对于此问题，使用两个数组
l2r_inc_cnt和r2l_inc_cnt分别维护某个元素左侧/右侧连续递增的最大长度(不包括该元素)。然后再重新遍历一次数组，对于下标i，取l2r_inc_cnt[i] + r2l_inc_cnt[i] + 1的最大者即可。进阶要求一次遍历+
O(1)空间复杂度，可以考虑使用双指针，两个指针left和right分别指向山峰左右两侧的山脚，然后取right - left + 1的最大者即可。需要留意的是连续重复值的处理，可以使用peak记录山顶的位置，如果peak和right的位置一致(说明arr[peak] == arr[right])，不构成题意的山峰，跳过此次的处理，并将right快速移向不重复的地方。 - LC 题目链接
-
-
LeetCode 826 - 安排工作以达到最大收益
-
朴素做法是，对于每一个
worker，遍历所有的工作，找到难度满足工人能力中收益的最大值，这样的复杂度为O(nm)。可以通过排序的方法降到O(nlogn + mlogm)：对工作按工作难度进行排序，以及对工人的能力进行排序，使用一个指针cur_valid_work_cnt维护当前有效的工作数量(即对于当前遍历的工人都能干的活)，并使用cur_valid_work_max_profit维护当前有效工作最大收益，然后对于每一个worker，首先更新下有效工作信息(cur_valid_work_cnt指针往右移动直到下一个工作不满足工人难度，并最大收益)，并累加有效工作的最大收益即可。 - LC 题目链接
-
-
LeetCode 787 - K站中转内最便宜的航班
-
一开始使用了Dijkstra算法，后面发现不太适用，因为最多K次中转不代表最多K次循环。后面改用了队列+BFS的做法，队列维护节点、从源节点到该节点的路径总开销以及中转站数量，在每次循环中，从队列取出队首，更新节点的最小开销，如果该节点的中转站数量达到
k后则不再进行松弛，否则松弛其后继节点并将松弛后的开销加入到队列中。由于一开始没考虑到稠密图的情况，因此可能会出现队列迅速膨胀导致MLE的问题，因此，如果循环中对应节点的开销大于当前的最小开销，则不再继续后面的松弛操作(如果没有负权, 后续的松弛操作是没意义的)。后面想了想，这不就是队列版本的Bellman-Ford算法嘛。 - LC 题目链接
-
-
LeetCode 1017 - 负二进制转换
-
首先对数字按正常的二进制展开，然后如果某个二进制位在新的表示法中属于负数，则需要”往前借一位”，比如，第
3个比特在新的表示法中是-8，如果需要表示8，则需要利用第4个比特，即8 = -8 + 16，然后再进一步处理16之后的数字(前面的处理结果已经固定了，无后效)。如果某一位比特不仅原来的表示法需要使用到，且前面的数字又存在进位，则需要合并、往后面继续进位，如24 = 8 + 16 = -8 + 16 + 16 = -8 + 32，后面再继续处理32 = -32 + 64，最终结果为24 = -8 - 32 + 64。因此，最终的思路为从小往大处理比特位，如果某个比特按正常的表示法需要使用到，则进一步判断在新的表示法中是否为负数，如果是，则置为1向左边的比特位进位；如果某个比特不仅原表示法需要使用到，且存在进位，则置为0继续进位。 - LC 题目链接
-
-
LeetCode 39 & 216 & 377 - 组合总和相关问题
-
这三天的每日一题都是组合总和的问题：
-
第一天的题目39可以用回溯法解决，在参数中记录当前回溯的数组开始位置（由于重复选取，下一次回溯的数组开始位置可以和本次相同）、当前所选用的数字组合
arr及其和cur_sum = sum(arr)。如果当前的cur_sum等于target，则加入到结果列表中并返回。为了加快搜寻，如果下一次回溯的cur_sum已经大于target，则直接剪枝。 -
第二天的题目216同样也是回溯法，由于不能重复选择，则下一次回溯的数组需要从下一个位置开始遍历。如果当前所选用的数字组合长度恰好为
k，则加入到结果列表中并返回。同理，可以采用多个剪枝的方法：如果当前选用数字的总和大于等于n，则提前返回；如果直接选用1 - k都大于n，或者直接选用(9 - k + 1) - 9都小于n，则直接返回空数组。 -
第三天的题目377则使用的是dp，使用
dp[i]表示nums中能凑成和为i的元素组合个数。则状态转移方程可以写为dp[i] = sum(dp[i - num] for num in nums if i - num >= 0)(选用数字num，将状态递归到子问题target = i - num的搜寻中)。
-
- LC
-
-
LeetCode 712 - 两个字符串的最小ASCII删除和
-
带权重的编辑问题，其中删除一个字符的成本为字符的ASCII值。令
dp[i][j]为子串s1[:i]和s2[:j]的最小编辑距离：如果s1[i - 1]等于s2[j - 1]，则dp[i][j] = dp[i - 1][j - 1](两字符串该字符无需修改)，否则dp[i][j] = min(dp[i][j - 1] + ord(s2[j - 1]), dp[i - 1][j] + ord(s1[i - 1]))(删除s1[:i]的最后一个字符的代价 + 子串s1[:i - 1]和s2[:j]的累积代价 or 删除s2[:j]的最后一个字符的代价 + 子串s1[:i]和s2[:j - 1]的累积代价)。 - LC 题目链接
-
-
解决文件资源管理器中鼠标频繁转圈的问题
-
今天入职装环境的时候发现文件管理器中鼠标疯狂转圈（加载），打开文件夹和右键的反应都比较卡顿，最后发现是安装了Windows Terminal的问题，卸载了就好了~自己建个目录手动安装就可以。
- DE
-
-
Flash闪念页改版完成
-
今天看了下Jekyll的文档，发现Flash页面可以使用Jekyll的机制从静态改成动态。 于是用了一个晚上改好了，外观不变，但是短文可以使用Markdown + YAML的形式来输入，不用在HTML页面上改来改去了。
Get到了一个新技能～
- DE
-
