先过一下Hard模式的题目吧。
| 65 | Valid Number | 12.6% | Hard |
好像很繁琐。
| 126 | Word Ladder II | 13.6% | Hard |
方法是很好的。不是采用查找备选集的方式，而是采用逐个字符替换(可以加Hash来查找)，这样复杂度从很高，降低到O(26*n), n是字典长度。
| 149 | Max Points on a Line | 15.6% | Hard |
解法很好。通过角度来判断是否一条直线。我看了解法之后，觉得可以再优化一下，比如记下后续点已经处理过的角度。
| 146 | LRU Cache | 16.0% | Hard |
我觉得用一个Hash, 加一个双向链表比较好。Hash里面记录链表实际节点，然后每次访问，这个节点移到双向链表的头部，成为新的head。每次满了删除，就删除尾部的。
里面还用了stl的list实现里面的一种很快的方式（当然了，自己来移动节点，也行）：
// 貌似用这个splice比较快
dl.splice(dl.begin(), dl, mitr->second);
| 68 | Text Justification | 18.1% | Hard |
这道题目主要的难点就是gap的处理，尤其是gap不一致的情况。用的是下面的方法：
if (i < extra) {
line.push_back(‘ ‘);
}
也就是说，对于前面”extra”个数的间隔，都加上一个。
| 460 | LFU Cache | 19.0% | Hard |
很好，非常好！用了一个抽象数据结构Node，来记录同一访问频次层级的key，然后用了LinkedHashSet来记录这些key，进一步保证了先来后到（先达到的，会先删除）。好好领悟，很好！
还用了两个HashMap，分别记录真实的结果，以及一个key对应的Node（如上所述，这个Node里面包含了很多key，用LinkedHashSet来组织的）
| 44 | Wildcard Matching | 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; }
View Code
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(); }
View Code
| 4 | Median of Two Sorted Arrays | 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
View Code
| 420 | Strong Password Checker | 21.0% | Hard |
太繁琐，意义不大。
| 273 | Integer to English Words | 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); }
View Code
| 30 | Substring with Concatenation of All Words | 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<int> findSubstring(string S, vector<string> &L) { vector<int> ans; int n = S.size(), cnt = L.size(); if (n <= 0 || cnt <= 0) return ans; // init word occurence unordered_map<string, int> 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<string, int> 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; }
View Code
| 440 | K-th Smallest in Lexicographical Order | 22.1% | Hard |
我给出的解法很好（当然了，也是参考了别人的）。使用了前缀、范围等各种技巧来处理。很不错。
| 140 | Word Break II | 22.2% | Hard |
其实题目不难。用递归，然后用DP加速。开始的时候，我没有一下子想到。开始我也想到用Trie树去查找，但是Trie树会复杂一些，而且不如Hash快。
| 212 | Word Search II | 22.2% | Hard |
这道题目就是可以用Trie树了。
复习下Trie树的加入。就是26个子树，如果是叶子，标记一下；如果不是叶子，继续递归加。
取的时候，对于每一个格子的元素，如果Trie树找到，就移动到相应的子树，或者是叶子就添加结果；如果Trie树没有找到，就返回。
| 269 | Alien Dictionary | 22.3% | Hard |
解法很复杂。都要建立图。图是用unordered_map(C++)来处理的。一种使用类似DFS的拓扑排序。注意排序的时候要用visited和path两个数组，前一个是记录是否访问过，后一个是记录是否有环。
另外一种是用BFS的解法，来计算每个节点的入度，然后根据入度来一个一个取出来。
| 174 | Dungeon Game | 22.9% | Hard |
我之前的方法用的是DP。但是现在我想到了一个很好的方法，就是从右下角开始，往上和往左回溯，来发现最小的代价。
| 214 | Shortest Palindrome | 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;
View Code
但是反过来理解，如果中间那段能够是回文，那j必然走到了中间那段的后面，说明中间那段必然不是回文。那么后面的就必然是结果的一部分。再把中间的进行递归，就行了。