首页 > 代码库 > 练练脑,继续过Hard题目
练练脑,继续过Hard题目
http://www.cnblogs.com/charlesblc/p/6384132.html
继续过Hard模式的题目吧。
# | Title | Editorial | Acceptance | Difficulty | Frequency | |
---|---|---|---|---|---|---|
。 | 65 | Valid Number | 12.6% | Hard | ||
。 | 126 | Word Ladder II | 13.6% | Hard | ||
。 | 149 | Max Points on a Line | 15.6% | Hard | ||
。 | 146 | LRU Cache | 16.0% | Hard | ||
。 | 68 | Text Justification | 18.1% | Hard | ||
。 | 460 | LFU Cache | 19.0% | Hard | ||
。 | 44 | Wildcard Matching | 19.0% | Hard | ||
。 | 308 | Range Sum Query 2D - Mutable | 19.8% | Hard | ||
。 | 4 | Median of Two Sorted Arrays | 20.8% | Hard | ||
。 | 420 | Strong Password Checker | 21.0% | Hard | ||
。 | 273 | Integer to English Words | 21.1% | Hard | ||
。 | 30 | Substring with Concatenation of All Words | 21.7% | Hard | ||
。 | 440 | K-th Smallest in Lexicographical Order | 22.1% | Hard | ||
。 | 140 | Word Break II | 22.2% | Hard | ||
。 | 212 | Word Search II | 22.2% | Hard | ||
。 | 269 | Alien Dictionary | 22.3% | Hard | ||
。 | 174 | Dungeon Game | 22.9% | Hard | ||
。 | 214 | Shortest Palindrome | 23.0% | Hard | ||
。 | 446 | Arithmetic Slices II - Subsequence | 23.0% | Hard | ||
。 | 32 | Longest Valid Parentheses | 23.1% | Hard | ||
。 | 295 | Find Median from Data Stream | 23.3% | Hard | ||
。 | 132 | Palindrome Partitioning II | 23.4% | Hard | ||
。 | 10 | Regular Expression Matching | 23.6% | Hard | ||
。 | 76 | Minimum Window Substring | 23.8% | Hard | ||
。 | 188 | Best Time to Buy and Sell Stock IV | 23.8% | Hard | ||
。 | 321 | Create Maximum Number | 23.9% | Hard | ||
。 | 135 | Candy | 23.9% | Hard | ||
。 | 335 | Self Crossing | 23.9% | Hard | ||
。 | 97 | Interleaving String | 23.9% | Hard | ||
。 | 391 | Perfect Rectangle | 24.2% | Hard | ||
158 | Read N Characters Given Read4 II - Call multiple times | 24.4% | Hard | |||
466 | Count The Repetitions | 24.6% | Hard | |||
336 | Palindrome Pairs | 24.7% | Hard | |||
41 | First Missing Positive | 24.9% | Hard | |||
124 | Binary Tree Maximum Path Sum | 25.0% | Hard | |||
224 | Basic Calculator | 25.5% | Hard | |||
218 | The Skyline Problem | 25.5% | Hard | |||
84 | Largest Rectangle in Histogram | 25.6% | Hard | |||
23 | Merge k Sorted Lists | 25.9% | Hard | |||
45 | Jump Game II | 26.0% | Hard | |||
85 | Maximal Rectangle | 26.1% | Hard | |||
57 | Insert Interval | 26.3% | Hard | |||
138 | Copy List with Random Pointer | 26.6% | Hard | |||
233 | Number of Digit One | 27.3% | Hard | |||
381 | Insert Delete GetRandom O(1) - Duplicates allowed | 28.0% | Hard | |||
37 | Sudoku Solver | 28.1% | Hard | |||
432 | All O`one Data Structure | 28.2% | Hard | |||
87 | Scramble String | 28.3% | Hard | |||
123 | Best Time to Buy and Sell Stock III | 28.3% | Hard | |||
56 | Merge Intervals | 28.4% | Hard | |||
282 | Expression Add Operators | 28.5% | Hard | |||
316 | Remove Duplicate Letters | 28.6% | Hard | |||
164 | Maximum Gap | 28.6% | Hard | |||
99 | Recover Binary Search Tree | 28.7% | Hard | |||
327 | Count of Range Sum | 28.9% | Hard | |||
51 | N-Queens | 29.0% | Hard | |||
25 | Reverse Nodes in k-Group | 29.7% | Hard | |||
472 | Concatenated Words | 30.1% | Hard | |||
465 | Optimal Account Balancing | 30.1% | Hard | |||
248 | Strobogrammatic Number III | 30.5% | Hard | |||
72 | Edit Distance | 30.6% | Hard | |||
115 | Distinct Subsequences | 30.6% | Hard | |||
403 | Frog Jump | 30.9% | Hard | |||
411 | Minimum Unique Word Abbreviation | 31.1% | Hard | |||
239 | Sliding Window Maximum | 31.4% | Hard | |||
330 | Patching Array | 31.5% | Hard | |||
297 | Serialize and Deserialize Binary Tree | 31.6% | Hard | |||
354 | Russian Doll Envelopes | 31.8% | Hard | |||
358 | Rearrange String k Distance Apart | 31.8% | Hard | |||
33 | Search in Rotated Sorted Array | 31.9% | Hard | |||
363 | Max Sum of Rectangle No Larger Than K | 32.1% | Hard | |||
410 | Split Array Largest Sum | 32.2% | Hard | |||
480 | Sliding Window Median | 33.1% | Hard | |||
317 | Shortest Distance from All Buildings | 33.3% | Hard | |||
117 | Populating Next Right Pointers in Each Node II | 33.5% | Hard | |||
315 | Count of Smaller Numbers After Self | 33.5% | Hard | |||
301 | Remove Invalid Parentheses | 34.5% | Hard | |||
42 | Trapping Rain Water | 35.3% | Hard | |||
128 | Longest Consecutive Sequence | 35.3% | Hard | |||
329 | Longest Increasing Path in a Matrix | 35.4% | Hard | |||
407 | Trapping Rain Water II | 35.6% | Hard | |||
154 | Find Minimum in Rotated Sorted Array II | 36.2% | Hard | |||
265 | Paint House II | 37.1% | Hard | |||
272 | Closest Binary Search Tree Value II | 37.6% | Hard | |||
291 | Word Pattern II | 37.7% | Hard | |||
305 | Number of Islands II | 38.1% | Hard | |||
380 | Insert Delete GetRandom O(1) | 38.4% | Hard | |||
145 | Binary Tree Postorder Traversal | 38.4% | Hard | |||
340 | Longest Substring with At Most K Distinct Characters | 38.6% | Hard | |||
352 | Data Stream as Disjoint Intervals | 38.9% | Hard | |||
159 | Longest Substring with At Most Two Distinct Characters | 39.7% | Hard | |||
312 | Burst Balloons | 41.6% | Hard | |||
287 | Find the Duplicate Number | 41.8% | Hard | |||
425 | Word Squares | 41.9% | Hard | |||
52 | N-Queens II | 42.8% | Hard | |||
302 | Smallest Rectangle Enclosing Black Pixels | 44.0% | Hard | |||
471 | Encode String with Shortest Length | 44.2% | Hard | |||
296 | Best Meeting Point | 50.4% | Hard |
97 | Interleaving String | 23.9% | Hard |
这道题目很好,是使用DP的典型方案。可惜我开始还是没能做出来。Discuss的解法非常好。好好学习。
bool isInterleave(string s1, string s2, string s3) { if(s3.length() != s1.length() + s2.length()) return false; bool table[s1.length()+1][s2.length()+1]; for(int i=0; i<s1.length()+1; i++) for(int j=0; j< s2.length()+1; j++){ if(i==0 && j==0) table[i][j] = true; else if(i == 0) table[i][j] = ( table[i][j-1] && s2[j-1] == s3[i+j-1]); else if(j == 0) table[i][j] = ( table[i-1][j] && s1[i-1] == s3[i+j-1]); else table[i][j] = (table[i-1][j] && s1[i-1] == s3[i+j-1] ) || (table[i][j-1] && s2[j-1] == s3[i+j-1] ); } return table[s1.length()][s2.length()]; }
391 | Perfect Rectangle | 24.2% | Hard |
这道题目很难。而这个解法,真是太巧了。
两个基本点:一是总面积等于各个区域面积之和;另一个是所有的点出现偶数次,除了四个角上面的点。
View Code
练练脑,继续过Hard题目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。