杨记

碎片化学习令人焦虑，系统化学习使人进步

0%

LeetCode题

发表于 更新于 分类于

我刷过的力扣题，我的答案和官方答案

两数之和

1. 两数之和 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashTable;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hashTable.count(target - nums[i]) > 0)
            {
                return {hashTable[target - nums[i]], i};
            }
            hashTable.insert(make_pair(nums[i], i));
        }
        return {};
    }
};

两数相加

2. 两数相加 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
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
/**
 * 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:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = nullptr, * tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            }
            else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
            carry = sum / 10;
        }
        if (carry) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
};

无重复字符的最长字串

3. 无重复字符的最长子串 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        int pos = 0; 
        int len = 0;
        for(int i = 0; i < s.size(); i++) {
            int sub = s.find(s[i], pos);
            if(sub != i) {
                len = i - pos;
                maxLen = (maxLen > len ? maxLen : len);
                pos = sub + 1;
            }
        }
        len = s.size() - pos;
        maxLen = (maxLen > len ? maxLen : len);
        return maxLen;
    }
};

寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() < nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int num = nums1.size() + nums2.size();  
        bool isOdd = num % 2;  
        int k = num / 2;  //pos1 + pos2 == k或k+1
        if(isOdd) k++; // pos1-1 pos2-1     pos1 pos2
        int pos1 = k, pos2 = 0;
        int maxLeft = 0, minRight = INT_MAX;
        while(pos2 <= nums2.size()) {
            if(pos2 == 0) {
                maxLeft = nums1[pos1 - 1];
            }
			else if(pos1 == 0) {
                maxLeft = nums2[pos2 - 1]; 
            }
            else {
                maxLeft = (nums1[pos1 - 1] > nums2[pos2 - 1] ? nums1[pos1 - 1] : nums2[pos2 - 1]);
            }

            if(pos1 == nums1.size() && pos2 != nums2.size()) {
                minRight = nums2[pos2];
            }
            else if(pos1 != nums1.size() && pos2 != nums2.size()) {
                minRight = (nums1[pos1] < nums2[pos2] ? nums1[pos1] : nums2[pos2]);
            }
			else if(pos1 != nums1.size() && pos2 == nums2.size()) {
                minRight = nums1[pos1];
            }

            if(maxLeft <= minRight) break;
            pos1--;
            pos2++;
        }

        if(isOdd) return maxLeft;
        else return (maxLeft + minRight) / 2.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
//官方答案
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;
        // median1：前一部分的最大值
        // median2：后一部分的最小值
        int median1 = 0, median2 = 0;

        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);
            int nums_i = (i == m ? INT_MAX : nums1[i]);
            int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);
            int nums_j = (j == n ? INT_MAX : nums2[j]);

            if (nums_im1 <= nums_j) {
                median1 = max(nums_im1, nums_jm1);
                median2 = min(nums_i, nums_j);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
};

最长回文子串

5. 最长回文子串 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "ac"
输出："a"
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
class Solution {
public:
    string longestPalindrome(string s) {
        int pos = 0;
        int maxLen = 0;
        for(int i = 0; i < s.size(); i++) {
            int len = 0;
            for(int j = s.size() - 1; j >= i; j--) {
                int flag = 1;
                int p = i;
                for(int k = j; k >= i; k--, p++) {
                    if(s[p] != s[k]) {
                        flag = 0;
                        break;
                    }
                }
                if(flag) {
                    len = j - i + 1;
                    break;
                }
            }
            if(len > maxLen) {
                pos = i;
                maxLen = len;
            }
        }
        return s.substr(pos, maxLen);
    }
};
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
// 官方答案，真的强，回文扩展中心
class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

Z字形变换

6. Z 字形变换 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
输入：s = "A", numRows = 1
输出："A"

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I
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
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        
        string cs = "";
        int add = 2 * numRows - 2;
        for(int i = 0; i < numRows; i++) {
            if(i == 0 || i + 1 == numRows) {
                for(int j = i; j < s.size(); j = j + add) {
                    cs += s[j];
                }
            } else {
                int j = i;
                int add2 = 2 * i;
                int add1 = add - add2;
                bool flag = true;
                while(j < s.size()) {
                    cs += s[j];
                    if(flag) j += add1;
                    else j += add2;
                    flag = !flag;
                }
            }
        }
        return cs;
    }
};

整数反转

7. 整数反转 - 力扣（LeetCode） (leetcode-cn.com)

反转后整数超过 32 位的有符号整数的范围 [$−2^{31}$, $2^{31}$ − 1] ，就返回 0

1
2
3
4
5
输入：x = -123
输出：-321

输入：x = 120
输出：21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//官方答案
class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
};

字符串转换整数(atoi)

8. 字符串转换整数 (atoi) - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：s = "42"
输出：42

输入：s = "   -42"
输出：-42

输入：s = "4193 with words"
输出：4193

输入：s = "words and 987"
输出：0

输入：s = "-91283472332"
输出：-2147483648
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
// "words and 987"  输出 987   要求没搞清楚
class Solution {
public:
    int myAtoi(string s) {
        long re = 0;
        int flag = 0; // 0 正数  1 负数
        int i = 0;
        for(; i < s.size(); i++) {
            if(s[i] <= '9' && s[i] >= '0') break;
            
            if((s[i] == '-' || s[i] == '+') && i < s.size()) {
                ++i;
                if(s[i] > '9' && s[i] < '0') return re;
                flag = s[i - 1] == '+' ? 0 : 1;
                break;
            }
        }
        while(s[i] <= '9' && s[i] >= '0' && i < s.size()) {
            re = re * 10 + s[i] - '0';
            i++;
        }
        if(re > INT_MAX) return INT_MAX;
        if(re < INT_MIN) return INT_MIN;
        return flag == 0 ? re : -re;
    }
};

// -----------------------

class Solution {
public:
    int myAtoi(string s) {
        long re = 0;
        int flag = 0; // 0 正数  1 负数
        int i = 0;
        for(; i < s.size(); i++) {
            if(s[i] == ' ') continue;
            else if((s[i] == '-' || s[i] == '+') && i < s.size()) {
                flag = s[i] == '+' ? 0 : 1;
                ++i;
                break;
            }
            else if(s[i] <= '9' && s[i] >= '0') break;
            else return re;
        }
        while(s[i] <= '9' && s[i] >= '0' && i < s.size()) {
            if(flag) {
                re = re * 10 - s[i] + '0';
                if(re < INT_MIN) return INT_MIN;
            } else {
                re = re * 10 + s[i] - '0';
                if(re > INT_MAX) return INT_MAX;
            }
            i++;
        }
        return re;
    }
};
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
// 官方答案，有穷自动机DFA，厉害
class Automaton {
    string state = "start";
    unordered_map<string, vector<string>> table = {
        {"start", {"start", "signed", "in_number", "end"}},
        {"signed", {"end", "end", "in_number", "end"}},
        {"in_number", {"end", "end", "in_number", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };

    int get_col(char c) {
        if (isspace(c)) return 0;
        if (c == '+' or c == '-') return 1;
        if (isdigit(c)) return 2;
        return 3;
    }
public:
    int sign = 1;
    long long ans = 0;

    void get(char c) {
        state = table[state][get_col(c)];
        if (state == "in_number") {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
        }
        else if (state == "signed")
            sign = c == '+' ? 1 : -1;
    }
};

class Solution {
public:
    int myAtoi(string str) {
        Automaton automaton;
        for (char c : str)
            automaton.get(c);
        return automaton.sign * automaton.ans;
    }
};

回文数

9. 回文数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

输入：x = 121
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0 || (x % 10 == 0 && x != 0)) return false;
        if(x < 10) return true;
        int rev = 0;
        while(rev < x) {
            rev = rev * 10 + x % 10;
            if(rev == x) return true;
            x /= 10;
        }
        return rev == x;
    }
};
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:
    bool isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
};

正则表达式匹配

10. 正则表达式匹配 - 力扣（LeetCode） (leetcode-cn.com)

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
// 官方答案
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();

        auto matches = [&](int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };

        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] |= f[i][j - 2];
                    if (matches(i, j - 1)) {
                        f[i][j] |= f[i - 1][j];
                    }
                }
                else {
                    if (matches(i, j)) {
                        f[i][j] |= f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
};

盛最多水的容器

11. 盛最多水的容器 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 官方答案，双指针
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
};

整数转罗马数字

12. 整数转罗马数字 - 力扣（LeetCode） (leetcode-cn.com)

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
// 官方答案一
const pair<int, string> valueSymbols[] = {
    {1000, "M"},
    {900,  "CM"},
    {500,  "D"},
    {400,  "CD"},
    {100,  "C"},
    {90,   "XC"},
    {50,   "L"},
    {40,   "XL"},
    {10,   "X"},
    {9,    "IX"},
    {5,    "V"},
    {4,    "IV"},
    {1,    "I"},
};

class Solution {
public:
    string intToRoman(int num) {
        string roman;
        for (const auto &[value, symbol] : valueSymbols) {
            while (num >= value) {
                num -= value;
                roman += symbol;
            }
            if (num == 0) {
                break;
            }
        }
        return roman;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
// 官方答案二
const string thousands[] = {"", "M", "MM", "MMM"};
const string hundreds[]  = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string tens[]      = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string ones[]      = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

class Solution {
public:
    string intToRoman(int num) {
        return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
    }
};

罗马数字转整数

13. 罗马数字转整数 - 力扣（LeetCode） (leetcode-cn.com)

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
// 官方答案
class Solution {
private:
    unordered_map<char, int> symbolValues = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };

public:
    int romanToInt(string s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues[s[i]];
            if (i < n - 1 && value < symbolValues[s[i + 1]]) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
};

最长公共前缀

14. 最长公共前缀 - 力扣（LeetCode） (leetcode-cn.com)

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:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        string prefix = strs[0];
        int count = strs.size();
        for (int i = 1; i < count; ++i) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (!prefix.size()) {
                break;
            }
        }
        return prefix;
    }

    string longestCommonPrefix(const string& str1, const string& str2) {
        int length = min(str1.size(), str2.size());
        int index = 0;
        while (index < length && str1[index] == str2[index]) {
            ++index;
        }
        return str1.substr(0, index);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 官方答案二，纵向扫描
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        int length = strs[0].size();
        int count = strs.size();
        for (int i = 0; i < length; ++i) {
            char c = strs[0][i];
            for (int j = 1; j < count; ++j) {
                if (i == strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[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
// 官方答案三，分治
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        else {
            return longestCommonPrefix(strs, 0, strs.size() - 1);
        }
    }

    string longestCommonPrefix(const vector<string>& strs, int start, int end) {
        if (start == end) {
            return strs[start];
        }
        else {
            int mid = (start + end) / 2;
            string lcpLeft = longestCommonPrefix(strs, start, mid);
            string lcpRight = longestCommonPrefix(strs, mid + 1, end);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    string commonPrefix(const string& lcpLeft, const string& lcpRight) {
        int minLength = min(lcpLeft.size(), lcpRight.size());
        for (int i = 0; i < minLength; ++i) {
            if (lcpLeft[i] != lcpRight[i]) {
                return lcpLeft.substr(0, i);
            }
        }
        return lcpLeft.substr(0, minLength);
    }
};
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
// 官方答案四，二分查找
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        int minLength = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size();
        int low = 0, high = minLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isCommonPrefix(strs, mid)) {
                low = mid;
            }
            else {
                high = mid - 1;
            }
        }
        return strs[0].substr(0, low);
    }

    bool isCommonPrefix(const vector<string>& strs, int length) {
        string str0 = strs[0].substr(0, length);
        int count = strs.size();
        for (int i = 1; i < count; ++i) {
            string str = strs[i];
            for (int j = 0; j < length; ++j) {
                if (str0[j] != str[j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

三数之和

15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)

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:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() == 0) return res;
        sort(nums.begin(), nums.end());
        vector<int>::iterator sep = find_if(nums.begin(), nums.end(), [&](int x){ return x >= 0; });

        for(vector<int>::iterator left = nums.begin(); left <= sep; ++left) {
            if(left > nums.begin() && *left == *(left - 1)) continue;
            vector<int>::iterator right = nums.end() - 1;
            int target = -(*left);
            for(vector<int>::iterator mid = left + 1; mid < nums.end() - 1; ++mid) {
                if(mid > left + 1 && *mid == *(mid - 1)) continue;
                while(mid < right && *mid + *right > target) --right;
                if(mid == right) break;
                if(*mid + *right == target) {
                    res.push_back({*left, *mid, *right});
                }
            }
        }
        return res;
    }
};
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
// 官方答案，排序+双指针
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

最接近的三数之和

16. 最接近的三数之和 - 力扣（LeetCode） (leetcode-cn.com)

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:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int best = 1e7;

        // 根据差值的绝对值来更新答案
        auto update = [&](int cur) {
            if (abs(cur - target) < abs(best - target)) {
                best = cur;
            }
        };

        // 枚举 a
        for (int i = 0; i < n; ++i) {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                update(sum);
                if (sum > target) {
                    // 如果和大于 target，移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target，移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
};

电话号码的字母组合

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> letterCombinations(string digits) {
        vector<string> combina;
        if(digits.size() == 0) return combina;
        map<char,string> letter = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        for(int i = 0; i < letter[digits[0]].size(); ++i) {
            combina.push_back(letter[digits[0]].substr(i, 1));
        }
        for(int i = 1; i < digits.size(); ++i) {
            char c = digits[i];
            vector<string> temp(combina);
            combina.clear();
            for(int j = 0; j < temp.size(); ++j) {
                for(int k = 0; k < letter[c].size(); ++k) {
                    combina.push_back(temp[j] + letter[c][k]);
                }
            }
        }
        return combina;
    }
};
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
// 官方答案，回溯
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> combinations;
        if (digits.empty()) {
            return combinations;
        }
        unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string combination;
        backtrack(combinations, phoneMap, digits, 0, combination);
        return combinations;
    }

    void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
        if (index == digits.length()) {
            combinations.push_back(combination);
        } else {
            char digit = digits[index];
            const string& letters = phoneMap.at(digit);
            for (const char& letter: letters) {
                combination.push_back(letter);
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};

四数之和

18. 四数之和 - 力扣（LeetCode） (leetcode-cn.com)

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int first = 0; first < n - 3; ++first) {
            if(first > 0 && nums[first] == nums[first - 1]) continue;
            for(int second = first + 1; second < n - 2; ++second) {
                if(second > first + 1 && nums[second] == nums[second - 1]) continue;
                int fourth = n - 1, third = second + 1;
                int need = target - nums[first] - nums[second];
                while(third < fourth) {
                    if(third > second + 1 && nums[third] == nums[third - 1]) {
                        ++third;
                        continue;
                    }
                    if(nums[third] + nums[fourth] < need) { 
                        ++third; 
                    }
                    else if(nums[third] + nums[fourth] > need) {
                        --fourth;
                    }
                    else {
                        vector<int> temp = {nums[first], nums[second], nums[third], nums[fourth]};
                        result.push_back(temp);
                        ++third;
                        --fourth;
                    }
                }
            }
        }
        return result;
    }
};
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
// 官方答案，排序+双指针
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> quadruplets;
        if (nums.size() < 4) {
            return quadruplets;
        }
        sort(nums.begin(), nums.end());
        int length = nums.size();
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
};

删除链表的倒数第N个结点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * 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:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* tail = head;
        int length = 0;
        while(tail) {
            ++length;
            tail = tail->next;
        }
        ListNode* remove = new ListNode(0, head); 
        ListNode* nullHead = remove;
        for(int pos = 0; pos < length - n; ++pos) {
            remove = remove->next;
        }
        remove->next = remove->next->next;
        return nullHead->next;
    }
};
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 getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head); // 哑结点，其next指向链表头head
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        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:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        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:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        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:
    bool isValid(string s) {
        auto brackets = [&](char c) {
            switch(c) {
                case '}': return '{';
                case ']': return '[';
                case ')': return '(';
                default : return '\0';
            }
        };
        stack<char> stk;
        stk.push(s[0]);
        for(int i = 1; i < s.size(); ++i) {
            if(!stk.empty() && brackets(s[i]) == stk.top()) stk.pop();
            else stk.push(s[i]);
        }
        return stk.empty();
    }
};
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
// 官方答案，栈
class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

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 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:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *merge = new ListNode();
        ListNode *head = merge;
        while(list1 != nullptr && list2 != nullptr) {
            if(list1->val < list2->val) {
                merge->next = list1;
                list1 = list1->next;
            }
            else {
                merge->next = list2;
                list2 = list2->next;
            }
            merge = merge->next;
        }
        if(list1 != nullptr) merge->next = list1;
        else merge->next = list2;
        return head->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//官方答案，递归
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};
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:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(-1);

        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;

        return preHead->next;
    }
};

括号生成

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
//官方答案，暴力法递归
class Solution {
    bool valid(const string& str) {
        int balance = 0;
        for (char c : str) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    void generate_all(string& current, int n, vector<string>& result) {
        if (n == current.size()) {
            if (valid(current)) {
                result.push_back(current);
            }
            return;
        }
        current += '(';
        generate_all(current, n, result);
        current.pop_back();
        current += ')';
        generate_all(current, n, result);
        current.pop_back();
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        generate_all(current, n * 2, result);
        return result;
    }
};
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 {
    void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
        if (cur.size() == n * 2) {
            ans.push_back(cur);
            return;
        }
        if (open < n) {
            cur.push_back('(');
            backtrack(ans, cur, open + 1, close, n);
            cur.pop_back();
        }
        if (close < open) {
            cur.push_back(')');
            backtrack(ans, cur, open, close + 1, n);
            cur.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
};
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 {
    shared_ptr<vector<string>> cache[100] = {nullptr};
public:
    shared_ptr<vector<string>> generate(int n) {
        if (cache[n] != nullptr)
            return cache[n];
        if (n == 0) {
            cache[0] = shared_ptr<vector<string>>(new vector<string>{""});
        } else {
            auto result = shared_ptr<vector<string>>(new vector<string>);
            for (int i = 0; i != n; ++i) {
                auto lefts = generate(i);
                auto rights = generate(n - i - 1);
                for (const string& left : *lefts)
                    for (const string& right : *rights)
                        result -> push_back("(" + left + ")" + right);
            }
            cache[n] = result;
        }
        return cache[n];
    }
    vector<string> generateParenthesis(int n) {
        return *generate(n);
    }
};

合并K个升序链表

23. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * 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:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        int lists_num = lists.size();
        ListNode* head = new ListNode(0, lists[0]);
        for(int i = 1; i < lists_num; ++i) {
            ListNode* front_of_tail = head; //指向空头，tail的前一个结点
            ListNode* tail = front_of_tail->next;    //front_of_tail的后一个结点
            ListNode* node = lists[i];              //要插入的结点
            while(node && tail) {        
                if(node->val < tail->val) {   //如果要插入结点值比tail的值小，插入front_of_tail和tail之间
                    front_of_tail->next = node; 
                    node = node->next;
                    front_of_tail = front_of_tail->next;
                    front_of_tail->next = tail;
                }
                else {
                    front_of_tail = front_of_tail->next;
                    tail = tail->next;
                }
            }
            if(node) front_of_tail->next = node;
        }
        return head->next;
    }
};
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:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        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
//官方答案，分治合并
class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};
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:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * 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:
    ListNode* swapPairs(ListNode* head) {
        //if(head == nullptr || head->next == nullptr) return head;
        ListNode* preHead = new ListNode(0, head);
        ListNode *preFirst = preHead, *first, *second;
        while(preFirst) {
            first = preFirst->next;
            if(first == nullptr) break;
            second = first->next;
            if(second == nullptr) break;
            preFirst->next = second;
            first->next = second->next;
            second->next = first;
            preFirst = preFirst->next->next;
        }
        return preHead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
//官方答案，递归
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//官方答案，迭代
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* temp = dummyHead;
        while (temp->next != nullptr && temp->next->next != nullptr) {
            ListNode* node1 = temp->next;
            ListNode* node2 = temp->next->next;
            temp->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            temp = node1;
        }
        return dummyHead->next;
    }
};

K个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * 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:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k == 1) return head;
        stack<ListNode*> sl;
        ListNode* newHead = reverseKG(head, k, sl);
        return newHead;
    }
    ListNode* reverseKG(ListNode* head, int &k, stack<ListNode*> &sl) {
        ListNode* temp = head;
        int num = k;
        while(--num > 0) {
            if(temp == nullptr) return head;
            sl.push(temp);
            temp = temp->next;
        }
        if(temp == nullptr) return head;
        ListNode* follow = temp->next; 
        ListNode* newHead = temp;
        while(!sl.empty()) {
            temp->next = sl.top();
            temp = temp->next;
            sl.pop(); 
        }
        temp->next = reverseKG(follow, k, sl);
        return newHead;
    }
};
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
//官方答案，模拟
class Solution {
public:
    // 翻转一个子链表，并且返回新的头与尾
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            // 这里是 C++17 的写法，也可以写成
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
            // head = result.first;
            // tail = result.second;
            tie(head, tail) = myReverse(head, tail);
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
};

删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int length = nums.size(), k = 0;
        if(length == 0) return k;
        for(int i = 1; i < length; ++i) {
            while(i < length && nums[i] == nums[i - 1]) ++i;
            if(i < length) nums[++k] = nums[i];
        }
        return ++k;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//官方答案，双指针法
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

移除元素

27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//官方答案，双指针
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//双指针优化
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
};

实现strStr()

28. 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com)

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
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle == "") return 0;
        int *next = new int[needle.size()];
        getNext(needle, next);
        int result = KMP(haystack, needle, next);
        delete[] next;
        return result;
    }

    void getNext(string &T, int *next) {
        int length = T.size(), j = 0, k = -1;
        next[j] = k;
        while(j < length - 1) {
            if(k == -1 || T[j] == T[k]) {
                ++j; ++k;
                if(T[j] != T[k]) next[j] = k;
                else next[j] = next[k];
            }
            else {
                k = next[k];
            }
        }
    }

    int KMP(string &S, string &T, int* next) {
        int i = 0, j = 0;
        int sLen = S.size(), tLen = T.size();
        while(i < sLen && j < tLen) {
            if(j == -1 || S[i] == T[j]) {
                ++i; ++j;
            }
            else j = next[j];
        }
        return j < tLen ? -1 : i - j;
    }
};
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
//官方答案，KMP
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

两数相除

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
78
79
80
81
//官方答案，二分查找
class Solution {
public:
    int divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == INT_MIN) {
            if (divisor == 1) {
                return INT_MIN;
            }
            if (divisor == -1) {
                return INT_MAX;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == INT_MIN) {
            return dividend == INT_MIN ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }
        
        // 一般情况，使用二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        bool rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        // 快速乘
        auto quickAdd = [](int y, int z, int x) {
            // x 和 y 是负数，z 是正数
            // 需要判断 z * y >= x 是否成立
            int result = 0, add = y;
            while (z) {
                if (z & 1) {
                    // 需要保证 result + add >= x
                    if (result < x - add) {
                        return false;
                    }
                    result += add;
                }
                if (z != 1) {
                    // 需要保证 add + add >= x
                    if (add < x - add) {
                        return false;
                    }
                    add += add;
                }
                // 不能使用除法
                z >>= 1;
            }
            return true;
        };
        
        int left = 1, right = INT_MAX, ans = 0;
        while (left <= right) {
            // 注意溢出，并且不能使用除法
            int mid = left + ((right - left) >> 1);
            bool check = quickAdd(divisor, mid, dividend);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == INT_MAX) {
                    break;
                }
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return rev ? -ans : 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
//官方答案，类二分查找
class Solution {
public:
    int divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == INT_MIN) {
            if (divisor == 1) {
                return INT_MIN;
            }
            if (divisor == -1) {
                return INT_MAX;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == INT_MIN) {
            return dividend == INT_MIN ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }
        
        // 一般情况，使用类二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        bool rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        vector<int> candidates = {divisor};
        // 注意溢出
        while (candidates.back() >= dividend - candidates.back()) {
            candidates.push_back(candidates.back() + candidates.back());
        }
        int ans = 0;
        for (int i = candidates.size() - 1; i >= 0; --i) {
            if (candidates[i] >= dividend) {
                ans += (1 << i);
                dividend -= candidates[i];
            }
        }

        return rev ? -ans : ans;
    }
};

下一个排列

31. 下一个排列 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//官方答案
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

阶乘后的零

172. 阶乘后的零 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
//官方答案
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {
            for (int x = i; x % 5 == 0; x /= 5) {
                ++ans;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
//官方答案
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while (n) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
};

各位相加

258. 各位相加 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int addDigits(int num) {
        int add = 0;
        while(true) {
            while(num) {
                add += num % 10;
                num /= 10;
            }
            if(add < 10) break;
            num = add;
            add = 0;
        }
        return add;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//官方答案，模拟
class Solution {
public:
    int addDigits(int num) {
        while (num >= 10) {
            int sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }
};
1
2
3
4
5
6
7
//官方答案二，妙啊，牛逼
class Solution {
public:
    int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
};

区域和检索

307. 区域和检索 - 数组可修改 - 力扣（LeetCode） (leetcode-cn.com)

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 NumArray {
private:
    vector<int> sum; // sum[i] 表示第 i 个块的元素和
    int size; // 块的大小
    vector<int> &nums;
public:
    NumArray(vector<int>& nums) : nums(nums) {
        int n = nums.size();
        size = sqrt(n);
        sum.resize((n + size - 1) / size); // n/size 向上取整
        for (int i = 0; i < n; i++) {
            sum[i / size] += nums[i];
        }
    }

    void update(int index, int val) {
        sum[index / size] += val - nums[index];
        nums[index] = val;
    }

    int sumRange(int left, int right) {
        int b1 = left / size, i1 = left % size, b2 = right / size, i2 = right % size;
        if (b1 == b2) { // 区间 [left, right] 在同一块中
            return accumulate(nums.begin() + left, nums.begin() + right + 1, 0);
        }
        int sum1 = accumulate(nums.begin() + b1 * size + i1, nums.begin() + b1 * size + size, 0);
        int sum2 = accumulate(nums.begin() + b2 * size, nums.begin() + b2 * size + i2 + 1, 0);
        int sum3 = accumulate(sum.begin() + b1 + 1, sum.begin() + b2, 0);
        return sum1 + sum2 + sum3;
    }
};
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
//官方答案，线段数
class NumArray {
private:
    vector<int> segmentTree;
    int n;

    void build(int node, int s, int e, vector<int> &nums) {
        if (s == e) {
            segmentTree[node] = nums[s];
            return;
        }
        int m = s + (e - s) / 2;
        build(node * 2 + 1, s, m, nums);
        build(node * 2 + 2, m + 1, e, nums);
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    void change(int index, int val, int node, int s, int e) {
        if (s == e) {
            segmentTree[node] = val;
            return;
        }
        int m = s + (e - s) / 2;
        if (index <= m) {
            change(index, val, node * 2 + 1, s, m);
        } else {
            change(index, val, node * 2 + 2, m + 1, e);
        }
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    int range(int left, int right, int node, int s, int e) {
        if (left == s && right == e) {
            return segmentTree[node];
        }
        int m = s + (e - s) / 2;
        if (right <= m) {
            return range(left, right, node * 2 + 1, s, m);
        } else if (left > m) {
            return range(left, right, node * 2 + 2, m + 1, e);
        } else {
            return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e);
        }
    }

public:
    NumArray(vector<int>& nums) : n(nums.size()), segmentTree(nums.size() * 4) {
        build(0, 0, n - 1, nums);
    }

    void update(int index, int val) {
        change(index, val, 0, 0, n - 1);
    }

    int sumRange(int left, int right) {
        return range(left, right, 0, 0, n - 1);
    }
};
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
//官方答案，树状数组
class NumArray {
private:
    vector<int> tree;
    vector<int> &nums;

    int lowBit(int x) {
        return x & -x;
    }

    void add(int index, int val) {
        while (index < tree.size()) {
            tree[index] += val;
            index += lowBit(index);
        }
    }

    int prefixSum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowBit(index);
        }
        return sum;
    }

public:
    NumArray(vector<int>& nums) : tree(nums.size() + 1), nums(nums) {
        for (int i = 0; i < nums.size(); i++) {
            add(i + 1, nums[i]);
        }
    }

    void update(int index, int val) {
        add(index + 1, val - nums[index]);
        nums[index] = val;
    }

    int sumRange(int left, int right) {
        return prefixSum(right + 1) - prefixSum(left);
    }
};

最小高度树

310. 最小高度树 - 力扣（LeetCode） (leetcode-cn.com)

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
//官方答案，广度优先搜索
class Solution {
public:
    int findLongestNode(int u, vector<int> & parent, vector<vector<int>>& adj) {
        int n = adj.size();
        queue<int> qu;
        vector<bool> visit(n);
        qu.emplace(u);
        visit[u] = true;
        int node = -1;
  
        while (!qu.empty()) {
            int curr = qu.front();
            qu.pop();
            node = curr;
            for (auto & v : adj[curr]) {
                if (!visit[v]) {
                    visit[v] = true;
                    parent[v] = curr;
                    qu.emplace(v);
                }
            }
        }
        return node;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }
        vector<vector<int>> adj(n);
        for (auto & edge : edges) {
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
        }
        
        vector<int> parent(n, -1);
        /* 找到与节点 0 最远的节点 x */
        int x = findLongestNode(0, parent, adj);
        /* 找到与节点 x 最远的节点 y */
        int y = findLongestNode(x, parent, adj);
        /* 求出节点 x 到节点 y 的路径 */
        vector<int> path;
        parent[x] = -1;
        while (y != -1) {
            path.emplace_back(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0) {
            return {path[m / 2 - 1], path[m / 2]};
        } else {
            return {path[m / 2]};
        }
    }
};
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
//官方答案，深度优先搜索
class Solution {
public:
    void dfs(int u, vector<int> & dist, vector<int> & parent, const vector<vector<int>> & adj) {
        for (auto & v : adj[u]) {
            if (dist[v] < 0) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                dfs(v, dist, parent, adj); 
            }
        }
    }

    int findLongestNode(int u, vector<int> & parent, const vector<vector<int>> & adj) {
        int n = adj.size();
        vector<int> dist(n, -1);
        dist[u] = 0;
        dfs(u, dist, parent, adj);
        int maxdist = 0;
        int node = -1;
        for (int i = 0; i < n; i++) {
            if (dist[i] > maxdist) {
                maxdist = dist[i];
                node = i;
            }
        }
        return node;
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }
        vector<vector<int>> adj(n);
        for (auto & edge : edges) {
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
        }
        vector<int> parent(n, -1);
        /* 找到距离节点 0 最远的节点  x */
        int x = findLongestNode(0, parent, adj);
        /* 找到距离节点 x 最远的节点  y */
        int y = findLongestNode(x, parent, adj);
        /* 找到节点 x 到节点 y 的路径 */
        vector<int> path;
        parent[x] = -1;
        while (y != -1) {
            path.emplace_back(y);
            y = parent[y];
        }
        int m = path.size();
        if (m % 2 == 0) {
            return {path[m / 2 - 1], path[m / 2]};
        } else {
            return {path[m / 2]};
        }
    }
};
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
//官方答案，拓扑排序
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }
        vector<int> degree(n);
        vector<vector<int>> adj(n);
        for (auto & edge : edges){
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        queue<int> qu;
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                qu.emplace(i);
            }
        }
        int remainNodes = n;
        while (remainNodes > 2) {
            int sz = qu.size();
            remainNodes -= sz;
            for (int i = 0; i < sz; i++) {
                int curr = qu.front();
                qu.pop();
                for (auto & v : adj[curr]) {
                    if (--degree[v] == 1) {
                        qu.emplace(v);
                    }
                }
            }
        }
        while (!qu.empty()) {
            ans.emplace_back(qu.front());
            qu.pop();
        }
        return ans;
    }
};

统计各位数字都不同的数字个数

357. 统计各位数字都不同的数字个数 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//官方答案，排列组合
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 10;
        }
        int ans = 10, cur = 9;
        for (int i = 0; i < n - 1; ++i) {
            cur *= 9 - i;
            ans += cur;
        }
        return ans;
    }
};

#

380. O(1) 时间插入、删除和获取随机元素 - 力扣（LeetCode） (leetcode-cn.com) 

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
//官方答案
class RandomizedSet {
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));
    }
    
    bool insert(int val) {
        if (indices.count(val)) {
            return false;
        }
        int index = nums.size();
        nums.emplace_back(val);
        indices[val] = index;
        return true;
    }
    
    bool remove(int val) {
        if (!indices.count(val)) {
            return false;
        }
        int index = indices[val];
        int last = nums.back();
        nums[index] = last;
        indices[last] = index;
        nums.pop_back();
        indices.erase(val);
        return true;
    }
    
    int getRandom() {
        int randomIndex = rand()%nums.size();
        return nums[randomIndex];
    }
private:
    vector<int> nums;
    unordered_map<int, int> indices;
};

迷你语法分析器

385. 迷你语法分析器 - 力扣（LeetCode） (leetcode-cn.com) 看不懂题目

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:
    int index = 0;

    NestedInteger deserialize(string s) {
        if (s[index] == '[') {
            index++;
            NestedInteger ni;
            while (s[index] != ']') {
                ni.add(deserialize(s));
                if (s[index] == ',') {
                    index++;
                }
            }
            index++;
            return ni;
        } else {
            bool negative = false;
            if (s[index] == '-') {
                negative = true;
                index++;
            }
            int num = 0;
            while (index < s.size() && isdigit(s[index])) {
                num = num * 10 + s[index] - '0';
                index++;
            }
            if (negative) {
                num *= -1;
            }
            return NestedInteger(num);
        }
    }
};

字典序排数

386. 字典序排数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//官方答案，迭代实现DFS
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ret(n);
        int number = 1;
        for (int i = 0; i < n; i++) {
            ret[i] = number;
            if (number * 10 <= n) {
                number *= 10;
            } else {
                while (number % 10 == 9 || number + 1 > n) {
                    number /= 10;
                }
                number++;
            }
        }
        return ret;
    }
};

文件的最长绝对路径

388. 文件的最长绝对路径 - 力扣（LeetCode） (leetcode-cn.com)

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
//官方答案
class Solution {
public:
    int lengthLongestPath(string input) {
        int n = input.size();
        int pos = 0;
        int ans = 0;
        stack<int> st;

        while (pos < n) {
            /* 检测当前文件的深度 */
            int depth = 1;
            while (pos < n && input[pos] == '\t') {
                pos++;
                depth++;
            }
            /* 统计当前文件名的长度 */   
            int len = 0; 
            bool isFile = false;     
            while (pos < n && input[pos] != '\n') {
                if (input[pos] == '.') {
                    isFile = true;
                }
                len++;
                pos++;
            }
            /* 跳过换行符 */
            pos++;

            while (st.size() >= depth) {
                st.pop();
            }
            if (!st.empty()) {
                len += st.top() + 1;
            }
            if (isFile) {
                ans = max(ans, len);
            } else {
                st.emplace(len);
            }
        }
        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
//官方答案
class Solution {
public:
    int lengthLongestPath(string input) {
        int n = input.size();
        int pos = 0;
        int ans = 0;
        vector<int> level(n + 1);

        while (pos < n) {
            /* 检测当前文件的深度 */
            int depth = 1;
            while (pos < n && input[pos] == '\t') {
                pos++;
                depth++;
            }
            /* 统计当前文件名的长度 */   
            int len = 0; 
            bool isFile = false;     
            while (pos < n && input[pos] != '\n') {
                if (input[pos] == '.') {
                    isFile = true;
                }
                len++;
                pos++;
            }
            /* 跳过换行符 */
            pos++;

            if (depth > 1) {
                len += level[depth - 1] + 1;
            }
            if (isFile) {
                ans = max(ans, len);
            } else {
                level[depth] = len;
            }
        }
        return ans;
    }
};

UTF-8编码验证

393. UTF-8 编码验证 - 力扣（LeetCode） (leetcode-cn.com)

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:
    bool validUtf8(vector<int>& data) {
        int length = data.size();
        for(int i = 0; i < length;) {
            int flag = 128, pos = 0;
            while(data[i] & flag) { 
                ++pos; 
                flag = flag >> 1 //4ms，改成flag /= 2;8ms
            }
            if(pos == 0) { 
                ++i; 
                continue; 
            }
            if(pos == 1 || pos > 4 || length - i < pos) return false;
            ++i;
            bool isFalse = false;
            for(int j = 1; j < pos; ++j, ++i) {
                if(!(data[i] & 128) || (data[i] & 64)) {
                    isFalse = true;
                }
            }
            if(isFalse) return false;
        }
        return true;
    }
};
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
//官方答案
class Solution {
public:
    static const int MASK1 = 1 << 7;
    static const int MASK2 = (1 << 7) + (1 << 6);

    bool isValid(int num) {
        return (num & MASK2) == MASK1;
    }

    int getBytes(int num) {
        if ((num & MASK1) == 0) {
            return 1;
        }
        int n = 0;
        int mask = MASK1;
        while ((num & mask) != 0) {
            n++;
            if (n > 4) {
                return -1;
            }
            mask >>= 1;
        }
        return n >= 2 ? n : -1;
    }

    bool validUtf8(vector<int>& data) {
        int m = data.size();
        int index = 0;
        while (index < m) {
            int num = data[index];
            int n = getBytes(num);
            if (n < 0 || index + n > m) {
                return false;
            }
            for (int i = 1; i < n; i++) {
                if (!isValid(data[index + i])) {
                    return false;
                }
            }
            index += n;
        }
        return true;
    }
};

旋转函数

396. 旋转函数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//官方答案
class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int f = 0, n = nums.size();
        int numSum = accumulate(nums.begin(), nums.end(), 0);
        for (int i = 0; i < n; i++) {
            f += i * nums[i];
        }
        int res = f;
        for (int i = n - 1; i > 0; i--) {
            f += numSum - n * nums[i];
            res = max(res, f);
        }
        return res;
    }
};

随机数索引

398. 随机数索引 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//官方答案，哈希表
class Solution {
    unordered_map<int, vector<int>> pos;
public:
    Solution(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            pos[nums[i]].push_back(i);
        }
    }

    int pick(int target) {
        auto &indices = pos[target];
        return indices[rand() % indices.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//官方答案，水塘抽样
class Solution {
    vector<int> &nums;
public:
    Solution(vector<int> &nums) : nums(nums) {}

    int pick(int target) {
        int ans;
        for (int i = 0, cnt = 0; i < nums.size(); ++i) {
            if (nums[i] == target) {
                ++cnt; // 第 cnt 次遇到 target
                if (rand() % cnt == 0) {
                    ans = i;
                }
            }
        }
        return ans;
    }
};

太平洋大西洋水流问题

417. 太平洋大西洋水流问题 - 力扣（LeetCode） (leetcode-cn.com) 

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
//官方答案，深度优先遍历
static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class Solution {
public:
    vector<vector<int>> heights;

    void dfs(int row, int col, vector<vector<bool>> & ocean) {
        int m = ocean.size();
        int n = ocean[0].size();
        if (ocean[row][col]) {
            return;
        }
        ocean[row][col] = true;
        for (int i = 0; i < 4; i++) {
            int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
                dfs(newRow, newCol, ocean);
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        this->heights = heights;
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacific);
        }
        for (int j = 1; j < n; j++) {
            dfs(0, j, pacific);
        }
        for (int i = 0; i < m; i++) {
            dfs(i, n - 1, atlantic);
        }
        for (int j = 0; j < n - 1; j++) {
            dfs(m - 1, j, atlantic);
        }
        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    vector<int> cell;
                    cell.emplace_back(i);
                    cell.emplace_back(j);
                    result.emplace_back(cell);
                }
            }
        }
        return result;
    }
};
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
//官方答案，广度优先搜索
static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

class Solution {
public:
    vector<vector<int>> heights;

    void bfs(int row, int col, vector<vector<bool>> & ocean) {
        if (ocean[row][col]) {
            return;
        }
        int m = heights.size();
        int n = heights[0].size();
        ocean[row][col] = true;
        queue<pair<int, int>> qu;
        qu.emplace(row, col);
        while (!qu.empty()) {
            auto [row, col] = qu.front();
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col] && !ocean[newRow][newCol]) {
                    ocean[newRow][newCol] = true;
                    qu.emplace(newRow, newCol);
                }
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        this->heights = heights;
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            bfs(i, 0, pacific);
        }
        for (int j = 1; j < n; j++) {
            bfs(0, j, pacific);
        }
        for (int i = 0; i < m; i++) {
            bfs(i, n - 1, atlantic);
        }
        for (int j = 0; j < n - 1; j++) {
            bfs(m - 1, j, atlantic);
        }
        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    vector<int> cell;
                    cell.emplace_back(i);
                    cell.emplace_back(j);
                    result.emplace_back(cell);
                }
            }
        }
        return result;
    }
};

强密码检验器

420. 强密码检验器 - 力扣（LeetCode） (leetcode-cn.com) 做不出来，长度大于20不知道怎么处理了

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//官方答案
class Solution {
public:
    int strongPasswordChecker(string password) {
        int n = password.size();
        bool has_lower = false, has_upper = false, has_digit = false;
        for (char ch: password) {
            if (islower(ch)) {
                has_lower = true;
            }
            else if (isupper(ch)) {
                has_upper = true;
            }
            else if (isdigit(ch)) {
                has_digit = true;
            }
        }
        int categories = has_lower + has_upper + has_digit;

        if (n < 6) {
            return max(6 - n, 3 - categories);
        }
        else if (n <= 20) {
            int replace = 0;
            int cnt = 0;
            char cur = '#';

            for (char ch: password) {
                if (ch == cur) {
                    ++cnt;
                }
                else {
                    replace += cnt / 3;
                    cnt = 1;
                    cur = ch;
                }
            }
            replace += cnt / 3;
            return max(replace, 3 - categories);
        }
        else {
            // 替换次数和删除次数
            int replace = 0, remove = n - 20;
            // k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作
            int rm2 = 0;
            int cnt = 0;
            char cur = '#';

            for (char ch: password) {
                if (ch == cur) {
                    ++cnt;
                }
                else {
                    if (remove > 0 && cnt >= 3) {
                        if (cnt % 3 == 0) {
                            // 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作
                            --remove;
                            --replace;
                        }
                        else if (cnt % 3 == 1) {
                            // 如果是 k % 3 = 1 的组，那么存下来备用
                            ++rm2;
                        }
                        // k % 3 = 2 的组无需显式考虑
                    }
                    replace += cnt / 3;
                    cnt = 1;
                    cur = ch;
                }
            }
            if (remove > 0 && cnt >= 3) {
                if (cnt % 3 == 0) {
                    --remove;
                    --replace;
                }
                else if (cnt % 3 == 1) {
                    ++rm2;
                }
            }
            replace += cnt / 3;

            // 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定
            int use2 = min({replace, rm2, remove / 2});
            replace -= use2;
            remove -= use2 * 2;
            // 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量
            int use3 = min({replace, remove / 3});
            replace -= use3;
            remove -= use3 * 3;
            return (n - 20) + max(replace, 3 - categories);
        }
    }
};

建立四叉树

427. 建立四叉树 - 力扣（LeetCode） (leetcode-cn.com) 

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        return abc(grid, 0, 0, grid.size());
    }

    Node* abc(vector<vector<int>>& grid, int x, int y, int len)
    {
        Node* root = new Node();
        if(len == 1 || same(grid, x, y, len))
        {
            root->val = grid[x][y];
            root->isLeaf = true;
            return root;
        }

        len = len / 2;
        root->val = grid[x][y];
        root->isLeaf = false;

        int topLeft_i = x, topLeft_j = y;
        // root->topLeft = new Node();
        root->topLeft = abc(grid, topLeft_i, topLeft_j, len);

        int topRight_i = x, topRight_j = y + len;
        // root->topRight = new Node();
        root->topRight = abc(grid, topRight_i, topRight_j, len);

        int bottomLeft_i = x + len, bottomLeft_j = y;
        // root->bottomLeft = new Node();
        root->bottomLeft = abc(grid, bottomLeft_i, bottomLeft_j, len);

        int bottomRight_i = x + len, bottomRight_j = y + len;
        // root->bottomRight = new Node();
        root->bottomRight = abc(grid, bottomRight_i, bottomRight_j, len);
        
        return root;
    }

    bool same(vector<vector<int>>& grid, int row, int col, int len)
    {
        int tmp = grid[row][col];
        for(int i = row; i < row + len; ++i)
        {
            for(int j = col; j < col + len; ++j)
            {
                if(tmp != grid[i][j]) return false;
            }
        }
        return true;
    }
};
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:
    Node *construct(vector<vector<int>> &grid) {
        function<Node*(int, int, int, int)> dfs = [&](int r0, int c0, int r1, int c1) {
            for (int i = r0; i < r1; ++i) {
                for (int j = c0; j < c1; ++j) {
                    if (grid[i][j] != grid[r0][c0]) { // 不是叶节点
                        return new Node(
                                true,
                                false,
                                dfs(r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
                                dfs(r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
                                dfs((r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
                                dfs((r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
                        );
                    }
                }
            }
            // 是叶节点
            return new Node(grid[r0][c0], true);
        };
        return dfs(0, 0, grid.size(), grid.size());
    }
};
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
//官方答案，递归+二维前缀和优化
class Solution {
public:
    Node *construct(vector<vector<int>> &grid) {
        int n = grid.size();
        vector<vector<int>> pre(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }

        auto getSum = [&](int r0, int c0, int r1, int c1) {
            return pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0];
        };

        function<Node *(int, int, int, int)> dfs = [&](int r0, int c0, int r1, int c1) {
            int total = getSum(r0, c0, r1, c1);
            if (total == 0) {
                return new Node(false, true);
            }
            if (total == (r1 - r0) * (c1 - c0)) {
                return new Node(true, true);
            }
            return new Node(
                    true,
                    false,
                    dfs(r0, c0, (r0 + r1) / 2, (c0 + c1) / 2),
                    dfs(r0, (c0 + c1) / 2, (r0 + r1) / 2, c1),
                    dfs((r0 + r1) / 2, c0, r1, (c0 + c1) / 2),
                    dfs((r0 + r1) / 2, (c0 + c1) / 2, r1, c1)
            );
        };

        return dfs(0, 0, n, n);
    }
};

N叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

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
//官方答案
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (!root) {
            return {};
        }

        vector<vector<int>> ans;
        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            int cnt = q.size();
            vector<int> level;
            for (int i = 0; i < cnt; ++i) {
                Node* cur = q.front();
                q.pop();
                level.push_back(cur->val);
                for (Node* child: cur->children) {
                    q.push(child);
                }
            }
            ans.push_back(move(level));
        }

        return ans;
    }
};

全O(1)的数据结构

432. 全 O(1) 的数据结构 - 力扣（LeetCode） (leetcode-cn.com)

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
class AllOne {
public:
    unordered_map<string, int> hashTable;
    //vector<pair<string, int>> strKey;
    string maxKey = "";  //保存数量最多的字符串
    string minKey = "";  //保存数量最少的字符串
    AllOne() {

    }
    
    void inc(string key) {
        ++hashTable[key];  // key 对应的数量加 1 
        if(maxKey == "" || hashTable[key] > hashTable[maxKey]) { 
            maxKey = key;
        }  //如果最多数量字符串为空，或增加的字符串key数量多于maxKey，更新maxKey
        if(minKey == key) { 
            minString();
        } //如果增加的是最少的字符串，调用minString()函数重新遍历查找最小字符串
        else if(minKey == "" || hashTable[key] < hashTable[minKey]) {
            minKey = key;
        } //如果最多数量字符串为空，或增加的字符串key数量少于mixKey，更新minKey
    }

    void dec(string key) {
        if(hashTable[key] == 1) { //如果要删除的key的数量为1，擦除key
            hashTable.erase(key);
            if(key == minKey) {   //如果被擦除的是最小字符串，重新遍历查找最少数量字符串
                minString();
            }
        }
        else {       //否则key对应的数量减1
            --hashTable[key];  
        }
        if(maxKey == key) {  //如果减少的最多字符串，调用maxString()更新maxkey
            maxString();
        }
    }

    void minString() {    //遍历hashTable查找最少数量字符串
        int min = INT_MAX;
        for(auto it = hashTable.begin(); it != hashTable.end(); ++it) {
            if((*it).second < min) {
                min = (*it).second;
                minKey = (*it).first;
            }
        }
    }

    void maxString() { //遍历hashTable查找最多数量字符串
        int max = 0;
        for(auto it = hashTable.begin(); it != hashTable.end(); ++it) {
            if((*it).second > max) {
                max = (*it).second;
                maxKey = (*it).first;
            }
        }
    }
    
    string getMaxKey() {  
        return maxKey;
    }
    
    string getMinKey() {
        return minKey;
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */
1
2
3
4
5
6
我的一个想法（和上面的解答想法不一样）和官方答案的想法很像。
官方是双向链表+哈希表，
我的想法是哈希表+vector：
哈希表中存放<string, int>，string是关键字，int为string在vector中的下标而不是string的个数
而vector中的元素为pair<string,int>，int是string的个数，
vector按int从高到低排序，每调用一次inc函数对应的key都会和前面一个元素比较或交换，每调用一次dec函数对应的key都会和后面一个元素比较或交换
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
//官方答案：双向链表+哈希表
class AllOne {
    list<pair<unordered_set<string>, int>> lst;
    unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> nodes;

public:
    AllOne() {}

    void inc(string key) {
        if (nodes.count(key)) {
            auto cur = nodes[key], nxt = next(cur);
            if (nxt == lst.end() || nxt->second > cur->second + 1) {
                unordered_set<string> s({key});
                nodes[key] = lst.emplace(nxt, s, cur->second + 1);
            } else {
                nxt->first.emplace(key);
                nodes[key] = nxt;
            }
            cur->first.erase(key);
            if (cur->first.empty()) {
                lst.erase(cur);
            }
        } else { // key 不在链表中
            if (lst.empty() || lst.begin()->second > 1) {
                unordered_set<string> s({key});
                lst.emplace_front(s, 1);
            } else {
                lst.begin()->first.emplace(key);
            }
            nodes[key] = lst.begin();
        }
    }

    void dec(string key) {
        auto cur = nodes[key];
        if (cur->second == 1) { // key 仅出现一次，将其移出 nodes
            nodes.erase(key);
        } else {
            auto pre = prev(cur);
            if (cur == lst.begin() || pre->second < cur->second - 1) {
                unordered_set<string> s({key});
                nodes[key] = lst.emplace(cur, s, cur->second - 1);
            } else {
                pre->first.emplace(key);
                nodes[key] = pre;
            }
        }
        cur->first.erase(key);
        if (cur->first.empty()) {
            lst.erase(cur);
        }
    }

    string getMaxKey() {
        return lst.empty() ? "" : *lst.rbegin()->first.begin();
    }

    string getMinKey() {
        return lst.empty() ? "" : *lst.begin()->first.begin();
    }
};

最小基因变化

433. 最小基因变化 - 力扣（LeetCode） (leetcode-cn.com) 

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
//官方答案
class Solution {
public:    
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> cnt;
        unordered_set<string> visited;
        char keys[4] = {'A', 'C', 'G', 'T'};        
        for (auto & w : bank) {
            cnt.emplace(w);
        }
        if (start == end) {
            return 0;
        }
        if (!cnt.count(end)) {
            return -1;
        }
        queue<string> qu;
        qu.emplace(start);
        visited.emplace(start);
        int step = 1;
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                string curr = qu.front();
                qu.pop();
                for (int j = 0; j < 8; j++) 
                {
                    for (int k = 0; k < 4; k++) 
                    {
                        if (keys[k] != curr[j]) 
                        {
                            string next = curr;
                            next[j] = keys[k];
                            if (!visited.count(next) && cnt.count(next)) 
                            {
                                if (next == end) return step;
                                qu.emplace(next);
                                visited.emplace(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
};
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
//官方答案
class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        int m = start.size();
        int n = bank.size();
        vector<vector<int>> adj(n);
        int endIndex = -1;
        for (int i = 0; i < n; i++) {
            if (end == bank[i]) {
                endIndex = i;
            }
            for (int j = i + 1; j < n; j++) {
                int mutations = 0;
                for (int k = 0; k < m; k++) {
                    if (bank[i][k] != bank[j][k]) {
                        mutations++;
                    }
                    if (mutations > 1) {
                        break;
                    }
                }
                if (mutations == 1) {
                    adj[i].emplace_back(j);
                    adj[j].emplace_back(i);
                }
            }
        }
        if (endIndex == -1) {
            return -1;
        }

        queue<int> qu;
        vector<bool> visited(n, false);
        int step = 1;
        for (int i = 0; i < n; i++) {
            int mutations = 0;
            for (int k = 0; k < m; k++) {
                if (start[k] != bank[i][k]) {
                    mutations++;
                }
                if (mutations > 1) {
                    break;
                }
            }
            if (mutations == 1) {
                qu.emplace(i);
                visited[i] = true;
            }
        }        
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                int curr = qu.front();
                qu.pop();
                if (curr == endIndex) {
                    return step;
                }
                for (auto & next : adj[curr]) {
                    if (visited[next]) {
                        continue;
                    }
                    visited[next] = true;
                    qu.emplace(next);
                }
            }
            step++;
        }
        return -1;
    }
};

字典序的第K小数字

440. 字典序的第K小数字 - 力扣（LeetCode） (leetcode-cn.com)

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
//字典树，超时了
class Trie {

public:
    Trie() {
        this->children = vector<Trie*>(10, nullptr);
        saveVal = 0;
    }

    bool insert(const int val) {
        string str = to_string(val);
        int length = str.size();
        Trie *temp = this;
        for(char c : str) {
            int ic = c - '0';
            if(temp->children[ic] == nullptr) {
                temp->children[ic] = new Trie();
            }
            temp = temp->children[ic];
        }
        temp->end = true;
        temp->saveVal = val;
        return true;
    }

    int search_k(const int k) {
        int index = 0;
        return dfs(this, index, k);
    }

    int dfs(Trie* root, int &index, const int k) {
        if(root == nullptr) return 0;
        if(root->end) ++index;
        if(index == k) return root->saveVal;
        for(int i = 0; i < 10; ++i) {
            int ret = dfs(root->children[i], index, k);
            if(ret) return ret;
        }
        return 0;
    }

private:
    vector<Trie *> children;
    bool end = false;
    int saveVal;
};

class Solution {
public:
    int findKthNumber(int n, int k) {
        Trie *root = new Trie();
        for(int i = 1; i <= n; ++i) {
            root->insert(i);
        }
        return root->search_k(k);
    }
};
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:
    int getSteps(int curr, long n) {
        int steps = 0;
        long first = curr;
        long last = curr;
        while (first <= n) {
            steps += min(last, n) - first + 1;
            first = first * 10;
            last = last * 10 + 9;
        }
        return steps;
    }

    int findKthNumber(int n, int k) {
        int curr = 1;
        k--;
        while (k > 0) {
            int steps = getSteps(curr, n);
            if (steps <= k) {
                k -= steps;
                curr++;
            } else {
                curr = curr*10;
                k--;
            }
        }
        return curr;
    }
};

数据中重复的数据

442. 数组中重复的数据 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//官方答案
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (nums[i] - 1 != i) {
                ans.push_back(nums[i]);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//官方答案，负数做标记
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            int x = abs(nums[i]);
            if (nums[x - 1] > 0) {
                nums[x - 1] = -nums[x - 1];
            }
            else {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

序列化和反序列化二叉搜索树

449. 序列化和反序列化二叉搜索树 - 力扣（LeetCode） 

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL) return "";
        queue<TreeNode *> q;
        string ret;
        q.push(root);
        while(!q.empty())
        {
            string tmp;
            TreeNode* curr = q.front();
            q.pop();
            tmp += to_string(curr->val);
            if(curr->left != NULL)
            {
                tmp += '-';
                tmp += to_string(curr->left->val);
                q.push(curr->left);
            }
            else
            {
                tmp += "-N";
            }
            if(curr->right != NULL)
            {
                tmp += '-';
                tmp += to_string(curr->right->val);
                q.push(curr->right);
            }
            else
            {
                tmp += "-N";
            }
            tmp += ',';
            ret += tmp;
        }
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "") return NULL;
        queue<TreeNode *> q;
        int pos = data.find('-');
        int val = stoi(data.substr(0, pos));
        TreeNode *root = new TreeNode(val);
        q.push(root);
        pos = 0;
        int prepos;
        while(!q.empty() && pos < data.size())
        {
            TreeNode *curr = q.front();
            q.pop();

            prepos = pos;
            pos = data.find('-', prepos);
            val = stoi(data.substr(prepos, pos - prepos));
            if(val != curr->val) continue;
            ++pos;

            prepos = pos;
            pos = data.find('-', prepos);
            if(data[pos - 1] != 'N')
            {
                val = stoi(data.substr(prepos, pos - prepos));                
                curr->left = new TreeNode(val);
                q.push(curr->left);
            }
            ++pos;
            prepos = pos;
            pos = data.find(',', prepos);
            if(data[pos - 1] != 'N')
            {
                val = stoi(data.substr(prepos, pos - prepos));
                curr->right = new TreeNode(val);
                q.push(curr->right);
            }
            ++pos;
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// 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
//官方答案，后序遍历
class Codec {
public:
    string serialize(TreeNode* root) {
        string res;
        vector<int> arr;
        postOrder(root, arr);
        if (arr.size() == 0) {
            return res;
        }
        for (int i = 0; i < arr.size() - 1; i++) {
            res.append(to_string(arr[i]) + ",");
        }
        res.append(to_string(arr.back()));
        return res;
    }

    vector<string> split(const string &str, char dec) {
        int pos = 0;
        int start = 0;
        vector<string> res;
        while (pos < str.size()) {
            while (pos < str.size() && str[pos] == dec) {
                pos++;
            }
            start = pos;
            while (pos < str.size() && str[pos] != dec) {
                pos++;
            }
            if (start < str.size()) {
                res.emplace_back(str.substr(start, pos - start));
            }
        }
        return res;
    }

    TreeNode* deserialize(string data) {
        if (data.size() == 0) {
            return nullptr;
        }
        vector<string> arr = split(data, ',');
        stack<int> st;
        for (auto & str : arr) {
            st.emplace(stoi(str));
        }
        return construct(INT_MIN, INT_MAX, st);
    }

    void postOrder(TreeNode *root,vector<int> & arr) {
        if (root == nullptr) {
            return;
        }
        postOrder(root->left, arr);
        postOrder(root->right, arr);
        arr.emplace_back(root->val);
    }

    TreeNode * construct(int lower, int upper, stack<int> & st) {
        if (st.size() == 0 || st.top() < lower || st.top() > upper) {
            return nullptr;
        }
        int val = st.top();
        st.pop();
        TreeNode *root = new TreeNode(val);
        root->right = construct(val, upper, st);
        root->left = construct(lower, val, st);
        return root;
    }
};

最大回文数乘积

479. 最大回文数乘积 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//官方答案，枚举+数学
class Solution {
public:
    int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        int upper = pow(10, n) - 1;
        for (int left = upper;; --left) { // 枚举回文数的左半部分
            long p = left;
            for (int x = left; x > 0; x /= 10) {
                p = p * 10 + x % 10; // 翻转左半部分到其自身末尾，构造回文数 p
            }
            for (long x = upper; x * x >= p; --x) {
                if (p % x == 0) { // x 是 p 的因子
                    return p % 1337;
                }
            }
        }
    }
};

七进制数

504. 七进制数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string convertToBase7(int num) {
        int remainder = 0, pos = 0;
        string result;
        if(num == 0) return "0";
        if(num < 0) {
            result += '-';
            pos = 1;
            num = -num;
        }
        while(num != 0) {
            remainder = num % 7;
            num /= 7;
            result.insert(pos, 1, char(remainder + '0'));
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//官方答案
class Solution {
public:
    string convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        bool negative = num < 0;
        num = abs(num);
        string digits;
        while (num > 0) {
            digits.push_back(num % 7 + '0');
            num /= 7;
        }
        if (negative) {
            digits.push_back('-');
        }
        reverse(digits.begin(), digits.end());
        return digits;
    }
};

最长特殊子序列 I

521. 最长特殊序列 Ⅰ - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
class Solution { //不敢相信这么简单
public:
    int findLUSlength(string a, string b) {
        if(a == b) return -1;
        return max(a.size(), b.size());
    }
};
1
2
3
4
5
6
7
// 官方答案，脑筋急转弯
class Solution {
public:
    int findLUSlength(string a, string b) {
        return a != b ? max(a.length(), b.length()) : -1;
    }
};

有序数组中的单一元素

540. 有序数组中的单一元素 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 官方答案一，全数组的二分查找
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (nums[mid] == nums[mid ^ 1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 官方答案二，偶数下标的二分查找
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            mid -= mid & 1;
            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
};

N叉树的前序遍历

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> result;
    vector<int> preorder(Node* root) {
        preOrder(root);
        return result;
    }

    void preOrder(Node *root) {
        if(root == nullptr) return;
        result.push_back(root->val);
        for(int i = 0; i < root->children.size(); ++i) {
            preOrder(root->children[i]);
        }
    }
};
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
//官方答案，迭代
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        
        unordered_map<Node *, int> cnt;
        stack<Node *> st;
        Node * node = root;
        while (!st.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val);
                st.emplace(node);
                if (node->children.size() > 0) {
                    cnt[node] = 0;
                    node = node->children[0];
                } else {
                    node = nullptr;
                }         
            }
            node = st.top();
            int index = (cnt.count(node) ? cnt[node] : -1) + 1;
            if (index < node->children.size()) {
                cnt[node] = index;
                node = node->children[index];
            } else {
                st.pop();
                cnt.erase(node);
                node = nullptr;
            }
        }
        return res;
    }
};
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:
    vector<int> preorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<Node *> st;
        st.emplace(root);
        while(!st.empty()) {
            Node * node = st.top();
            st.pop();
            res.emplace_back(node->val);
            for (auto it = node->children.rbegin(); it != node->children.rend(); it++) {
                st.emplace(*it);
            }
        }
        return res;
    }
};

N叉树的后序遍历

590. N 叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com)

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> result;
    vector<int> postorder(Node* root) {
        if(root == nullptr) return result;
        postOrder(root);
        return result;
    }

    void postOrder(Node *root) {
        for(int i = 0; i < root->children.size(); ++i) {
            postOrder(root->children[i]);
        }        
        result.emplace_back(root->val);
    }
};
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
//官方答案，迭代
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        
        unordered_map<Node *, int> cnt;
        stack<Node *> st;
        Node * node = root;
        while (!st.empty() || node != nullptr) {
            while (node != nullptr) {
                st.emplace(node);
                if (node->children.size() > 0) {
                    cnt[node] = 0;
                    node = node->children[0];
                } else {
                    node = nullptr;
                }         
            }
            node = st.top();
            int index = cnt.count(node) ? (cnt[node] + 1) : 0;
            if (index < node->children.size()) {
                cnt[node] = index;
                node = node->children[index];
            } else {
                res.emplace_back(node->val);
                st.pop();
                cnt.erase(node);
                node = nullptr;
            }
        }
        return res;
    }
};
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
//官方答案，迭代优化
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<Node *> st;
        unordered_set<Node *> visited;
        st.emplace(root);
        while (!st.empty()) {
            Node * node = st.top();
            /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
            if (node->children.size() == 0 || visited.count(node)) {
                res.emplace_back(node->val);
                st.pop();
                continue;
            }
            for (auto it = node->children.rbegin(); it != node->children.rend(); it++) {
                st.emplace(*it);
            }
            visited.emplace(node);
        }       
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//官方答案，利用前序遍历反转，妙啊，前序遍历时子结点从右向左遍历，最后序列翻转
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<Node *> st;
        st.emplace(root);
        while (!st.empty()) {
            Node * node = st.top();
            st.pop();
            res.emplace_back(node->val);
            for (auto &item : node->children) {
                st.emplace(item);
            }
        }       
        reverse(res.begin(), res.end()); 
        return res;
    }
};

两个列表的最小索引总和

599. 两个列表的最小索引总和 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> result;
        int length1 = list1.size() - 1, length2 = list2.size() - 1;
        int length = length1 + length2;
        for(int i = 0; i <= length; ++i) {
            int l1 = min(i, length1), l2 = i - l1;
            while(l1 >= 0 && l2 <= length2) {
                if(list1[l1] == list2[l2]) {
                    result.emplace_back(list1[l1]);
                }
                --l1; ++l2;
            }
            if(!result.empty()) break;
        }
        return result;
    }
};
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<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> index;
        for (int i = 0; i < list1.size(); i++) {
            index[list1[i]] = i;
        }

        vector<string> ret;
        int indexSum = INT_MAX;
        for (int i = 0; i < list2.size(); i++) {
            if (index.count(list2[i]) > 0) {
                int j = index[list2[i]];
                if (i + j < indexSum) {
                    ret.clear();
                    ret.push_back(list2[i]);
                    indexSum = i + j;
                } else if (i + j == indexSum) {
                    ret.push_back(list2[i]);
                }
            }
        }
        return ret;
    }
};

根据二叉树创建字符串

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
/**
 * 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:
    string result;
    string tree2str(TreeNode* root) {
        preOrder(root);
        return result;
    }

    void preOrder(TreeNode* root) {
        if(root == nullptr) 
        {
            return;
        }
        result += to_string(root->val);
        if(root->left != nullptr) 
        {
            result += '(';
            preOrder(root->left);
            result += ')';
        } 
        if(root->right != nullptr) 
        {
            if(root->left == nullptr) 
            {
                result += "()";
            }
            result += '(';
            preOrder(root->right);
            result += ')';
        } 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//官方答案，递归
class Solution {
public:
    string tree2str(TreeNode *root) {
        if (root == nullptr) {
            return "";
        }
        if (root->left == nullptr && root->right == nullptr) {
            return to_string(root->val);
        }
        if (root->right == nullptr) {
            return to_string(root->val) + "(" + tree2str(root->left) + ")";
        }
        return to_string(root->val) + "(" + tree2str(root->left) + ")(" + tree2str(root->right) + ")";
    }
};
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
//官方答案，迭代
class Solution {
public:
    string tree2str(TreeNode *root) {
        string ans = "";
        stack<TreeNode *> st;
        st.push(root);
        unordered_set<TreeNode *> vis;
        while (!st.empty()) {
            auto node = st.top();
            if (vis.count(node)) {
                if (node != root) {
                    ans += ")";
                }
                st.pop();
            } else {
                vis.insert(node);
                if (node != root) {
                    ans += "(";
                }
                ans += to_string(node->val);
                if (node->left == nullptr && node->right != nullptr) {
                    ans += "()";
                }
                if (node->right != nullptr) {
                    st.push(node->right);
                }
                if (node->left != nullptr) {
                    st.push(node->left);
                }
            }
        }
        return ans;
    }
};

两数之和IV - 输入 BST

653. 两数之和 IV - 输入 BST - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * 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:
    bool findTarget(TreeNode* root, int k) {
        vector<int> nodeVal;
        inOrder(root, nodeVal);
        int l = 0, r = nodeVal.size() - 1;
        while(l < r) 
        {
            int sum = nodeVal[l] + nodeVal[r];
            if(sum == k) return true;
            else if(sum > k) --r;
            else ++l;
        }
        return false;
    }

    void inOrder(TreeNode* root, vector<int>& nodeVal)
    {
        if(root == nullptr) return;
        inOrder(root->left, nodeVal);
        nodeVal.emplace_back(root->val);
        inOrder(root->right, nodeVal);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//官方答案，深度优先搜索+哈希表，哈希表用的妙啊
class Solution {
public:
    unordered_set<int> hashTable;

    bool findTarget(TreeNode *root, int k) {
        if (root == nullptr) {
            return false;
        }
        if (hashTable.count(k - root->val)) {
            return true;
        }
        hashTable.insert(root->val);
        return findTarget(root->left, k) || findTarget(root->right, k);
    }
};
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:
    bool findTarget(TreeNode *root, int k) {
        unordered_set<int> hashTable;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            TreeNode *node = que.front();
            que.pop();
            if (hashTable.count(k - node->val)) {
                return true;
            }
            hashTable.insert(node->val);
            if (node->left != nullptr) {
                que.push(node->left);
            }
            if (node->right != nullptr) {
                que.push(node->right);
            }
        }
        return false;
    }
};
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<int> vec;

    void inorderTraversal(TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        inorderTraversal(node->left);
        vec.push_back(node->val);
        inorderTraversal(node->right);
    }

    bool findTarget(TreeNode *root, int k) {
        inorderTraversal(root);
        int left = 0, right = vec.size() - 1;
        while (left < right) {
            if (vec[left] + vec[right] == k) {
                return true;
            }
            if (vec[left] + vec[right] < k) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
};
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
//官方答案，迭代+中序遍历+双指针
class Solution {
public:
    TreeNode *getLeft(stack<TreeNode *> &stk) {
        TreeNode *root = stk.top();
        stk.pop();
        TreeNode *node = root->right;
        while (node != nullptr) {
            stk.push(node);
            node = node->left;
        }
        return root;
    }

    TreeNode *getRight(stack<TreeNode *> &stk) {
        TreeNode *root = stk.top();
        stk.pop();
        TreeNode *node = root->left;
        while (node != nullptr) {
            stk.push(node);
            node = node->right;
        }
        return root;
    }

    bool findTarget(TreeNode *root, int k) {
        TreeNode *left = root, *right = root;
        stack<TreeNode *> leftStack, rightStack;
        leftStack.push(left);
        while (left->left != nullptr) {
            leftStack.push(left->left);
            left = left->left;
        }
        rightStack.push(right);
        while (right->right != nullptr) {
            rightStack.push(right->right);
            right = right->right;
        }
        while (left != right) {
            if (left->val + right->val == k) {
                return true;
            }
            if (left->val + right->val < k) {
                left = getLeft(leftStack);
            } else {
                right = getRight(rightStack);
            }
        }
        return false;
    }
};

图片平滑器

661. 图片平滑器 - 力扣（LeetCode） (leetcode-cn.com) 

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:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int x = img.size() - 1, y = img[0].size() - 1;
        vector<vector<int>> ret(x + 1, vector(y + 1, 0));
        auto avrge = [=](int i, int j) {
            int sum = img[i][j];
            int num = 1;
            if(i > 0) {
                sum += img[i - 1][j];
                ++num;
                if(j > 0) {
                    sum += img[i - 1][j - 1];
                    ++num;
                }
            }
            if(i < x) {
                sum += img[i + 1][j]; 
                ++num;
                if(j < y) {
                    sum += img[i + 1][j + 1];
                    ++num;
                }
            }
            if(j > 0) {
                sum += img[i][j - 1];
                ++num;
                if(i < x) {
                    sum += img[i + 1][j - 1];
                    ++num;
                }
            }
            if(j < y) {
                sum += img[i][j + 1];
                ++num;
                if(i > 0) {
                    sum += img[i - 1][j + 1];
                    ++num;
                }
            }
            return sum / num;
        };
        for(int i = 0; i <= x; ++i)
        {
            for(int j = 0; j <= y; ++j)
            {
                ret[i][j] = avrge(i, j);
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//官方答案
class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m = img.size(), n = img[0].size();
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = 0, sum = 0;
                for (int x = i - 1; x <= i + 1; x++) {
                    for (int y = j - 1; y <= j + 1; y++) {
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            num++;
                            sum += img[x][y];
                        }
                    }
                }
                ret[i][j] = sum / num;
            }
        }
        return ret;
    }
};

棒球比赛

682. 棒球比赛 - 力扣（LeetCode） (leetcode-cn.com)

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:
    int calPoints(vector<string>& ops) {
        vector<int> scores;
        int result = 0;
        for(string &s : ops)
        {
            if(s == "C")
            {
                result -= *(scores.end()-1);
                scores.erase(scores.end()-1);
            }
            else if(s == "D")
            {
                int tmp = *(scores.end()-1) * 2;
                scores.emplace_back(tmp);
                result += tmp;
            }
            else if(s == "+")
            {
                int tmp = *(scores.end()-1) + *(scores.end()-2);
                scores.emplace_back(tmp);
                result += tmp;
            }
            else 
            {
                int tmp = stoi(s);
                result += tmp;
                scores.emplace_back(tmp);
            }
        }
        return result;
    }
};

交替位二进制数

693. 交替位二进制数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool hasAlternatingBits(int n) {
        int pre = n & 1;
        while(n)
        {
            n = n >> 1;
            if(pre == (n & 1)) return false;
            pre = n & 1;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
//官方答案
class Solution {
public:
    bool hasAlternatingBits(int n) {
        long a = n ^ (n >> 1);
        return (a & (a + 1)) == 0;
    }
};

乘积小于K的子数组

713. 乘积小于 K 的子数组 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//官方答案，滑动窗口
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n = nums.size(), ret = 0;
        int prod = 1, i = 0;
        for (int j = 0; j < n; j++) {
            prod *= nums[j];
            while (i <= j && prod >= k) {
                prod /= nums[i];
                i++;
            }
            ret += j - i + 1;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//官方答案，log
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) {
            return 0;
        }
        int n = nums.size();
        vector<double> logPrefix(n + 1);
        for (int i = 0; i < n; i++) {
            logPrefix[i + 1] = logPrefix[i] + log(nums[i]);
        }
        double logk = log(k);
        int ret = 0;
        for (int j = 0; j < n; j++) {
            int l = upper_bound(logPrefix.begin(), logPrefix.begin() + j + 1, logPrefix[j + 1] - log(k) + 1e-10) - logPrefix.begin();
            ret += j + 1 - l;
        }
        return ret;
    }
};

词典中最长的单词

720. 词典中最长的单词 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//官方答案，哈希集合
class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string & a, const string & b) {
            if (a.size() != b.size()) {
                return a.size() < b.size();
            } else {
                return a > b;
            }
        });
        string longest = "";
        unordered_set<string> cnt;
        cnt.emplace("");
        for (auto & word : words) {
            if (cnt.count(word.substr(0, word.size() - 1))) {
                cnt.emplace(word);
                longest = word;
            }
        }
        return longest;
    }
};
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
//官方答案，Trie树
class Trie {
public:
    Trie() {
        this->children = vector<Trie *>(26, nullptr);
        this->isEnd = false;
    }
    
    bool insert(const string & word) {
        Trie * node = this;
        for (const auto & ch : word) {
            int index = ch - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new Trie();
            }
            node = node->children[index];
        }
        node->isEnd = true;
        return true;
    }

    bool search(const string & word) {
        Trie * node = this;
        for (const auto & ch : word) {
            int index = ch - 'a';
            if (node->children[index] == nullptr || !node->children[index]->isEnd) {
                return false;
            }
            node = node->children[index];
        }
        return node != nullptr && node->isEnd;
    }
private:
    vector<Trie *> children;
    bool isEnd;
};

class Solution {
public:
    string longestWord(vector<string>& words) {
        Trie trie;
        for (const auto & word : words) {
            trie.insert(word);
        }
        string longest = "";
        for (const auto & word : words) {
            if (trie.search(word)) {
                if (word.size() > longest.size() || (word.size() == longest.size() && word < longest)) {
                    longest = word;
                }
            }
        }
        return longest;
    }
};

自除数

728. 自除数 - 力扣（LeetCode） (leetcode-cn.com)

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
class Solution {
public:
    bool isSelfDividing(int digit)
    {
        int num = digit;
        while(num)  
        {
            int tmp = num % 10;
            if(tmp == 0 || digit % tmp != 0)
            {
                return false;
            }
            num /= 10;
        }
        return true;
    }

    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> ret;
        for(int i = left; i <= right; ++i)
        {
            if(isSelfDividing(i))
            {
                ret.emplace_back(i);
            }
        }
        return ret;
    }
};

寻找比目标字母大的最小字母

744. 寻找比目标字母大的最小字母 - 力扣（LeetCode） (leetcode-cn.com) 

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:
    char nextGreatestLetter(vector<char>& letters, char target) {
        if(letters.back() <= target) return letters[0];
        int left = 0, right = letters.size() - 1;
        int mid;
        while(left + 1 < right)
        {
            mid = (left + right) / 2;
            if(letters[mid] > target)
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
        if(letters[left] > target) return letters[left];
        else return letters[right];
    }
};
1
2
3
4
5
6
7
//官方答案，二分查找，我以为这个二分查找算法官方会自己写，没想到直接用upper_bound
class Solution {
public:
    char nextGreatestLetter(vector<char> &letters, char target) {
        return target < letters.back() ? *upper_bound(letters.begin(), letters.end() - 1, target) : letters[0];  //upper_bound查找大于target的最小数
    }
};

二进制表示中质数个计算置位

762. 二进制表示中质数个计算置位 - 力扣（LeetCode） (leetcode-cn.com) 

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 {
    bool isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

public:
    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if (isPrime(__builtin_popcount(x))) {
                ++ans;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//官方答案，
//用一个二进制数mask=665772=10100010100010101100表示2,3,5,7,11,13,17,19
class Solution {
public:
    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if ((1 << __builtin_popcount(x)) & 665772) {
                ++ans;
            }
        }
        return ans;
    }
};

到达终点

780. 到达终点 - 力扣（LeetCode） (leetcode-cn.com)

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:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        if (tx == sx && ty == sy) {
            return true;
        } else if (tx == sx) {
            return ty > sy && (ty - sy) % tx == 0;
        } else if (ty == sy) {
            return tx > sx && (tx - sx) % ty == 0;
        } else {
            return false;
        }
    }
};

旋转字符串

796. 旋转字符串 - 力扣（LeetCode） (leetcode-cn.com) 

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:
    bool rotateString(string s, string goal) {
        if(s.size() != goal.size())
        {
            return false;
        }
        vector<int> next(goal.size(), 0);
        getNext(goal, next);
        s += s;
        if(KMP(s, goal, next) == -1) return false;
        return true;
    }

    void getNext(string &T, vector<int> &next)
    {
        int length = T.size();
        int j = 0, k = -1;
        next[0] = -1;
        while(j < length - 1)
        {
            if(k == -1 || T[j] == T[k])
            {
                ++j; ++k;
                if(T[j] != T[k]) next[j] = k;
                else next[j] = next[k];
            }
            else
            {
                k = next[k];
            }
        }
    }

    int KMP(string &S, string &T, vector<int> &next)
    {
        int i = 0, j = 0;
        int sLen = S.size(), tLen = T.size();
        while(i < sLen && j < tLen)
        {
            if(j == -1 || S[i] == T[j])
            {
                ++i; ++j;
            }
            else
            {
                j = next[j];
            }
        }
        return j < tLen ? -1 : i - j;
    }
};
1
2
3
4
5
6
7
//官方答案
class Solution {
public:
    bool rotateString(string s, string goal) {
        return s.size() == goal.size() && (s + s).find(goal) != string::npos;
    }
};

得分最高的最小轮调

798. 得分最高的最小轮调 - 力扣（LeetCode） (leetcode-cn.com)

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
//官方答案，差分数组
class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int n = nums.size();
        vector<int> diffs(n);
        for (int i = 0; i < n; i++) {
            int low = (i + 1) % n;
            int high = (i - nums[i] + n + 1) % n;
            diffs[low]++;
            diffs[high]--;
            if (low >= high) {
                diffs[0]++;
            }
        }
        int bestIndex = 0;
        int maxScore = 0;
        int score = 0;
        for (int i = 0; i < n; i++) {
            score += diffs[i];
            if (score > maxScore) {
                bestIndex = i;
                maxScore = score;
            }
        }
        return bestIndex;
    }
};

唯一摩尔斯密码词

804. 唯一摩尔斯密码词 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//官方答案
const static string MORSE[] = {
        ".-", "-...", "-.-.", "-..", ".", "..-.", "--.",
        "....", "..", ".---", "-.-", ".-..", "--", "-.",
        "---", ".--.", "--.-", ".-.", "...", "-", "..-",
        "...-", ".--", "-..-", "-.--", "--.."
};

class Solution {
public:
    int uniqueMorseRepresentations(vector<string> &words) {
        unordered_set<string> seen;
        for (auto &word: words) {
            string code;
            for (auto &c: word) {
                code.append(MORSE[c - 'a']);
            }
            seen.emplace(code); // emplace比insert快
        }
        return seen.size();
    }
};

写字符串需要的行数

806. 写字符串需要的行数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//官方答案
const int MAX_WIDTH = 100;

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string s) {
        int lines = 1;
        int width = 0;
        for (auto & c : s) {
            int need = widths[c - 'a'];
            width += need;
            if (width > MAX_WIDTH) {
                lines++;
                width = need;
            }
        }
        return {lines, width};
    }
};

最常见的单词

819. 最常见的单词 - 力扣（LeetCode） (leetcode-cn.com) 

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
//仿官方答案
class Solution {
public:
    string mostCommonWord(string paragraph, vector<string>& banned) {
        int maxFrequency = 0;
        unordered_map<string, int> frequencies;
        string word;
        int length = paragraph.size();
        for(int i = 0; i <= length; ++i)
        {
            if(i < length && isalpha(paragraph[i]))
            {
                word.push_back(tolower(paragraph[i]));
            }
            else if(word.size() > 0)
            {
                if(!count(banned.begin(), banned.end(), word))
                {
                    frequencies[word]++;
                    maxFrequency = max(maxFrequency, frequencies[word]);
                }
                word="";
            }
        }
        string result;
        for(auto &[word, count] : frequencies)
        {
            if(count == maxFrequency)
            {
                result = word;
            }
        }
        return result;
    }
};

字符的最短距离

821. 字符的最短距离 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//官方答案
class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.length();
        vector<int> ans(n);

        for (int i = 0, idx = -n; i < n; ++i) {
            if (s[i] == c) {
                idx = i;
            }
            ans[i] = i - idx;
        }

        for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
            if (s[i] == c) {
                idx = i;
            }
            ans[i] = min(ans[i], idx - i);
        }
        return ans;
    }
};

山羊拉丁文

824. 山羊拉丁文 - 力扣（LeetCode） (leetcode-cn.com) 

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
class Solution {
public:
    string toGoatLatin(string sentence) {
        unordered_set<char> oyin = {'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'};
        string ret;
        int len = sentence.size();
        int num = 1;
        for(int i = 0; i < len; ++i)
        {
            if(oyin.count(sentence[i]))
            {
                while(i < len && sentence[i] != ' ')
                {
                    ret += sentence[i];
                    ++i;
                }
                ret += "ma";
            }
            else
            {
                char c = sentence[i];
                ++i;
                while(i < len && sentence[i] != ' ')
                {
                    ret += sentence[i];
                    ++i;
                }
                ret += c;
                ret += "ma";
            }
            ret += string(num, 'a');
            ++num;
            ret += ' ';
        }
        return ret.substr(0, ret.size() - 1);
    }
};

二进制间距

868. 二进制间距 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//官方答案
class Solution {
public:
    int binaryGap(int n) {
        int last = -1, ans = 0;
        for (int i = 0; n; ++i) {
            if (n & 1) {
                if (last != -1) {
                    ans = max(ans, i - last);
                }
                last = i;
            }
            n >>= 1;
        }
        return ans;
    }
};

按奇偶数排序数组

905. 按奇偶排序数组 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, n = nums.size();
        while(left < right)
        {
            while(left < right && nums[left] % 2 == 0) ++left;
            while(right > left && nums[right] % 2 == 1) --right;
            if(left < right)
            {
                swap(nums[left], nums[right]); // swap交换比自己写个tmp交换快
                ++left;
                --right;
            }
        }
        return nums;
    }
};

最小差值I

908. 最小差值 I - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int maxNum = *max_element(nums.begin(), nums.end());
        int minNum = *min_element(nums.begin(), nums.end());
        int range = maxNum - minNum;
        return range < 2 * k ? 0 : range - 2 * k;
    }
};

最近的请求次数

933. 最近的请求次数 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class RecentCounter {
public:
    RecentCounter() {

    }
    
    int ping(int t) {
        time.emplace_back(t);
        auto it = find_if(time.rbegin(), time.rend(), [=](int val){
            return val < (t - 3000);
        });
        return it - time.rbegin();
    }

private:
    vector<int> time;
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//官方答案，队列
class RecentCounter {
    queue<int> q;
public:
    RecentCounter() {}

    int ping(int t) {
        q.push(t);
        while (q.front() < t - 3000) {
            q.pop();
        }
        return q.size();
    }
};

重新排列日志文件

937. 重新排列日志文件 - 力扣（LeetCode） (leetcode-cn.com) 

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:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(logs.begin(), logs.end(), [&](const string & log1, const string & log2) {
            int pos1 = log1.find_first_of(" ");
            int pos2 = log2.find_first_of(" ");
            bool isDigit1 = isdigit(log1[pos1 + 1]);
            bool isDigit2 = isdigit(log2[pos2 + 1]);
            if (isDigit1 && isDigit2) {
                return false;
            }
            if (!isDigit1 && !isDigit2) {
                string s1 = log1.substr(pos1);
                string s2 = log2.substr(pos2);
                if (s1 != s2) {
                    return s1 < s2;
                }
                return log1 < log2;
            }
            return isDigit1 ? false : true;
        });
        return logs;
    }
};

增减字符串匹配

942. 增减字符串匹配 - 力扣（LeetCode） 

1
2
3
4
5
6
7
8
9
10
11
12
13
//官方答案，贪心
class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.length(), lo = 0, hi = n;
        vector<int> perm(n + 1);
        for (int i = 0; i < n; ++i) {
            perm[i] = s[i] == 'I' ? lo++ : hi--;
        }
        perm[n] = lo; // 最后剩下一个数，此时 lo == hi
        return perm;
    }
};

删列造序

944. 删列造序 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//官方答案
class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int row = strs.size();
        int col = strs[0].size();
        int ans = 0;
        for (int j = 0; j < col; ++j) {
            for (int i = 1; i < row; ++i) {
                if (strs[i - 1][j] > strs[i][j]) {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
};

二倍数对数组

954. 二倍数对数组 - 力扣（LeetCode） (leetcode-cn.com) 

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
//官方答案，哈希表+排序
class Solution {
public:
    bool canReorderDoubled(vector<int> &arr) {
        unordered_map<int, int> cnt;
        for (int x : arr) {
            ++cnt[x];
        }
        if (cnt[0] % 2) {
            return false;
        }

        vector<int> vals;
        vals.reserve(cnt.size());
        for (auto &[x, _] : cnt) {
            vals.push_back(x);
        }
        sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });

        for (int x : vals) {
            if (cnt[2 * x] < cnt[x]) { // 无法找到足够的 2x 与 x 配对
                return false;
            }
            cnt[2 * x] -= cnt[x];
        }
        return true;
    }
};

网格照明

1001. 网格照明 - 力扣（LeetCode） (leetcode-cn.com)

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
// 官方答案
class Solution {
public:
    vector<int> gridIllumination(int n, vector<vector<int>> &lamps, vector<vector<int>> &queries) {
        unordered_map<int, int> row, col, diagonal, antiDiagonal;
        auto hash_p = [](const pair<int, int> &p) -> size_t {
            static hash<long long> hash_ll;
            return hash_ll(p.first + (static_cast<long long>(p.second) << 32));
        };
        unordered_set<pair<int, int>, decltype(hash_p)> points(0, hash_p);
        for (auto &lamp : lamps) {
            if (points.count({lamp[0], lamp[1]}) > 0) {
                continue;
            }
            points.insert({lamp[0], lamp[1]});
            row[lamp[0]]++;
            col[lamp[1]]++;
            diagonal[lamp[0] - lamp[1]]++;
            antiDiagonal[lamp[0] + lamp[1]]++;
        }
        vector<int> ret(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            int r = queries[i][0], c = queries[i][1];
            if (row.count(r) > 0 && row[r] > 0) {
                ret[i] = 1;
            } else if (col.count(c) > 0 && col[c] > 0) {
                ret[i] = 1;
            } else if (diagonal.count(r - c) > 0 && diagonal[r - c] > 0) {
                ret[i] = 1;
            } else if (antiDiagonal.count(r + c) > 0 && antiDiagonal[r + c] > 0) {
                ret[i] = 1;
            }
            for (int x = r - 1; x <= r + 1; x++) {
                for (int y = c - 1; y <= c + 1; y++) {
                    if (x < 0 || y < 0 || x >= n || y >= n) {
                        continue;
                    }
                    auto p = points.find({x, y});
                    if (p != points.end()) {
                        points.erase(p);
                        row[x]--;
                        col[y]--;
                        diagonal[x - y]--;
                        antiDiagonal[x + y]--;
                    }
                }
            }
        }
        return ret;
    }
};

飞地的数量

1020. 飞地的数量 - 力扣（LeetCode） (leetcode-cn.com)

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
class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size() - 1, n = grid[0].size() - 1;
        int num = 0;
        
        for(int i = 0; i <= n; ++i) {
            if(grid[0][i] == 1) {
                search(0, i, grid, m, n);
            }
            if(grid[m][i] == 1) {
                search(m, i, grid, m, n);
            }
        }
        for(int i = 1; i < m; ++i) {
            if(grid[i][0] == 1) {
                search(i, 0, grid, m, n);
            }
            if(grid[i][n] == 1) {
                search(i, n, grid, m, n);
            }
        }
        for(int i = 1; i < m; ++i) {
            num += count(grid[i].begin(), grid[i].end(), 1);
        }
        return num;
	}
	
	void search(int x, int y, vector<vector<int>>& grid, int& m, int& n) {
		grid[x][y] = 2;
		if(x > 0 && grid[x - 1][y] == 1) search(x - 1, y, grid, m ,n);
		if(x < m && grid[x + 1][y] == 1) search(x + 1, y, grid, m ,n);
		if(y > 0 && grid[x][y - 1] == 1) search(x, y - 1, grid, m ,n);
		if(y < n && grid[x][y + 1] == 1) search(x, y + 1, grid, m ,n); 
	}
};
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
// 官方答案一，深度优先搜索
class Solution {
public:
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int numEnclaves(vector<vector<int>>& grid) {
        this->m = grid.size();
        this->n = grid[0].size();
        this->visited = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }

    void dfs(const vector<vector<int>> & grid, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return;
        }
        visited[row][col] = true;
        for (auto & dir : dirs) {
            dfs(grid, row + dir[0], col + dir[1]);
        }
    }
private:
    int m, n;
    vector<vector<bool>> visited;
};
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
//官方答案二，广度优先搜索
class Solution {
public:
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(m, vector<bool>(n, false));
        queue<pair<int,int>> qu;
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                visited[i][0] = true;
                qu.emplace(i, 0);
            }
            if (grid[i][n - 1] == 1) {
                visited[i][n - 1] = true;
                qu.emplace(i, n - 1);
            }
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) {
                visited[0][j] = true;
                qu.emplace(0, j);
            }
            if (grid[m - 1][j] == 1) {
                visited[m - 1][j] = true;
                qu.emplace(m - 1, j);
            }
        }
        while (!qu.empty()) {
            auto [currRow, currCol] = qu.front();
            qu.pop();
            for (auto & dir : dirs) {
                int nextRow = currRow + dir[0], nextCol = currCol + dir[1];
                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    qu.emplace(nextRow, nextCol);
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
};
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
78
79
80
81
82
83
84
//官方答案三，并查集
class UnionFind {
public:
    UnionFind(const vector<vector<int>> & grid) {
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);
        this->onEdge = vector<bool>(m * n, false);
        this->rank = vector<int>(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        onEdge[index] = true;
                    }
                }
            }
        }
    }

    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    void uni(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
                onEdge[rooty] = onEdge[rooty] | onEdge[rootx];
            } else {
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
                rank[rootx]++;
            }
        }
    }

    bool isOnEdge(int i) {
        return onEdge[find(i)];
    }
private:
    vector<int> parent;
    vector<bool> onEdge;
    vector<int> rank;    
};

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        UnionFind uf(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == 1) {
                        uf.uni(index, index + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1) {
                        uf.uni(index, index + n);
                    }
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !uf.isOnEdge(i * n + j)) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
};

气球的最大数量

1189. “气球” 的最大数量 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
拼"balloon"（气球）的个数，每个字母只能用一次
输入：text = "loonbalxballpoon"
输出：2
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 maxNumberOfBalloons(string text) {
        int a = 0, b = 0, l = 0, o = 0, n = 0;
        int num = INT_MAX;
        for(int i = 0; i < text.size(); ++i) {
            switch(text[i]){
                case 'a': ++a; break;
                case 'b': ++b; break;
                case 'l': ++l; break;
                case 'o': ++o; break;
                case 'n': ++n; break;
                default: break;
            }
        }
        l /= 2;
        o /= 2;
        if(a < num) num = a;
        if(b < num) num = b;
        if(l < num) num = l;
        if(o < num) num = o;
        if(n < num) num = n;
        return num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 官方答案
class Solution {
public:
    int maxNumberOfBalloons(string text) {
        vector<int> cnt(5);
        for (auto & ch : text) {
            if (ch == 'b') {
                cnt[0]++;
            } else if (ch == 'a') {
                cnt[1]++;
            } else if (ch == 'l') {
                cnt[2]++;
            } else if (ch == 'o') {
                cnt[3]++;
            } else if (ch == 'n') {
                cnt[4]++;
            }
        }
        cnt[2] /= 2;
        cnt[3] /= 2;
        return *min_element(cnt.begin(), cnt.end());
    }
};

黄金矿工

1219. 黄金矿工 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释：
[[0,6,0],
 [5,8,7],
 [0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。
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
class Solution {
public:
    int maxGold = 0;
    int getMaximumGold(vector<vector<int>>& grid) {
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[0].size(); j++) {
                search(grid, i, j, 0, 0);
            }
        }
        return maxGold;
    }

    void search(vector<vector<int>>& grid, int x, int y, int gold, int flag) {
        if(grid[x][y] == 0) {
            maxGold = maxGold > gold ? maxGold : gold;
            return;
        }
        gold += grid[x][y];
        int reserve = grid[x][y];
        grid[x][y] = 0;
        // flag    1 向下  2 向上   3 向左   4 向右
        if(x + 1 < grid.size() && flag != 2) {
            search(grid, x + 1, y, gold, 1);
        }
        if(x > 0 && flag != 1) {
            search(grid, x - 1, y, gold, 2);
        }
        if(y > 0 && flag != 4) {
            search(grid, x, y - 1, gold, 3);
        } 
        if(y + 1 < grid[x].size() && flag != 3) {
            search(grid, x, y + 1, gold, 4);
        }
        grid[x][y] = reserve;
    }
};

两棵二叉搜索树中的所有元素

1305. 两棵二叉搜索树中的所有元素 - 力扣（LeetCode） (leetcode-cn.com) 

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 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 {
    void inorder(TreeNode *node, vector<int> &res) {
        if (node) {
            inorder(node->left, res);
            res.push_back(node->val);
            inorder(node->right, res);
        }
    }

public:
    vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {
        vector<int> nums1, nums2;
        inorder(root1, nums1);
        inorder(root2, nums2);

        vector<int> merged;
        auto p1 = nums1.begin(), p2 = nums2.begin();
        while (true) {
            if (p1 == nums1.end()) {
                merged.insert(merged.end(), p2, nums2.end());
                break;
            }
            if (p2 == nums2.end()) {
                merged.insert(merged.end(), p1, nums1.end());
                break;
            }
            if (*p1 < *p2) {
                merged.push_back(*p1++);
            } else {
                merged.push_back(*p2++);
            }
        }
        return merged;
    }
};

矩阵中的幸运数

1380. 矩阵中的幸运数 - 力扣（LeetCode） (leetcode-cn.com)

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> luckyNumbers (vector<vector<int>>& matrix) {
        vector<int> luck;
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; ++i) {
            int minSub = 0;
            for(int j = 0; j < n; ++j) {
                if(matrix[i][j] < matrix[i][minSub]) {
                    minSub = j;
                }
            }
            bool flag = true;
            for(int k = 0; k < m; ++k) {
                if(matrix[i][minSub] < matrix[k][minSub]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                luck.push_back(matrix[i][minSub]);
            }
        }
        return luck;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 官方答案，预处理
class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> minRow(m, INT_MAX), maxCol(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                minRow[i] = min(minRow[i], matrix[i][j]);
                maxCol[j] = max(maxCol[j], matrix[i][j]);
            }
        }
        vector<int> ret;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == minRow[i] && matrix[i][j] == maxCol[j]) {
                    ret.push_back(matrix[i][j]);
                }
            }
        }
        return ret;
    }
};

最长快乐字符串

1405. 最长快乐字符串 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。
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:
    string longestDiverseString(int a, int b, int c) {
        vector<pair<int, char>> arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};
        char before = '\0';
        int count = 0;
        string re = "";
        while(true) {
            sort(arr.begin(), arr.end(), [](const pair<int, char>& p1, const pair<int, char>& p2){ return p1.first > p2.first; });
			if(!(count == 2 && before == arr[0].second) && arr[0].first) {
                if(before == arr[0].second) count++;
                else count = 1;
                before = arr[0].second;
                --arr[0].first;                    
            } else if(arr[1].first){
                before = arr[1].second;
                count = 0;
                --arr[1].first;
            } else break;
			re += before;
        };
        return re;
    }
};
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:
    string longestDiverseString(int a, int b, int c) {
        int idx[3] = {0,1,2}, cc[3] = {a,b,c};
        string ans;
        auto get_rank = [&](int i){
            sort(idx, idx+3, [&](int x, int y){return cc[x] > cc[y];});
            return i;
        };
        auto test_insert = [&](int i){
            if(!cc[idx[i]]) return false;
            --cc[idx[i]], ans.push_back(idx[i]+'a');
            return true;
        };
        do{
            test_insert(get_rank(0));
            test_insert(get_rank(0));        
        }while(test_insert(1) || test_insert(2));
        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
// 官方答案
class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        string res;
        vector<pair<int, char>> arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};
        
        while (true) {
            sort(arr.begin(), arr.end(), [](const pair<int, char> & p1, const pair<int, char> & p2) {
                return p1.first > p2.first;
            });
            bool hasNext = false;
            for (auto & [freq, ch] : arr) {
                int m = res.size();
                if (freq <= 0) {
                    break;
                }
                if (m >= 2 && res[m - 2] == ch && res[m - 1] == ch) {
                    continue;
                }
                hasNext = true;
                res.push_back(ch);
                freq--;
                break;
            }
            if (!hasNext) {
                break;
            }
        }
      
        return res;
    }
};

和为 K 的最少斐波那契数字数目

1414. 和为 K 的最少斐波那契数字数目 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
输入：k = 7
输出：2 
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。
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:
    int findMinFibonacciNumbers(int k) {
        vector<int> fibonacci(2,1);
        int top = fibonacci.size() - 1;
        while(fibonacci[top] <= k) {
            fibonacci.push_back(fibonacci[top] + fibonacci[top - 1]);
            top++;
        }
		top--;
		fibonacci.pop_back();
        int num = 1;
        int findNum = k - fibonacci[top];
		if (findNum == 0) return num;
        while (true) {
            vector<int>::iterator it = find(fibonacci.begin(), fibonacci.end(), findNum);
            if(it == fibonacci.end()) {
                for(int i = top; i >= 0; i--) {
                    if (findNum > fibonacci[i]) {
                        findNum -= fibonacci[i];
                        num++;
						break;
                    }
                }
            } else {
                num++;
                break;
            }
        }
        return num;
    }
};

最简分数

1447. 最简分数 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
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<string> simplifiedFractions(int n) {
        vector<string> re;

        auto simplestfraction = [&](int i, int j) {
            for(int k = 2; k <= j / 2; k++) {
                if(i % k == 0 && j % k == 0) {
                    return false;
                }
            }
            return true;
        };

        for(int i = 1; i < n; i++) {
            for(int j = i + 1; j <= n; j++) {
                if(!simplestfraction(i, j)) continue;
                string temp = to_string(i) + '/' + to_string(j);
                re.push_back(temp);                
            }
        }
        return re;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 官方答案
class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ans;
        for (int denominator = 2; denominator <= n; ++denominator) {
            for (int numerator = 1; numerator < denominator; ++numerator) {
                if (__gcd(numerator, denominator) == 1) {
                    ans.emplace_back(to_string(numerator) + "/" + to_string(denominator));
                }
            }
        }
        return ans;
    }
};

最多可达成的换楼请求数目

1601. 最多可达成的换楼请求数目 - 力扣（LeetCode） (leetcode-cn.com)

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
// 官方答案，DFS+回溯
class Solution {
private:
    vector<int> delta;
    int ans = 0, cnt = 0, zero, n;

public:
    void dfs(vector<vector<int>> &requests, int pos) {
        if (pos == requests.size()) {
            if (zero == n) {
                ans = max(ans, cnt);
            }
            return;
        }

        // 不选 requests[pos]
        dfs(requests, pos + 1);

        // 选 requests[pos]
        int z = zero;
        ++cnt;
        auto &r = requests[pos];
        int x = r[0], y = r[1];
        zero -= delta[x] == 0;
        --delta[x];
        zero += delta[x] == 0;
        zero -= delta[y] == 0;
        ++delta[y];
        zero += delta[y] == 0;
        dfs(requests, pos + 1);
        --delta[y];
        ++delta[x];
        --cnt;
        zero = z;
    }

    int maximumRequests(int n, vector<vector<int>> &requests) {
        delta.resize(n);
        zero = n;
        this->n = n;
        dfs(requests, 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
25
// 官方答案，二进制枚举
class Solution {
public:
    int maximumRequests(int n, vector<vector<int>> &requests) {
        vector<int> delta(n);
        int ans = 0, m = requests.size();
        for (int mask = 0; mask < (1 << m); ++mask) {
            int cnt = __builtin_popcount(mask);
            if (cnt <= ans) {
                continue;
            }
            fill(delta.begin(), delta.end(), 0);
            for (int i = 0; i < m; ++i) {
                if (mask & (1 << i)) {
                    ++delta[requests[i][0]];
                    --delta[requests[i][1]];
                }
            }
            if (all_of(delta.begin(), delta.end(), [](int x) { return x == 0; })) {
                ans = cnt;
            }
        }
        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
//官方答案，模拟+有序集合+优先队列
class Solution {
public:
    vector<int> busiestServers(int k, vector<int> &arrival, vector<int> &load) {
        set<int> available;
        for (int i = 0; i < k; i++) {
            available.insert(i);
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;
        vector<int> requests(k);
        for (int i = 0; i < arrival.size(); i++) {
            while (!busy.empty() && busy.top().first <= arrival[i]) {
                available.insert(busy.top().second);
                busy.pop();
            }
            if (available.empty()) {
                continue;
            }
            auto p = available.lower_bound(i % k);
            if (p == available.end()) {
                p = available.begin();
            }
            requests[*p]++;
            busy.emplace(arrival[i] + load[i], *p);
            available.erase(p);
        }
        int maxRequest = *max_element(requests.begin(), requests.end());
        vector<int> ret;
        for (int i = 0; i < k; i++) {
            if (requests[i] == maxRequest) {
                ret.push_back(i);
            }
        }
        return ret;
    }
};
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> busiestServers(int k, vector<int> &arrival, vector<int> &load) {
        priority_queue<int, vector<int>, greater<int>> available;
        for (int i = 0; i < k; i++) {
            available.push(i);
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busy;
        vector<int> requests(k, 0);
        for (int i = 0; i < arrival.size(); i++) {
            while (!busy.empty() && busy.top().first <= arrival[i]) {
                auto[_, id] = busy.top();
                busy.pop();
                available.push(i + ((id - i) % k + k) % k); // 保证得到的是一个不小于 i 的且与 id 同余的数
            }
            if (available.empty()) {
                continue;
            }
            int id = available.top() % k;
            available.pop();
            requests[id]++;
            busy.push({arrival[i] + load[i], id});
        }
        int maxRequest = *max_element(requests.begin(), requests.end());
        vector<int> ret;
        for (int i = 0; i < k; i++) {
            if (requests[i] == maxRequest) {
                ret.push_back(i);
            }
        }
        return ret;
    }
};

最富有客户的资产总量

1672. 最富有客户的资产总量 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
//官方答案
class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int maxWealth = INT_MIN;
        for (auto &account : accounts) {
            maxWealth = max(maxWealth, accumulate(account.begin(), account.end(), 0));
        }
        return maxWealth;
    }
};

可以形成最大正方形的矩形数目

1725. 可以形成最大正方形的矩形数目 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]
输出：3
解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
最大正方形的边长为 5 ，可以由 3 个矩形切分得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int maxLen=0;
        int maxRec=0;
        for (int i = 0; i < rectangles.size(); i++) {
            int rec = rectangles[i][0]<rectangles[i][1]?rectangles[i][0]:rectangles[i][1];
            if (maxRec == rec) {
                ++maxLen;
            }
            else if(maxRec < rec) {
                maxLen=1;
                maxRec=rec;
            }
        }
        return maxLen;
    }
};

猫和老鼠

1728. 猫和老鼠 II - 力扣（LeetCode） 

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//官方答案，拓扑排序，好复杂啊
static const int MOUSE_TURN = 0, CAT_TURN = 1;
static const int UNKNOWN = 0, MOUSE_WIN = 1, CAT_WIN = 2;
static const int MAX_MOVES = 1000;

class Solution {
public: 
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int rows, cols;
    vector<string> grid;
    int catJump, mouseJump;
    int food;
    int degrees[64][64][2];
    int results[64][64][2][2];

    bool canMouseWin(vector<string> grid, int catJump, int mouseJump) {
        this->rows = grid.size();
        this->cols = grid[0].size();
        this->grid = grid;
        this->catJump = catJump;
        this->mouseJump = mouseJump;
        int startMouse = -1, startCat = -1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = grid[i][j];
                if (c == 'M') {
                    startMouse = getPos(i, j);
                } else if (c == 'C') {
                    startCat = getPos(i, j);
                } else if (c == 'F') {
                    food = getPos(i, j);
                }
            }
        }
        int total = rows * cols;
        memset(degrees, 0, sizeof(degrees));
        memset(results, 0, sizeof(results));
        queue<tuple<int, int, int>> qu;
        // 计算每个状态的度
        for (int mouse = 0; mouse < total; mouse++) {
            int mouseRow = mouse / cols, mouseCol = mouse % cols;
            if (grid[mouseRow][mouseCol] == '#') {
                continue;
            }
            for (int cat = 0; cat < total; cat++) {
                int catRow = cat / cols, catCol = cat % cols;
                if (grid[catRow][catCol] == '#') {
                    continue;
                }
                degrees[mouse][cat][MOUSE_TURN]++;
                degrees[mouse][cat][CAT_TURN]++;
                for (auto & dir : dirs) {
                    for (int row = mouseRow + dir[0], col = mouseCol + dir[1], jump = 1; row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#' && jump <= mouseJump; row += dir[0], col += dir[1], jump++) {
                        int nextMouse = getPos(row, col), nextCat = getPos(catRow, catCol);
                        degrees[nextMouse][nextCat][MOUSE_TURN]++;
                    }
                    for (int row = catRow + dir[0], col = catCol + dir[1], jump = 1; row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#' && jump <= catJump; row += dir[0], col += dir[1], jump++) {
                        int nextMouse = getPos(mouseRow, mouseCol), nextCat = getPos(row, col);
                        degrees[nextMouse][nextCat][CAT_TURN]++;
                    }
                }
            }
        }
        // 猫和老鼠在同一个单元格，猫获胜
        for (int pos = 0; pos < total; pos++) {
            int row = pos / cols, col = pos % cols;
            if (grid[row][col] == '#') {
                continue;
            }
            results[pos][pos][MOUSE_TURN][0] = CAT_WIN;
            results[pos][pos][MOUSE_TURN][1] = 0;
            results[pos][pos][CAT_TURN][0] = CAT_WIN;
            results[pos][pos][CAT_TURN][1] = 0;
            qu.emplace(pos, pos, MOUSE_TURN);
            qu.emplace(pos, pos, CAT_TURN);
        }
        // 猫和食物在同一个单元格，猫获胜
        for (int mouse = 0; mouse < total; mouse++) {
            int mouseRow = mouse / cols, mouseCol = mouse % cols;
            if (grid[mouseRow][mouseCol] == '#' || mouse == food) {
                continue;
            }
            results[mouse][food][MOUSE_TURN][0] = CAT_WIN;
            results[mouse][food][MOUSE_TURN][1] = 0;
            results[mouse][food][CAT_TURN][0] = CAT_WIN;
            results[mouse][food][CAT_TURN][1] = 0;
            qu.emplace(mouse, food, MOUSE_TURN);
            qu.emplace(mouse, food, CAT_TURN);
        }
        // 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜
        for (int cat = 0; cat < total; cat++) {
            int catRow = cat / cols, catCol = cat % cols;
            if (grid[catRow][catCol] == '#' || cat == food) {
                continue;
            }
            results[food][cat][MOUSE_TURN][0] = MOUSE_WIN;
            results[food][cat][MOUSE_TURN][1] = 0;
            results[food][cat][CAT_TURN][0] = MOUSE_WIN;
            results[food][cat][CAT_TURN][1] = 0;
            qu.emplace(food, cat, MOUSE_TURN);
            qu.emplace(food, cat, CAT_TURN);
        }
        // 拓扑排序
        while (!qu.empty()) {
            auto [mouse, cat, turn] = qu.front();
            qu.pop();
            int result = results[mouse][cat][turn][0];
            int moves = results[mouse][cat][turn][1];
            vector<tuple<int, int, int>> prevStates = getPrevStates(mouse, cat, turn);
            for (auto [prevMouse, prevCat, prevTurn] : prevStates) {
                if (results[prevMouse][prevCat][prevTurn][0] == UNKNOWN) {
                    bool canWin = (result == MOUSE_WIN && prevTurn == MOUSE_TURN) || (result == CAT_WIN && prevTurn == CAT_TURN);
                    if (canWin) {
                        results[prevMouse][prevCat][prevTurn][0] = result;
                        results[prevMouse][prevCat][prevTurn][1] = moves + 1;
                        qu.emplace(prevMouse, prevCat, prevTurn);
                    } else {
                        degrees[prevMouse][prevCat][prevTurn]--;
                        if (degrees[prevMouse][prevCat][prevTurn] == 0) {
                            int loseResult = prevTurn == MOUSE_TURN ? CAT_WIN : MOUSE_WIN;
                            results[prevMouse][prevCat][prevTurn][0] = loseResult;
                            results[prevMouse][prevCat][prevTurn][1] = moves + 1;
                            qu.emplace(prevMouse, prevCat, prevTurn);
                        }
                    }
                }
            }
        }
        return results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN && results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES;
    }
    
    vector<tuple<int, int, int>> getPrevStates(int mouse, int cat, int turn) {
        vector<tuple<int, int, int>> prevStates;
        int mouseRow = mouse / cols, mouseCol = mouse % cols;
        int catRow = cat / cols, catCol = cat % cols;
        int prevTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
        int maxJump = prevTurn == MOUSE_TURN ? mouseJump : catJump;
        int startRow = prevTurn == MOUSE_TURN ? mouseRow : catRow;
        int startCol = prevTurn == MOUSE_TURN ? mouseCol : catCol;
        prevStates.emplace_back(mouse, cat, prevTurn);
        for (auto & dir : dirs) {
            for (int i = startRow + dir[0], j = startCol + dir[1], jump = 1; i >= 0 && i < rows && j >= 0 && j < cols && grid[i][j] != '#' && jump <= maxJump; i += dir[0], j += dir[1], jump++) {
                int prevMouseRow = prevTurn == MOUSE_TURN ? i : mouseRow;
                int prevMouseCol = prevTurn == MOUSE_TURN ? j : mouseCol;
                int prevCatRow = prevTurn == MOUSE_TURN ? catRow : i;
                int prevCatCol = prevTurn == MOUSE_TURN ? catCol : j;
                int prevMouse = getPos(prevMouseRow, prevMouseCol);
                int prevCat = getPos(prevCatRow, prevCatCol);
                prevStates.emplace_back(prevMouse, prevCat, prevTurn);
            }
        }
        return prevStates;
    }

    int getPos(int row, int col) {
        return row * cols + col;
    }
};

唯一元素的和

1748. 唯一元素的和 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
输入：nums = [1,2,3,2]
输出：4
解释：唯一元素为 [1,3] ，和为 4 。

输入：nums = [1,1,1,1,1]
输出：0
解释：没有唯一元素，和为 0 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        int sum = 0;
        vector<int> temp;
        for(int i = 0; i < nums.size(); i++) {
            vector<int>::iterator it = find(temp.begin(), temp.end(), nums[i]);
            if(it == temp.end() || temp.size() == 0) {
                int num = count(nums.begin() + i + 1, nums.end(), nums[i]);
                if(num) {
                    temp.push_back(nums[i]);
                } else {
                    sum += nums[i];
                }
            }
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 官方答案
class Solution {
public:
    int sumOfUnique(vector<int> &nums) {
        int ans = 0;
        unordered_map<int, int> state;
        for (int num : nums) {
            if (state[num] == 0) {
                ans += num;
                state[num] = 1;
            } else if (state[num] == 1) {
                ans -= num;
                state[num] = 2;
            }
        }
        return ans;
    }
};

最长的美好字符串

1763. 最长的美好子字符串 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。
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:
    string longestNiceSubstring(string s) {
        int leng = s.size();
        int maxPos = 0;
        int maxLen = 0;
        for (int i = 0; i < leng; i++)
        {
            int lower = 0;
            int upper = 0;
            for (int j = i; j < leng; j++)
            {
                if(islower(s[j])) {
                    lower |= 1 << (s[j] - 'a');
                }
                else if(isupper(s[j])) {
                    upper |= 1 << (s[j] - 'A');
                }
                if(lower == upper && j - i + 1 > maxLen) {
                    maxPos = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substr(maxPos, maxLen);
    }
};

找出游戏获胜者

1823. 找出游戏的获胜者 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//官方答案，队列
class Solution {
public:
    int findTheWinner(int n, int k) {
        queue<int> qu;
        for (int i = 1; i <= n; i++) {
            qu.emplace(i);
        }
        while (qu.size() > 1) {
            for (int i = 1; i < k; i++) {
                qu.emplace(qu.front());
                qu.pop();
            }
            qu.pop();
        }
        return qu.front();
    }
};
1
2
3
4
5
6
7
8
9
10
//官方答案，递归
class Solution {
public:
    int findTheWinner(int n, int k) {
        if (n == 1) {
            return 1;
        }
        return (k + findTheWinner(n - 1, k) - 1) % n + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
//官方答案，迭代
class Solution {
public:
    int findTheWinner(int n, int k) {
        int winner = 1;
        for (int i = 2; i <= n; i++) {
            winner = (k + winner - 1) % i + 1;
        }
        return winner;
    }
};

学生分数的最小差值

1984. 学生分数的最小差值 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4, , ] 最高分和最低分之间的差值是 9 - 4 = 5
- [9, ,1, ] 最高分和最低分之间的差值是 9 - 1 = 8
- [9, , ,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [ ,4,1, ] 最高分和最低分之间的差值是 4 - 1 = 3
- [ ,4, ,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [ , ,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2
1
2
3
4
5
6
7
8
9
10
11
12
13
// 官方答案
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};

差的绝对值为K的数对数目

2006. 差的绝对值为 K 的数对数目 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
输入：nums = [1,2,2,1], k = 1
输出：4
解释：差的绝对值为 1 的数对为：
- [1,2, , ]
- [1, ,2, ]
- [ ,2, ,1]
- [ , ,2,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 官方答案
class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int res = 0, n = nums.size();
        unordered_map<int, int> cnt;
        for (int j = 0; j < n; ++j) {
            res += (cnt.count(nums[j] - k) ? cnt[nums[j] - k] : 0);
            res += (cnt.count(nums[j] + k) ? cnt[nums[j] + k] : 0);
            ++cnt[nums[j]];
        }
        return res;
    }
};

考试的最大困扰度

2024. 考试的最大困扰度 - 力扣（LeetCode） (leetcode-cn.com) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//官方答案，滑动窗口
class Solution {
public:
    int maxConsecutiveChar(string& answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey[right] != ch;
            while (sum > k) {
                sum -= answerKey[left++] != ch;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }

    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(maxConsecutiveChar(answerKey, k, 'T'),
                   maxConsecutiveChar(answerKey, k, 'F'));
    }
};
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
//评论区的答案
class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        int len = answerKey.size(),sum_t = 0,sum_f = 0;        //实时记录对应的t和f的总数
        int left_t = 0,left_f = 0,max_sum = 0;                 //遍历过程中t数列和f数列的左边界
        for(int i = 0;i < len;i++){            //i可以理解为右边界
            if(answerKey[i] == 'F')
               sum_f++;
            else sum_t++;
            //把T理解为主数列，那么F就是冗余项，需要判断实时的数量，不能超过k
            //如果超过了，就要左边界向右移动，直到F的数量恢复正常标准
            while(sum_f > k){
                if(answerKey[left_t] == 'F')
                   sum_f--;
                left_t++;
            }
            //同理，把F理解为主数列，那么T就是冗余项
            while(sum_t > k){
                if(answerKey[left_f] == 'T')
                   sum_t--;
                left_f++;
            }
            //比较取最大值
            max_sum = max(max_sum,max(i-left_t,i-left_f)+1);
        }
        return max_sum;
    }
};

找出缺失的数据

2028. 找出缺失的观测数据 - 力扣（LeetCode） (leetcode-cn.com) 

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<int> missingRolls(vector<int>& rolls, int mean, int n) {
        int m = rolls.size();
        int sum = (n + m) * mean;
        for(int &i : rolls)
        {
            sum -= i;
        } 
        double avr = (double)sum / n;
        if(avr > 6 || avr < 1) return {};
        int avrge = (int)avr;
        vector<int> ret(n, avrge);
        sum -= avrge * n;
        for(int i = 0; i < n; ++i)
        {
            int tmp = 6 - ret[i];
            if(sum > tmp)
            {
                sum -= tmp;
                ret[i] = 6;
            }
            else
            {
                ret[i] += sum;
                sum = 0;
                break;
            }
        }
        return ret;
    }
};

2038. 如果相邻两个颜色均相同则删除当前颜色 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool winnerOfGame(string colors) {
        int length = colors.size();
        int Anum = 0, Bnum = 0;
        for(int i = 1; i < length - 1; ++i)
        {
            if(colors[i - 1] == 'A' && colors[i] == 'A' && colors[i + 1] == 'A')
            {
                ++Anum;
            }
            else if(colors[i - 1] == 'B' && colors[i] == 'B' && colors[i + 1] == 'B')
            {
                ++Bnum;
            }
        }
        return Anum > Bnum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//官方答案
class Solution {
public:
    bool winnerOfGame(string colors) {
        int freq[2] = {0, 0};
        char cur = 'C';
        int cnt = 0;
        for (char c : colors) {
            if (c != cur) {
                cur = c;
                cnt = 1;
            } else if (++cnt >= 3) {
                ++freq[cur - 'A'];
            }
        }            
        return freq[0] > freq[1];
    }
};

网络空闲的时刻

2039. 网络空闲的时刻 - 力扣（LeetCode） (leetcode-cn.com)

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
//官方答案
class Solution {
public:
    int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {
        int n = patience.size();       
        vector<vector<int>> adj(n);
        vector<bool> visit(n, false);  
        for (auto & v : edges) {  
            adj[v[0]].emplace_back(v[1]);
            adj[v[1]].emplace_back(v[0]);
        }

        queue<int> qu;
        qu.emplace(0);
        visit[0] = true;
        int dist = 1;
        int ans = 0;
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; ++i) {
                int curr = qu.front();
                qu.pop();
                for (auto & v : adj[curr]) {
                    if (visit[v]) {
                        continue;
                    }
                    qu.emplace(v);
                    int time = patience[v] * ((2 * dist - 1) / patience[v]) + 2 * dist + 1;
                    ans = max(ans, time);
                    visit[v] = true;
                }
            }
            dist++;
        }
        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
class Bank {
public:
    vector<long long> balance;
    int accountNum;
    Bank(vector<long long>& balance) {
        this->balance = balance;
        accountNum = balance.size();
    }
    
    bool transfer(int account1, int account2, long long money) {
        if(account1 > accountNum || account2 > accountNum || balance[account1 - 1] < money)
        {
            return false;
        }
        balance[account1 - 1] -= money;
        balance[account2 - 1] += money;
        return true;
    }
    
    bool deposit(int account, long long money) {
        if(account > accountNum)
        {
            return false;
        }
        balance[account - 1] += money;
        return true;
    }
    
    bool withdraw(int account, long long money) {
        if(account > accountNum || balance[account - 1] < money)
        {
            return false;
        }
        balance[account - 1] -= money;
        return true;
    }
};

/**
 * Your Bank object will be instantiated and called as such:
 * Bank* obj = new Bank(balance);
 * bool param_1 = obj->transfer(account1,account2,money);
 * bool param_2 = obj->deposit(account,money);
 * bool param_3 = obj->withdraw(account,money);
 */
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
//官方答案
class Bank {
private:
    vector<long long> balance;

public:
    Bank(vector<long long>& balance) : balance(balance) {}

    bool transfer(int account1, int account2, long long money) {
        if (account1 > balance.size() || account2 > balance.size() || balance[account1 - 1] < money) {
            return false;
        }
        balance[account1 - 1] -= money;
        balance[account2 - 1] += money;
        return true;
    }

    bool deposit(int account, long long money) {
        if (account > balance.size()) {
            return false;
        }
        balance[account - 1] += money;
        return true;
    }

    bool withdraw(int account, long long money) {
        if (account > balance.size() || balance[account - 1] < money) {
            return false;
        }
        balance[account - 1] -= money;
        return true;
    }
};

统计按位或能得到最大值的子集数目

2044. 统计按位或能得到最大值的子集数目 - 力扣（LeetCode） (leetcode-cn.com)

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 maxOr = 0;
    int count = 0;
    int countMaxOrSubsets(vector<int>& nums) {
        for(int i : nums) {
            maxOr |= i;
        }
        dfsEnum(nums, 0, 0);
        return count;
    } 

    void dfsEnum(vector<int>& nums, int pos, int numOr) {
        if(pos == nums.size()) {
            if(numOr == maxOr) {
                ++count;
            }
            return;
        }
        dfsEnum(nums, pos + 1, numOr);
        numOr |= nums[pos];
        dfsEnum(nums, pos + 1, numOr);
    }
};
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 countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size(), maxValue = 0, cnt = 0, stateNumber = 1 << n;
        for (int i = 0; i < stateNumber; i++) {
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    cur |= nums[j];
                }
            }
            if (cur == maxValue) {
                cnt++;
            } else if (cur > maxValue) {
                maxValue = cur;
                cnt = 1;
            }
        }
        return cnt;
    }
};
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
//官方答案，回溯
class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        this->nums = nums;
        this->maxOr = 0;
        this->cnt = 0;
        dfs(0, 0);
        return cnt;
    }

    void dfs(int pos, int orVal) {
        if (pos == nums.size()) {
            if (orVal > maxOr) {
                maxOr = orVal;
                cnt = 1;
            } else if (orVal == maxOr) {
                cnt++;
            }
            return;
        }
        dfs(pos + 1, orVal| nums[pos]);
        dfs(pos + 1, orVal);
    }

private:
    vector<int> nums;
    int maxOr, cnt;
};

蜡烛之间的盘子

2055. 蜡烛之间的盘子 - 力扣（LeetCode） (leetcode-cn.com)

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> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> preSum(n);
        for (int i = 0, sum = 0; i < n; i++) {
            if (s[i] == '*') {
                sum++;
            }
            preSum[i] = sum;
        }
        vector<int> left(n);
        for (int i = 0, l = -1; i < n; i++) {
            if (s[i] == '|') {
                l = i;
            }
            left[i] = l;
        }
        vector<int> right(n);
        for (int i = n - 1, r = -1; i >= 0; i--) {
            if (s[i] == '|') {
                r = i;
            }
            right[i] = r;
        }
        vector<int> ans;
        for (auto& query : queries) {
            int x = right[query[0]], y = left[query[1]];
            ans.push_back(x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x]);
        }
        return ans;
    }
};

适合打劫银行的日子

2100. 适合打劫银行的日子 - 力扣（LeetCode） (leetcode-cn.com)

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
class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& security, int time) {
        int length = security.size();
        if(length < time) return {};
        vector<int> result;
        if(time == 0) {
            for(int i = 0; i < length; ++i) {
                result.push_back(i);
            }
            return result;
        }
        int *later = new int[length];
        later[length - 1] = 0;
        for(int i = length - 2; i >= 0; --i) {
            if(security[i] <= security[i + 1]) later[i] = later[i + 1] + 1;
            else later[i] = 0;
        }
        int front = 0;
        for(int i = 1; i < length - time; ++i) {
            if(security[i] <= security[i - 1]) front++;
            else front = 0;
            if(front >= time && later[i] >= time) result.push_back(i);
        }
        delete[] later;
        return result;
    }
};
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:
    vector<int> goodDaysToRobBank(vector<int>& security, int time) {
        int n = security.size();
        vector<int> left(n);
        vector<int> right(n);
        for (int i = 1; i < n; i++) {
            if (security[i] <= security[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
            if (security[n - i - 1] <= security[n - i]) {
                right[n - i - 1] = right[n - i] + 1;
            }
        }

        vector<int> ans;
        for (int i = time; i < n - time; i++) {
            if (left[i] >= time && right[i] >= time) {
                ans.emplace_back(i);
            }
        }
        return ans;
    }
};

子数组范围和

2104. 子数组范围和 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long result = 0;
        int length = nums.size();
        for(int i = 0; i < length - 1; ++i) {
            int maxNum = nums[i], minNum = nums[i];
            for(int j = 1; j < length - i; ++j) {
                maxNum = max(maxNum, nums[i + j]);
                minNum = min(minNum, nums[i + j]);
                result += maxNum - minNum;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//官方答案，遍历子数组
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        int n = nums.size();
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            int minVal = INT_MAX, maxVal = INT_MIN;
            for (int j = i; j < n; j++) {
                minVal = min(minVal, nums[j]);
                maxVal = max(maxVal, nums[j]);
                ret += maxVal - minVal;
            }
        }
        return ret;
    }
};
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
//官方答案，单调栈
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        int n = nums.size();
        vector<int> minLeft(n), minRight(n), maxLeft(n), maxRight(n);
        stack<int> minStack, maxStack;
        for (int i = 0; i < n; i++) {
            while (!minStack.empty() && nums[minStack.top()] > nums[i]) {
                minStack.pop();
            }
            minLeft[i] = minStack.empty() ? -1 : minStack.top();
            minStack.push(i);
            
            // 如果 nums[maxStack.top()] == nums[i], 那么根据定义，
            // nums[maxStack.top()] 逻辑上小于 nums[i]，因为 maxStack.top() < i
            while (!maxStack.empty() && nums[maxStack.top()] <= nums[i]) { 
                maxStack.pop();
            }
            maxLeft[i] = maxStack.empty() ? -1 : maxStack.top();
            maxStack.push(i);
        }
        minStack = stack<int>();
        maxStack = stack<int>();
        for (int i = n - 1; i >= 0; i--) {
            // 如果 nums[minStack.top()] == nums[i], 那么根据定义，
            // nums[minStack.top()] 逻辑上大于 nums[i]，因为 minStack.top() > i
            while (!minStack.empty() && nums[minStack.top()] >= nums[i]) { 
                minStack.pop();
            }
            minRight[i] = minStack.empty() ? n : minStack.top();
            minStack.push(i);

            while (!maxStack.empty() && nums[maxStack.top()] < nums[i]) {
                maxStack.pop();
            }
            maxRight[i] = maxStack.empty() ? n : maxStack.top();
            maxStack.push(i);
        }

        long long sumMax = 0, sumMin = 0;
        for (int i = 0; i < n; i++) {
            sumMax += static_cast<long long>(maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
            sumMin += static_cast<long long>(minRight[i] - i) * (i - minLeft[i]) * nums[i];
        }
        return sumMax - sumMin;
    }
};

面试 04.06.后继者

面试题 04.06. 后继者 - 力扣（LeetCode） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> st;
        TreeNode *prev = nullptr, *curr = root;
        while (!st.empty() || curr != nullptr) {
            while (curr != nullptr) {
                st.emplace(curr);
                curr = curr->left;
            }
            curr = st.top();
            st.pop();
            if (prev == p) {
                return curr;
            }
            prev = curr;
            curr = curr->right;
        }
        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
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *successor = nullptr;
        if (p->right != nullptr) {
            successor = p->right;
            while (successor->left != nullptr) {
                successor = successor->left;
            }
            return successor;
        }
        TreeNode *node = root;
        while (node != nullptr) {
            if (node->val > p->val) {
                successor = node;
                node = node->left;
            } else {
                node = node->right;
            }
        }
        return successor;
    }
};

欢迎关注我的其它发布渠道