image frame

Wei

编程,不需要天赋异禀,也不需要魔法,更不需要长胡子。

Grokking

Grokking the Coding Interview: Patterns for Coding Questions

课程原地址

题目目录与答案 Python版——完整题目目录,包含challenge。

题目目录与答案 C++版(附题目OJ的地址)——推荐用OJ测试自己的算法,但是这个repo里基本没有challenge题目。

1. Pattern: Sliding Window

Maximum Sum Subarray of Size K (easy) – GeeksforGeeks

k长的连续子序列,使该子序列和最大,这个和为output。
窗口长度都固定了,只需在遍历一遍时加后一个减前一个就行了,O(n)。

Smallest Subarray with a given sum (medium) – LeetCode

注意读题,nums都是正整数,target也是正整数。这个条件大概率需要用到。

假设有一段连续子序列了,它已经>=target了,就不需要再继续加入元素了(序列外右边第一个元素),因为再加的话size就变大了。而这个size可以向右横移一格,可以立马算出新的sum(这里很节约时间,降低算法复杂度)。

这个sum如果 >= target,那么它就有机会再小一点,而这一次需要的是减去序列内的第一个元素,可以理解为“收缩窗口”。
这个sum如果 < target,那就可以再向右横移了,因为size扩大,对结果没有任何帮助。

总体看下来,只要横移和收缩,算法复杂度是O(n)。

初步思路

初步思路是,先算个nums[0…x]之和 >= target的窗口,然后这个窗口开始向右移并尝试收缩。但其实不对,因为第一个窗口,不是非得从第0个元素开始,这个窗口自身就应该尝试收缩。这个逻辑补上后是能ac的。
不过,初步思路翻译为代码,还是有些小坑,肉眼很难查。建议背一个滑动窗口模板。

滑动窗口模板思路

此思路最核心的思想就是,不强求窗口横移,反正先向右扩展1个,再左边收缩一个,就达到了横移。
因此滑动窗口的头尾都可以移动,而且是分别移动,用两个变量来表示,(start,end)。
因为收缩(start向右移)和扩展(end向右移)可以各做各的,所以没必要先找到一个总和 >= target的初始窗口了。

所以,步骤可以化简为,每一次都扩展1下,然后尽力收缩(while不定次收缩)。

1
2
3
4
5
6
7
while end < n:
tmp_sum += nums[end]
while tmp_sum >= target:
win_size = min(win_size, end-start+1)
tmp_sum -= nums[start]
start += 1
end += 1

至于几个变量的初始值,现场推理一下也可以得到,不做赘述。
P.S. win_size没必要用int的max,用len(nums)+1就可以了,反正都是不可能的值。

补充

滑动窗口的算法,nums就算有负数也无所谓。(被烟雾弹迷惑🐶)这个条件大概是为“前缀和”这一方法准备的。

前缀和方法,简单来讲就是nums[0..i]之和组成一个sum数组,这个数组严格递增,都不存在相等的元素。

然后就可以用二分来找了(看到有序就要想到二分),当前sum[i]为0到i元素的和,sum[j] - sum[i] >= target转换为sum[j]>=target+sum[i],那么就是在sum数组里找target+sum[i]的lower bound。

为什么不是以j为结尾,sum[j] - sum[x] >= target转换成sum[x] <= sum[j]-target,找sum[x]呢?因为是upper bound(第一个>某值的元素)的前一个(必定<=某值),不如直接找lower bound简洁,而且不用处理减出负数的情况。

Longest Substring with K Distinct Characters (medium, google) – LintCode

Given a string, find the length of the longest substring in it with no more than K distinct characters.

也就是LeetCode340题 Longest Substring at Most K Distinct Characters。

这道题输出是最长子串的长度,所以显然可以套用滑动窗口的模板。和上一个题目一样,都是扩展会使得条件不符,要通过收缩来满足条件。
即,窗口扩展一旦字符种类超过k,就可以通过窗口收缩来削减字符种类。
唯一不同的点是:update longest string的时机(其实就是用end-start+1来尝试更新记录的longest)
因为while distinct_count(dict) > k时是去收缩,break while时说明distinct_count(dict) 已经<=k了,这个时候的[start, end]才是一个可能解,符合条件的可能解。
所以update longest string len是在while循环外,而且是之后。
至于如何实现dict和distinct_count,随便吧,简单也好,高效也好。

P.S.注意到了吗,这个题目和前面一题Smallest Subarray的区别?

看不出来也正常,我做了几道题才突然回头发现的😂而且明明之前做过笔记,重蹈覆撤🙄️

果然人类的本质都是复读机

这个题已经开始了longest之路,也就是说,只是想求一个最长的长度,根本不在意“重复无意义的更新”。

按之前的模板,此题的伪代码应写为:

1
2
3
4
5
6
7
8
9
while end < n:
dic[s[end]]+=1
while len(dic)>k:
dic[s[start]]-=1
if dic[s[start]]==0:
del dic[s[start]]
start+=1
longest = max(longest, end-start+1)
end+=1

这样的写法,保证了longest变量更新时,当前窗口都是len(dic)<=k的,也就是合法的情况。但确实可能会出现窗口被收缩的很小的时候(为了合法),此时max更新也是白干的(longest还是原值)。

而如果代码将内层while变为if:

1
2
3
4
5
6
7
8
9
while end < n:
dic[s[end]]+=1
if len(dic)>k:
dic[s[start]]-=1
if dic[s[start]]==0:
del dic[s[start]]
start+=1
longest = max(longest, end-start+1)
end+=1

自然,在longest更新时,当前窗口可能都还满足条件,不合法,但仍旧去做了一次longest的更新。但从数值上来讲,由于不满足条件会被收缩一次,加上前面的end扩展一次,窗口等于做了一次平移。那么end=start+1的值就不会变大,longest的更新自然也是不会有实际作用的。

这一个改动,它到底好在了哪里呢?光看经过,start,end两个游标都是单向前进的,2-while和while-if都不会使两个游标左右飘。但由于2-while会保证每次窗口都是合法的,和while-if相比,start这个游标可能会更靠右。举个极端例子,如果longest是[0, n-2]这个窗口,下一次扩展end就会到末尾n-1,while-if此时发现窗口不合法,收缩一次,就溜了。而2-while,会愣是要求[start, n-1]窗口合法,可能start从0不断右移,直到n-1才停止。无用操作在这个例子就占了一半。具体例子就是AAAAB, k =1。

这个优化并不容易读,我也不建议平时代码搞这么tricky。在这个题目里,仅仅在节省len查询和dict更新,都是较高效的操作,而且有次数上限(由于start标最多都走到末尾,操作次数最多n次)。优化效果仅仅锦上添花。但这个将while改为if,在其他题目中可能有奇效。因为while的判断条件如果复杂度较高,这里的收益就很大了,见Longest Substring with Same Letters after Replacement一题。

Fruits into Baskets (medium) – LeetCode

跟上题一模一样。题目暗示着连续区间,就可以尝试滑动窗口方法。

但这一题case比上一题的规模大,最简单的dict实现(不及时删除value为0的项,每次都要遍历得到distinct count)这种方法就超时了。还是推荐及时删除value为0的项,其实比不删还简单,因为删除这个操作只会在收缩时出现(只有此处count–)。

可优化为while-if。

No-repeat Substring (medium) – LeetCode

和前面的题目毫无差别。

但注意第二层while的判断条件是什么,如果判断条件是“窗口dict的value全为1”,那么你可以改出while-if。

如果是“当前字符c的count>1”,就改不了了。因为现在只看当前字符,那就意味着窗口必须是合法的,然后扩展,加入当前字符。while-if便不可用。

“只看当前字符”这种方法的优化思路是,如果start要跳,直接让start去“当前字符上一次出现的位置的右边”。 因为前面的字符都可以跳过了。还可以再化简代码,但会很难读,所以还是适合而止吧。

Longest Substring with Same Letters after Replacement (medium, amazon) – GeeksforGeeks

We have a string s of length n, which consist only UPPERCASE characters and we have a number k (always less than n and greater than 0). We can make at most k changes in our string such that we can get a sub-string of maximum length which have all same characters.

Example 1:

1
2
3
Input: s = "ABAB", k = 2
Output: 4
Explanation: Change 2 'B' into 'A'.

Example:

1
2
3
Input: s = "ABCD", k = 1
Output: 2
Explanation: Change one 'B' into 'A'.

这种要替换字符的题目,往往不用真的替换,只要数值上达到某个条件就行了。比如这个题,不用想着应该替换哪些字符,而应该想“总字符个数 - 不需要被替换的字符个数 >= k”就行了。很容易想到,“不需要被替换的字符个数”就是区间内个数最多的那个字符,这样,总字符数才能多一点(对某个区间而言,不需要理会那些无意义的可能解,“保留频率最高的字符,把其他的替换为该字符”肯定是操作数最少的)。于是,替不替换的问题就化简为简单的统计问题。

统计问题虽然简单,但是复杂度略高。想要快速,可能需要两个map,ch->count, count->ch。所以,while-if就很适合了,由于只收缩一次,max_count就从dict里统计一次就好了,不用强求更快速。

Longest Subarray with Ones after Replacement (medium) – GeeksforGeeks

比上题更简单,只需要一个int变量就能描述一个窗口内的0的个数。

Problem Challenge 1 - Permutation in a String (hard)

排列,不允许多一个字符,所以窗口大小是固定的,滑动用来节省“更新窗口属性的代价”。题目如果对字符多加限制,比如此题限制只有小写字母,也就只有26个可能,其实描述窗口用长26的数组都可以,不用非要用counter。用counter有个麻烦点在于当某个字符的count为0时,你需要删掉它,不然就没法和s1的counter比大小。如果两个字符串的counter都先把26个字母的空间开出来,那还不如数组节省空间。

Problem Challenge 2 - String Anagrams (hard)

和challenge1没有区别

Problem Challenge 3 - Smallest Window containing Substring (hard) *

没啥特别,就是用collections.Counter()减法,比自己写的比较函数要慢不少,1200ms vs 500ms。

Problem Challenge 4 - Words Concatenation (hard)

注意读题!words长度相同!匆忙读题后,我还以为要处理不同的切割方式,以为会出现“一个substring里有几种正确的word排列”。那这题可能不止hard了。

可以简单想到的办法就是窗口从0一直滑到尾,step为1,每一次窗口都得重新计算下word-count,然后和words参数比较。

显然这个没有什么巧妙点,没有节约计算量,所以想要利用滑动窗口,当然得想点骚方法。其实就是,每一次都设置一个起点,从这个起点开始,只会按词长来拓展,这样就能像字符型的题目一样,充分利用滑动窗口的扩展收缩,减少计算。举例说明,就是一个单词长度为len,s串总长为n的话,第一趟是从0开始一个len切一刀,这样切割后的串扩展和收缩都是一个词的,第二趟就是从1开始切,以此类推,最后一次是len-1开始切。可以想到,这样也是把所有可能性都考虑到了。

改进后的滑动窗口方法效果是明显的,1000ms到100ms。

Additional

Sliding Window Maximum (hard) – LeetCode

这个题跟滑动窗口模板毫无关系,窗口大小都固定牢了。唯一的问题点在于用什么结构体来提炼窗口信息,既能很快查到最大值,又能在窗口滑动时很快更新好(滑动本质就是加入一个数,去掉一个数)。快速查到最大值,可以想到利用堆。但是堆有一个明显问题,就是它不适合去删除内部的某个元素(不是堆首)。而“去掉一个数”这个操作很可能就是去删除某个中间的值。堆的删除操作是个不太ok的操作,因为这个堆是简单的堆(并非压平了看,完全有序的,不是堆排序之后的结果),也就是删除操作不能快速定位到要删除的元素。

但是别直接放弃堆(我就放弃了,想别的方法,走远了)。这时候,尝试多推导一下,就会发现,不用着急删除元素。因为元素可以跟上自己的位置idx,如果堆顶拿到的idx已经不在窗口内,再删除也不迟。也就是延迟了删除操作,正好还让删除操作符合堆的操作习惯,只删堆顶。

到这里,起码算是题目做出来了,而且这个方法也不差,能交差。

但这道题更想考的点是别的,所以还需要再优化。说是优化,不如说是换了解法。从堆想到单调队列,反正我是做不到。。。

单调队列是什么东西?先记住它能够动态地维护定长序列中的最值。所以只要定长、最值,就可以想到尝试单调队列。具体来讲,单调队列是,push元素前会把前面的元素都从后往前访问一遍(遇到比自己大的停止),比当前元素小的都删除,再将元素放在队尾。其实,全访问也没关系,最后结果没有差别,不过,遇到比自己大的就停止可以节省点时间。最后的结果就是队列里头到尾是从大到小有序的。

举例说明(为了多点情况,和leetcode原例子有差别):

1
nums = [1,3,-1,-3,-2,3,6,7], k = 3

单调队列应该长什么样?

[1,3,-1]初始窗口入队列后,q=[3,-1],那么这个窗口的最值就是3;

[3,-1,-3], q=[3,-1,-3],最值还是3;

[-1,-3,-2], q=[3,-1,-2],最值3,但3已经不在窗口内,所以pop,q=[-1,-2],最值-1;

[-3,-2,3], q=[3],最值3;

[5,3,6], q=[6],最值6;

[3,6,7], q=[7],最值7。

可以看到,只用进行简单比较,就能维持着最值,比堆的时间复杂度低。

单调队列它为什么做到了呢?

可以这么想,首先简单起见,只考虑窗口内元素的单调队列情况,比如3,1,2序列,k=3,很明显1会在2进入时被扔掉,因为2进入了之后,怎么也是2比1晚出窗口,就算可能是最大值,也是2可能,1是完全没有可能竞争最大值的。

再考虑队列前部还有窗口外元素的情况,窗口外的元素还留在队列里(可以称为过期元素),也就是说窗口内的单调队列最大值(也就是队列列首)比过期元素小。但这并不影响窗口元素那部分的选择,无论有没有过期元素,窗口那部分的单调队列都长一个样。所以过期元素可以简单地pop出来扔掉。

总的来说,单调队列就是剔除了“必然不能争最大值”的那部分无用值。单调队列实现上没有什么难度,不再赘述。

P.S. Python实现遇到超时问题,因为我没有用pop,而是选择到一个点,取出切片[:x],然后又append。具体细节待调查。从耗时来看,很明显这一连串操作应该搞出了deep copy之类的耗时操作。都叫单调队列了,就好好用python collections里的deque。

Shortest Subarray with Sum at Least K (hard) – LeetCode

仔细读题,这个题的数组里有负数。滑动窗口的算法模板是没办法直接套用的,因为窗口收缩的停止条件是sum < k,由于有负数,你不能在窗口sum < k时停止,你必须继续收缩,否则就可能错过解。

停留在滑动窗口算法模板这个框架里,是没办法找到解法的。

这时候只能躺平

只能说先回答个O(n^2)的解法吧,聊胜于无。很明显,所有区间和都是可能的最佳答案,所以前缀和加二级遍历所有区间,能得到答案。

当然可以优化,但是很难凭空想出来参考答案“单调队列”。接下来的说明是以知道“前缀和+单调队列是较好解法”为前提来看这个题目,所以没有什么顺理成章推导,全凭参考答案提示。

单调队列维护什么?

题目核心是求最短的合法子串,所以短是最核心的,和只要>=k什么都行。那么假设当前看i,以i开头的最佳子串,当然是从i开始寻找第一个j,能使sum[i..j]>k(前缀和数组里两个数减一下就好了)。j之后的都不用找了,没有比i到j更短的了。那么反过来思考,从i到j,中间可能有多个值,一一遍历就是暴力解法,优化当然是更快找到j,那么如何迅速定位到j呢?

或者换个说法,i到j中间的多个可能性,有哪些是必然不可能的,可以直接过滤?答案是没得😛。因为如果从[i, n)区间提取出单调递增的部分,可以使用二分,但这个题应该用不着。那这个思路还有什么优势呢?我们一一遍历到j,然后得到这个i的最优解,然后i++,然后你还是得遍历过去,因为单调递增队列本身不能有更多的改动,最多把队列头比i小的pop出来。那换个角度,递增队列是不是能从后往前看,当某个靠后的j满足了条件,你能把它怎么样?你不能动它,因为接下来的i(更大的i)和j一起也能满足条件,这个窗口长度肯定比现在的短,你删了这个j,就丢掉了解。

那么就应该考虑换个顺序,以当前j为标杆,去找前面的i,它有个什么好处呢?当你从前往后找i,某个i满足条件后,你可以大胆删了它,因为j会++,当前的i充分发挥价值(用来更新window len)后,就不需要了,后面的j和这个i组合是无意义的。

P.S. 我想到了以j找i,但又想的是从j-1往0这个方向找,想想看,跟以i找j没什么差别,它们跟暴力解法比,完全不是稳定降低复杂度,甚至可以劣到没区别。(于是Python实现也完美超时了)

总的看“前缀和+单调队列”,大概的最好状态是每次O(1),然后n个j,所以O(n),比如,每次看队列头d[0]的preSum都很大,不能让preSum[j]-preSum[d[0]]>=k,单调递增的d后面的元素也不能满足要求了,所以每次就立马完成。最差的状态可能是某次j,从0到j遍历,每次都符合条件,都要pop并更新window len。但很明显,队列最多跟n一样长,而且pop出去了又不会回来,所以次数最多n次,并不会膨胀。所以总的复杂度还是O(n)的。

这道题还是很难的,难在拼出正确的方法,知道方法后,代码实现不难。

Max Consecutive Ones III

突如其来的一道复习题。while-if即可,虽然和while-while实测没什么区别,大概是case的原因。

Replace the Substring for Balanced String (medium) – LeetCode

题目是说要替换的字符包含在一个子串里,要求子串最短,子串符合某个条件即可,那就很适合套用滑动窗口模板了。

Count Number of Nice Subarrays (medium) – LeetCode

这题一看就不适合立马套用模板,扩展和收缩求最长最短很有效,但这里没有用处。举例说明,当我们找到一个窗口恰好有k个奇数,此时可以滑动窗口么?当然不能。所以放弃吧。然后考虑到奇数是核心,先找到k个奇数的最小可能,它的左右两边如果分别有a个偶数和b个偶数,那么这里就有很多个子串可能,1+a+b+a*b。而找奇数,可以直接抽出奇数,这样奇数数组里每k个就是一个base,延展下两边的偶数。既没有重复也不会漏算。

滑动窗口完结撒花🎉

2. Pattern: Two Pointers

Pair with Target Sum (easy) – LeetCode

这题第一感觉是map或者排序后二分查找,双指针是个什么操作?

双指针自然得用在排序后的数组上,头尾各一个,[left]+[right] == target返回,>target right–,<target left++。确实也比二分好写,如果不能用库函数二分,双指针编码不容易错,也是个很好的选择。

就是答案要求返回索引,排序后的索引怎么查也是个问题。代价还是不小的。

Remove Duplicates (easy) – LeetCode

原地当然是要原地替换了,那么应该被替换的地方需要一个指针,理应替换到前面去的需要一个指针。

比如,00111,第二位的0会被第三位1覆盖,那么第三位理论上是个空缺位,但编码上,不用管一位,因为一视同仁的话,序列等于是01111,第三位是1,也不并妨碍接着删除1。所以可以不用特别处理,代码会写的很简单。

Squaring a Sorted Array (easy) – LeetCode

非递增序列,类似概念还有:非递减,单调递增,单调递减。。。

单调就是相邻两个数不会相等,非xx自然是可能相等的。

用高数教材的定义,当x1<x2时,都有f(x1)<f(x2),f(x)就是递增函数,increasing function。其实“单调”这个词有些干扰。

increasing就是上升,不存在横着走,non-decreasing就是不下降,那自然可能横着走走(也就是,可能相邻几个数相等)。剩下两个同理。

题目本身很简单,结果是从小到大,但是绝对值最小的数不好找,所以反其道而行之,找大的然后放在尾部就行了。

Triplet Sum to Zero (medium) – LeetCode

在此题必然用双指针的提示下,想到了固定1个数,然后变成两数之和问题,用双指针处理这一子问题。

但这个题的输出很多限制,需要排除的东西很多,示例

1
2
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

基本包含所有可能,完成这个test就能AC。

编码上,可以避开很多不必要计算,始终记住,假设当前固定的数是nu ms[i]=a,双指针肯定是i<left<right。不要把left始终设为从0开始,没必要。

Triplet Sum Close to Target (medium) – LeetCode

其实比上一题简单,因为不用担心解重复的问题。注意的是result一开始设置一个极大值以便更新,别写做10^4了,这个python里会解释为14。表示次方使用两个星号。

Triplets with Smaller Sum (medium, google) – LintCode

不是直接套用模板能搞定的了,好好理解下面这个example。

1
2
3
4
5
6
Input:  nums = [-2,0,1,3], target = 2
Output: 2
Explanation:
Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]

应该是能O(n^2)解决的。

稍微暴力点,但容易想到的解法是for i, for j in [i+1, n),这一层,可能有多个k可以是三数之和<target。这里可以考虑二分找,lower bound还是upper bound,不用细想,但可以知道二分方法能做到。但是复杂度就是n^2 * logn,肯定有优化点。忘记二分,如果我们顺序找k,从左或者从右都行,但考虑到“如果这一轮j找到了,j++后k是不需要跳回最右边的,k可以就从当前位置开始”,这个应该很好懂。所以如果k是从右往左找,代码就可以写的很简洁。而且明显降低了复杂性。

再来思考下复杂度是多少,由于固定i后,j和k又是最多只会遍历[i+1,n)的部分,所以总的是O(n^2)。

Subarrays with Product Less than a Target (medium) *

要求输出所有subarrays,也有要求输出subarrays个数。输出要求都不太难。

套用双指针或者说是滑动窗口模板时,需要考虑到乘积的写法。尤其是当某一个数本身就>=k时,窗口应该收缩成0。这个用双while写起来就很怪,所以我是在最开头就判断下,如果是就重新设置那一堆变量,进入下一次循环。官方代码使用for-while把这一情况包含了,不用单独判断。这里可以再思考下,官方的是不是正确,当nums内有数字1或者k==1时又会不会有奇怪的问题出现?

for-while的写法,就是可能会出现while结束后,start == end + 1,此时product == 1,因为没有取到任何一个数。接着会马上进入下一次外层for,end++后就会是start == end,即想选择[end]这一个数作为subarrary,然后接着while判断。这一整段没毛病。

至于nums内有数字1,完全不影响计算。而k==1,也不会有问题,走一遍逻辑就知道了,k==1时无论数组长什么样,结果都是0个,不存在<1的正整数,更不会有乘积<1了。

官方还有二分查找法,乘积[0, i]是非递减的,确实有道理。而且由于乘积可能很大,还用对数,很强势,看一看。

  • 取对数后很难是正整数,那么必然有精度损失,不影响正确性?

Problem Challenge 1 - Quadruple Sum to Target (medium) *

四数之和,数组是整数但可零可负。

在已知此题可用双指针的情况下,自然去思考如何利用双指针,但双指针只能用于两数和问题(指定这两个数和为某定值,找出两数的所有可能解),那四数还有两个数怎么办,最简单的想法就是把这两个数所有可能列出来。于是平方复杂度列举出所有a和b的可能,对每一对ab,用线性复杂度的双指针找出c和d的所有可能解。大约就是三次方的复杂度了(可能真实复杂度可以算的更精确点,但反正小于等于三次方复杂度,暂不纠结这个问题,简单看待)。

想到这里,三次方的复杂度让我有点虚。不过,转头想这个题如果是暴力解法就是四次方,如果是定三个数再利用有序二分找第四个数,就是n^3*logn,n^3的复杂度好像瞬间就容易接受了。

题目有个麻烦点是不能有重复的四元组,如果不通过某种方式设置set(对四元组去重)的话,就需要跳过那些重复的组合。也能写出来,就是代码有点丑,也需要case来调试。不能一气呵成。

这个比较顺畅的思路是:

  1. 首先思考第一个和第二个数,简写为a和b,它们都是for循环,比较类似。

    假设a固定,看b的移动。b如果右移还是同样的值,“右移之后的解集”只会小于等于“右移前”的(cd因为b的右移,可能性变少了),可以想到,解集不会增加任何可能性,反而只可能减少,b的取值却又是一模一样,那么右移后的abcd组合,在右移前遍历中都考虑完了,自然完全没必要重复遍历,所以b要一直跳到和前一个值不一样的地方,才需要进行遍历求解。

    而a的情况也一样,a的右移只可能使得bcd组合减少,没有新花样,a右移前后的解,值都一样,右移后的完全可以被跳过。所以a也是要跳到和前一个值不一样的地方。

  2. 再思考cd两个值,如何过滤重复的解。

    c+d不等于想要的值时,方向很明确,只会left或者right某一个移动。如果c移动到下一个值还是不变,那还是c+d不等于期望值。所以不等于的情况不用过滤。而c+d==期望值时,如果只有left右移,那么肯定要跳过重复的值。但如果是right那边重复,只left跳过重复值,能否解决问题?答案是可以。举例说明,当left这边序列是11111xxx时,1+d==期望值,那么left一直移动到最后一个1,下一个数就不是1的时候,abcd这个组合可以成为一个合法解,然后left++,那么下一次while时就是大于1的数+没有动的d,那肯定是大于期望值,right那边就会左移,遇到重复的right还是左移,并不需要考虑过滤。

    当然,只做right的重复过滤也可以。没必要做两边的。当然两边都跳过也行,但少写代码少错😄。

再思考下几数和问题,两数和就是双指针,线性复杂度,三数和就是指定一个数再解决两数和,平方复杂度,四数和三次方复杂度。

Problem Challenge 2 - Comparing Strings containing Backspaces (medium)

顺序找规律怎么也找不到时,一定要记得反向试试。数组题一定要记得反向可能有奇效!!!

此题没有什么巧妙写法,写出来的代码有点长,不过容易调试成功。

Problem Challenge 3 - Minimum Window Sort (medium) *

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Given an array, find the length of the smallest subarray in it which when sorted will sort the whole array.

Example 1:

Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted

Example 2:

Input: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted

Example 3:

Input: [1, 2, 3]
Output: 0
Explanation: The array is already sorted

Example 4:

Input: [3, 2, 1]
Output: 3
Explanation: The whole array needs to be sorted.

这个题没找到OJ地址。思考的时候想到了拐点,不过后续思考没跟上。

首先,找到了subarray之后,这个subarray一旦能排好序,整个array就有序了。那么,非subarray的值就应该是它们应该在的位置。

Example1中1和2在应该在的位置,就很容易想到指针找到第一个比右边还大的值(也就是拐点),也就是5。但Example2直接打脸,1本就不在该在的位置。

到这儿就没继续沿着这个思路继续下去了。然后就没找到思路了。。。

找到左右两边的拐点后,拐点之间的这个区间必然不是都在正确位置上,所以这个区间肯定在subarray里面。但Example2也提示了,找到了拐点区间[3,2,0,-1],可以看到前面的1也是错的,为什么呢?因为1排序后也不应该站在它现在的位置,也就是说subarray应该还需要扩张。

扩张的依据是什么?这个元素是否在当前区间的最大最小值之间。因为如果在之间,全局排序后,这个元素和当前区间的位置都是要变的。画一下折线图,纵坐标表示值的大小,横坐标是元素位置,就可以很直观的看到,区间的扩张是简单的,因为它只需要往外1个1个check就行了,没有什么复杂规则。

  • code

3. Pattern: Fast & Slow pointers

LinkedList Cycle (easy)

题目描述很反人类,但其实就是给你一个链表(只有head指针),让你判断是否有环。进阶是只使用O(1)的空间,也就是常量空间。

有环的链表肯定会访问到重复的节点,环内有1个或以上的节点。搞一个空间存已经访问过的节点,查到之前访问过就能判断了,但空间最坏能到O(n)。常量空间,自然要用快慢指针。

推理一下,快慢指针什么时候能证明链表有环?

猜想肯定是快慢指针指向同一个节点时,但怀疑是否存在“有环链表下快慢指针也不会同时指向同一个节点”。画画图,列一下方程式,假设链表入环前有s个节点,环上有c个节点,可以知道,当走整数倍c(2倍起,同时还得>s)的时候快慢指针是能遇到的,这个值不会不存在,还会多次相遇。所以不用担心快慢节点会永远遇不到。

编码上很简单了,记住init时fast,slow都指向head,然后while内先走再check。

Middle of the LinkedList (easy)

很简单的题,把两个case都手动推理一遍,就知道了。hint:fast先走,提前退出,slow就不用走了。

Start of LinkedList Cycle (medium)

这个题猜得到是需要快慢指针相遇后再加点什么操作的,但是推理容易卡壳。主要还是对快慢指针相遇的情况理解的不够。

快慢指针相遇很好写,node地址相等就是了。但相遇时,快慢指针并不是可能走了无数圈。这里有一个点必须记住,就是“慢指针入环后,和快指针相遇时,慢指针在环上是不会走超过一圈的”。也就是慢指针入环后继续走,一圈以内必定碰到快指针。

这个知识点,我以前应该用方程式推过,也不记得推理有没有漏洞了,这次做题还没推出来。所以这里最直观也正确的解法是数学归纳法。我们讲slow入环后和fast相遇,那么最快相的情况,当然是slow和fast直接在入环点直接相遇,0步。再麻烦点,就是fast在slow的前面(此刻的位置是fast.next==slow),这样两个相邻的节点,只需1步就能相遇。假设fast更远一点,即fast.next.next==slow,就需要2步,以此类推,入环时刻,fast和slow的距离(fast的n个next==slow)假设为n,就需要n步相遇。但fast和slow之间最大距离就是fast在slow的前一个,假设环里有k个节点,fast和slow的最大距离就是k-1,所以最多k-1步,fast和slow必定相遇。所以slow不可能在相遇前走几圈。

知道slow在一圈内就会和fast相遇,其中几个关键长度如下图所示。那么相遇时slow的公式应该写为,slow=a+b,fast=a+b+n(b+c)。

示意图

(leetcode图源,可能会挂,自行戳网址)

再回到题目本身,当两指针在紫色点上相遇时,代入化简一下已有式子,得a+b=n(b+c),即a=c+(n-1)(b+c),为什么化简成这样?不是因为这样a可以通过等式右边得到,右边这式子也没法继续求。而是因为,右边写成这样,b+c是一整圈,也就是说,如果一个指针从链表头开始走起,另一个指针从紫色点走了c长度又走了几个完整圈,它们会在入环口相遇,另一个指针走几圈完全不用在意。

但注意,这个式子可能有坑,思考下有没有可能a很小,c很大?

n必然>=1,因为fast肯定走的多点,不然fast=a+b+n(b+c)就不对了。那么,a最小就等于c,不可能比c小。这个事情挺有趣的。没有想到一个很通俗易懂的表达,但数学证明了也就证明了吧。

Happy Number (medium)

这题现在是简单😂

题目没有读仔细,所以第一时间没能察觉到和快慢指针有什么联系。题目表述为“也可能是 无限循环 但始终变不到 1”,我简单地想到了不能一直计算,但忘记了无限循环不是每一次结果都不一样,它只是每次结果都是不是1,不是说每次结果都是从未出现的数字。

接着,就排除了用定义一直计算这种思路,变成了想利用数学之类的其他方法来解决。虽然也推理出了平方和计算中,不能爆出非常大的值,最大32bit的数,十进制也就是13位,就算13位都是9,一次平方和计算下来,也不过1053。而1053的平方和也挺小的,1053以内能算出较大平方和的也就是999。而999再算一步也就是243。

可以明显感觉到,不可能出现一个小的数字经过多次计算膨胀的很大,只可能很大的初始数一下子变得很小。当然像case1中19经过计算会变大,但这都是一定范围,最大不可能超过1053。

然而,从这里开始,我就期待用动态规划一类的方式,类似斐波那契数列,提前算好所有快乐数。所以我认为,可以从1,10,100,1000反推平方和等于它们的数,但是反推的链路有点长,说不定反推也会不能停止,毕竟这个思路不太对劲,可能有不少漏洞。

总结还是应该利用平方和结果范围有限这一点,也就是抽象成链表的有环判定。当然,因为平方和都是即时算的,不像链表问题提前准备好链表。简单的方案就是直接保存之前计算出的结果,也就是不用快慢指针,而是用是否已存在来判断。而如果还是想用快慢指针,可以def一个next函数,考虑到节约空间,next函数只管计算不用缓存。快指针两次next,慢指针一次next就好了。

纯数学的角度其实也可以继续推下去。但需要更仔细的范围研究。所以,回顾之前的推理,最大的数字13个9,也会瞬间收缩到1053,再归纳总结,12个9收缩到。。。4个9收缩到324,这里特别的来了,999到243。为什么说999到243特别,因为这里位数不降了,之前的那些大数都会收缩位数,变得更小,999虽然会经过一次计算变小,但位数不会收。所以一旦计算结果收缩到3位数,接下来的所有平方和结果都是三位数以内,不可能膨胀,且跌入三位数后(三位数后再计算一次),必然困在243以下。而为什么就243了,有没有可能实际数字更小?简单举例99就知道,它能变大到162,也就是涨到三位数,但不可能从三位数继续变大。所以,计算进入243以内后,可能会振荡,比如2位数蹦到3位数,但不可能比243更大,也就是出不去了。

那么,假设计算结果小于等于243时,我们能直接给出结论,是不是快乐数。就不用进入无限的循环了。所以问题变成243以内的数字,哪些是快乐数?

而这样的问题缩减,有什么好处呢?好处在于,243个数字,最大值也就是243,大可以暴力算加是否已存在判定,最大空间复杂度也就到243,比起给一个数就缓存,空间占用要小一些。(其实应该也小不了多少,毕竟收缩很快)但把<=243的数字直接打成表,对于频繁查快乐数的情况,就会节约时间的多。oj时间上节省的会比较明显。如果只是一次快乐数判定,当然打表反而还浪费时间。

Problem Challenge 1 - Palindrome LinkedList (medium)

难度简单。

很明显快慢指针能够找到链表的中部。而中部开始向左向右比对,就能判定是否回文。右半边很顺畅,不用改动,关键在于左半部分。但左半部分再快慢指针途中是被遍历访问过的。这其实也就提示了,如果修改链表,就能降低空间复杂度。题目进阶就是希望用O(1)空间,那大概率就是原地修改链表的左半部分。

很直接的就能想到是反向指。写写画画,不难得到简单的代码。得到了链表中部的指针后,当然是往两边走,逐个对比。但注意,奇数回文串和偶数回文串比较的起点是不一样的。我粗心的只想到了偶数回文,跑测试才发现奇数回文跑不过。

P.S.

这个题还有个递归解法,我不太擅长递归,经常起手就是迭代,所以这里值得再学习下。首先,递归能给我们什么?假设我们只是简单的print val,那么递归就能从尾到头,逆序读出每个节点的值。假设我们递归到底了,现在能读到尾部节点,这个时候我们应该拿头部节点和它进行比较,接着递归会读倒数第二个,而这时又应该拿顺数第二个节点比较。可以看到,从头部开始读也可以用一个指针来解决,但这个指针得是外部的变量,放在递归函数里面太困难了。再思考奇偶情况,奇数节点两指针地址会指向同一个节点,容易判断,偶数情况本来以为会麻烦点,但还好,因为两个指针指向的节点是相邻的,所以只要next判断一下就好了。leetcode官方解更飘逸,全遍历,不用提前返回,那对栈空间要求更高了。不大实用,但可以多熟悉下递归。论简单,还是递归这个写法代码少。

  • Problem Challenge 2 - Rearrange a LinkedList (medium)
  • Problem Challenge 3 - Cycle in a Circular Array (hard) *

leetcode-roadmap

推荐站点:

https://qoogle.top/how-to-brush-leetcode/

https://codetop.cc/

https://codetop.cc/ 微软

227. 基本计算器 II 2012/03/22-23

这道题,用栈是最快速的,可以现场推理思路,完成80%应该不是问题。
但这种表达式,很可能会被考变种,比如加了括号,加了UnaryOp,甚至更难。
括号,UnaryOp或是自定义函数,这几类还是可以通过少量修改代码支持。但要能做到像高级计算器一样的,抵抗各种灵活拷问,我目前知道的万能方法就是,编译器的基本思路,也就是词法-解析-翻译,这种流程。毕竟我们使用的编译器就是这个思路,没有比这个更完善的了。

当然,编译器思路不好写。总结来说,基本思路需要Lexer,Interpreter。如果Token过于复杂,最好加个Parser,Parser解析出AST,Interpreter再遍历AST树,计算结果。

面试时使用这个思路,写代码会慢一点,但是比栈思路,更深更硬核。

双栈思路

一个栈存操作符Op,一个栈存数字Int。双栈思路的核心就是“先算乘除”,所以扫描处理完整个表达式后,Op栈里应该只有加减号,没有乘除号。

但还有一个点要考虑,就是Op里已有+号,此时你扫描到了新的+号,要怎么做?

如果将栈中的+号及时处理了(也就是同优先级优先计算前面的符号),那么整个表达式算完,就只有一个加号或减号,没什么问题。

如果选择了加减号不先算,直接放栈里,就需要注意,之后的计算顺序。举例说明,一个复杂的表达式化简成只剩加减号时,可能是1-2-3,这时候Op栈是“-,-”,Int栈是“1,2,3”,不能再使用栈的pop,那样就变成了1-(2-3),得用list/vector的顺序计算。
(我临时推理时用了这个思路,大概率以后还会这么干😅。我习惯思维是只push进栈,不爱随时pop,最后会统一pop出来计算。大概是觉得这种流程,代码会比较好看。)

还是推荐大家尽量改善自己的思路,选择第一种方式,以免现场推理出来的逻辑不够完备。

单栈

Leetcode官方题解其实是单栈,但如果你亲手写了双栈,你一定会感受到,如果及时计算同优先级的运算符,Op栈最多只会有一个运算符(+/-号),所以不需要栈,一个变量就能保存了。这就是单栈思路,没什么特别。

边界

栈的大体思路都是如此,如果加入括号或是其他二元运算符,都还能work。加入括号的话,请一定要用第一种方式😂,处理起来方便很多,不然思路容易卡住。

如果加入UnaryOp正负号,尤其是负号,也就是说leetcode 227题的表达式中的整数不保证是非负整数,又需要一次变化。巧妙的思路是给“-”打头的表达式开头添“0”,变成“0-正整数”。将所有”(-“替换为”(0-“,用字符串replace,还可以不用改变算法主体代码,很简单。
而如果还加正号,比如“3++4”合理,这种情况就比有负数的情况还要麻烦了。这要求你的算法能,判断第二个+号是和整数结合的正号(Unary Plus)。再扩展下,“3–++2”等等。代码上就得增加一段逻辑,来处理好UnaryOp。这样当然可以work,但是这也暴露了栈思路的一个问题,就是它没有符合逻辑的解析能力。它似乎只是我们在努力的修补规则,“3–++2”是读取了“3-”后发现还是符号,才会开始解释为一元符号,从左到右计算到底是正号还是负号。但按照逻辑,我们应该是将表达式看作3-(-(+(+(2)))),也就是,真的计算的时刻,2是和前面的正负号结合,然后作为整体又跟前面的正负号结合。也就是解析是顺序,计算是倒序,有种递归下降,然后逐层返回结果的感觉。

其实没什么差别,但是我个人觉得,栈的思路是有些勉强的。因此,当学了一点点编译原理后,我就想用编译的思路来解决这道题了。

TODO

所有计算器题目,都总结下。

  1. 双栈,加减括号,注意允许(+4)这种写法出现,但不用考虑1++2。

  2. 双栈,加减乘除,无括号,不用考虑(+4)或一元运算符的情况。

  3. 基本计算器 IV,只可能使用编译器思路来解决了,而且还要能处理变量。

编译器思路

编译器思路,自然是难的,写起来也不够快。但是学习编译器基本原理,我觉得是有意义的,因为底层到程序编译,稍高层的SQL解析,都是这套思路。Parser,Token,blabla。

简单来说,就是用代码实现几行范式。加入新的符号,就修改范式。

比如,只有加减乘除:

加入括号(LPAREN,RPAREN):

再加入一元运算符(正负号):

Parser/Interpreter实现这几条规则就可以了。

91. 解码方法 2021/03/24-25

需要注意dp访问越界的问题。
通常dp[i]负责看第i个元素(索引其实是i-1),就可以保护住需要访问dp[i-1]的dp公式,因为计算dp数组是i从1开始,dp[0]不会越界。
如果dp公式有dp[i-2],不要慌,dp[1]特殊处理后,dp[2]开始又可以通用处理了。

124. 二叉树中的最大路径和 2021/03/26

  • wait zx

224. Basic Calculator 2021/03/31-04/03

s consists of digits, ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘.

227类型的题。这个版本由于没有乘除,用Lexer+Interpreter的版本,范式也不难写。

  • TODO 写一下范式

当然更简单的,还是可以使用双栈。

而且建议只记忆双栈,不用去记一些扩展性不够高的思路

注意,test case有”1-(+1+1)”这种。虽然不用考虑1+-1这种写法,但’(‘号后跟’+/-‘号是要被考虑的。
因此是基本的双栈思路,加过滤空格,再加处理’(+/-‘。

具体说下双栈思路。

首先,框架是逐个字符扫描,但考虑到数字可能是多位,所以最方便的做法应该是while i < len(s):,解析数字时i可能会多加点,其他符号只需+1。

再是每个字符c可能是些什么,各自需要如何处理。如果没什么印象,建议逐个分析,有需要的再合并,想不清楚,直接逐个if-else都行,总比写错了强。
所以,逐个看待,伪代码写作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if c is space:
pass
elif c is digit:
# func parse_int TODO
num = parse_int()
# TODO calc or push to nums?
elif c is '(':
# TODO handle '(+/-'
push to ops queue
elif c is ')':
# ops top is '('
ops pop
num = nums.pop()
# TODO calc or push to nums?
elif c is '+' or '-':
push to nums queue

上面就是最详细的分支情况,由于没有乘除,所以分支数量也没什么可以优化的点。注意我写的TODO,基本都应该封装为一个函数,以免主逻辑太难读,给自己增加难度。

特别的,calc or push to nums是最需要注意的一个地方,明显的,两个分支都用到这一逻辑,封成函数是最好的,我命名为calc_with()

而这个数什么时候用来计算,什么时候直接push进栈呢?

举例分析,我想把nums栈顶top和现有的num拿来计算,那么ops栈顶当然得是+/-号,如果栈顶是’(‘,那自然不该算。只需要考虑这一个条件。

如果不计算,直接push。如果pop栈顶计算了一次,之后的结果,该如何处理?

很容易想到,这个结果,还是应该push进栈。但还是应该多思考一下,有没有什么坑?

这一点可能有点不直观,但你可以手写推理或者debug代码测试,就会知道,calc_with()总是在尽力地合并,只有遇到’(‘才会无法合并,导致nums和ops栈多增一个元素。

简单起见,假设只有+号没有-号,某个时刻的栈只能是+(+((+,不会有++(++(++

假设此时ops栈为+(+((+,现有num,ops栈pop出+号,再nums栈里pop一个数num1,计算出结果res,这个res push回nums栈是合理的。无论后面跟什么符号,都能正确处理。

770. 基本计算器 IV

这个题太长了,看的人头皮发麻。但是抽象一下,就能发现,它实际上难点在于括号展开。因为我们已有的知识已经能把一个有括号的表达式解析出来了,可以转成AST树,也可以在解析parse时及时计算。但是,没有包含过“括号展开”的逻辑。

简单的想一下,AST树完全不知道该怎么去实现括号的展开,所以pass。

所以就考虑下parse时及时计算的时候能不能加上“括号展开”。

parse时,可以知道pre_calc * new term的,具体2 * (a-b),new term为(a-b),之前的计算结果为2(简单起见,用数字举例)。

接下来,该怎么做?

应该做到拆出2 * a-2 * b。这一步即括号展开,是此题的核心。题目也暗示了可以理解为2 * a与-2 * b两项,那么也就是2要跟(1 * a)和(-1 * b)都分别乘一下。代码上其实就是for循环。当然(a-b)这个factor得拆成一个数组(2个元素,a和-b)。还需要拆成系数和word,那系数和word怎么对上号呢?

考虑到2 * a + 1 * a能合并为3 * a,主要功劳是在word上,所以以word为key,系数为value是很合适的。

所以可以用dict,{a: 1, b: -1}这样来表示。

再进一步完善,如果是(c * d - 2 * f) * (a - b),那pre_calc,即(c * d - 2 * f),也得用dict来表示。其实pre_calc没有什么特别,就是一个factor,无论是一个数,还是圆括号扩起来的长表达式。所以用一样的规则,{c*d: 1, f: -2},很通用,也合理。

整理思路

  • TODO 写出范式

也就是说,每个factor(不可再拆分的元素)都可以用一组kv来表示,也就是一个dict。一个term是多个dict合并,最终可以得到1个dict(遍历所有dict,体现加法,因为负号作为系数去了,所以可以当作只有加法)。

term和term之间的乘法,也就是dict和dict组合出一个新的dict(二维for循环,体现乘法)。从左到右一个一个组合,最后得到一个dict,即为最后结果。

剑指 Offer 40. 最小的k个数

TopK,面试时也遇到过,我认为heap K最稳定,但面试官更希望我用快排思想,虽然快排思想有一定几率会很慢,因为最坏O(n^2)。

就是想考考快排。

  • 整理下

快排容易想的方法是3个while,一个while外循环,加每次左标移动和右标移动的while。但这个翻译成代码很容易出错,你没法跑单测就很难补好洞。虽然面试的自己可能都写不出来,但他复制你的代码去跑,那就还是你gg。

所以快排建议记忆单循环的写法,该写法也不用死记,需要记住几个点

  1. 单次快排,又每个元素都得参与比较,所以for循环肯定是[l, r-1] 或者[l+1, r]的
  2. pivot选最右的那一个,这样可以直接利用range左闭右开的性质。
  3. 遍历用i,那么还得有个标号j来表示[l, j]区间都是<=pivot的,初始可以j = i - 1,每次都先++再交换。强调,[l, j]闭区间都是<=pivot的。
  4. 什么时候交换?[i]<=pivot时,应该挪到前面去,那么[l, j]区间应该扩充,所以是j先++再交换,j加加后的值可能是已经被访问过的>pivot的,也可能是i自身,但ok,因为自己跟自己交换也不会错。极端情况就是pivot就是最大的值,一路访问过来,到r-1的位置都不会实际交换。
  5. 最后结果是i访问完了,没有什么指示性。j则肯定代表点什么。j位置必然是小于等于pivot的,那j本身肯定不能跟pivot交换,不能把小于等于pivot的换到尾部吧。所以应该是j+1。
  6. 为什么判断式子是当前值小于等于pivot,小于不行么?好像也没有什么不行,就是pivot最后的位置不一样。但快排是三切分,会分为前段,pivot自己,后段。pivot值只要有重复,递归的子段都有pivot一样的值,判断式子解决不了这个问题。 https://segmentfault.com/a/1190000004410119 这个题解还正好是小于判断,而不是小于等于。

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/

其实三while也可以,陈斌的写法没有这个题解的写法简单。再看看。

Partial sort就是先构建k大小的堆,然后把剩下的都和堆顶比。

JAVA String Charset

JAVA String Charset

JAVA的String使用上一般不会考虑到编码字符集的问题,即encode charset。但如果出现数据交互,就需要考虑了,因为不同环境就可能存在差别。如果编码对不上,可能会出现乱码。JAVA中我经常见到的是?乱码(多个问号),不排除其他可能。

An Example

host A用utf-8编码String,以byte[]形式发送到host B,如果host B只简单的用

1
new String(receivedBytes)

来转成String使用,这里使用的charset就是default charset。

The Java platform depends heavily on a property called the default charset. The Java Virtual Machine (JVM) determines the default charset during start-up.

可以用下面的方法测试出当前平台的default charset。

1
Charset.defaultCharset().displayName();

我个人的jvm default charset是US-ASCII,所以不设置String的charset就出现乱码。

解决方法

  1. new String时指定charset
  2. 修改JVM的default charset,方法自行搜索

Further

即使String的编码正确了,也不代表console output或output file就不会乱码。涉及了多个模块,可能需要更多的配置,请随机应变。

Hexo

Hexo

Hexo的创建使用不多赘述。

With github

Hexo通过hexo d来发布到github,因此github中deploy到的分支是网站目录。也就是deploy后在本地可以看到的.deloy_git
我个人使用了另一个branch来保存hexo项目的原始文件,也就是_config.yml配置,md文档等等。

Q&A

名字解释:
<root>: 指的网页根目录,或者说是hexo deploy到的repo分支根目录。

Q: 遇到网站repo中路径是存在的,比如<root>/categories/index.html确实存在,但是浏览器点击却是404?
A: 可以自行访问尝试下<root>/categories/或者全路径,看看index.html是不是有问题。如果这样就能访问到正常页面,那么问题大概就是缓存了。你可以换个浏览器快速检查下,或清除该页面缓存重试下。

附赠-chrome清除单个页面缓存

chrome的开发者工具-settingNetwork-Disable cache(while DevTools is open),此选项打开后,在你想要调试的页面,打开开发者工具,就不会出现一些奇怪的缓存现象了。

Hexo cmds

1
2
3
4
5
6
7
npm install -g hexo-cli
cd <blog-source>
npm install

hexo new draft <draft_name>
# writing, writing, ...
hexo publish <draft_name>
1
hexo clean && hexo d

If you want to delete a post, delete it in the source folder.

  • Copyrights © 2021 Huang Wei
  • Visitors: | Views:

请我喝杯82年的咖啡吧

支付宝
微信