Leetcode 刷题打卡记录 包括Solution

535. Encode and Decode TinyURL

1. class Solution {
   
2.     unordered_map<long long, string> cache;
   
3.    
   
4.     const static int LEN = 7;
   
5.     static const constexpr char* table = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
   
6. public:
   
7.     // Encodes a URL to a shortened URL.
   
8.     string encode(string longUrl) {
   
9.         long long uid = cache.size() + 1;
   
10.         cache.insert(make_pair(uid, longUrl));
    
11. 
    
12.         string code;
    
13.         for (int i = 0; i < LEN; i++) {
    
14.             code += table[uid%62];
    
15.             uid /= 62;
    
16.         }
    
17.         return string(code.rbegin(), code.rend());
    
18.     }
    
19. 
    
20.     // Decodes a shortened URL to its original URL.
    
21.     string decode(string shortUrl) {
    
22.         long long uid = 0;
    
23.         for (auto &c : shortUrl) {
    
24.             int a = 0;
    
25.             if (c >= 'a' && c <= 'z') a = c - 'a';
    
26.             else if (c >= 'A' && c <= 'Z') a = c - 'A' + 26;
    
27.             else if (c >= '0' && c <= '9') a = c - '0' + 52;
    
28.             else {
    
29.                 // error
    
30.             }
    
31.             uid = uid * 62 + a;
    
32.         }
    
33.         auto it = cache.find(uid);
    
34.         if (it == cache.end()) {
    
35.             return "error";
    
36.         }
    
37.         return it->second;
    
38.     }
    
39. };

复制代码

739. Daily Temperatures

1. class Solution {
   
2. public:
   
3.     vector<int> dailyTemperatures(vector<int>& T) {
   
4.         vector<int> res(T.size(), 0);
   
5.         
   
6.         for (int i = T.size()-2; i >= 0; i--) {
   
7.             int j = i + 1;
   
8.             while (j < T.size()) {
   
9.                 if (T[i] < T[j]) {
   
10.                     res[i] = j - i;
    
11.                     break;
    
12.                 }
    
13.                 if (res[j] == 0) break;
    
14.                
    
15.                 if (T[i] == T[j]) {
    
16.                     res[i] = res[j] + j - i;
    
17.                     break;
    
18.                 }
    
19.                
    
20.                 j = j + res[j];
    
21.             }
    
22.         }
    
23.         
    
24.         return res;
    
25.     }
    
26. };

复制代码

760. Find Anagram Mappings

1. class Solution {
   
2. public:
   
3.     vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
   
4.         unordered_map<int, list<int>> cache;
   
5.         for (int i = 0; i < B.size(); i++) {
   
6.             cache[B[i]].push_back(i);
   
7.         }
   
8.         vector<int> res(A.size(), 0);
   
9.         for (int i = 0; i < A.size(); i++) {
   
10.             auto it = cache.find(A[i]);
    
11.             res[i] = it->second.front();
    
12.             it->second.pop_front();
    
13.         }
    
14.         return res;
    
15.     }
    
16. };

复制代码

904. Fruit Into Baskets

1. class Solution {
   
2. public:
   
3.     int totalFruit(vector<int>& tree) {
   
4.         if (tree.empty()) return 0;
   
5.         
   
6.         int res = 1;
   
7.         int a = tree.front();
   
8.         int a_count = 1;
   
9.         int b;
   
10.         bool bf = false;
    
11.         int acc = 1;
    
12.         for (int i = 1; i < tree.size(); i++) {
    
13.             int c = tree[i];
    
14.             // same as last one
    
15.             if (c == a) {
    
16.                 ++acc;
    
17.                 a_count++;
    
18.             } else {
    
19.                 // the other basket is empty
    
20.                 if (!bf) {
    
21.                     bf = true;
    
22.                     b = a;
    
23.                     a = c;
    
24.                     a_count = 1;
    
25.                     ++acc;
    
26.                 } else {
    
27.                     if (c == b) {
    
28.                         ++acc;
    
29.                         swap(a, b);
    
30.                         a_count = 1;
    
31.                     } else {
    
32.                         // discard b
    
33.                         b = a;
    
34.                         acc = a_count + 1;
    
35.                         a = c;
    
36.                         a_count = 1;
    
37.                     }
    
38.                 }
    
39.             }
    
40.             res = max(res, acc);
    
41.         }
    
42.         return res;
    
43.     }
    
44. };

复制代码

30. Substring with Concatenation of All Words
Solution 2 using Trie, 44ms

1. class Trie {
   
2.     Trie *cc[26];
   
3.     int pos;
   
4. public:
   
5.     Trie() {
   
6.         pos = -1;
   
7.         fill_n(cc, 26, nullptr);
   
8.     }
   
9.     void insert(const string &s, int position) {
   
10.         Trie* p = this;
    
11.         for (auto &c : s) {
    
12.             int idx = c - 'a';
    
13.             if (!p->cc[idx]) {
    
14.                 p->cc[idx] = new Trie();
    
15.             }
    
16.             p = p->cc[idx];
    
17.         }
    
18.         p->pos = position;
    
19.     }
    
20.     int search(const string &s, int start, int sz) {
    
21.         Trie* p = this;
    
22.         for (int i = start; i < start + sz; i++) {
    
23.             int idx = s[i] - 'a';
    
24.             if (!p->cc[idx]) return -1;
    
25.             p = p->cc[idx];
    
26.         }
    
27.         return p->pos;
    
28.     }
    
29. };
    
30. 
    
31. class Solution {
    
32. public:
    
33.     vector<int> findSubstring(string s, vector<string>& words) {
    
34.         vector<int> res;
    
35.         if (words.empty() || s.empty())
    
36.             return res;
    
37.         unordered_map<string,int> mm;
    
38.         for (auto &w : words) {
    
39.             mm[w]++;
    
40.         }
    
41.         vector<int> flagTmpl(mm.size(), 0);
    
42.         Trie trie;
    
43.         int i = 0;
    
44.         for (auto itt : mm) {
    
45.             flagTmpl[i] = itt.second;
    
46.             trie.insert(itt.first, i);
    
47.             i++;
    
48.         }
    
49. 
    
50.         vector<int> dp(s.size(), -2);
    
51.         const int WD_LEN = words[0].size();
    
52.         for (int i = 0; i <= (int)s.size()-(int)(WD_LEN*words.size()); i++) {
    
53.             if (dp[i] == -1) continue;
    
54. 
    
55.             vector<int> flags(flagTmpl);
    
56.             int flagCount = 0;
    
57.             int start = i;
    
58.             while (flagCount < words.size() && start <= s.size() - WD_LEN) {
    
59.                 int pos = dp[start];
    
60.                 if (pos == -1) break;
    
61.                 if (pos == -2) {
    
62.                     pos = trie.search(s, start, WD_LEN);
    
63.                 }
    
64.                 if (pos < 0) {
    
65.                     dp[start] = -1;
    
66.                     break;
    
67.                 }
    
68.                 if (flags[pos] < 1) {
    
69.                     break;
    
70.                 }
    
71.                 flags[pos]--;
    
72.                 dp[start] = pos;
    
73.                 start += WD_LEN;
    
74.                 ++flagCount;
    
75.             }
    
76.             if (flagCount == words.size()) {
    
77.                 res.push_back(i);
    
78.             }
    
79.         }
    
80.         return res;
    
81.     }
    
82. };

复制代码

41. First Missing Positive
Sulotion 2

1. class Solution {
   
2. public:
   
3.     int firstMissingPositive(vector<int>& nums) {
   
4.         if (nums.empty()) return 1;
   
5.         
   
6.         int i = 0;
   
7.         while (i < nums.size()) {
   
8.             while (true) {
   
9.                 int v = nums[i];
   
10.                 if (v == i+1) break;
    
11.                
    
12.                 if (v <= 0 || v > nums.size()) {
    
13.                     nums[i] = -1;
    
14.                     break;
    
15.                 }
    
16.                 if (v == nums[v-1]){
    
17.                     nums[i] = -1;
    
18.                     break;
    
19.                 }
    
20. 
    
21.                 swap(nums[i], nums[v-1]);
    
22.             }
    
23.             ++i;
    
24.         }
    
25.         i = 0;
    
26.         for (; i < nums.size(); i++) {
    
27.             if (nums[i] != i+1) return i+1;
    
28.         }
    
29.         return i+1;
    
30.     }
    
31. };

复制代码

43. Multiply Strings

1. class Solution {
   
2. public:
   
3.     string multiply(string num1, string num2) {
   
4.         vector<int> res(num1.size() + num2.size(), 0);
   
5.         for (int j = 0; j < num2.size(); j++) {
   
6.             int d2 = num2[num2.size()-j-1] - '0';
   
7.             int i = j;
   
8.             for (int k = 0; k < num1.size(); k++) {
   
9.                 int d1 = num1[num1.size()-k-1] - '0';
   
10.                 int r = d1 * d2 + res[i];
    
11.                 res[i] = r % 10;
    
12.                 res[i+1] += r / 10;
    
13.                 i++;
    
14.             }
    
15.         }
    
16.         int i = res.size()-1;
    
17.         while (i >= 0 && res[i] == 0) i--;
    
18.         if (i < 0) return "0";
    
19.         
    
20.         string s;
    
21.         while (i >= 0) {
    
22.             s += to_string(res[i]);
    
23.             i--;
    
24.         }
    
25.         return s;
    
26.     }
    
27. };

复制代码

44. Wildcard Matching

1. class Solution {
   
2. public:
   
3.     bool isMatch(string s, string p) {
   
4.         vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1, false));
   
5.         dp[0][0] = true;
   
6.         for (uint32_t i = 0; i <= s.size(); i++) {
   
7.             for (uint32_t j = 1; j <= p.size(); j++) {
   
8.                 // for p starts with some '*'
   
9.                 if (i == 0) {
   
10.                     dp[0][j] = p[j-1] == '*' && dp[0][j-1];
    
11.                 }
    
12.                 else if (p[j-1] == s[i-1] || p[j-1] == '?')
    
13.                     dp[i][j] = dp[i-1][j-1];
    
14.                 else if (p[j-1] == '*')
    
15.                     dp[i][j] = dp[i-1][j]   // match 0 or 1 time
    
16.                      || dp[i][j-1];         // match 1+ times
    
17.             }
    
18.         }
    
19.         return dp[s.size()][p.size()];
    
20.     }
    
21. };

复制代码