-
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
-
