【Fifty Project - D25】

今日完成记录

Leetcode

每日一题

到达最后一个房间的最小时间II：和昨天的每日一题大致一样，增加一个条件，第一次走需要1s，第二次要2s，第三次1s，依次更迭。
思路：依然是单源最短路，只是队列中多存储一个状态，用来表示这一次需要耗时1s还是2s，计算费用时加上这个状态即可，其余不变。

差分

使数组中所有数等于0：给一个数组arr，以及数字k，可以进行若干次操作：选择一个连续长度为k的子数组，所有数减一。判断若干次操作后能否使得整个数组为0。
思路：从头开始往后走，遇到大于0的数判断是否能进行操作（剩余长度至少为k），不能则失败，能就直接进行操作，直到当前数为0，如途中遇到因为前者操作而变为小于0则失败。使用差分数组记录操作点，每次操作cf[i] -= arr[i]; cf[i + k] += arr[i];

子矩阵元素加一：给一个n*n的0矩阵，以及一个queries数组，每个数组由两个坐标对组成，表示这个坐标对组成的矩阵元素均加一，问queries操作后这个矩阵是什么情况
思路：这是个二维差分问题，一开始一直想不到怎么构建这个二维差分数组，就一直反复想灵神写的那句话“差分和前缀和的关系，就好像导数和积分一样”，差分的前缀和是原数组，原数组的前缀和是前缀和，最后用类似前缀和的想法写出来这个二维差分。

差分的题就到此为止了，明天开始栈部分的题，最近确实很松懈了，每天进度贼慢，佛系写题hhh

笔试题

记一个师弟今天的笔试题
给一个字符串s，以及数字k，要求构建一个字符串t，这个字符串必须是s的子串（s中去除任意字符得到的串），要求这个t满足相邻字符绝对值差不超过k（不存在环的关系，也就是a和z相差25 而不是1），要求返回最长的t
思路：线性dp，这应该算dp吧，dp[i]表示以s[i]结尾的符合要求的t的最大长度。用一个数组memo记录此前出现过的以a到z结尾的最大长度，然后每次判断当前字母结尾的最大长度时，从与当前字母绝对值差小于等于k的字母中选择最大长度并且+1。dp[i] = Math.max(memo[k] + 1, dp[i]);//其中Math.abs(k - s[i]) <= k，时间复杂度是O(n * 26) 即O(n)