LC_HOT100

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, vector<int>> mp;
        for (int i = 0; i < (int) nums.size(); ++i) {
            mp[nums[i]].push_back(i);
        }
        for (int i = 0; i < (int) nums.size(); ++i) {
            if (nums[i] * 2 == target and mp[nums[i]].size() > 1) {
                return vector<int>{mp[nums[i]][0], mp[nums[i]][1]};
            } else if (nums[i] * 2 != target and mp.find(target - nums[i]) != mp.end()) {
                return vector<int>{mp[nums[i]][0], mp[target - nums[i]][0]};
            }
        }
        return vector<int>{};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<int>> mp;
        for (int i = 0; i < (int) strs.size(); ++i) {
            string str = strs[i];
            unordered_map<char, int> mmp;
            for (char i : str) {
                mmp[i]++;
            }
            string tmp;
            for (char i = 'a'; i <= 'z'; ++i) {
                if (mmp.find(i) != mmp.end()) {
                    int tv = mmp[i];
                    while (tv--) {
                        tmp += i;
                    }
                }
            }
            mp[tmp].push_back(i);
        }
        vector<vector<string>> ans;
        for (auto& [x, y] : mp) {
            vector<string> now;
            for (int i : y) {
                now.push_back(strs[i]);
            }
            ans.push_back(now);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> us;
        for (int i : nums) {
            us.insert(i);
        }
        int ans = 0;
        for (int i : us) {
            if (us.find(i - 1) == us.end()) {   // 序列头
                int num = 0;
                for (int j = i; ; ++j) {
                    if (us.find(j) != us.end()) {
                        num++;
                    } else {
                        ans = max(ans, num);
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = (int) nums.size();
        if (n == 0) {
            return ;
        }
        int l = 0, r = 1;
        while (r < n) {
            if (nums[l] == 0 and nums[r] != 0) {
                swap(nums[l], nums[r]);
            }
            while (l < n) {
                if (nums[l] == 0) break;
                else l++;
            }
            r = l + 1;
            while (r < n) {
                if (nums[r] != 0) break;
                else r++;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int l = 0, r = 1;
        if (n == 1) {
            return 1;
        }
        unordered_map<char, int> mp;
        mp[s[0]]++;
        int ans = 0;
        while (l < r and r <= n) {
            if (r - l > (int) mp.size()) {
                mp[s[l]]--;
                if (mp[s[l]] == 0) mp.erase(s[l]);
                l++;
            } else {
                ans = max(ans, r - l);
                if (r < n) {mp[s[r]]++; r++;}
                else break;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = (int) nums.size();
        int sum = 0;
        int ans = 0;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            int now = sum - k;
            ans += mp[now];
            mp[sum]++;
            if (sum == k) ans++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = 0;
        int ans = -(1e4 + 3);
        for (int i : nums) {
            dp = max(dp + i, i);
            ans = max(ans, dp);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = (int) matrix.size();
        int m = (int) matrix[0].size();
        bool colflag = false;
        bool rowflag = false;
        for (int i = 0; i < n; ++i) {
            if (matrix[i][0] == 0) {
                colflag = true;
                break;
            }
        }
        for (int j = 0; j < m; ++j) {
            if (matrix[0][j] == 0) {
                rowflag = true;
                break;
            }
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < n; ++i) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < m; ++j) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 1; j < m; ++j) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < n; ++i) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowflag) {
            for (int j = 0; j < m; ++j) {
                matrix[0][j] = 0;
            }
        }
        if (colflag) {
            for (int i = 0; i < n; ++i) {
                matrix[i][0] = 0;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len1 = 0, len2 = 0;
        auto ptr1 = headA, ptr2 = headB;
        while (ptr1 != nullptr) {
            len1++;
            ptr1 = ptr1->next;
        }
        while (ptr2 != nullptr) {
            len2++;
            ptr2 = ptr2->next;
        }
        if (len1 > len2) {
            auto dif = len1 - len2;
            while (dif--) {
                headA = headA->next;
            }
        }
        if (len1 < len2) {
            auto dif = len2 - len1;
            while (dif--) {
                headB = headB->next;
            }
        }
        while (headA != nullptr) {
            if (headA == headB) {
                return headA;
            } else {
                headA = headA->next;
                headB = headB->next;
            }
        }
        return nullptr;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        function<void(TreeNode*)> dfs = [&](TreeNode* node) {
            if (node == nullptr) return;
            if (node->left != nullptr) dfs(node->left);
            ans.push_back(node->val);
            if (node->right != nullptr) dfs(node->right);
        };
        dfs(root);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        stack<TreeNode*> st;
        auto cnt = root;
        while (cnt != nullptr || !st.empty()) { //!st.empty() 是关键
            while (cnt != nullptr) {	// 一直找左节点并入栈
                st.emplace(cnt);
                cnt = cnt->left;
            }
            cnt = st.top();
            st.pop();
            ans.push_back(cnt->val);	// 取出，打印节点
            cnt = cnt->right; //去右节点，然后再一直找左节点
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = (int) grid.size();
        int m = (int) grid[0].size();
        int ans = 0;
        int dir[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        function<void(int, int)> dfs = [&](int x, int y) {
            grid[x][y] = '2';
            for (int k = 0; k < 4; ++k) {
                int tx = x + dir[k][0], ty = y + dir[k][1];
                if (tx >= 0 and tx < n and ty >= 0 and ty < m and grid[tx][ty] == '1') dfs(tx, ty);
            }
        };
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = (int) nums.size();
        function<void(int)> dfs = [&](int pos) {
            if (pos == n) {
                ans.emplace_back(nums);
                return ;
            }
            for (int i = pos; i < n; ++i) {	// 注意从pos开始遍历
                swap(nums[pos], nums[i]);
                dfs(pos + 1);	// 从下一个数开始
                swap(nums[pos], nums[i]);
            }
        };
        dfs(0);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = (int) nums.size();
        function<void(int)> dfs = [&](int pos) {
            if (pos == n) {
                ans.emplace_back(nums);
                return ;
            }
            unordered_set<int> s; //让它不出现5，6，6交换两次的情况，如果是5，5，5也不会重复交换
            for (int i = pos; i < n; ++i) {
                if (s.find(nums[i]) == s.end()) {
                    s.insert(nums[i]);
                    swap(nums[i], nums[pos]);
                    dfs(pos + 1);
                    swap(nums[i], nums[pos]);
                }
            }
        };
        dfs(0);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int l = 0, r = 1;
        unordered_map<char, int> mp;
        mp[s[0]] = 1;
        int ans = 0;
        while (r <= n and l < r) {
            if (r - l != (int) mp.size()) {
                mp[s[l]]--;
                if (mp[s[l]] == 0) mp.erase(s[l]);
                l++;
            } else {
                ans = max(ans, r - l);
                //if (r < n) // infinite loop
                {mp[s[r]]++; r++;}
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

class LRUCache {
private:
    struct DLinkedList {
        int key, value;
        DLinkedList* prev;
        DLinkedList* next;
        DLinkedList() : key(0), value(0), prev(nullptr), next(nullptr) {}
        DLinkedList(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    unordered_map<int, DLinkedList*> mp;
    size_t sz;
    size_t cap;
    DLinkedList* head, *tail;
public:
    LRUCache(int capacity) : cap(capacity), sz(0) {
        head = new DLinkedList();
        tail = new DLinkedList();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (mp.find(key) != mp.end()) {
            auto node = mp[key];
            deleteNode(node);
            addHead(node);
            return node->value;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        if (mp.find(key) != mp.end()) {
            auto node = mp[key];
            node->value = value;
            deleteNode(node);
            addHead(node);
        } else {
            auto node = new DLinkedList(key, value);
            mp[key] = node;
            addHead(node);
            sz++;
            if (sz > cap) {
                removeTail();
                sz--;
            } 
        }
    }
    
    void removeTail() {
        auto node = tail->prev;
        node->prev->next = tail;
        tail->prev = node->prev;
        mp.erase(node->key);	// 别忘了这一步
        delete node;
    }
    
    void deleteNode(DLinkedList* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    void addHead(DLinkedList* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for (int i : nums) {
            mp[i]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        for (auto& [x, y] : mp) {
            if ((int) pq.size() < k) {
                pq.emplace(y, x);
            } else {
                if (y > pq.top().first) {
                    pq.pop();
                    pq.emplace(y, x);
                }
            }
        }
        vector<int> ans;
        while (!pq.empty()) {
            ans.emplace_back(pq.top().second);
            pq.pop();
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        int n = (int) words.size();
        unordered_map<string, int> mp;
        for (const string& i : words) {
            mp[i]++;
        }
        struct cmp {
            bool operator() (const pair<string, int>& p1, const pair<string, int>& p2) const {
                if (p1.second == p2.second) return p1.first < p2.first;
                return p1.second > p2.second;
            }
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;
        for (auto& [x, y] : mp) {
            pq.emplace(x, y);
            if ((int) pq.size() > k) {
                pq.pop();
            }
        }
        vector<string> ans;
        while (!pq.empty()) {
            auto& [x, _] = pq.top();
            ans.emplace_back(x);
            pq.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reverse(ListNode* head, ListNode* tail) {
        ListNode* l, *m, *r;
        l = nullptr;
        m = head;
        r = m->next;
        while (l != tail) {
            m->next = l;
            l = m;
            m = r;
            if (r == nullptr) break;
            r = r->next;
        } 
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre, *start, *end, *nxt;
        pre = dummy;
        start = pre->next;
        while (start != nullptr) {
            end = pre;
            for (int i = 0; i < k and end != nullptr; ++i) {
                end = end->next;
            }
            if (end == nullptr) break;
            nxt = end->next;
            reverse(start, end);
            pre->next = end;	// 注意这部分代码
            start->next = nxt;	//
            pre = start; //
            start = nxt; //
        }
        return dummy->next;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int) nums.size();
        const int inf = 0x3f3f3f3f;
        vector<int> dp((size_t) n, inf);	//注意初始化
        for (int i = 0; i < n; ++i) {
            *lower_bound(dp.begin(), dp.end(), nums[i]) = nums[i];
        }
        return lower_bound(dp.begin(), dp.end(), inf) - dp.begin();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int findKthSmallest(vector<int>&nums, int l, int r, int k) {
        int ptrl = l, ptrr = r, x = nums[l];
        if (l < r) {
            while (ptrl < ptrr) {
                while (nums[ptrl] <= x and ptrl < r) ptrl++;
                while (nums[ptrr] >= x and ptrr > l) ptrr--;
                if (ptrl < ptrr) swap(nums[ptrl], nums[ptrr]);
            }
            swap(nums[ptrr], nums[l]);
            if (ptrr == k) return nums[ptrr];	// 注意这里的k是对整个数组而言
            if (ptrr > k) return findKthSmallest(nums, l, ptrr - 1, k);
            else return findKthSmallest(nums, ptrr + 1, r, k);
        }
        return nums[k];	// 注意这里返回nums[k]，而不是随意返回
    }
    int findKthLargest(vector<int>& nums, int k) {
        mt19937 rng{random_device{}()};
        shuffle(nums.begin(), nums.end(), rng);
        int n = (int) nums.size();
        return findKthSmallest(nums, 0, n - 1, n - k);	// 注意n - k不是k
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] > target) r = mid - 1;
            else l = mid + 1; 
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    bool isValid(string ss) {
        stack<char> st;
        for (char i : ss) {
            if (i == '(' or i == '[' or i == '{') st.push(i);
            else if (i == ')') {
                if (st.empty() or st.top() != '(') {
                    return false;
                } else {
                    st.pop();
                }
            } 
            else if (i == ']') {
                if (st.empty() or st.top() != '[') {
                    return false;
                } else {
                    st.pop();
                }
            } else {
                if (st.empty() or st.top() != '{') {
                    return false;
                } else {
                    st.pop();
                }
            }
        }
        return st.empty();	// 注意这里
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> sufmax(n);
        sufmax[n - 1] = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            sufmax[i] = max(sufmax[i + 1], prices[i]);
        }
        int ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            ans = max(ans, sufmax[i + 1] - prices[i]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        const int MAX = amount + 3;
        vector<int> dp(MAX, MAX);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == MAX ? -1 : dp[amount];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> mp, mpp;
        for (char i = 'a'; i <= 'z'; i++) {	//预热
            mp[i] = 0;
            mpp[i] = 0;
        }
        vector<int> ans;
        int ns = s.length();
        int np = p.length();
        for (int i = 0; i < np; ++i) {
            mp[s[i]]++;
        }
        for (char i : p) {
            mpp[i]++;
        } 
        int ind = np;
        while (ind <= ns) {
            bool ok = true;
            for (char i = 'a'; i <= 'z'; i++) {
                if (mp[i] != mpp[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) ans.push_back(ind - np);
            mp[s[ind]]++;
            mp[s[ind - np]]--;
            ind++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        int n = nums.size(); 
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (!dq.empty() and dq.front() <= i - k) {
                dq.pop_front();
            }
            while (!dq.empty() and nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }
            dq.push_back(i);
            if (i >= k - 1) {
                ans.push_back(nums[dq.front()]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<pair<int, int>> v;
        for (auto& i : intervals) {
            v.emplace_back(i[0], i[1]);
            //cout << i[0] << ' ' << i[1] << '\n';
        }
        sort(v.begin(), v.end());
        vector<pair<int, int>> ans;
        int n = v.size();
        ans.emplace_back(v[0].first, v[0].second);
        for (int i = 1; i < n; i++) {
            auto [l, r] = v[i];
            auto [prel, prer] = ans.back();
            //cout << l << ' ' << r << ' ' << prel << ' ' << prer ;
            if (prer < l) {
                ans.emplace_back(l, r);
            } else {
                ans.pop_back();
                ans.emplace_back(min(l, prel), max(r, prer));
            }
        }
        vector<vector<int>> fans;
        for (auto& [i, j] : ans) {
            fans.push_back(vector<int>{i, j});
        }
        return fans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int dir[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int now = 0;
        int x = 0, y = 0;
        int n = matrix.size(), m = matrix[0].size();
        bool step = true;
        while ((int) ans.size() < n * m) {
            if (step) {
                ans.push_back(matrix[x][y]);
                matrix[x][y] = -1000;
            }
            int tx = x + dir[now][0], ty = y + dir[now][1];
            if (tx >= 0 and tx < n and ty >= 0 and ty < m and matrix[tx][ty] != -1000) {
                x = tx; y = ty;
                step = true;
            } else {
                now++;
                now %= 4;
                step = false;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) {
            return vector<vector<int>>{};
        }
        queue<pair<TreeNode*, int>> q;
        vector<vector<int>> ans;
        q.emplace(root, 0);
        int now = -1;
        vector<int> tmp;
        bool ok = true;
        while (!q.empty()) {
            auto [node, depth] = q.front(); // 不能写auto& 
            q.pop(); 
            if (depth > now) {
                now = depth;
                if (!ok) ans.push_back(tmp);
                tmp.clear();
                ok = false;
            }
            tmp.push_back(node->val);
            if (node->left != nullptr) {
                q.emplace(node->left, depth + 1);
            }
            if (node->right != nullptr) {
                q.emplace(node->right, depth + 1);
            }
        }
        ans.push_back(tmp);
        return ans;
    }
};