Leetcode 刷题打卡记录 包括Solution

341. Flatten Nested List Iterator

1. class NestedIterator {
   
2. private:
   
3.     using ContainerType = const vector<NestedInteger>;
   
4.     using IterType = ContainerType::const_iterator;
   
5.     stack<pair<ContainerType*, IterType>> mList;
   
6.    
   
7.     void locateData() {
   
8.         if (mList.empty()) return;
   
9.         while (true) {
   
10.             if (mList.top().first->end() == mList.top().second) {
    
11.                 if (mList.size() == 1) return;
    
12.                 mList.pop();
    
13.                 mList.top().second++;
    
14.                 continue;
    
15.             }
    
16.             auto &this_list = *(mList.top().second);
    
17.             if (this_list.isInteger()) return;
    
18.             mList.push(make_pair(&(this_list.getList()), this_list.getList().begin()));
    
19.         }
    
20.     }
    
21.     void incrIter() {
    
22.         if (mList.empty()) return;
    
23.         if (mList.top().first->end() == mList.top().second) {
    
24.             if (mList.size() == 1)
    
25.                 return;
    
26.             mList.pop();
    
27.         }
    
28.         mList.top().second++;
    
29.         locateData();
    
30.     }
    
31. public:
    
32.     NestedIterator(vector<NestedInteger> &nestedList) {
    
33.         mList.push(make_pair(&nestedList, nestedList.begin()));
    
34.         locateData();
    
35.     }
    
36. 
    
37.     int next() {
    
38.         // assert mList not empty and has next element
    
39.         auto &top = mList.top();
    
40.         auto pList = top.first;
    
41.         auto iter = top.second;
    
42.         int res;
    
43.         if (iter == pList->end()) return -1;
    
44.         
    
45.         if ((*iter).isInteger()) {
    
46.             res = (*iter).getInteger();
    
47.         } else {
    
48.             // not defined
    
49.         }
    
50.         incrIter();
    
51.         
    
52.         return res;
    
53.     }
    
54. 
    
55.     bool hasNext() {
    
56.         return !mList.empty() && mList.top().second != mList.top().first->end();
    
57.     }
    
58. };

复制代码

341. Flatten Nested List Iterator
Solution 2: Pre-processing

1. class NestedIterator {
   
2. private:
   
3.     vector<int> m_list;
   
4.     int m_idx;
   
5.    
   
6.     void add(const vector<NestedInteger> &nestedList) {
   
7.         for (auto &node : nestedList) {
   
8.             if (node.isInteger()) {
   
9.                 m_list.push_back(node.getInteger());
   
10.             } else {
    
11.                 add(node.getList());
    
12.             }
    
13.         }
    
14.     }
    
15. public:
    
16.     NestedIterator(vector<NestedInteger> &nestedList) {
    
17.         add(nestedList);
    
18.         m_idx = 0;
    
19.     }
    
20. 
    
21.     int next() {
    
22.         return m_list[m_idx++];
    
23.     }
    
24. 
    
25.     bool hasNext() {
    
26.         return m_idx < m_list.size();
    
27.     }
    
28. };

复制代码

345. Reverse Vowels of a String

1. class Solution {
   
2. public:
   
3.     string reverseVowels(string s) {
   
4.         int i = 0, j = s.size()-1;
   
5.         unordered_set<char> vws = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
   
6.         while (i < j) {
   
7.             while (i < j && vws.count(s[i]) == 0) i++;
   
8.             while (i < j && vws.count(s[j]) == 0) j--;
   
9.             swap(s[i++], s[j--]);
   
10.         }
    
11.         return s;
    
12.     }
    
13. };

复制代码

楼主加油，坚持

388. Longest Absolute File Path

1. class Solution {
   
2. public:
   
3.     int lengthLongestPath(string input) {
   
4.         stack<int> stk;
   
5.         int level = 0;
   
6.         string tok;
   
7.         int res = 0;
   
8.         int len = 0;
   
9.         input += "\n";
   
10.         bool isFile = false;
    
11.         for (auto &c : input) {
    
12.             if (c == '\t') {
    
13.                 ++level;
    
14.                 continue;
    
15.             }
    
16.             if (c == '\n') {
    
17.                 if (!stk.empty()) {
    
18.                     // same level, and the previous folder has finished
    
19.                     while (level + 1 <= stk.size()) {
    
20.                         if (stk.size() > 1) --len; // the path sep '/'
    
21.                         len -= stk.top();
    
22.                         stk.pop();
    
23.                     }
    
24.                 }
    
25.                 if (len > 0) ++len; // the path sep '/'
    
26.                 len += tok.size();
    
27.                 if (isFile) {
    
28.                     res = max(res, len);
    
29.                 }
    
30.                 stk.push(tok.size());
    
31.                
    
32.                 isFile = false;
    
33.                 level = 0;
    
34.                 tok.clear();
    
35.                 continue;
    
36.             }
    
37.             if (c == '.') isFile = true;
    
38.             tok += c;
    
39.         }
    
40.         return res;
    
41.     }
    
42. };

复制代码

406. Queue Reconstruction by Height, medium

1. class Solution {
   
2. public:
   
3.     vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
   
4.         // sort so people with k == 0 appear first and sorted by height
   
5.         sort(people.begin(), people.end(), [](auto &a, auto &b) {
   
6.             return a.second < b.second ||
   
7.                 (a.second == b.second && a.first < b.first);
   
8.         });
   
9.         vector<pair<int, int>> res;
   
10.         int i = 0;
    
11.         while (i < people.size()) {
    
12.             auto &a = people[i];
    
13.             if (a.second == 0) {
    
14.                 res.push_back(a);
    
15.             } else {
    
16.                 auto it = res.begin();
    
17.                 int gt = a.second;
    
18.                 while (it != res.end()) {
    
19.                     if (it->first >= a.first) {
    
20.                         if (gt > 0) {
    
21.                             gt--;
    
22.                         } else {
    
23.                             break;
    
24.                         }
    
25.                     }
    
26.                     it++;
    
27.                 }
    
28.                 res.insert(it, a);
    
29.             }
    
30.             i++;
    
31.         }
    
32.         return res;
    
33.     }
    
34. };

复制代码

406. Queue Reconstruction by Height
Solution 2

1. class Solution {
   
2. public:
   
3.     vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
   
4.         // sort by height desc then by k asc
   
5.         sort(people.begin(), people.end(), [](auto &a, auto &b) {
   
6.             return a.first > b.first ||
   
7.                 (a.first == b.first && a.second < b.second);
   
8.         });
   
9.         // insert the person into their correct place.
   
10.         // because they are sorted by descending height, inserting later people don't affect people in the queue.
    
11.         vector<pair<int, int>> res;
    
12.         for (int i = 0; i < people.size(); i++) {
    
13.             res.insert(res.begin() + people[i].second, people[i]);
    
14.         }
    
15.         return res;
    
16.     }
    
17. };

复制代码

421. Maximum XOR of Two Numbers in an Array

1. class Trie {
   
2.     Trie* cb[2];
   
3.     int val;
   
4. public:
   
5.     Trie() {
   
6.         cb[0] = cb[1] = nullptr;
   
7.         val = 0;
   
8.     }
   
9.     void insert(int n) {
   
10.         Trie* p = this;
    
11.         for (int i = 30; i >= 0; i--) {
    
12.             int bit = (n & ( 1 << i)) > 0;
    
13.             if (!p->cb[bit])
    
14.                 p->cb[bit] = new Trie();
    
15.             p = p->cb[bit];
    
16.         }
    
17.         p->val = n;
    
18.     }
    
19.     int search(int n) {
    
20.         Trie* p = this;
    
21.         for (int i = 30; i >= 0; i--) {
    
22.             int bit = (n & ( 1 << i)) > 0;
    
23.             if (p->cb[!bit])
    
24.                 p = p->cb[!bit];
    
25.             else {
    
26.                 if (p->cb[bit])
    
27.                     p = p->cb[bit];
    
28.                 else
    
29.                     return 0;
    
30.             }
    
31.         }
    
32.         return p->val;
    
33.     }
    
34. };
    
35. 
    
36. class Solution {
    
37.    
    
38. public:
    
39.     int findMaximumXOR(vector<int>& nums) {
    
40.         if (nums.size() < 2) return 0;
    
41.         
    
42.         Trie root;
    
43.         root.insert(nums.front());
    
44.         int res = 0;
    
45.         for (auto &a : nums) {
    
46.             int b = root.search(a);
    
47.             res = max(res, a ^ b);
    
48.             root.insert(a);
    
49.         }
    
50.         return res;
    
51.     }
    
52. };

复制代码

448. Find All Numbers Disappeared in an Array

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

复制代码

448. Find All Numbers Disappeared in an Array
Solution 2

1. class Solution {
   
2. public:
   
3.     vector<int> findDisappearedNumbers(vector<int>& nums) {
   
4.         vector<int> res;
   
5.         for (int i = 0; i < nums.size(); i++) {
   
6.             int a = nums[i];
   
7.             if (nums[abs(a) - 1] > 0) {
   
8.                 nums[abs(a) - 1] *= -1;
   
9.             }
   
10.         }
    
11.         for (int i = 0; i < nums.size(); i++) {
    
12.             if (nums[i] > 0) {
    
13.                 res.push_back(i + 1);
    
14.             }
    
15.         }
    
16.         return res;
    
17.     }
    
18. };

复制代码