Leetcode 刷题打卡记录 包括Solution

mwen2 发表于 2019-2-19 15:01
感觉我刷题有时候不会了或者没思路就想看答案。。。而且会强迫自己背别人的算法。然后mock interview导致自 ...

太正常了，不过还是要尽量先自己努力的想，实在想不出来再观摩别人的答案。千万别背答案，理解

312. Burst Balloons
Non-recursive

1. class Solution {
   
2.     int get(const vector<int>& nums, int i) {
   
3.         if (i < 0 || i >= nums.size())
   
4.             return 1;
   
5.         return nums[i];
   
6.     }
   
7. public:
   
8.     int maxCoins(vector<int>& nums) {
   
9.         if (nums.empty()) return 0;
   
10.         
    
11.         vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
    
12.         
    
13.         for (int i = 1; i <= nums.size(); i++) {
    
14.             for (int j = 0; j <= nums.size()-i; j++) {
    
15.                 int start = j;
    
16.                 int end = j + i - 1; // inclusive
    
17.                
    
18.                 // assume nums[k] will be bursted last
    
19.                 int res = 0;
    
20.                 for (int k = start; k <= end; k++) {
    
21.                     int r = (k > 0? dp[start][k-1] : 0) +
    
22.                         get(nums, start-1)*nums[k]*get(nums, end+1) +
    
23.                         (k < nums.size()-1? dp[k+1][end] : 0);
    
24.                     res = max(res, r);
    
25.                 }
    
26.                 dp[start][end] = res; //max(res, dp[start][end]);
    
27.             }
    
28.         }
    
29.         return dp[0][nums.size()-1];
    
30.     }
    
31. };

复制代码

背答案就是我，背了其实过没多久就全忘记了。。。惭愧

huihuiyang 发表于 2019-2-20 02:16
背答案就是我，背了其实过没多久就全忘记了。。。惭愧

看懂了之后自己写几遍印象就深了。leetcode，lintcode换着地方写

315. Count of Smaller Numbers After Self, hard

1. class Solution {
   
2. public:
   
3.     vector<int> countSmaller(vector<int>& nums) {
   
4.         vector<int> res(nums.size(), 0);
   
5.         vector<int> n_sorted;
   
6.         for (int i = nums.size()-1; i >= 0; i--) {
   
7.             auto& v = nums[i];
   
8.             auto it = lower_bound(n_sorted.begin(), n_sorted.end(), v);
   
9.             int r = it - n_sorted.begin();
   
10.             n_sorted.insert(it, v);
    
11.             res[i] = r;
    
12.         }
    
13.         return res;
    
14.     }
    
15. };

复制代码

wglacier 发表于 2019-2-19 19:22
太正常了，不过还是要尽量先自己努力的想，实在想不出来再观摩别人的答案。千万别背答案，理解

多谢楼主鼓励，我争取自己努力想一下，下周有电面，希望可以边刷题边有改变，已加米~

315. Count of Smaller Numbers After Self
Merge sort

1. class Solution {
   
2. public:
   
3.     struct Node {
   
4.         int val;
   
5.         int idx;
   
6.         int smallerCount;
   
7.         Node(int a, int b)
   
8.         : val(a), idx(b), smallerCount(0)
   
9.         {}
   
10.     };
    
11.     void merge(vector<Node>& merged, int start, int end) {
    
12.         if (start >= end) return;
    
13. 
    
14.         int m = start + (end - start)/2;
    
15.         merge(merged, start, m);
    
16.         merge(merged, m+1, end);
    
17. 
    
18.         vector<Node> sorted;
    
19.         int i = start, j = m+1;
    
20.         int smallerCount = 0;
    
21.         while (i <= m && j <= end) {
    
22.             int k;
    
23.             if (merged[i].val > merged[j].val) {
    
24.                 smallerCount++;
    
25.                 k = j++;
    
26.             } else {
    
27.                 merged[i].smallerCount += smallerCount;
    
28.                 k = i++;
    
29.             }
    
30.             sorted.push_back(merged[k]);
    
31.         }
    
32.         while (i <= m) {
    
33.             merged[i].smallerCount += smallerCount;
    
34.             sorted.push_back(merged[i++]);
    
35.         }
    
36.         while (j <= end) {
    
37.             sorted.push_back(merged[j++]);
    
38.         }
    
39.         copy(sorted.begin(), sorted.end(), merged.begin() + start);
    
40.     }
    
41. 
    
42.     vector<int> countSmaller(vector<int>& nums) {
    
43.         vector<Node> merged;
    
44.         for (int i = 0; i < nums.size(); i++) {
    
45.             merged.push_back(Node(nums[i], i));
    
46.         }
    
47.         merge(merged, 0, merged.size()-1);
    
48. 
    
49.         vector<int> res(nums.size(), 0);
    
50.         for (auto& n : merged) {
    
51.             res[n.idx] = n.smallerCount;
    
52.         }
    
53.         return res;
    
54.     }
    
55. };

复制代码

315. Count of Smaller Numbers After Self
Solution 3, BST

1. class Solution {
   
2. public:
   
3.     struct Node {
   
4.         Node* left;
   
5.         Node* right;
   
6.         int val;
   
7.         int lessEqualCount; // number of nodes that are less or equal to it (include itself)
   
8.         Node(int v)
   
9.         : val(v), left(nullptr), right(nullptr)
   
10.         , lessEqualCount(1)
    
11.         {}
    
12.     };
    
13.     int check(Node* root, int val) {
    
14.         int res = 0;
    
15.         while (true) {
    
16.             if (val <= root->val) {
    
17.                 root->lessEqualCount++;
    
18.                 if (!root->left) {
    
19.                     root->left = new Node(val);
    
20.                     break;
    
21.                 }
    
22.                 root = root->left;
    
23.             } else {
    
24.                 res += root->lessEqualCount;
    
25.                 if (!root->right) {
    
26.                     root->right = new Node(val);
    
27.                     break;
    
28.                 }
    
29.                 root = root->right;
    
30.             }
    
31.         }
    
32.         return res;
    
33.     }
    
34.     vector<int> countSmaller(vector<int> &nums) {
    
35.         if (nums.size() < 2) {
    
36.             return vector<int>(nums.size(), 0);
    
37.         }
    
38.         vector<int> res(1, 0);
    
39.         Node* root = new Node(nums.back());
    
40.         for (int i = nums.size()-2; i >= 0; i--) {
    
41.             auto r = check(root, nums[i]);
    
42.             res.push_back(r);
    
43.         }
    
44.         return vector<int>(res.rbegin(), res.rend());
    
45.     }
    
46. };

复制代码

316. Remove Duplicate Letters

1. class Solution {
   
2. public:
   
3.      /*
   
4.      1. calc the last occurrence of each char
   
5.      2. sort the array in asc order
   
6.      3. for each group, find the smallest char in the group until find the char same as the last char
   
7.      4. extend the current group to the next and repeat step 3.
   
8.      */
   
9. 
   
10.     string removeDuplicateLetters(string &s) {
    
11.         if (s.empty()) return "";
    
12.         
    
13.         // last idex of each char
    
14.         int buf[26];
    
15.         fill_n(buf, 26, -1);
    
16.         for (int i = 0; i < s.size(); i++) {
    
17.             buf[s[i]-'a'] = i;
    
18.         }
    
19.         sort(buf, buf+26);
    
20.         
    
21.         // find the first non-empty group
    
22.         int k = 0;
    
23.         while (buf[k] < 0) k++;
    
24. 
    
25.         int start = 0, end = buf[k];
    
26.         string res;
    
27.         set<char> cused;
    
28.         while (start <= end) {
    
29.             auto min_char = 'z' + 1;
    
30.             int i = start;
    
31.             while (i <= end) {
    
32.                 auto c = s[i];
    
33.                 if (cused.count(c) < 1 && c < min_char) {
    
34.                     min_char = c;
    
35.                     start = i + 1;
    
36.                 }
    
37.                 i++;
    
38.             }
    
39.             cused.insert(min_char);
    
40.             res += min_char;
    
41. 
    
42.             if (min_char == s[end]) {
    
43.                 // extend to next group
    
44.                 while (++k < 26) {
    
45.                     if (cused.count(s[buf[k]]) < 1) break;
    
46.                 }
    
47.                 if (k >= 26) break;
    
48.                 end = buf[k];
    
49.             };
    
50.         }
    
51.         return res;
    
52.     }
    
53. };

复制代码

336. Palindrome Pairs
Use map

1. class Solution {
   
2. public:
   
3.     bool isPalindrome(const string & s) {
   
4.         if (s.size() < 2) return true;
   
5.         
   
6.         int i = 0, j = s.size() - 1;
   
7.         while (i < j) {
   
8.             if (s[i] != s[j]) return false;
   
9.             i++, j--;
   
10.         }
    
11.         return true;
    
12.     }
    
13.     vector<vector<int>> palindromePairs(vector<string> &words) {
    
14.         vector<vector<int>> res;
    
15.         if (words.size() < 2) return res;
    
16.         
    
17.         // reverse all words into map
    
18.         map<string, int> wordMap;
    
19.         map<string, int> wordPalin;
    
20.         for (int i = 0; i < words.size(); i++) {
    
21.             auto & w = words[i];
    
22.             wordMap.emplace(string(w.rbegin(), w.rend()), i);
    
23.             if (!w.empty() && isPalindrome(w)) {
    
24.                 wordPalin.emplace(w, i);
    
25.             }
    
26.         }
    
27. 
    
28.         for (int i = 0; i < words.size(); i++) {
    
29.             auto &w = words[i];
    
30.             if (w.empty()) {
    
31.                 for (auto &pw : wordPalin) {
    
32.                     res.push_back({i, pw.second});
    
33.                     res.push_back({pw.second, i});
    
34.                 }
    
35.                 continue;
    
36.             }
    
37.             // prefix and suffix may contain empty string
    
38.             for (int j = 1; j <= w.size(); j++) {
    
39.                 auto prefix = w.substr(0, j);
    
40.                 auto suffix = w.substr(j);
    
41.                 auto it = wordMap.find(prefix);
    
42.                 if ( it != wordMap.end() && isPalindrome(suffix) && it->second != i) {
    
43.                     res.push_back({i, it->second});
    
44.                 }
    
45.                 if (suffix.empty()) continue;
    
46. 
    
47.                 it = wordMap.find(suffix);
    
48.                 if ( it != wordMap.end() && isPalindrome(prefix)) {
    
49.                     res.push_back({it->second, i});
    
50.                 }
    
51.             }
    
52.         }
    
53.         return res;
    
54.     }
    
55. };

复制代码