先过一下Hard模式的题目吧。

 

	#	Title	Editorial	Acceptance	Difficulty	Frequency
。	65			12.6%	Hard
。	126			13.6%	Hard
。	149			15.6%	Hard
。	146			16.0%	Hard
。	68			18.1%	Hard
。	460			19.0%	Hard
。	44			19.0%	Hard
。	308			19.8%	Hard
。	4			20.8%	Hard
。	420			21.0%	Hard
。	273			21.1%	Hard
。	30			21.7%	Hard
。	440			22.1%	Hard
。	140			22.2%	Hard
。	212			22.2%	Hard
。	269			22.3%	Hard
。	174			22.9%	Hard
。	214			23.0%	Hard
	446			23.0%	Hard
	32			23.1%	Hard
	295			23.3%	Hard
	132			23.4%	Hard
	10			23.6%	Hard
	76			23.8%	Hard
	188			23.8%	Hard
	321			23.9%	Hard
	135			23.9%	Hard
	335			23.9%	Hard
	97			23.9%	Hard
	391			24.2%	Hard
	158			24.4%	Hard
	466			24.6%	Hard
	336			24.7%	Hard
	41			24.9%	Hard
	124			25.0%	Hard
	224			25.5%	Hard
	218			25.5%	Hard
	84			25.6%	Hard
	23			25.9%	Hard
	45			26.0%	Hard
	85			26.1%	Hard
	57			26.3%	Hard
	138			26.6%	Hard
	233			27.3%	Hard
	381			28.0%	Hard
	37			28.1%	Hard
	432			28.2%	Hard
	87			28.3%	Hard
	123			28.3%	Hard
	56			28.4%	Hard
	282			28.5%	Hard
	316			28.6%	Hard
	164			28.6%	Hard
	99			28.7%	Hard
	327			28.9%	Hard
	51			29.0%	Hard
	25			29.7%	Hard
	472			30.1%	Hard
	465			30.1%	Hard
	248			30.5%	Hard
	72			30.6%	Hard
	115			30.6%	Hard
	403			30.9%	Hard
	411			31.1%	Hard
	239			31.4%	Hard
	330			31.5%	Hard
	297			31.6%	Hard
	354			31.8%	Hard
	358			31.8%	Hard
	33			31.9%	Hard
	363			32.1%	Hard
	410			32.2%	Hard
	480			33.1%	Hard
	317			33.3%	Hard
	117			33.5%	Hard
	315			33.5%	Hard
	301			34.5%	Hard
	42			35.3%	Hard
	128			35.3%	Hard
	329			35.4%	Hard
	407			35.6%	Hard
	154			36.2%	Hard
	265			37.1%	Hard
	272			37.6%	Hard
	291			37.7%	Hard
	305			38.1%	Hard
	380			38.4%	Hard
	145			38.4%	Hard
	340			38.6%	Hard
	352			38.9%	Hard
	159			39.7%	Hard
	312			41.6%	Hard
	287			41.8%	Hard
	425			41.9%	Hard
	52			42.8%	Hard
	302			44.0%	Hard
	471			44.2%	Hard
	296			50.4%	Hard

 

 

65

12.6%

Hard

好像很繁琐。

 

126

13.6%

Hard

方法是很好的。不是采用查找备选集的方式，而是采用逐个字符替换(可以加Hash来查找)，这样复杂度从很高，降低到O(26*n), n是字典长度。

 

149

15.6%

Hard

解法很好。通过角度来判断是否一条直线。我看了解法之后，觉得可以再优化一下，比如记下后续点已经处理过的角度。

 

146

16.0%

Hard

我觉得用一个Hash, 加一个双向链表比较好。Hash里面记录链表实际节点，然后每次访问，这个节点移到双向链表的头部，成为新的head。每次满了删除，就删除尾部的。

里面还用了stl的list实现里面的一种很快的方式（当然了，自己来移动节点，也行）：

// 貌似用这个splice比较快

dl.splice(dl.begin(), dl, mitr->second);

 

68

18.1%

Hard

这道题目主要的难点就是gap的处理，尤其是gap不一致的情况。用的是下面的方法：

if (i < extra) {

line.push_back(' ');

}

也就是说，对于前面"extra"个数的间隔，都加上一个。

 

460

19.0%

Hard

很好，非常好！用了一个抽象数据结构Node，来记录同一访问频次层级的key，然后用了LinkedHashSet来记录这些key，进一步保证了先来后到（先达到的，会先删除）。好好领悟，很好！

还用了两个HashMap，分别记录真实的结果，以及一个key对应的Node（如上所述，这个Node里面包含了很多key，用LinkedHashSet来组织的）

 

 

44

19.0%

Hard

下面这个真是写的非常非常好：

C++版本的：

bool isMatch(const char *s, const char *p) {        const char* star=NULL;        const char* ss=s;        while (*s){            //advancing both pointers when (both characters match) or ('?' found in pattern)            //note that *p will not advance beyond its length             if ((*p=='?')||(*p==*s)){s++;p++;continue;}             // * found in pattern, track index of *, only advancing pattern pointer             if (*p=='*'){star=p++; ss=s;continue;}             //current characters didn't match, last pattern pointer was *, current pattern pointer is not *            //only advancing pattern pointer            if (star){ p = star+1; s=++ss;continue;}            //current pattern pointer is not star, last patter pointer was not *           //characters do not match            return false;        }       //check for remaining characters in pattern        while (*p=='*'){p++;}        return !*p;      }

Java版本的：

boolean comparison(String str, String pattern) {        int s = 0, p = 0, match = 0, starIdx = -1;                    while (s < str.length()){            // advancing both pointers            if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){                s++;                p++;            }            // * found, only advancing pattern pointer            else if (p < pattern.length() && pattern.charAt(p) == '*'){                starIdx = p;                match = s;                p++;            }           // last pattern pointer was *, advancing string pointer            else if (starIdx != -1){                p = starIdx + 1;                match++;                s = match;            }           //current pattern pointer is not star, last patter pointer was not *          //characters do not match            else return false;        }                //check for remaining characters in pattern        while (p < pattern.length() && pattern.charAt(p) == '*')            p++;                return p == pattern.length();}

 

4

20.8%

Hard

下面这个解法真的是太棒了！讲解也讲的很好。基本就是分成两部分，使得右边的始终>=左边的，然后求出左边的max 与 右边的min，然后取中，就可以啦！

真的是太好了！

def median(A, B):    m, n = len(A), len(B)    if m > n:        A, B, m, n = B, A, n, m    if n == 0:        raise ValueError    imin, imax, half_len = 0, m, (m + n + 1) / 2    while imin <= imax:        i = (imin + imax) / 2        j = half_len - i        if i < m and B[j-1] > A[i]:            # i is too small, must increase it            imin = i + 1        elif i > 0 and A[i-1] > B[j]:            # i is too big, must decrease it            imax = i - 1        else:            # i is perfect            if i == 0: max_of_left = B[j-1]            elif j == 0: max_of_left = A[i-1]            else: max_of_left = max(A[i-1], B[j-1])            if (m + n) % 2 == 1:                return max_of_left            if i == m: min_of_right = B[j]            elif j == n: min_of_right = A[i]            else: min_of_right = min(A[i], B[j])            return (max_of_left + min_of_right) / 2.0

 

420

21.0%

Hard

 太繁琐，意义不大。

 

273

21.1%

Hard

下面这个代码写的非常的赞。逻辑很清晰。递归和函数都组织的很好。

private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};public String numberToWords(int num) {    if (num == 0) return "Zero";    int i = 0;    String words = "";        while (num > 0) {        if (num % 1000 != 0)            words = helper(num % 1000) +THOUSANDS[i] + " " + words;        num /= 1000;        i++;    }        return words.trim();}private String helper(int num) {    if (num == 0)        return "";    else if (num < 20)        return LESS_THAN_20[num] + " ";    else if (num < 100)        return TENS[num / 10] + " " + helper(num % 10);    else        return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);}

 

 

30

21.7%

Hard

下面代码写的很好。

// travel all the words combinations to maintain a window    // there are wl(word len) times travel    // each time, n/wl words, mostly 2 times travel for each word    // one left side of the window, the other right side of the window    // so, time complexity O(wl * 2 * N/wl) = O(2N)    vector
      
        findSubstring(string S, vector
       
         &L) {        vector
        
          ans;        int n = S.size(), cnt = L.size();        if (n <= 0 || cnt <= 0) return ans;                // init word occurence        unordered_map
         
           dict;        for (int i = 0; i < cnt; ++i) dict[L[i]]++;                // travel all sub string combinations        int wl = L[0].size();        for (int i = 0; i < wl; ++i) {            int left = i, count = 0;            unordered_map
          
            tdict;            for (int j = i; j <= n - wl; j += wl) {                string str = S.substr(j, wl);                // a valid word, accumulate results                if (dict.count(str)) {                    tdict[str]++;                    if (tdict[str] <= dict[str])                         count++;                    else {                        // a more word, advance the window left side possiablly                        while (tdict[str] > dict[str]) {                            string str1 = S.substr(left, wl);                            tdict[str1]--;                            if (tdict[str1] < dict[str1]) count--;                            left += wl;                        }                    }                    // come to a result                    if (count == cnt) {                        ans.push_back(left);                        // advance one word                        tdict[S.substr(left, wl)]--;                        count--;                        left += wl;                    }                }                // not a valid word, reset all vars                else {                    tdict.clear();                    count = 0;                    left = j + wl;                }            }        }                return ans;    }
          
         
        
       
      

 

440

22.1%

Hard

我给出的解法很好（当然了，也是参考了别人的）。使用了前缀、范围等各种技巧来处理。很不错。

 

140

22.2%

Hard

其实题目不难。用递归，然后用DP加速。开始的时候，我没有一下子想到。开始我也想到用Trie树去查找，但是Trie树会复杂一些，而且不如Hash快。

 

212

22.2%

Hard

这道题目就是可以用Trie树了。

复习下Trie树的加入。就是26个子树，如果是叶子，标记一下；如果不是叶子，继续递归加。

取的时候，对于每一个格子的元素，如果Trie树找到，就移动到相应的子树，或者是叶子就添加结果；如果Trie树没有找到，就返回。

 

269

22.3%

Hard

解法很复杂。都要建立图。图是用unordered_map(C++)来处理的。一种使用类似DFS的拓扑排序。注意排序的时候要用visited和path两个数组，前一个是记录是否访问过，后一个是记录是否有环。

另外一种是用BFS的解法，来计算每个节点的入度，然后根据入度来一个一个取出来。

 

174

22.9%

Hard

我之前的方法用的是DP。但是现在我想到了一个很好的方法，就是从右下角开始，往上和往左回溯，来发现最小的代价。

 

214

23.0%

Hard

这个在回文类题目系列里面也有写到。通过先反向，再用KMP的next数组来辅助。能够做出来。

另外下面这个方法真是太绝妙了：直接理解有点难。

int j = 0;    for (int i = s.length() - 1; i >= 0; i--) {        if (s.charAt(i) == s.charAt(j)) { j += 1; }    }    if (j == s.length()) { return s; }    String suffix = s.substring(j);    return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;

但是反过来理解，如果中间那段能够是回文，那j必然走到了中间那段的后面，说明中间那段必然不是回文。那么后面的就必然是结果的一部分。再把中间的进行递归，就行了。