LeetCode-究极刷题【合集】

$注重思路-输入输出略轻$

题目来源LeetCode

LeetCode 1. 两数之和-规律

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= $10^4$
-$10^9$<= nums[i] <= $10^9$
-$10^9$ <= target <= $10^9$
只会存在一个有效答案

class Solution {  //思路：n1 + n2 = target , n1确定, 是否存在n2 = target - n1 
public://hash表：{数值, 下标}
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++)
        {
            int r = target - nums[i];//另一个数
            if(hash.count(r)) return {hash[r], i}; //调用count函数看查看否存在r
            hash[nums[i]] = i; //把之前遍历过的数存入hash中,已经遍历过且在其前面的数没有匹配(后面可能与其匹配)
        }
        return {}; //安全级别高【这句肯定不会执行,但是要写】
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 2. 两数相加-链表

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

题意：用链表完成加法计算【头指针指向的头结点为个位】

class Solution {//虚拟头结点dummy【简化边界判断】
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { //题意初始两个链表非空
        auto dummy = new ListNode(-1) , cur = dummy;
        int t = 0; //是否进位【高精度加法hh】
        while(l1 || l2 || t) //链表不为空 ,或者还有向高位的进位
        {
            if(l1) t += l1->val, l1 = l1->next;  //l1与l2对应位相加，指针向后移计算下一位【头指针指向的头结点为个位】
            if(l2) t += l2->val, l2 = l2->next; 
            cur = cur->next = new ListNode(t % 10); //若有余数先向高位进1【创建新结点, 赋值1，没有进位则为0】
            t /= 10;
        }
        return dummy->next;//返回真正的头结点
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

y总写法二

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) 
    {
        ListNode *res = new ListNode(-1);   //添加虚拟头结点，简化边界情况的判断
        ListNode *cur = res;
        int carry = 0;  //表示进位
        while (l1 || l2) 
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(1); //如果最高位有进位，则需在最前面补1.
        return res->next;   //返回真正的头结点
    }
};

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

LeetCode 3. 无重复字符的最长子串-模板

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * $10^4$
s 由英文字母、数字、符号和空格组成

双指针 维护无重复字符区间 取res = max区间[j, i] ， 注意j为左边界

class Solution { 
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> heap; //LeetCode刷题实现函数【头文件不用写，已给形参可依据题目说明直接用】
        int res = 0;//空串
        for(int i = 0, j = 0; i < s.size(); i++)
        {
            heap[s[i]] ++;
            while(heap[s[i]] > 1) heap[s[j++]] --;
            res = max(res, i - j + 1); //j左边界, i右边界
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 4. 寻找两个正序数组的中位数-理解

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-$10^6$ <= nums1[i], nums2[i] <= $10^6$

详解需再次理解

class Solution { //思路： 取size() / 2大的作为 k / 2 , 比较a[k/2] 与 b[k / 2] 小的可以删去不是答案区间（类似二分的递归）
public:
   double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0) //中位数要特判奇偶：元素个数为偶数取中间两个数的平均值
        {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);//查找第一个数
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);//查找第二个数
            return (left + right) / 2.0;//返回平均值
        }
        else
        {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {
        if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
        if (nums1.size() == i) return nums2[j + k - 1]; 
        if (k == 1) return min(nums1[i], nums2[j]); //查找区间只剩下一个数
        int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
        {
            return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else
        {
            return findKthNumber(nums1, si, nums2, j, k - (si - 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

LeetCode 5. 最长回文子串-双指针中间开始

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

双指针

思路：指针出发点作为回文串中点遍历:指针l, r若相等则继续往两边走, (l往左, r往右)
停止时以i为中点的回文串最长为[l + 1, r - 1] ,超过边界或者不相等停止
回文子串元素个数偶数与奇数划分: 偶数初始下标: l = i - 1， r = i + 1 ; 奇数初始下标: l = i, r = i + 1
**回文子串len = (r-1) - (l-1) + 1 = r - l - 1 **

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i = 0; i < s.size(); i ++) {
            int l = i - 1, r = i + 1;  //枚举所有元素个数为奇数的回文串
            while(l >= 0 && r < s.size() && s[l] == s[r]) l --, r++;//往左右循环两边判断
            if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1); //substr(起始, 长度)

            l = i , r = i + 1;  //枚举所有元素个数为偶数的回文串
            while(l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
            if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1); //substr(起始, 长度)
        }
        
        return res;
    }
};


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

LeetCode 6. Z 字形变换-规律

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = “PAYPALISHIRING”, numRows = 3
输出：“PAHNAPLSIIGYIR”
示例 2：
输入：s = “PAYPALISHIRING”, numRows = 4
输出：“PINALSIGYAHRPI”
解释：

P     I    N
A   L S  I G
Y A   H R
P     I
1
2
3
4

示例 3：

输入：s = "A", numRows = 1
输出："A"
1
2

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
1 <= numRows <= 1000

【规律题画图】按每行看： 每行都是一组等差数列 , a1 + a2 = 2 * n - 2 ： 公差 == (n - 1) * 2

class Solution {  
public:
    string convert(string s, int n) {  
        string res;
        if (n == 1) return s; //等于1要停止否则死循环(或者类似希尔排序)
        for (int j = 0; j < n; j ++ )
        {
            if (j == 0 || j == n - 1) //第一行和最后一行
            {
                for (int i = j; i < s.size(); i += (n-1) * 2)  //公差规律
                    res += s[i];
            }
            else//中间行分两组公差为d = (n -1) * 2 的等差数列
            {//i与k的关系 第二个数列首项i + 第一个数列首项k = 公差d
                for (int k = j, i = n * 2 - 1 - j - 1; i < s.size() || k < s.size(); i += (n - 1) * 2, k += (n - 1) * 2)    
                {
                    if (k < s.size()) res += s[k];//按顺序先加k  
                    if (i < s.size()) res += s[i];
                }
            }
        }
        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

LeetCode 7. 整数反转-简

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0

提示：

-231 <= x <= 231 - 1

long long版【虽有限制但可AC】

class Solution {
public:
    int reverse(int x) {
        long long r = 0;
        while(x)
        {
            r = r * 10 + x % 10;
            x /= 10;
        }
        if(r > INT_MAX) return 0; //题目限制边界【意思像是不能用long long但是不报错(代码写法可以多样, 所有结果正确就行)】
        if(r < INT_MIN) return 0; //超出int取int的边界值
        return r;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

依题意版

溢出等式： r * 10 + x % 10 > INT_MAX <==> r > (INT_MAX - x % 10) / 10 且r > 0才是溢出

class Solution {
public:
    int reverse(int x) {
        int r = 0;
        while (x) {
            if (r > 0 && r > (INT_MAX - x % 10) / 10) return 0;
            if (r < 0 && r < (INT_MIN - x % 10) / 10) return 0;
            r = r * 10 + x % 10;
            x /= 10;
        }
        return r;
    }
};

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

LeetCode 8. 字符串转换整数 (atoi)-模拟

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = “42”
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步：“42”（当前没有读入字符，因为没有前导空格）
^
第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
^
第 3 步：“42”（读入 “42”）
^
解析得到整数 42 。
由于 “42” 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：

输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
^
第 2 步：" -42"（读入 ‘-’ 字符，所以结果应该是负数）
^
第 3 步：" -42"（读入 “42”）
^
解析得到整数 -42 。
由于 “-42” 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：

输入：s = “4193 with words”
输出：4193
解释：
第 1 步：“4193 with words”（当前没有读入字符，因为没有前导空格）
^
第 2 步：“4193 with words”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
^
第 3 步：“4193 with words”（读入 “4193”；由于下一个字符不是一个数字，所以读入停止）
^
解析得到整数 4193 。
由于 “4193” 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+‘、’-’ 和 ‘.’ 组成

long long简化版

class Solution {
public:
    int myAtoi(string str) { //实现字符串转整数：atoi()函数
        int k = 0;
        while (k < str.size() && str[k] == ' ') k ++ ; //过滤空白字符串
        if (k == str.size()) return 0; 

        int minus = 1;//判断符号 【判断符号位】
        if (str[k] == '-') minus = -1, k ++ ;
        else if (str[k] == '+') k ++ ;

        long long res = 0; //long long版
        while (k < str.size() && str[k] >= '0' && str[k] <= '9') { //只有0-9可以有效转化
            int x = str[k] - '0';        
            res = res * 10 + x;
            k ++ ;
           if (res > INT_MAX) break; //res存的一定是正数
        }

        res *= minus;//乘上符号
        if(res > INT_MAX) return INT_MAX; //long long版不会溢出, 则按数值判断, 题意超出int范围返回int边界值 
        if(res < INT_MIN) return INT_MIN;

        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

依题防溢出int版

class Solution {
public:
    int myAtoi(string str) { //实现字符串转整数：atoi()函数
        int k = 0;
        while (k < str.size() && str[k] == ' ') k ++ ; //过滤空白字符串
        if (k == str.size()) return 0; 

        int minus = 1;//判断符号
        if (str[k] == '-') minus = -1, k ++ ;
        else if (str[k] == '+') k ++ ;

        int res = 0; //int版
        while (k < str.size() && str[k] >= '0' && str[k] <= '9') {
            int x = str[k] - '0';
            if (minus > 0 && res > (INT_MAX - x) / 10) return INT_MAX; //正数溢出等式: res * 10 + x > INT_MAX
            if (minus < 0 && -res < (INT_MIN + x) / 10) return INT_MIN;//负数溢出等输: -res * 10 - x < INT_MIN
            if (-res * 10 - x == INT_MIN) return INT_MIN; //等于特判
            res = res * 10 + x;//秦九韶
            k ++ ;//判断下一位
            if (res > INT_MAX) break; //大于溢出 
        }

        res *= minus;//乘上符号

        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

LeetCode 9. 回文数-多解

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true
示例 2：

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

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

-$2^{3}1$ <= x <= $2^{3}1$ - 1

最简版-【时间稍慢】

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        string s = to_string(x); //把x转化为字符串类型
        return s == string(s.rbegin(), s.rend()); //正序 与 逆序(妙)   【直接把表达式比较结果作为返回值】
    }
};
1
2
3
4
5
6
7
8

次简化版-【效率还行】

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        
        long long num = 0, t = x; //题目中x没有取值限制，需取LL  【此法更快】 
        while(x)
        {
            num = num * 10 + x % 10;
            x /= 10;
        }
        // if(num == t) return true;
        // return false;
        return num == t; //慢一些, 但是简化好写！！
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

reverse 与 string res(s)

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        string s = to_string(x);
        string res(s);
        reverse(s.begin(), s.end()); //reverse函数没有返回值
        return res == s;
    }
};
1
2
3
4
5
6
7
8
9
10

LeetCode 10. 正则表达式匹配-难

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2:

输入：s = “aa”, p = “a*”
输出：true
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3：

输入：s = “ab”, p = “."
输出：true
解释：".” 表示可匹配零个或多个（‘*’）任意字符（‘.’）。

提示：

1 <= s.length <= 20
1 <= p.length <= 30
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;
        for (int i = 0; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                if (j + 1 <= m && p[j + 1] == '*') continue;
                if (i && p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                } else if (p[j] == '*') {
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }

        return f[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 11. 盛最多水的容器-规律

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：

输入：height = [1,1]
输出：1

    \\~\\~   
提示：

• n == height.length
• 2 <= n <= $10^5$
• 0 <= height[i] <= $10^4$

class Solution {
public://双指针做法正确性证明：一定有一个指针先到达最优解边界, 之后另一个指针也不断靠近最优解边界【即一定会遍历到最优解】
    int maxArea(vector<int>& height) {  
        int res = 0;
        for(int i = 0, j = height.size() - 1; i < j;){      
            res = max(res, (j - i) * min(height[i], height[j]));//高度取min   ,宽度j - i
            if(height[i] > height[j]) j --;
            else i++;    
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11

my_code

class Solution {
public://双指针做法正确性证明：一定有一个指针先到达最优解边界, 之后另一个指针也不断靠近最优解边界【即一定会遍历到最优解】
    int maxArea(vector<int>& height) {  
        int res = 0;
        for(int i = 0, j = height.size() - 1; i < j;)
        {
            if(height[i] > height[j])
            {
                res = max(res, (j - i) * height[j]);
                j --;
            }
            else 
            {
                res = max(res, (j - i) * height[i]);
                i++;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 12. 整数转罗马数字-映射规律

y总详解跳转

class Solution { //找规律打表【从大到小找零钱】
public:
    string intToRoman(int num) {
        int values[] = {
            1000,                   //千位
            900, 500, 400, 100,     //百位
            90, 50, 40, 10,         //十位
            9, 5, 4, 1              //千位
        };
        string reps[] = {
            "M", 
            "CM", "D", "CD", "C", 
            "XC", "L", "XL", "X", 
            "IX", "V", "IV", "I"
        };

        string res;
        for (int i = 0; i < 13; i ++ ) 
            while(num >= values[i])//当前值大于对应值
            {
                num -= values[i]; //拼接后剩余值再次寻找匹配字符
                res += reps[i]; //拼接字符
            }
        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

class Solution {
public:
    string intToRoman(int num) {
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string reps[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        string res;
        for (int i = 0; i < 13; i ++ )
            while(num >= values[i])
            {
                num -= values[i];  //拼接后剩余值再次寻找匹配字符
                res += reps[i];
            }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 13. 罗马数字转整数
打表查表unordered_map hash

罗马数字规则：两个字母凑成的数改成单个判断：若前一位字符对应数值<后一位对应数值, 则减去前一位的数值,反之加上【如 $IV=V-I$ 】

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> hash;
        hash['I'] = 1, hash['V'] = 5, hash['X'] = 10;
        hash['L'] = 50, hash['C'] = 100, hash['D'] = 500;
        hash['M'] = 1000;

        int res = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(hash[s[i]] < hash[s[i + 1]]) res -= hash[s[i]];
            else res += hash[s[i]]; 
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode 14. 最长公共前缀-模拟

遍历string数组逐位判断

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) { //字符串数组strs
        string res;
        if(strs.empty()) return res; 

        for(int i = 0; ; i++)
        {
            if(i >= strs[0].size() ) return res; //不超出size() , 剪枝
            char c = strs[0][i]; //取第一个的字符串的第i个元素, 循环比较
            for(auto &str: strs) //遍历每一个字符串str 
                if(str.size() <= i || c != str[i] )   //若有不符合第i个长度超过或者第i个不相等, 停止循环,返回最长前缀
                    return res; 
            res += c; //每轮加上相等前缀
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode 15. 三数之和-单调枚举[模板]

$三数之和-模板$
最后两层双指针枚举-不重叠【注意下标】-加优化(跳过重复情况)

双指针:一般需 单调性(能优化一维)
三个数存1个数, 四个数存2个数, 五个数存3个数 , n个数枚举用dp

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end()); //双指针优化：【需要单调性】
        for (int i = 0; i < nums.size(); i ++ ) { //i > 0 因为下标i - 1 
            if (i > 0 && nums[i] == nums[i - 1]) continue; //跳过相同的数值【等效情况不重复判断】
            for (int j = i + 1, k = nums.size() - 1; j < k; j ++ ) { //三个指针不重叠 ,k从后往前
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; //用j-1同理需j > i + 1(第二项开始) && 过滤重复情况
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k -- ; //相加大于等于0的最小数,枚举的是k-1
                if (nums[i] + nums[j] + nums[k] == 0) {  //因为最后k--, 所以现在k位置对应上一句的k-1的位置
                    res.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return res; //不存在则返回空
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//这类写法可能更好理解一下：
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 三元组
        vector <vector<int>> a;
        int target;
        sort(nums.begin(), nums.end());
        // 先定一个点target，再用双指针进行扫描
        for (int i = 0; i < nums.size(); ++i) {
            // 去重操作
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((target = nums[i]) > 0) {
                break;
            }
            // 双指针扫描另外两个点
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (target + nums[l] + nums[r] < 0) ++l;
                else if (target + nums[l] + nums[r] > 0) --r;
                else {
                    a.push_back({target, nums[l], nums[r]});
                    ++l;
                    --r;
                    // 去重操作
                    while (l < r && nums[l - 1] == nums[l]) ++l;
                    while (l < r && nums[r + 1] == nums[r]) --r;
                }
            }
        }
        return 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
30
31
32
33
34
35

LeetCode 17. 电话号码的字母组合-dfs

class Solution { //全排列dfs爆搜
public:
    
    vector<string> res;
    string hash[10] = {  //映射表[直接利用下标位置关联]
        "", "", "abc", "def", //0, 1均空串
         "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz",
    };

    
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return res;
        dfs(digits, 0, "");
        return res;
    }

    void dfs(string& digits, int u, string path){
        if(u == digits.size() ) res.push_back(path);
        else{
            for(auto c: hash[digits[u] - '0'])
                dfs(digits, u + 1, path + c);
        }
    }
};


// 另一种变型想法：[解决语法问题]  (更主要用于离散式存储)
    // unordered_map hash[10] = {
    //     {0,""}, {1,""}, {2, "abc"}, {3,"def"},
    //     {4,"ghi"}, {5,"jkl"}, {6, "mno"}, 
    //     {7,"pqrs"}, {8,"tuv"}, {9,"wxyz"}, 
    // };
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

LeetCode 18. 四数之和-单调枚举[模板]

三数之和的扩展-当模板记

4枚举1,双指针2,3 ; 4枚举2,双指针3,4 ;同理5普通枚举3, 双指针4,5 ;再多就用dp

class Solution { //双指针先看单调性, 枚举n个数：跳过重复优化-可当模板记
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for(int i = 0; i < nums.size(); i++)
        {
            if(i && nums[i] == nums[i - 1] ) continue;
            for(int j = i + 1; j < nums.size(); j++)
            {
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                for(int k = j + 1, u = nums.size() - 1; k < u; k++) //最后只需 k < u ： k肯定不会越界
                {
                    if(k > j + 1 && nums[k] == nums[k - 1]) continue;
                    while(u - 1 > k && (long)nums[i] + nums[j] + nums[k] + nums[u - 1] >= target) u --;
                    if((long)nums[i] + nums[j] + nums[k] + nums[u] == target) //被卡常数开long
                        res.push_back({nums[i], nums[j], nums[k], nums[u]});
                }                    
            }
        }
        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

LeetCode 20. 有效的括号-栈

【栈】 + 妙用ASCLL码表-括号对的差值<=2

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        
        for(auto c: s)
        {
            if(c == '(' || c == '{' || c == '[' )  stk.push(c);
            else{
                if(stk.size() && abs(stk.top() - c) <= 2 ) stk.pop(); //观察ASCLL码表：不同括号的的ASCLL码差值均不超过2
                else return false;
            }
        }
        return stk.empty();//为空说明全部匹配成功 【或者返回stk.size() == 0 (bool类型只能返回0或1)】 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 22. 括号生成-dfs

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
1
2

示例 2：

输入：n = 1
输出：["()"]
1
2

提示：

1 <= n <= 8

---

$常用合法括号的枚举条件$

①任意前缀和 [左括号]的数量 >= [右括号]的数量
②左右括号数量相等

$扩展【卡特兰数】：合法括号序列数量=\frac{C_{2n}^n}{(n+1)}$

class Solution {
public:
    vector<string> res;

    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, ""); // n对括号, 选取左括号数量, 选取右括号数量, 返回合法括号字符串
        return res;
    }
    void dfs(int n, int lc, int rc, string str)
    {
        if(lc == n && rc == n) res.push_back(str); //②左右括号数量相等 && 填完n对 , 加入答案
        else
        {
            if(lc < n) dfs(n, lc + 1, rc, str + '(');  //①任意前缀和 '('的数量 >= ')'的数量
            if(rc < n && lc > rc ) dfs(n, lc , rc + 1, str + ')');  
        }
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode 28. 实现 strStr() -kmp

kmp

vector next(n + 1); 创建一个大小为n + 1，初始n + 1个元素为0的动态数组
next[j]回溯到j(上一个前缀和相等的位置),即j同时代表模式串p自身前后缀相等长度

class Solution {
public:
    int strStr(string s, string p) {
        if(p.empty()) return 0; //出题人的出的边界不是很好
        //if(s.empty() || p.empty()) return -1;
        int m = s.size(), n = p.size();  //(长度会+1,先计算长度)
        s = ' ' + s, p = ' ' + p;//【变成从1开始】,此时size+1
        vector<int> next(n + 1); //指定next数组长度n + 1  [p与s匹配时的每一个回溯位置, p的长度]【不加(n + 1)会报错】
        for(int i = 2, j = 0; i <= n; i++) 
        {
            while (j && p[i] != p[j + 1]) j = next[j];
            if (p[i] == p[j + 1]) j ++ ;
            next[i] = j;
        }

        for(int i = 1, j = 0; i <= m; i++)
        {
            while (j && s[i] != p[j + 1]) j = next[j];
            if (s[i] == p[j + 1]) j ++ ;
            if (j == n) return i - n;
        }
        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

LeetCode 29. 两数相除-模拟

二进制处理-倍增

class Solution { //要求不使用乘法、除法和 mod 运算符。
public:
    int divide(int x, int y) {
        typedef long long LL; 
        vector<LL> exp; //指数集
        bool is_minus = false;//符号位 
        if (x < 0 && y > 0 || x > 0 && y < 0) is_minus = true; //负数

        LL a = abs((LL)x), b = abs((LL)y); //转化为LL型正数相除
        for (LL i = b; i <= a; i = i + i) exp.push_back(i); //预处理除数y的2n次幂倍数：二进制表示  

        LL res = 0;
        for (int i = exp.size() - 1; i >= 0; i -- )
            if (a >= exp[i]) {
                a -= exp[i];
                res += 1ll << i; //注意res转LL防止过程中溢出(int型31位就溢出), 用1ll运算中转换
            }

        if (is_minus) res = -res; //确定符号 

        if (res > INT_MAX || res < INT_MIN) res = INT_MAX; //溢出返回INT_MAX

        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

LeetCode 32. 最长有效括号-栈

【理解抽象】
按段判断：
每段合法序列前缀必然是左括号数量 > 右括号数量

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int res = 0;

        // start 表示上一段第一次出现不合法的括号序列的右括号的位置
        for (int i = 0, start = -1; i < s.size(); i ++ ) {
            // 如果是左括号，左括号下标入栈
            if (s[i] == '(') stk.push(i); //栈存的是下标
            else { // 右括号
                if (stk.size()) { // 栈不为空，将当前右括号匹配掉
                    stk.pop(); // 弹出与之匹配的左括号
                    if (stk.size()) { // 如果当前栈中还有左括号，说明从栈顶所在位置的下一个位置到这个右括号之间是一个合法的括号序列，所以更新长度（样例："(()()"）
                        res = max(res, i - stk.top());
                    } else { // 否则如果和当前右括号匹配结束后，当前栈为空，那么从 start 位置开始的下一个位置（即下一段的开始位置）到当前右括号之间是一个合法的括号序列，所以用 start 更新长度（样例："()()"）
                        res = max(res, i - start);
                    }
                } else { // 如果当前右括号不能匹配成功，那这个位置就是这一段第一次出现不合法的括号序列的位置，更新 start
                    start = i;
                }
            }
        }

        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

LeetCode 33. 搜索旋转排序数组-相似

类比数的范围

前半段与后半段整体交换(内部顺序不变[保持段单调递增])
二分得到边界点下标： 找到满足某个性质的最后一个点
二分原理:区间分两段第一段满足某个性质, 另一段不满足
找边界位置下标：
if(其他位置都满足的性质) 更新排除满足的区间继续判断
else 不满足排除不满足的多个元素区间【缩减到只剩下一个位置：第一个不满足性质的位置】

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int l = 0, r = nums.size() - 1; //答案可能存在的区间
        while (l < r) {  //nums[k] 变为num[0]   【第一个二分查找段边界】
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;// 找第一个小等于nums[0]值【原nums[k]值】的位置（即此单调段边界r） //找到第一个不大于num[k]的值的下标【即两个段的分界下标,刚好是原来的num[0]的值】
            else r = mid - 1; 
        }

        if (target >= nums[0]) l = 0; //如果查找的target>=num[0]【原nums[k]值】则target在第一段查找
        else l = r + 1, r = nums.size() - 1; //否则在第二段二分查找

        while (l < r) { //判断完所在段区间,x >= target的条件具有二段性【即区间可根据性质二分,一段满足性质,另一段不满足性质】
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;//找到第一个满足nums[mid] >= target的下标
            else l = mid + 1;
        }

        if (nums[r] == target) return r;
        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

依题意得[暴力找hh]

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i = 0;i < nums.size(); i++)
            if(nums[i] == target) return i;
        return -1;
    }
};
1
2
3
4
5
6
7
8

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置-二分模板

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1}; //c++11返回写法    还有【return vector({-1, -1});】 和初始化 vector res(2, -1);

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if (nums[r] != target) return {-1, -1};

        int L = r;
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }

        return {L, r}; //c++11返回写法
    }
};
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

LeetCode 35. 搜索插入位置-简模板

STL

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(),nums.end(),target) - nums.begin(); //返回 >= target的第一个位置
    }
};
1
2
3
4
5
6

单调二分查找

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size(); 
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 36. 有效的数独-经典模拟

模拟-行-列-九宫格-偏移量-循环

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool st[9]; //映射0-8

        // 判断行
        for (int i = 0; i < 9; i ++ ) {
            memset(st, 0, sizeof st);
            for (int j = 0; j < 9; j ++ ) {
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    if (st[t]) return false;
                    st[t] = true;
                }
            }
        }

        // 判断列
        for (int i = 0; i < 9; i ++ ) {
            memset(st, 0, sizeof st);
            for (int j = 0; j < 9; j ++ ) {
                if (board[j][i] != '.') {
                    int t = board[j][i] - '1';
                    if (st[t]) return false;
                    st[t] = true;
                }
            }
        }

        // 判断小方格
        for (int i = 0; i < 9; i += 3)
            for (int j = 0; j < 9; j += 3) {
                memset(st, 0, sizeof st);
                for (int x = 0; x < 3; x ++ )
                    for (int y = 0; y < 3; y ++ ) {
                        if (board[i + x][j + y] != '.') {
                            int t = board[i + x][j + y] - '1';
                            if (st[t]) return false;
                            st[t] = true;
                        }
                    }
            }

        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
46

LeetCode 37. 解数独-经典

(类似八皇后-标记数组)
$row[i][t]+col[t][j]+九宫格编号cell[i/3][j/3][t]$

class Solution {
public:

    bool row[9][9], col[9][9], cell[3][3][9]; //行, 列, 小方阵【9个3*3】  
        
    void solveSudoku(vector<vector<char>>& q) {
        memset(row, 0, sizeof row);
        memset(col, 0, sizeof col);
        memset(cell, 0, sizeof cell);

        for (int i = 0; i < 9; i ++ ) 
            for (int j = 0; j < 9; j ++ )
                if (q[i][j] != '.') {//已经填写的先标记
                    int t = q[i][j] - '1'; //映射0-9
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;//(x-3, y - 3)映射到编号1-9的小方阵：标记数t
                }

        dfs(q, 0, 0);
    }


    bool dfs(vector<vector<char>>& q, int x, int y) {
        if (y == 9) x ++, y = 0; //遍历到最后一个,跳到下一行
        if (x == 9) return true; //若x == 9 ,则说明当前为(9, 9) 【填完】

        if (q[x][y] != '.') return dfs(q, x, y + 1);
        for (int i = 0; i < 9; i ++) //0-8填写
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {  //若没有填过i = 0-8
                q[x][y] = '1' + i; //按顺序填写
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true; //标记已填
                if (dfs(q, x, y + 1)) return true; //判断下一位 ：若能填完return ture
                q[x][y] = '.';
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            }

        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

LeetCode 38. 外观数列-模拟

class Solution { //1 11(一个1) 21(两个1)  1211(一个2两个1)   111221（一个1一个2二个1）
public:
    string countAndSay(int n) {
        string s = "1"; //第一轮为1
        for (int i = 0; i < n - 1; i ++ ) {//双指针模拟
            string t;
            for (int j = 0; j < s.size();) { //遍历s = 上一轮的t
                int k = j + 1;//k往前探索 
                while (k < s.size() && s[k] == s[j]) k ++ ; //与s[j]值相同k++
                t += to_string(k - j) + s[j]; //连续相同数值个数k-j + 对应数值s[j]
                j = k;
            }
            s = t; //每轮的答案s 
        }

        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 39. 组合总和-dfs

dfs-【关键是搜索顺序】

class Solution { //顺序暴搜 -  每个数可以被重复选,每轮选取c[u]的第i倍，选择一次放入一个c[u]   
public:

    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum(vector<int>& c, int target) {
        dfs(c, 0, target);
        return ans;
    }

    void dfs(vector<int>& c, int u, int target) { //拆分target的组合数
       if(target == 0)
        {
            ans.push_back(path); //放入整个数组
            return ;
        }

        if(u == c.size()) return; //可行性剪枝[选到最后一个数但没有答案]

        for(int i = 0; c[u] * i <= target; i++) //每位可以使用的数量之和 <= 目标值
        {
            dfs(c, u + 1, target - c[u] * i); //分支尝试
            path.push_back(c[u]);
        }

         for(int i = 0; c[u] * i <= target; i++) //恢复现场
        {
            path.pop_back();
        }
    }
};
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

LeetCode 40. 组合总和 II -dfs

先排序方便统计相同数值个数 + 上一题枚举 + cnt限制

//此题每个数只能选一次 
class Solution {
public:

    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum2(vector<int>& c, int target) {
        sort(c.begin(), c.end()); //先排序【相同数连在一起，方便统计相同数的个数】
        dfs(c, 0, target);

        return ans;
    }

    void dfs(vector<int>& c, int u, int target) {
            if(target == 0)
            {
                ans.push_back(path);
                return;
            }

            if(u == c.size()) return;

            int k = u + 1;
            while(k < c.size() && c[u] == c[k]) k++; //下一个数值的下标
            int cnt = k - u; //用c[u]填的位数i <= 还需再填的位数cnt

            for(int i = 0; c[u] * i <= target && i <= cnt; i++)
            {
                dfs(c, k, target - c[u] * i); //指针位置移动到k 【下一个不同数值的位置】
                path.push_back(c[u]);
            }

            for(int i = 0; c[u] * i <= target && i <= cnt; i++)
            {
                path.pop_back();
            }
        }
};
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

LeetCode 41. 缺失的第一个正数-桶排序

桶排序

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 1;

        for (auto& x : nums)
            if (x != INT_MIN) x -- ;

        for (int i = 0; i < n; i ++ ) {
            while (nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]])
                swap(nums[i], nums[nums[i]]);
        }

        for (int i = 0; i < n; i ++ )
            if (nums[i] != i)
                return i + 1;

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

LeetCode 43. 字符串相乘-双高精度乘法

逐位相乘再对应相加

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> A, B;
        int n = num1.size(), m = num2.size();
        for (int i = n - 1; i >= 0; i -- ) A.push_back(num1[i] - '0'); //逆序读入
        for (int i = m - 1; i >= 0; i -- ) B.push_back(num2[i] - '0');

        vector<int> C(n + m);
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                C[i + j] += A[i] * B[j]; //*利用小学乘法：逐位相乘再对应相加(结果1-99 * 10^(i+j)相对位置)
                //10^(i + j) 有多个数积落在此位 (如10 * 1000 与 100 * 100 )
        for (int i = 0, t = 0; i < C.size(); i ++ ) { //每位存的数若超过10说明有进位：处理进位,得到真实数值
            t += C[i];
            C[i] = t % 10; //在第i位进位，放回第i位
            t /= 10;
        }

        int k = C.size() - 1; //从后往前读取答案res   
        while (k > 0 && !C[k]) k -- ;  //去除前导0

        string res;
        while (k >= 0) res += C[k -- ] + '0'; //res + 映射对应字符数字 

        return res;
    }
};
//思路： 先按位相乘, 若超过两位数就有进位, 与更高位乘法结果的个位相加
// C[i + j] += A[i] * B[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

45. 跳跃游戏 II-理解

观察性质,分段长度1,2,3,…

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n); //f[i]表示从i到终点的最短距离

        for (int i = 1, j = 0; i < n; i ++ ) {
            while (j + nums[j] < i) j ++ ;
            f[i] = f[j] + 1;
        }

        return f[n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

dp

class Solution {
public:
    int jump(vector<int>& nums) {

        int n = nums.size();
        vector<int> f(n + 1);

        f[0] = 0;
        for(int i = 1; i < n; i++)
        {
            f[i] = 1e9;
            for(int j = 1; j <= i; j++)
            {
                if(nums[i - j] >= j)
                    f[i] = min(f[i], f[i - j] + 1);
            }
        }
        return f[n - 1];
    }
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

dfs

class Solution {
public:
    int res = 0;
    int jump(vector<int>& nums) {
        int n = nums.size();
        dfs(nums, n - 1, 0);
        return res;
    }

    void dfs(vector<int>& nums, int ed, int cnt) { //从后往前跳
        if (ed == 0) {
            res = cnt;
            return;
        }

        // 找出能跳到ed点并且下标最小的点
        int idx = -1;
        for (int i = ed - 1; i >= 0; i --) {
            if (nums[i] >= (ed - i)) { //能跳
                idx = i;
            }
        }

        dfs(nums, idx, cnt + 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

注释1

/*
f[i]代表nums[i]到nums[0]的最短距离
f[i]是分段的，每隔一段就加1。idx就代表每段最后一个位置，idxNext代表下一段最后一个位置
根据当前分段的最远距离，不断更新idxNext
*/
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.empty()) return 0;
        // idx代表这次最远序号, idxNext代表下一个最远序号, f代表nums[i]到nums[0]的最短距离
        int len = nums.size(), idx = 0, idxNext = 0, f = 0;
        for (int i = 0; i < len; i ++) {
            if (idx == i-1) { //过了上个分段，本段f加1
                f ++;
                idx = idxNext; //先更新idx
            }
            idxNext = max(idxNext, i + nums[i]); //后更新idxNext
        }
        return f;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

注释2

class Solution {
public:
    int jump(vector<int>& nums) 
    {
        int max_far = 0;// 目前能跳到的最远位置
        int step = 0;   // 跳跃次数
        int end = 0;    // 上次跳跃可达范围右边界（下次的最右起跳点）
        for (int i = 0; i < nums.size() - 1; i++)
        {
            max_far = std::max(max_far, i + nums[i]);
            // 到达上次跳跃能到达的右边界了
            if (i == end)
            {
                end = max_far;  // 目前能跳到的最远位置变成了下次起跳位置的有边界
                step++;         // 进入下一次跳跃
            }
        }
        return step;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 46. 全排列 -经典dfs

初始化长度写法path = vector(nums.size())

class Solution {
public:

    vector<vector<int>> res;
    vector<int> path;//开全局
    vector<bool> st;   
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        path = vector<int>(nums.size()); //开相同动态空间!!
        st = vector<bool>(nums.size());//初始化数组长度
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u)
    {
        if(u == nums.size()) res.push_back(path);  

        for(int i = 0; i < nums.size(); i++) //全排列nums内的元素
            if(!st[i])
            {
                path[u] = nums[i];
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = 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

LeetCode 47. 全排列 II -dfs

dfs

class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size(), false);
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = start; i < nums.size(); i ++ )
            if (!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                if (u + 1 < nums.size() && nums[u + 1] != nums[u])
                    dfs(nums, u + 1, 0);
                else
                    dfs(nums, u + 1, i + 1);
                st[i] = 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

LeetCode 51. N 皇后 - 经典DFS

构造函数初始化：vector<类型type>(大小size)

class Solution {
public:

    int n;
    vector<bool> col, dg, udg; //定义全局！！！
    vector<vector<string>> ans; //全部答案
    vector<string> path; //临时路径答案

    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        col = vector<bool>(n); //构造函数初始化！！！
        dg = udg = vector<bool>(n * 2);  //注意对角线个数【2n-1条】
        path = vector<string>(n, string(n, '.')); //初始化！！！

        dfs(0);
        return ans;
    }

    void dfs(int u) {
        if (u == n) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < n; i ++ ) {
            if (!col[i] && !dg[u + i]  && !udg[u - i + n] ) {
                col[i] = dg[u + i] = udg[u - i + n] = true; //发现 u - i + n 与 i - u + n都行hh
                path[u][i] = 'Q';
                dfs(u + 1);
                path[u][i] = '.';
                col[i] = dg[u + i] = udg[u - i + n]  = 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

LeetCode 52. N皇后 II -合法数量

class Solution {
public:
    long long ans = 0;
    int col[15], dg[25], udg[25];
    int totalNQueens(int n) {
        dfs(0, n);
        return ans;
    }

    void dfs(int u, int n) {
        if (u == n) {
            ans ++;
        }

        for (int i = 0; i < n; i ++ ) {
            if (!col[i] && !dg[u + i]  && !udg[u - i + n] ) {
                col[i] = dg[u + i] = udg[u - i + n] = true; //发现 u - i + n 与 i - u + n都行hh
                // path[u][i] = 'Q';
                dfs(u + 1, n);
                // path[u][i] = '.';
                col[i] = dg[u + i] = udg[u - i + n]  = 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

LeetCode 53. 最大子序和-dp

DP 时间O(n)，空间 O(1)

f(i) 表示以第 i个数字为结尾的最大连续子序列的 总和 是多少

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(), ans;
        vector<int> f(n);
        f[0] = nums[0];
        ans = f[0];

        for (int i = 1; i < n; i++) {
            f[i] = max(f[i - 1] + nums[i], nums[i]);
            ans = max(ans, f[i]);
        }

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

分治 时间O(n)，空间O(logn)

class Solution {
public:

    struct Node {
        int sum, s, ls, rs;
    };

    Node build(vector<int>& nums, int l, int r) {
        if (l == r) {
            int v = max(nums[l], 0);
            return {nums[l], v, v, v};
        }

        int mid = l + r >> 1;
        auto L = build(nums, l, mid), R = build(nums, mid + 1, r);
        Node res;
        res.sum = L.sum + R.sum;
        res.s = max(max(L.s, R.s), L.rs + R.ls);
        res.ls = max(L.ls, L.sum + R.ls);
        res.rs = max(R.rs, R.sum + L.rs);
        return res;
    }

    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        for (auto x: nums) res = max(res, x);
        if (res < 0) return res;
        auto t = build(nums, 0, nums.size() - 1);
        return t.s;
    }
};
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

LeetCode 54. 螺旋矩阵 -基础

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int n = matrix.size();
        if (!n) return res; //没有元素
        int m = matrix[0].size();

        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
        vector<vector<bool>> st(n, vector<bool>(m)); //标记！！

        for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++ ) {
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) { //标记条件 (若没有标记会重复走：比如走一圈回到起点)
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }

            x = a, y = b;
        }

        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

LeetCode 55. 跳跃游戏 - 理解

class Solution {
public:
    bool canJump(vector<int>& nums) {
        for (int i = 0, j = 0; i < nums.size(); i ++ ) {
            if (j < i) return false; //说明j = i, 且nums[i] = 0 ,i++, i > j
            j = max(j, i + nums[i]);  
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10

LeetCode 56. 合并区间-模板题

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) { //a存放所有区间{l, r}
        vector<vector<int>> res;
        if (a.empty()) return res; //特判空，返回空

        sort(a.begin(), a.end()); //左端点从小到大
        int l = a[0][0], r = a[0][1];
        for (int i = 1; i < a.size(); i ++ ) {
            if (a[i][0] > r) { //没有交集, 加入res
                res.push_back({l, r});
                l = a[i][0], r = a[i][1];
            }
            else r = max(r, a[i][1]); //有交集合并, 更新右端点
        }

        res.push_back({l, r});
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 58. 最后一个单词的长度 - 模拟

class Solution {
public:
    int lengthOfLastWord(string s) { //self
        int cnt = 0;

            int i = s.size() - 1;
            while(s[i] == ' ') i--;
            while(i >= 0 && s[i] != ' ') i--, cnt ++;

        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int lengthOfLastWord(string s) {
        int sum = 0, res = 0;
        for (int i = 0; i < s.size(); i ++ )
            if (s[i] == ' ')
            {
                if (sum) res = sum;
                sum = 0;
            }
            else
                sum ++ ;
        if (sum) res = sum;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 59. 螺旋矩阵 II - 基础

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));

        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};

        for (int x = 0, y = 0, i = 0, d = 1; i < n * n; i ++ )
        {
            res[x][y] = i + 1;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a == n || b < 0 || b == n || res[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }

        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

LeetCode 60. 第k个排列 -STL

使用next_permutaion O(n!×n)

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        for (int i = 1; i <= n; i ++ ) res += to_string(i);
        for (int i = 0; i < k - 1; i ++ ) {
            next_permutation(res.begin(), res.end());
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11

LeetCode 62. 不同路径 - 经典模型

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(n, vector<int>(m));
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (!i && !j) f[i][j] = 1;
                else {
                    if (i) f[i][j] += f[i - 1][j];
                    if (j) f[i][j] += f[i][j - 1];
                }

        return f[n - 1][m - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode 63. 不同路径 II -加限制

走法相同+判断

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& o) {
        int n = o.size();
        if (!n) return 0;
        int m = o[0].size();

        vector<vector<int>> f(n, vector<int>(m));
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (!o[i][j]) { //【判断】
                    if (!i && !j) f[i][j] = 1;
                    else {
                        if (i) f[i][j] += f[i - 1][j];
                        if (j) f[i][j] += f[i][j - 1];
                    }
                }

        return f[n - 1][m - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

64. 最小路径和 - dp

dp

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        if (!n) return 0;
        int m = grid[0].size();

        vector<vector<int>> f(n, vector<int>(m, INT_MAX));
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ ) {
                if (!i && !j) f[i][j] = grid[i][j];
                else {
                    if (i) f[i][j] = min(f[i][j], f[i - 1][j] + grid[i][j]);
                    if (j) f[i][j] = min(f[i][j], f[i][j - 1] + grid[i][j]);
                }
            }

        return f[n - 1][m - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 66. 加一 - 模拟

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        reverse(digits.begin(), digits.end());
        int t = 1;
        for (auto& x: digits) { //修改
            t += x;
            x = t % 10;
            t /= 10;
        }
        if (t) digits.push_back(t);

        reverse(digits.begin(), digits.end());

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

LeetCode 67. 二进制求和-模板

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        string c;
        for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++ ) {
            if (i < a.size()) t += a[i] - '0';
            if (i < b.size()) t += b[i] - '0';
            c += to_string(t % 2);
            t /= 2;
        }

        reverse(c.begin(), c.end());
        return c;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

69. x 的平方根 -二分

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            int mid = l + 1ll + r >> 1;
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }

        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 70. 爬楼梯 - 斐波那契

class Solution {
public:
    int f[50];
    void init_Fib() //题目：下标从0开始为第一项
    {
        int a = 0, b = 1, c;
        f[0] = 0, f[1] = 1;
        for(int i = 2; i <= 46; i++)
        {
            c = a + b;
            a = b, b = c;
            f[i] = c;
        }
    }
    int climbStairs(int n) {
        init_Fib();
        return f[n+1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r; //输出递推c
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        while ( -- n) {
            int c = a + b;
            a = b, b = c;
        }
        return b;
    }
};
1
2
3
4
5
6
7
8
9
10
11

LeetCode 72. 编辑距离 - dp

线性DP-编辑距离模板

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size(), m = b.size();
        a = ' ' + a, b = ' ' + b;
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        for (int i = 0; i <= n; i ++ ) f[i][0] = i;
        for (int i = 1; i <= m; i ++ ) f[0][i] = i;

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
            }

        return f[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode 73. 矩阵置零 - 模拟

tql

// 我们先按行遍历，遍历每一行时，用数组记录更新每一列中是否出现过 0，然后更新这一行是否全为 0。
// 然后在对每一列进行判断，如果这一列出现过一次 0，则更新这一列
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size(); //m行n列
        vector<bool> zero(n, false);
        for (int i = 0; i < m; i++) {
            bool z = false; 
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == 0) { 
                    zero[j] = true; //i行j列有0
                    z = true;
                }
            if (z) { //若有0,j列对应行置0
                for (int j = 0; j < n; j++) 
                    matrix[i][j] = 0;
            }
        }

        for (int j = 0; j < n; j++) //遍历列
            if (zero[j]) { //有出现0把对应列置0
                for (int i = 0; i < m; i++)
                    matrix[i][j] = 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

LeetCode 74. 搜索二维矩阵 - 二分映射

1~n*m映射二维坐标(x, y)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false; // || matrix[0].empty()可略
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (matrix[mid / m][mid % m] >= target) r = mid;  //1-m*n下标映射(x, y)
            else l = mid + 1;
        }
        return matrix[r / m][r % m] == target;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode 75. 颜色分类-三指针

class Solution {
public:
    void sortColors(vector<int>& nums) { //三指针
        for(int i =0, j = 0, k = nums.size() - 1; i <= k;)
        {
            if(nums[i] == 0) swap(nums[i++], nums[j++]); //0归为前一段, 1归中间为一段, 
            else if(nums[i] == 2) swap(nums[i] ,nums[k--]); //
            else i++;
        }
    }
};
//没有限制 sort 函数则可以扫描一遍统计0, 1, 2 的个数填写一遍就好
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 77. 组合 - dfs

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combine(int n, int k) {
        dfs(0, 1, n, k);
        return ans;
    }

    void dfs(int u, int start, int n, int k) //start
    {
        if (u == k)
        {
            ans.push_back(path); //放入二维vector>的一个元素：vector
            return ;
        }

        for (int i = start; i <= n; i ++ )
        {
            path.push_back(i);
            dfs(u + 1, i + 1, n, k); 
            path.pop_back();
        }
    }
};
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

LeetCode 78. 子集 - dfs

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    void dfs(int cur, vector<int>& nums) {
        if (cur == nums.size()) {
            ans.push_back(t);
            return;
        }
        t.push_back(nums[cur]);
        dfs(cur + 1, nums);  // 考虑选择当前位置
        t.pop_back(); 
        dfs(cur + 1, nums);   // 考虑不选择当前位置
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0, nums);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

LeetCode 79. 单词搜索 - dfs

class Solution {
public:
    bool exist(vector<vector<char>>& board, string str) {
        for (int i = 0; i < board.size(); i ++ ) //枚举不同起点
            for (int j = 0; j < board[i].size(); j ++ )
                if (dfs(board, str, 0, i, j))
                    return true;
        return false;
    }

    bool dfs(vector<vector<char>> &board, string &str, int u, int x, int y) {
        if (board[x][y] != str[u]) return false;
        if (u == str.size() - 1) return true; 
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        char t = board[x][y];
        board[x][y] = '*'; //走过标记-若不可行则dfs不会重复走
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < board.size() && b >= 0 && b < board[0].size()) {
                if (dfs(board, str, u + 1, a, b)) return true;
            }
        }
        board[x][y] = t; //恢复现场
        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

LeetCode 80. 删除排序数组中的重复项 II - 单调指针

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3) return nums.size();
        int k = 1;
        for (int i = 2; i < nums.size(); i ++ )
            if (nums[i] != nums[k - 1]) //单调上升
                nums[ ++ k] = nums[i];
        k ++ ;
        return k;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 84. 柱状图中最大的矩形 - 难

模拟规律栈
wzc1995

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), ans = 0;
        heights.push_back(-1);
        // 为了算法书写方便，在数组末尾添加高度 -1
        // 这会使得栈中所有数字在最后出栈。

        stack<int> st;
        for (int i = 0; i <= n; i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int cur = st.top();
                st.pop();

                if (st.empty())
                    ans = max(ans, heights[cur] * i);
                else
                    ans = max(ans, heights[cur] 
                            * (i - st.top() - 1));
            }
            st.push(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

LeetCode 85. 最大矩形- 枚举-难

wzc1995

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m, ans = 0;
        if (n == 0)
            return 0;

        m = matrix[0].size();
        vector<int> heights(m + 1, 0);
        heights[m] = -1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == '0')
                    heights[j] = 0;
                else
                    heights[j]++;

            stack<int> st;
            for (int j = 0; j <= m; j++) {
                while (!st.empty() && heights[j] < heights[st.top()]) {
                    int cur = st.top();
                    st.pop();

                    if (st.empty())
                        ans = max(ans, heights[cur] * j);
                    else
                        ans = max(ans, heights[cur] * (j - st.top() - 1));
                }

                st.push(j);
            }
        }

        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

LeetCode 88. 合并两个有序数组 - 题目

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int k = n + m - 1;
        int i = m - 1, j = n - 1; //依题意从后往前不会覆盖
        while(i >= 0 && j >= 0)
        {
            if(nums1[i] >= nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }
        while(i >= 0) nums1[k--] = nums1[i--];
        while(j >= 0) nums1[k--] = nums2[j--];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 89. 格雷编码

构造
其他三种算法

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res(1, 0); //n >= 1 初始化
        while (n -- ) {
            for (int i = res.size() - 1; i >= 0; i -- ) { //最后一位数
                res[i] *= 2; // <<= 1  二进制最后一位后面加1  
                res.push_back(res[i] + 1); 
            }
        }
        return res;
    }
};//二进制表示
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 90. 子集 II - dfs

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 把所有相同的数放在一起，方便后续处理
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u)
    {
        res.push_back(path);
        for (int i = u; i < nums.size(); i ++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
            // 只要前一个数和后一个数相同，就不再遍历这个数
            while (i + 1 < nums.size() && nums[i] == nums[i + 1]) 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

LeetCode 91. 解码方法 - dp或

class Solution {  //DP  f[i] 表示前 i 个数字共有多少种解码方式
public:     //https://www.acwing.com/solution/content/173/
    int numDecodings(string s) {  
        if (s.empty()) return 0;
        int n = s.size();
        vector<int> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            if (s[i - 1] < '0' || s[i - 1] > '9')
                return 0;
            f[i] = 0;
            if (s[i - 1] != '0') f[i] = f[i - 1];
            if (i > 1)
            {
                int t = (s[i-2]-'0')*10+s[i-1]-'0';
                if (t >= 10 && t <= 26)
                    f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

//1 或 2位  映射分支递归，若能遍历到最后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

LeetCode 93. 复原IP地址

够直观够暴力

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;

        for (int a = 1; a < 4; a ++ )
            for (int b = 1; b < 4; b ++ )
                for (int c = 1; c < 4; c ++ )
                    for (int d = 1; d < 4; d ++ )           //abcd分别表示四段ip地址长度
                    {
                        if (a + b + c + d == s.size())      //四段长度刚好
                        {
                            string s1 = s.substr(0, a);     //分别截取四段ip地址
                            string s2 = s.substr(a, b);
                            string s3 = s.substr(a + b, c);
                            string s4 = s.substr(a + b + c);

                            if (check(s1) && check(s2) && check(s3) && check(s4))
                            {
                                string ip = s1 + '.' + s2 + '.' + s3 + '.' + s4;
                                res.push_back(ip);
                            }
                        }
                    }

        return res;
    }

    bool check(string s)        //判断ip地址每段的第一位不为0，或只有一位且该位为0
    {
        if (stoi(s) <= 255)
            if (s[0] != '0' || (s[0] == '0' && s.size() == 1)) return true;

        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

LeetCode 111. 二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        if (root->left && root->right) return min(minDepth(root->left), minDepth(root->right)) + 1;
        if (root->left) return minDepth(root->left) + 1;
        return minDepth(root->right) + 1;
    }
};
1
2
3
4
5
6
7
8
9
10

LeetCode 112. 路径总和 -dfs

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right) return root->val == sum;
        if (root->left && hasPathSum(root->left, sum - root->val)) return true;
        if (root->right && hasPathSum(root->right, sum - root->val)) return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10

LeetCode 113. 路径总和 II - dfs

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (root) dfs(root, sum);
        return ans;
    }

    void dfs(TreeNode* root, int sum) {
        path.push_back(root->val);
        sum -= root->val;
        if (!root->left && !root->right) {
            if (!sum) ans.push_back(path);
        } else {
            if (root->left) dfs(root->left, sum);
            if (root->right) dfs(root->right, sum);
        }
        path.pop_back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LeetCode 118. 杨辉三角 -多项式系数-$C_n^i$

class Solution {
public:
    vector<vector<int>> generate(int n) {
        vector<vector<int>> f; //二维存ans
        for (int i = 0; i < n; i ++ ) {
            vector<int> line(i + 1); //每行 
            line[0] = line[i] = 1;
            for (int j = 1; j < i; j ++ )
                line[j] = f[i - 1][j - 1] + f[i - 1][j]; //公式规律
            f.push_back(line);
        }
        return f;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 119. 杨辉三角 II -组合数

组合数模板

class Solution {
public:
    vector<int> getRow(int n) {
        vector<int> C(n + 1);

        long long res = 1;
        for(int i = 0, a = n, b = 1;i <= n; i ++) //组合数
        {
            C[i] = res;
            res = res * (a --) / (b ++);
        }

        vector<int> res;
        for(int i = 0;i <= n; i ++) res.push_back(C[i]);
       
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> last(rowIndex + 1), now(rowIndex + 1);
        last[0] = 1;
        for (int i = 0; i < rowIndex; i ++ )
        {
            now[0] = last[0]; //now辅助滚动
            for (int j = 0; j + 1 <= i; j ++ )
                now[j + 1] = last[j] + last[j + 1]; //当前层 = 上一层公式和 [一维优化]
            now[i + 1] = last[i]; //最后一位=1
            last = now; //引用
        }
        return last;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

空间O(1)-从右往左更新只用一个数组

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i; j > 0; j--) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

杨辉三角-组合数-数学

官方公式推导

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;
        }
        return row;
    }
};
1
2
3
4
5
6
7
8
9
10
11

LeetCode 120. 三角形最小路径和 -从后往前

class Solution {
public:
    int minimumTotal(vector<vector<int>>& f) {
        for (int i = f.size() - 2; i >= 0; i -- ) //从倒数第一行开始往上走
            for (int j = 0; j <= i; j ++ )
                f[i][j] += min(f[i + 1][j], f[i + 1][j + 1]); //当前行(从倒二算起) += 下一行最小路径和
        return f[0][0];
    }
};
1
2
3
4
5
6
7
8
9

LeetCode 121. 买卖股票的最佳时机 - 最大差值

class Solution { //求最大差值
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 0, minp = INT_MAX; i < prices.size(); i ++ ) {
            res = max(res, prices[i] - minp);  // 当天卖出利润_max =当天卖出的最大差值= (当前 - 过往买入最小值)
            minp = min(minp, prices[i]); //min(过往价格最小值,  当前价格)
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11

LeetCode 122. 买卖股票的最佳时机 II - 妙思

多天的差值可拆成间隔两天，有利润>0就交易

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 0; i + 1 < prices.size(); i ++ )
            res += max(0, prices[i + 1] - prices[i]);
        return res;
    }
};
1
2
3
4
5
6
7
8
9

状态机

LeetCode 123. 买卖股票的最佳时机 III -两次最大差值和

先计算出一次在第i天前卖出的交易max[题121]，存f[i]
再枚举第二轮交易的第i天$ma{x}_{i2}+f[i-1]$，(因不能同时拥有两支，先卖再买，需加f[n-1]，且【从后往前】枚举两次最大差值之和)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> f(n + 2);
        for (int i = 1, minp = INT_MAX; i <= n; i ++ ) {
            f[i] = max(f[i - 1], prices[i - 1] - minp);
            minp = min(minp, prices[i - 1]);
        }

        int res = 0;
        for (int i = n, maxp = 0; i; i -- ) { //【从后往前-后段延伸至前买卖】
            res = max(res, maxp - prices[i - 1] + f[i - 1]); //二轮利润max + 一轮利润max
            maxp = max(maxp, prices[i - 1]); //(未来卖出价格max,当前价格)
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode 125. 验证回文串

class Solution {
public:
    bool isPalindrome(string s) {
        string s2 = "";
        for(int i = 0; i < s.size();i++)
        {
            if(isalpha(s[i]) || isdigit(s[i]) ) s2 += tolower(s[i]); //保留字符和数字
        }
        //  cout << s2 << endl;
        for(int i = 0, j = s2.size() - 1; i <= j; i++, j--)
        {
            if(s2[i] != s2[j]) return false;
        }         
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 128. 最长连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> S; //set去重
        for (auto x: nums) S.insert(x); 

        int res = 0;
        for (auto x: nums) { //遍历一遍
            if (S.count(x) && !S.count(x - 1)) { //找到起点，(起点条件:前面一个数x-1不存在,x才为起点)
                int y = x;
                S.erase(x); //一定要删除起点,防止重复遍历 , O(n)
                while (S.count(y + 1)) {
                    y ++ ;
                    S.erase(y); //【确定y不是起点，删除防止遍历y为起点增加时间复杂度(更短非最长)】
                }
                res = max(res, y - x + 1);
            }
        }

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

LeetCode 130. 被围绕的区域

class Solution {  //类似池塘计数
public:
    int n, m;
    vector<vector<char>> board;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    void solve(vector<vector<char>>& _board) {
        board = _board; //元素相等，地址不同
        n = board.size();
        if (!n) return;//空
        m = board[0].size();

        for (int i = 0; i < n; i ++ ) { //遍历左右边界
            if (board[i][0] == 'O') dfs(i, 0); 
            if (board[i][m - 1] == 'O') dfs(i, m - 1);
        }

        for (int i = 0; i < m; i ++ ) { //遍历上下边界
            if (board[0][i] == 'O') dfs(0, i); 
            if (board[n - 1][i] == 'O') dfs(n - 1, i);
        }

        for (int i = 0; i < n; i ++ ) //【边界上的'o'被标记为'#'，其余都是'x'】
            for (int j = 0; j < m; j ++ )
                if (board[i][j] == '#') board[i][j] = 'O';  //任意一个其他字符如'#'标记搜过
                else board[i][j] = 'X';

        _board = board; //题目要求改变【引用更新】
    }

    void dfs(int x, int y) {  //遍历每块'O'区域,遍历过的标记为'#'
        board[x][y] = '#';
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && board[a][b] == 'O') //标记连通块
                dfs(a, b);
        }
    }
};
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

LeetCode 131. 分割回文串

bool f[i][j]：$字符串s[i]\to [j]是否为回文串$

class Solution { 
public:
    vector<vector<bool>> f;
    vector<vector<string>> ans;
    vector<string> path;

    vector<vector<string>> partition(string s) {
        int n = s.size();
        f = vector<vector<bool>>(n, vector<bool>(n));  //f[i][j] = true 代表 左边界i~ 右边界j 是回文串
        for (int j = 0; j < n; j ++ ) //【先枚举j, 保证f[i + 1][j - 1]状态先计算出】遍历区间[i,j]标记回文串
            for (int i = 0; i <= j; i ++ ) //左边界 <= 右边界
                if (i == j) f[i][j] = true; //自身回文
                else if (s[i] == s[j]) {//若相等 
                    if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true; //已经遍历完[i,j] 或 s[i] == s[j]&&中间f[i + 1][j - 1]=true 为回文串
                }

        dfs(s, 0);
        return ans;
    }

    void dfs(string& s, int u) { //递归字符串s,当前开始下标u开始分割  【爆搜】
        if (u == s.size()) ans.push_back(path); //能搜完成功分割,加入答案
        else {
            for (int i = u; i < s.size(); i ++ ) 
                if (f[u][i]) { //若u~i为回文串
                    path.push_back(s.substr(u, i - u + 1)); //path辅助数组暂存答案：起点u长度为i-u+1的回文串 
                    dfs(s, i + 1); //i是这段的最后一个字符，下一段判断回文的区间起点为i+1
                    path.pop_back(); //恢复现场
                }
        }
    }
};
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

LeetCode 134. 加油站 - 结论证明

class Solution { //环形抽象问题，能否从某个点走完一圈
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int i = 0, j; i < n; ) {  // 枚举起点
            int left = 0;
            for (j = 0; j < n; j ++ ) {
                int k = (i + j) % n;    
                left += gas[k] - cost[k];
                if (left < 0) break;
            }
            if (j == n) return i;
            i = i + j + 1; //优化： 若i走到j停止无法到终点, 则i~j中的任意一点都不可能成功走完   任取一点观察， 严格反证法 
        }

        return -1;
    }
};
//P1088 提高课 - 单调队列写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

LeetCode 136. 只出现一次的数字 - 简

class Solution {
public:
    
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            if(ans == nums[i]) i++, ans = nums[i]; //换下一个
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 137. 只出现一次的数字 II - 简

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            if(ans == nums[i]) i+=2, ans = nums[i]; //换下一个
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 149. 直线上最多的点数

class Solution { //枚举每一个点作为固定点，将剩下的点按照与该点的斜率划分
public:
    int maxPoints(vector<vector<int>>& points) {
        typedef long double LD; //精度

        int res = 0;
        for (auto& p: points) { //枚举起点
            int ss = 0, vs = 0;
            unordered_map<LD, int> cnt;
            for (auto& q: points) //枚举其他点(但也枚举了自己-需处理)
                if (p == q) ss ++ ; //（处理自己）与定点重合的点可以被分到所有组中，需要单独处理 中心点ssource   [hahs自带比较]
                else if (p[0] == q[0]) vs ++ ;  //特殊：竖直直线不存在斜率，需要单独计数
                else {
                    LD k = (LD)(q[1] - p[1]) / (q[0] - p[0]); //斜率
                    cnt[k] ++ ; 
                }
            int c = vs;
            for (auto [k, t]: cnt) c = max(c, t); //此点组成的直线的最多点的个数
            res = max(res, c + ss);//定点重合与其他点组合的直线数量+ss
        }
        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

LeetCode 150. 逆波兰表达式求值 - 栈

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        for (auto &t : tokens)
            if (t == "+" || t == "-" || t == "*" || t == "/") //遇到操作符，取栈顶两个数计算
            {
                int b = stk.top(); //先出为第二个操作数
                stk.pop();
                int a = stk.top();
                stk.pop();
                if (t == "+") stk.push(a + b); 
                else if (t == "-") stk.push(a - b);
                else if (t == "*") stk.push(a * b);
                else stk.push(a / b);
            }
            else stk.push(atoi(t.c_str())); //遇到数值，string转char数组->存入int栈
        return stk.top(); //返回计算结果
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 151. 翻转字符串里的单词 - 分步模拟

单词内部不变，单词间顺序颠倒，输入为含空格的一串单词组成字符串s

分步实现思想
①先把每个单词翻转
②再把整个字符串翻转
注意前后有多个空格要删掉

class Solution {
public:
    string reverseWords(string s) { //先翻转每个单词再翻转整个字符串
        int k = 0;  
        for (int i = 0; i < s.size(); i ++ ) { //①翻转每个单词
            if (s[i] == ' ') continue;
            int j = i, t = k; //j往前探索, k为新存放的位置 【类似merge排序的写法】
            while (j < s.size() && s[j] != ' ') s[t ++ ] = s[j ++ ];//去除多余空格放入
            reverse(s.begin() + k, s.begin() + t);  //把这个单词翻转
            s[t ++ ] = ' '; //最后一个位置放入空格
            k = t, i = j; //更新下一轮指针的初始位置
        }
        if (k) k -- ; //说明有单词, 最后一个空格要删去
        s.erase(s.begin() + k, s.end()); //删去末尾多余的空格[总长度为k] 
        reverse(s.begin(), s.end());  //②翻转整个字符串
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 152. 乘积最大子数组 - 区间乘积 - 推导

推导 - 三种可能

class Solution {
public:
    int maxProduct(vector<int>& nums) { //0~i区间最大值f[i]; 0~i区间最小值g[i]
        int res = nums[0]; //子序列至少包含一个数字
        int f = nums[0], g = nums[0];
        for (int i = 1; i < nums.size(); i ++ ) { //递推
            int a = nums[i], fa = f * a, ga = g * a; 
            f = max(a, max(fa, ga)); //a<0, f[i] = g[i - 1] * a 或 nums[i]; a > 0,  f[i] = f[i - 1] * a 或 nums[i];
            g = min(a, min(fa, ga)); //a<0, g[i] = f[i - 1] * a 或 nums[i]; a > 0,  g[i] = g[i - 1] * a; 或 nums[i]
            res = max(res, f); 
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 153. 寻找旋转排序数组中的最小值 -二分

class Solution {//二分
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        if (nums[r] >= nums[l]) return nums[0]; //整个区间单调递增，特判min.
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 154. 寻找旋转排序数组中的最小值 II -二分

class Solution { //二分
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r && nums[r] == nums[0]) r -- ; //多一步已找到的去重判断
        if (nums[l] <= nums[r]) return nums[0];
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 162. 寻找峰值 -简二分

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid; //单调递增-二分-找到下一个位置比自身小的第一个位置
            else l = mid + 1;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 164. 最大间距 - 简枚举

class Solution {
public:
    int res = 0;
    int maximumGap(vector<int>& nums) {
        if( nums.size() < 2) return 0; 
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 1; i++)
            res = max(res, abs(nums[i + 1] - nums[i]));
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11

LeetCode 167. 两数之和 II - 输入有序数组 - 双指针

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0, j = numbers.size() - 1; i < j; i ++ ) //j从后往前扫
        {
            while (numbers[j] + numbers[i] > target) j -- ;
            if (numbers[j] + numbers[i] == target)
            {
                vector<int> res;
                res.push_back(i + 1), res.push_back(j + 1); //下标
                return res;
            }
        }
        return {}; //......
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 168. Excel表列名称 -进制转换

int$\to$ string

class Solution {
public:
    string convertToTitle(int n) { //n看做26进制
        int k = 1;//确定位数,至少一位
        for (long long p = 26; n > p; p *= 26) { 
            n -= p; //减【去26进制的次方,判断位数】
            k ++ ; 
        }

        n -- ; //需n--后对应从0开始映射，0-25对应A-Z   (n >= 1可减)
        string res;
        while (k -- ) { //从个位开始填数
            res += n % 26 + 'A'; //【+=】
            n /= 26;
        }

        reverse(res.begin(), res.end()); //个位在最高位, 需翻转
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 169. 多数元素 - 摩尔投票法

class Solution {
public:
    
    int majorityElement(vector<int>& nums) {
        int ans = nums[0],cnt = 1;
        for(auto x: nums)
        {
            if(ans != x) cnt --;
            else cnt ++;
            if(cnt <= 0) ans = x,cnt = 1;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 171. Excel表列序号 -进制转换

string $\to$ int

class Solution {
public:
    int titleToNumber(string s) {
        long long res = 0, mul = 1;
        for(int i = s.size() - 1; i >= 0; i--) //从个位开始
        {
            res += (s[i] - 'A' + 1) * mul;
            mul *= 26;
        }
        return res;
    }
};
//'A' - 'A' + 1  == 1
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 172. 阶乘后的零 - 规律

$阶乘尾零-因子2与5的个数min(10=2\ast 5)$

class Solution {
public:
    int cnt2 = 0,cnt5 = 0;
    int trailingZeroes(int n) {
        for(int i = 1; i <= n; i++) //【统计1~n数的乘积的所有2,5因子】
        {
            int t = i;
            while(t % 2 == 0) t /= 2, cnt2 ++;
            while(t % 5 == 0) t /= 5, cnt5 ++;
        }
        return min(cnt2,cnt5);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 179. 最大数 - 模拟

重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int x, int y) {   //这种写法hh: [](int x, int y) 
            string a = to_string(x), b = to_string(y);
            return a + b > b + a; //定义了比较函数：如123 45 < 45 123  则45 排在123 前
        });
        string res;
        for (auto x: nums) res += to_string(x); //比较最高位to_string
        int k = 0;
        while (k + 1 < res.size() && res[k] == '0') k ++ ; //消除前导0 [全部0留下一个0，k+1开始]
        return res.substr(k); //截取子串从(k,结尾)
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 189. 旋转数组 - [原地算法-分段双翻转] - 空间O(1)

原地经典：【前k个与后k个交换】空间O(1),时间仍O(n)

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n; //等效后k个移为到前k个【翻转两步-先整体一次，再分两段翻转】
        reverse(nums.begin(), nums.end()); //先翻转
        reverse(nums.begin(), nums.begin() + k);  //翻转前k部分
        reverse(nums.begin() + k, nums.end());  //翻转后k部分
    }
};
1
2
3
4
5
6
7
8
9
10

非原地 - [无限制空间，使用]

class Solution {
public:
    vector<int> res;
    void rotate(vector<int>& nums, int k) {
        int n = nums.size(); k %= n; //先把k取模n，避省略重复移动
        for(int i = 0; i < n; i++)
        {
            res.push_back(nums[(i - k + n) % n]);
        }
        nums = res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 190. 颠倒二进制位

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; i ++ )
            res = res * 2 + (n >> i & 1);
        return res;
    }
};
1
2
3
4
5
6
7
8
9

LeetCode 198. 打家劫舍 - dp

$选或不选暴力枚举2^n，常用dp$

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1); //f[i]必选i的最大价值 , g[i]必不选i的最大价值
        for (int i = 1; i <= n; i ++ ) {
            f[i] = g[i - 1] + nums[i - 1]; //上一个不选即 g[i-1] 才能选i即f[i]
            g[i] = max(f[i - 1], g[i - 1]); //上一个状态f[i-1]与g[i-1]选或不选  转移到 g[i]
        }
        return max(f[n], g[n]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

200. 岛屿数量 - dfs连通块

class Solution {
public:
    vector<vector<char>> g;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        int cnt = 0;
        for (int i = 0; i < g.size(); i ++ )
            for (int j = 0; j < g[i].size(); j ++ )
                if (g[i][j] == '1') { //找到陆地，遍历陆地连通块
                    dfs(i, j);
                    cnt ++ ;
                }
        return cnt;
    }

    void dfs(int x, int y) {
        g[x][y] = 0; //【标记成0，节省空间】
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < g.size() && b >= 0 && b < g[a].size() && g[a][b] == '1') //连通块标记遍历
                dfs(a, b);
        }
    }
};
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

LeetCode 201. 数字范围按位与 -位运算-int型枚举

int取值范围[-2147483648 ~ 2147483647] $即-2^{31}\sim 2^{31}-1$
int型32位，二进制最高位为符号位，后31位数值
下标从0开始, 个位开始枚举，加上按位与

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int res = 0;
        for (int i = 30; i >= 0; i -- ) { //范围2^31-1=31位全为1 [个位下标0,最高位下标30]
            if ((m >> i & 1) != (n >> i & 1)) break;  // 按位与：某数字此二进制位为0，最后此二进制位为0，不用加
            if (m >> i & 1) res += 1 << i;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11

LeetCode 202. 快乐数 - 标记判环

hash表标记一轮,重复标记的数说明存在环不可能边变成1

class Solution {
public:
    int change(int x)
    {
        int res = 0;
        while(x) 
        {
            int t = x % 10;
            res += t * t; //每位的平方和
            x /= 10;
        }
        return res;
    }
    bool isHappy(int n) {
        unordered_map<int, int> hash; //st标记会炸int空间
        while(n != 1)
        {
            hash[n] ++;
            if(hash[n] > 1) return false;
            n = change(n);            
        }
        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

LeetCode 204. 计数质数 - 质数筛发

class Solution {
public:
    const static int M = 5000010; //不加static报错error
    bool st[M];
    int primes[M], cnt = 0;
    int countPrimes(int n) {
        for(int i = 2; i < n; i++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0; primes[j] <= n / i; j++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 205. 同构字符串 _一对一映射检查

(哈希表，映射) O(n)
我们要判断字母之间是否一一对应，即判断 s 中的相同字母是否对应到 t 中的相同字母，且 t 中的相同字母是否对应到 s 中的相同字母。

我们用两个哈希表分别存储 s 到 t 和 t 到 s 的映射关系。
然后从前往后扫描字符串，判断相同字符是否都映射到相同字符。

时间复杂度分析：哈希表的插入、查找操作的时间复杂度是 O(1)，两个字符串均只扫描一遍，所以总时间复杂度是 O(n)。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> st, ts;
        if (s.size() != t.size()) return false;
        for (int i = 0; i < s.size(); i ++ )
        {
            if (st.count(s[i])) //已有映射关系
            {
                if (st[s[i]] != t[i]) return false; //若s串中相同字符映射到t中不同字符，则false
            }
            else st[s[i]] = t[i]; //填写映射关系
             //同理
            if (ts.count(t[i]))
            {
                if (ts[t[i]] != s[i]) return false;
            }
            else ts[t[i]] = s[i];
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LeetCode 207. 课程表

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<int> d(n);
        for (auto& e: edges) {//[后完成课程, 先完成课程]
            int b = e[0], a = e[1]; //a→b
            g[a].push_back(b);//邻接矩阵存边
            d[b] ++ ; //入度++
        }

        queue<int> q;
        for (int i = 0; i < n; i ++ )
            if (d[i] == 0) //入度为0的点入队
                q.push(i);

        int cnt = 0;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            cnt ++ ; //统计点
            for (auto i : g[t])
                if ( -- d[i] == 0) 
                    q.push(i);
        }

        return cnt == n; //能遍历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

LeetCode 208. 实现 Trie (前缀树)

模板

LeetCode 209. 长度最小的子数组 - 双指针

目标和$⩾$ target，但是长度最短

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int res = INT_MAX; //统计长度
        for (int i = 0, j = 0, sum = 0; i < nums.size(); i ++ ) {
            sum += nums[i]; //累加
            while (sum - nums[j] >= s) sum -= nums[j ++ ]; //类似最长连续不重复子序列
            if (sum >= s) res = min(res, i - j + 1);
        }
        if (res == INT_MAX) res = 0;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode 210. 课程表 II

判断环，存路径

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<int> d(n); //【要用d[]先初始化空间】 等效int d[n]
        for (auto& e: edges) {
            int b = e[0], a = e[1];
            g[a].push_back(b);
            d[b] ++ ;
        }
        queue<int> q;
        for (int i = 0; i < n; i ++ )
            if (d[i] == 0)
                q.push(i);

        vector<int> res;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            res.push_back(t); //【存路径】
            for (int i: g[t])
                if ( -- d[i] == 0)
                    q.push(i);
        }
        if (res.size() < n) res = {}; //题目：有环返回空数组
        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

211. 添加与搜索单词 - 数据结构设计

LeetCode 213. 打家劫舍 II

打家劫舍I 基础上加限制：环-首尾相连(1与n相连)
分类选或不选1 (选1不能选n最大值g[n])

class Solution {
public:
    int rob(vector<int>& nums) { //多加了限制-1和n首尾相连不能一起选 【分类 选或不选 1】
        int n = nums.size();
        if (!n) return 0;
        if (n == 1) return nums[0];
        vector<int> f(n + 1), g(n + 1); //选i的最大值f[i], 不选i的最大值g[i]
        for (int i = 2; i <= n; i ++ ) { ///不选1
            f[i] = g[i - 1] + nums[i - 1]; 
            g[i] = max(f[i - 1], g[i - 1]);
        }
        int res = max(f[n], g[n]); 
        f[1] = nums[0]; //选1，不能选n ：最大值g[n]
        g[1] = INT_MIN; 
        for (int i = 2; i <= n; i ++ ) { //推导同理
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(res, g[n]); //max(不选1最大值, 选1最大值g[n])
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

214. 最短回文串 - 构造kmp

class Solution { //添加最少数量x得到最大 == len - 求原串的最长回文前缀
public:
    string shortestPalindrome(string s) {
        string t(s.rbegin(), s.rend()); //逆序
        int n = s.size();
        s = ' ' + s + '#' + t; //' '从1开始, '#'保证至少一个字符返回空 与逆序拼接【构造前后缀相等-kmp定义】
        vector<int> ne(n * 2 + 2);
        for (int i = 2, j = 0; i <= n * 2 + 1; i ++ ) { //kmp求拼接串的next数组
            while (j && s[i] != s[j + 1]) j = ne[j];
            if (s[i] == s[j + 1]) j ++ ;
            ne[i] = j;
        }
        int len = ne[n * 2 + 1]; //整个拼接串的最长相等前后缀- 最长前缀回文串
        string left = s.substr(1, len), right = s.substr(1 + len, n - len); //取出最长前缀回文串 和 需拼接两侧的回文部分
        return string(right.rbegin(), right.rend()) + left + right; //回文前需逆序 +  最长前缀回文串 + 回文后部分
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode 215. 数组中的第K个最大元素 -快排

LeetCode 216. 组合总和 III - dfs

选数组合成目标值

Y:求组合数一般要记个起始下标，求排列数一般每次从头开始枚举

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return ans;
    }

    void dfs(int k, int n, int start) 
    {
        if (!k) //挑选完
        {
            if (!n) ans.push_back(path);
            return;
        }

        for (int i = start; i <= 10 - k; i ++ )
            if (n >= i)
            {
                path.push_back(i); 
                dfs(k - 1, n - i, i + 1); //剩下挑k-1个,还需n-i,从数值i+1开始挑选
                path.pop_back(); //回溯
            }
    }
};
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

LeetCode 217. 存在重复元素 - 简

class Solution {
public:
    unordered_map<int, int> cnt;
    bool containsDuplicate(vector<int>& nums) {
        for(auto x: nums)
        {
            cnt[x] ++;
            if(cnt[x] >= 2) return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 219. 存在重复元素 II - 间距判断 简

间距判断存下标不存次数

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i ++ ) {
            int x = nums[i];
            if (hash.count(x) && i - hash[x] <= k) return true; //若已经出现过,判断间距
            hash[x] = i; //【存下标】
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 220. 存在重复元素 III - 滑动窗口二分-经典

是否存在 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k
维护区间 [j,i]小等于k的滑动窗口

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        typedef long long LL;
        multiset<LL> S; //盘距离不去重
        S.insert(1e18), S.insert(-1e18); //不会返回空 【加哨兵判边界】
        for (int i = 0, j = 0; i < nums.size(); i ++ ) {
            if (i - j > k) S.erase(S.find(nums[j ++ ])); //维护区间[j, i]小等于k滑动窗口, nums[j]滑出窗口
            int x = nums[i];
            auto it = S.lower_bound(x); //查找 >= x 的第一个元素
            if (*it - x <= t) return true; 
            -- it; //lower_bound下标的前一个函数为 < x 的第一个元素
            if (x - *it <= t) return true;
            S.insert(x); //加入窗口
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 221. 最大正方形 - dp

二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积

从左下往右上 dp 三条路径【正方形边长-木桶短板取min】

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0; 
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        int res = 0;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                if (matrix[i - 1][j - 1] == '1') { //matrix从0开始
                    f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + 1; //f[i][j]：以(i,j)为右下角的最大正方形边长
                    res = max(res, f[i][j]);
                }

        return res * res; //返回面积
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 222. 完全二叉树的节点个数

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        auto l = root->left, r = root->right;
        int x = 1, y = 1; //左右节点数量
        while (l) l = l->left, x ++ ; 
        while (r) r = r->right, y ++ ;
        if (x == y) return (1 << x) - 1; //满二叉树公式 2^n - 1  [剩下不相等节点-递归中当做子树的根]
        return countNodes(root->left) + 1 + countNodes(root->right); //左 + 根 + 右
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 223. 矩形面积 -容斥原理

class Solution { //(LL)面积和 - 交集
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        long long X = min(C, G) + 0ll - max(A, E);
        long long Y = min(D, H) + 0ll - max(B, F);
        return (C - A) * (D - B) - max(0ll, X) * max(0ll, Y) + (G - E) * (H - F);//加上 0ll 的效果就是把计算结果强制转化成long long
    }
};
1
2
3
4
5
6
7
8

LeetCode 226. 翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return 0;
        swap(root->left, root->right); //交换值
        invertTree(root->left), invertTree(root->right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9

LeetCode 228. 汇总区间 - 双指针 模拟

题目

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        for (int i = 0; i < nums.size(); i ++ ) {
            int j = i + 1;
            while (j < nums.size() && nums[j] == nums[j - 1] + 1) j ++ ;//找区间右端点
            if (j == i + 1) res.push_back(to_string(nums[i])); //区间仅一个元素
            else res.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1])); //区间多个元素
            i = j - 1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 229. 求众数 II - 摩尔投票法

n个数是否存在> n/3的众数[统计2个最多的数]

class Solution {//摩尔投票法-统计"仓库"里的数[不是数量-相对次数],不同减,相同加【可扩展到k个众数】
public:
    vector<int> majorityElement(vector<int>& nums) {
        int r1, r2, c1 = 0, c2 = 0; //c1，c2辅助相对数量，减到0换元素
        for (auto x: nums)
            if (c1 && x == r1) c1 ++ ;//相同加
            else if (c2 && x == r2) c2 ++ ;
            else if (!c1) r1 = x, c1 ++ ; //确定第一个数放入仓库
            else if (!c2) r2 = x, c2 ++ ; 
            else c1 --, c2 -- ;//不同减
        c1 = 0, c2 = 0; //二次使用用于统计仓库中的数(最多的两个数的)
        for (auto x: nums) //仓库存的r1,r2就是最多的两个数，答案就在其中 [>n/3最多两个ans], 统计数量
            if (x == r1) c1 ++ ;
            else if (x == r2) c2 ++ ;

        vector<int> res;
        int n = nums.size();
        if (c1 > n / 3) res.push_back(r1); //题意 > n / 3加入答案
        if (c2 > n / 3) res.push_back(r2);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LeetCode 230. 二叉搜索树中第K小的元素

作者：wzc1995

按照中序遍历规则遍历整棵二叉搜索树，并用数组记录结点的值。

class Solution {
public:
    void solve(TreeNode* cur, vector<int>& vals) {
        if (!cur) return;

        solve(cur -> left, vals);
        vals.push_back(cur->val);
        solve(cur->right, vals);
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> vals;
        solve(root, vals);

        return vals[k - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

LeetCode 231. 2的幂

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n; //若是2^k,则n的二进制仅1位为1
    }
};
1
2
3
4
5
6

LeetCode 239. 滑动窗口最大值

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        for (int i = 0; i < nums.size(); i ++ ) {
            if (q.size() && i - k + 1 > q.front()) q.pop_front();
            while (q.size() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

理解hh

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        deque<int> q;
        for (int i = 0; i < n; i++) {

            while (!q.empty() && i - q.front() >= k)
                q.pop_front();

            while (!q.empty() && nums[i] >= nums[q.back()])
                q.pop_back();

            q.push_back(i);

            if (i >= k - 1)
                ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LeetCode 240. 搜索二维矩阵 II

矩阵性质：从左到右升且从上到下升

class Solution { //[从左到右升且从上到下升] 以右上角假设分三条分支寻找
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = m - 1;
        while (i < n && j >= 0) {
            int t = matrix[i][j]; //第一行最后一格
            if (t == target) return true; 
            else if (t > target) j -- ; //若大于，不在此列，往左边更小的找
            else i ++ ; //若小于往下找
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode 242. 有效的字母异位词

hash表直接比较

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> a, b;
        for (auto c: s) a[c] ++ ;
        for (auto c: t) b[c] ++ ;
        return a == b; //hash表可直接比较wow
    }
};
1
2
3
4
5
6
7
8
9

LeetCode 263. 丑数 - 定义

只包含质因子2,3,5

class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0) return false;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
};
1
2
3
4
5
6
7
8
9
10

LeetCode 264. 丑数 II - 三指针排序

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> q(1, 1);
        for (int i = 0, j = 0, k = 0; q.size() < n;) { //2,3,5的倍数排序
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5)); //【比较】
            q.push_back(t);
            if (q[i] * 2 == t) i ++ ;
            if (q[j] * 3 == t) j ++ ;
            if (q[k] * 5 == t) k ++ ;
        }
        return q.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 268. 缺失数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++)
        {
            if(i != nums[i]) return i;
        }
        return nums.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11

LeetCode 274. H 指数

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int h = 0, i = citations.size() - 1;
        while (i >= 0 && citations[i] > h) { //从大到小判断
            h++;
            i--;
        }
        return h;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

原数组从小到大排序，然后从大到小枚举 h直到数组中后 h,个数大于等于 h为止

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int res = 0;
        for (int i = 0; i < citations.size(); i ++ )
            if (citations.size() - i <= citations[i])
            {
                res = citations.size() - i;
                break;
            }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 279. 完全平方数

平方数的和凑target的最少数量
tql

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, n);
        f[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j * j <= i; j++)
                f[i] = min(f[i], f[i - j * j] + 1);

        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 283. 移动零

双指针

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int i = 0, j = 0; i < nums.size() - 1; i++)
        {
            if(nums[i] == 0) 
                while(j < nums.size()) 
                    if(nums[j] == 0) j++;
                    else
                    {
                        swap(nums[i], nums[j]);
                        break;
                    } 
            j = i + 2;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

取出非零数，末尾补0

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int k = 0;
        for (auto x: nums)
            if (x)
                nums[k ++ ] = x;
        while (k < nums.size()) nums[k ++ ] = 0;
    }
};
1
2
3
4
5
6
7
8
9
10

LeetCode 287. 寻找重复数 - 空间优化

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n]
抽屉原理（必有重复） 二分
空间O(1) 双指针找环

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int a = 0, b = 0;
        while (true) {
            a = nums[a];
            b = nums[nums[b]]; //
            if (a == b) {
                a = 0;
                while (a != b) {
                    a = nums[a]; //映射到不同位置
                    b = nums[b];
                }
                return a;
            }
        }

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

空间O(n) - 简

class Solution {
public:
    unordered_map<int, int> cnt;
    int findDuplicate(vector<int>& nums) {
        for(auto x: nums)
        {
            cnt[x] ++;
            if(cnt[x] == 2) return x;
        }
        return 0;    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 289. 生命游戏

LeetCode 290. 单词规律 - stringstream

[类似205同构(字符 与 字符)，但不同的是此题：字符 与 单词 一对一映射]

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        stringstream raw(str); //字符串输入输出流 [构造函数]【输入str】
        vector<string> strs;//字符串数组
        string line; 
        while (raw >> line) strs.push_back(line); //放入每个单词[空格结束输入]
        if (pattern.size() != strs.size()) return false;
        unordered_map<char, string> PS;
        unordered_map<string, char> SP;//一对一应需两个方向映射,防止一对多和多对一
        for (int i = 0; i < pattern.size(); i ++ )
        {
            if (PS.count(pattern[i]) == 0) PS[pattern[i]] = strs[i]; //初始化关系
            if (SP.count(strs[i]) == 0) SP[strs[i]] = pattern[i];
            if (PS[pattern[i]] != strs[i]) return false; //相同字母对应关系不同,不符合
            if (SP[strs[i]] != pattern[i]) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 299. 猜数字游戏 - 模拟

Cows = 总匹配个数-相同位置个数
to_string(int)

class Solution {
public:
    string getHint(string secret, string guess) {
        unordered_map<char, int> hash;
        for (auto c: secret) hash[c] ++ ;
        int tot = 0;
        for (auto c: guess)
            if (hash[c]) { //Cows = 总匹配个数-相同位置个数
                tot ++ ;
                hash[c] -- ;
            }

        int bulls = 0;
        for (int i = 0; i < secret.size(); i ++ )
            if (secret[i] == guess[i])
                bulls ++ ;
        string res = string(to_string(bulls) + "A" + to_string(tot - bulls) + "B");//构造函数
        return res; //返回string拼接
    }//return string(to_string(bulls) + "A" + to_string(tot - bulls) + "B");
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LeetCode 300. 最长上升子序列 - dp

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> f(n, 1);
        int res = 1; //【非空,最小1】
        for(int i= 1;i < n;i++){
            for(int j = 0;j < i;j++){
                if(nums[i] > nums[j])
                    f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二分：找第一个大于q.back()的数

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> q;
        for (auto x: nums) {
            if (q.empty() || x > q.back()) q.push_back(x);
            else {
                if (x <= q[0]) q[0] = x;
                else {
                    int l = 0, r = q.size() - 1;
                    while (l < r) {
                        int mid = l + r + 1 >> 1;
                        if (q[mid] < x) l = mid; //【】
                        else r = mid - 1;
                    }
                    q[r + 1] = x;
                }
            }
        }
        return q.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

LeetCode 301. 删除无效的括号 dfs-困

class Solution {
public:
    vector<string> ans;

    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (auto x: s)
            if (x == '(') l ++ ;
            else if (x == ')') {
                if (l == 0) r ++ ;
                else l -- ;
            }

        dfs(s, 0, "", 0, l, r);
        return ans;
    }

    void dfs(string& s, int u, string path, int cnt, int l, int r) {
        if (u == s.size()) {
            if (!cnt) ans.push_back(path);
            return;
        }

        if (s[u] != '(' && s[u] != ')') dfs(s, u + 1, path + s[u], cnt, l, r);
        else if (s[u] == '(') {
            int k = u;
            while (k < s.size() && s[k] == '(') k ++ ;
            l -= k - u;
            for (int i = k - u; i >= 0; i -- ) {
                if (l >= 0) dfs(s, k, path, cnt, l, r);
                path += '(';
                cnt ++, l ++ ;
            }
        } else if (s[u] == ')') {
            int k = u;
            while (k < s.size() && s[k] == ')') k ++ ;
            r -= k - u;
            for (int i = k - u; i >= 0; i -- ) {
                if (cnt >= 0 && r >= 0) dfs(s, k, path, cnt, l, r);
                path += ')';
                cnt --, r ++ ;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45