首页 > 代码库 > 练练脑,继续过Hard题目

练练脑,继续过Hard题目

http://www.cnblogs.com/charlesblc/p/6384132.html

继续过Hard模式的题目吧。

 

 #TitleEditorialAcceptanceDifficultyFrequency 
 。 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()];
}
View Code

 

 

391 Perfect Rectangle     24.2% Hard

这道题目很难。而这个解法,真是太巧了。

两个基本点:一是总面积等于各个区域面积之和;另一个是所有的点出现偶数次,除了四个角上面的点。

技术分享View Code

 

练练脑,继续过Hard题目