New Year, New Start. Leet Code Records (3-5 per day)

The goal is here:
1). 3-5 per day at weekdays
2). 10 - 15 per day at weekends
Welcome other friends to join and let us keep up together.

2019-01-13:
1). 105 Construct Binary Tree from Preorder and Inorder Traversal
2). 108 Convert Sorted Array to Binary Search Tree
3). 116 Populating Next Right Pointers in Each Node
4). 118 Pascal's Triangle
5). 121 Best Time to Buy and Sell Stock  
6). 122 Best Time to Buy and Sell Stock II
7). 123. Best Time to Buy and Sell Stock III
8). 188. Best Time to Buy and Sell Stock IV
9). 124. Binary Tree Maximum Path Sum
10). 125. Valid Palindrome
11). 127 Word Ladder
post the one that I have improved, from one direction to two directions

1. class Solution {
   
2. public:
   
3.     int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
   
4.         unordered_set<string> dict(wordList.begin(), wordList.end());
   
5.         if (dict.find(endWord) == dict.end()) return 0;
   
6.         unordered_set<string> head{beginWord}, tail{endWord};
   
7.         int steps = 2;
   
8.         while (!head.empty() && !tail.empty()) {
   
9.             if (head.size() > tail.size()) swap(head, tail);
   
10.             unordered_set<string> next_set;
    
11.             for (auto str : head) dict.erase(str);
    
12.             for (auto str : head) {
    
13.                 for (int i = 0; i < str.size(); i++) {
    
14.                     char tmp = str[i];
    
15.                     for (char ch = 'a'; ch <= 'z'; ch++) {
    
16.                         if (ch == tmp) continue;
    
17.                         str[i] = ch;
    
18.                         if (tail.find(str) != tail.end()) return steps;
    
19.                         if (dict.find(str) != dict.end()) {
    
20.                             next_set.insert(str);
    
21.                             dict.erase(str);
    
22.                         }
    
23.                     }
    
24.                     str[i] = tmp;
    
25.                 }
    
26.             }
    
27.             steps++;
    
28.             swap(next_set, head);     
    
29.         }
    
30.         return 0;
    
31.     }
    
32. };

复制代码

2019-01-06
1). 17. Letter Combinations of a Phone Number
2). 19. Remove Nth Node From End of List
3). 20. Valid Parentheses
4). 21. Merge Two Sorted Lists
5). 22. Generate Parentheses
6). 23. Merge k Sorted Lists
7). 26. Remove Duplicates from Sorted Array
8). 28. Implement strStr()
9). 29. Divide Two Integers
10). 33. Search in Rotated Sorted Array
This is the second round, post the one that improved.

1. class Solution {
   
2. public:
   
3.     int strStr(string haystack, string needle) {
   
4.         const int size_h = haystack.size();
   
5.         const int size_n = needle.size();
   
6.         if (0 == size_n) return 0;
   
7.         vector<int> lps(size_n, 0);
   
8.         for (int i = 1; i < size_n; i++) {
   
9.             int pos = lps[i-1];
   
10.             while (pos > 0 && needle[pos] != needle[i]) pos = lps[pos - 1];
    
11.             if (needle[pos] == needle[i]) lps[i] = pos + 1;
    
12.         }
    
13.         int idx_h = 0, idx_n = 0;
    
14.         for (; idx_h < size_h; idx_h++) {
    
15.             while (idx_n > 0 && needle[idx_n] != haystack[idx_h]) idx_n = lps[idx_n - 1];
    
16.             if (needle[idx_n] == haystack[idx_h]) idx_n++;
    
17.             if (idx_n == size_n) return idx_h - size_n + 1;
    
18.         }
    
19.         return -1;
    
20.     }
    
21. };

复制代码

2019-01-11
happy Friday Day, and have a rest:
1). 76. Minimum Window Substring
and find a better solution:

1.    string minWindow(string s, string t) {
   
2.         unordered_map<char, int> expected;
   
3.         for (auto ch : t) expected[ch]++;
   
4.         int lenT = t.size(), min_win = s.size() + 1, idx_start = 0, idx_m = -1;
   
5.         for (int i = 0; i < s.size(); i++) {
   
6.             if (expected[s[i]]-- > 0) lenT--;
   
7.             while (lenT == 0) {
   
8.                 if (i - idx_start + 1 < min_win) {
   
9.                     min_win = i - idx_start + 1;
   
10.                     idx_m = idx_start;
    
11.                 }
    
12.                
    
13.                 if (++expected[s[idx_start++]] > 0) lenT++;
    
14.             }
    
15.         }
    
16.         return idx_m == -1 ? "" : s.substr(idx_m, min_win);
    
17.     }
    
18. };

复制代码

2019-03-05:
1). 341. Flatten Nested List Iterator
2). 759. Employee Free Time
3). 756. Pyramid Transition Matrix
4). 42. Trapping Rain Water
5). 76. Minimum Window Substring
6). 1. Two Sum
7). 829. Consecutive Numbers Sum

imiochen24 发表于 2019-3-5 21:42
大家一天刷个十几题怎么办到的

一般是周末刷个十几题， 还有就是那些题不是刷第一遍。
加油

大家一天刷个十几题怎么办到的

2019-03-03:
1). 843. Guess the Word
2). 755. Pour Water
3). 336. Palindrome Pairs
4). 269. Alien Dictionary
5). 773. Sliding Puzzle

2019-03-04:
1). 371. Sum of Two Integers
2). 751. IP to CIDR
3). 251. Flatten 2D Vector
4). 39. Combination Sum
5). 324. Wiggle Sort II

2019-03-02:
1). 364. Nested List Weight Sum II
2). 365. Water and Jug Problem
3). 366. Find Leaves of Binary Tree
4). 368. Largest Divisible Subset
5). 370. Range Addition
6).  773. Sliding Puzzle
7). 751. IP to CIDR
8). 756. Pyramid Transition Matrix
9). Consecutive Numbers Sum
10). 815. Bus Routes
11). 16. 3Sum Closest

2019-02-28:
1). 350. Intersection of Two Arrays II
2). 349. Intersection of Two Arrays
3). 351. Android Unlock Patterns
4). 351. Android Unlock Patterns
5). 359. Logger Rate Limiter
6). 354. Russian Doll Envelopes
7). 356. Line Reflection
8). 358. Rearrange String k Distance Apart

2019-02-26：
1). 337. House Robber III
2). 338. Counting Bits
3). 339. Nested List Weight Sum
4). 340. Longest Substring with At Most K Distinct Characters
5). 341. Flatten Nested List Iterator
6). 342. Power of Four
7). 343. Integer Break
8). 344. Reverse String
9). 345. Reverse Vowels of a String
10).346. Moving Average from Data Stream
11). 347. Top K Frequent Elements

2019-02-24:
1). 307. Range Sum Query - Mutable
2). 308. Range Sum Query 2D - Mutable
3). 309. Best Time to Buy and Sell Stock with Cooldown
4). 310. Minimum Height Trees
5). 311. Sparse Matrix Multiplication
6). 312. Burst Balloons
7). 313. Super Ugly Number
8). 314. Binary Tree Vertical Order Traversal
9). 317. Shortest Distance from All Buildings
10).318. Maximum Product of Word Lengths
11). 320. Generalized Abbreviation
12). 323. Number of Connected Components in an Undirected Graph
13). 325. Maximum Size Subarray Sum Equals k
14). 326. Power of Three
15). 327. Count of Range Sum
16). 328. Odd Even Linked List

2019-02-24:
1). 42. Trapping Rain Water
2). 84. Largest Rectangle in Histogram
3). 94. Binary Tree Inorder Traversal
4). 101. Symmetric Tree
5). 301. Remove Invalid Parentheses
6). 302. Smallest Rectangle Enclosing Black Pixels
7). 303. Range Sum Query - Immutable
8). 304. Range Sum Query 2D - Immutable
9). 305. Number of Islands II
10). 306. Additive Number