leetcode 1 ~ 100

文章目录

- - - 1. 两数之和（用哈希表减少查找的时间复杂度）
    - 2. 两数相加（高精度加法）
    - 3.无重复字符的最长子串：（模板：经典的滑动窗口算法）
    - 5. 最长回文子串（枚举）
    - 6. Z 自形变换（找规律）
    - 7.整数反转
    - 8. 字符串转换整数（atoi）
    - 9. 回文数
    - 11.盛水最多的容器（贪心（基于双指针来实现））
    - 12. 整数转罗马数字
    - 13. 罗马数字转整数
    - 14. 最长公共前缀
    - 15. 三数之和（双指针 + 去重）
    - 16. 最接近的三数之和（双指针算法）
    - 17. 电话号码的字母组合（标准 DFS）
    - 18. 四数之和（双指针算法）
    - 19. 删除链表的倒数第 N 个结点（前后双指针寻找结点 + dummy 避免特判）
    - 20. 有效的括号（栈的简单应用）
    - 21. 合并两个有序链表（模拟归并排序中的二路归并操作）
    - 22. 括号生成（DFS）
    - 24. 两两交换链表中的节点（链表结点交换算法）
    - 26. 删除有序数组中的重复项（经典双指针算法）
    - 27. 移除元素（简单的双指针算法）
    - 31. 下一个排列：
    - 32. 最长有效括号
    - 33.搜索旋转排序数组：
    - 34.在排序数组中查找元素的第一个和最后一个位置：
    - 35.搜索插入位置：
    - 36.有效的数独：
    - 37.解数独：
    - 38.外观数列：
    - 39.组合总和：
    - 40.组合总和：
    - 41.缺失的第一个正数：
    - 42.接雨水：
    - 43.字符串相乘：
    - 44.通配符匹配：
    - 45.跳跃游戏 II：
    - 46.全排列：
    - 47.全排列 II：
    - 48.旋转图像：
    - 49.字母异位词分组：
    - 50.Pow(x, n)：
    - 51. N 皇后（DFS）
    - 52. N 皇后 II（DFS，和 51 题完全一样，只是不需要记录方案是什么）
    - 53. 最大子数组和（动态规划）
    - 54. 螺旋矩阵
    - 55.跳跃游戏：
    - 56. 区间合并（模板：区间合并）
    - 57. 插入区间
    - 58. 最后一个单词的长度（模拟题）
    - 59. 螺旋矩阵 II（方向数组的简单应用）

1. 两数之和（用哈希表减少查找的时间复杂度）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> dict; // val : index
        for (int i = 0; i < nums.size(); i++)
        {
            if (dict.count(target - nums[i]))
                return {dict[target - nums[i]], i};
            else
                dict[nums[i]] = i;
        }

        return {};
    }
};

（注：本题也可以用双指针算法。）

2. 两数相加（高精度加法）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        int t = 0;
        while (l1 || l2 || t)
        {
            if (l1) {
                t += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                t += l2->val;
                l2 = l2->next;
            }
            p->next = new ListNode(t % 10);
            p = p->next;
            t /= 10;
        }

        return dummy->next;
    }
};

3.无重复字符的最长子串：（模板：经典的滑动窗口算法）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        unordered_map<char, int> ht; // ht: hashtable
        for (int l = 0, r = 0; r < s.size(); r++)
        {
            ht[s[r]]++;
            while (ht[s[r]] > 1)
            {
                ht[s[l]]--;
                l++;
            }

            res = max(res, r - l + 1);
        }

        return res;
    }
};

5. 最长回文子串（枚举）

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));

            // 看回文串的长度是否是偶数
            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));
        }

        return res;
    }
};

6. Z 自形变换（找规律）

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s; // numRows = 1会导致base为0，需要特判
        string res = "";
        
        int base = 2 * numRows - 2;
        for (int k = 0; k < numRows; k++)
            for (int i = 0; i < s.size(); i++)
                if ((i - k) % base == 0 || (i + k) % base == 0)
                    res += s[i];

        return res;
    }
};


// 每一趟会有 numRows + (nuRows - 2) = 2 * numRows - 2 = base 个数
// 故最终第0行应该是满足 (i + 0) % base == 0的数
// 第1行是 (i + 1) % base == 0的数
// 第 k 行是 (i + k) % base == 0的数
// k的范围是从 0 到 numRows - 1

7.整数反转

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

        return res;
    }
};

8. 字符串转换整数（atoi）

class Solution {
public:
    int myAtoi(string s) {
        int res = 0;
        bool is_minus = false;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == ' ') continue;
            else if (s[i] == '+' || s[i] == '-')
            {
                is_minus = (s[i] == '-');
                if (i + 1 < s.size() && !isdigit(s[i + 1])) return res;
                else continue;
            }
            else if (isdigit(s[i]))
            {
                while (i < s.size() && isdigit(s[i]))
                {
                    int t = s[i] - '0';
                    if (is_minus && res > (INT_MAX - t) / 10) return INT_MIN;
                    if (!is_minus && res > (INT_MAX - t) / 10) return INT_MAX;
                    res = res * 10 + t;
                    i++;
                }
                if (is_minus) return -res;
                else return res;
            }
            else return res;
        }

        return res;
    }
};

9. 回文数

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        if (!x) return true;

        long long res = 0; // 翻转后有可能会溢出
        int tmp = x;
        while (tmp)
        {
            res = res * 10 + tmp % 10;
            tmp /= 10;
        }

        return res == x;
    }
};

11.盛水最多的容器（贪心（基于双指针来实现））

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int i = 0, j = height.size() - 1;
        while (i < j)
        {
            res = max(res, min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) i++;
            else j--;
        }

        return res;
    }
};

12. 整数转罗马数字

class Solution {
public:
    string intToRoman(int num) {
        unordered_map<int, string> dict{
            {1, "I"}, {4, "IV"}, {5, "V"}, {9, "IX"}, 
            {10, "X"}, {40, "XL"}, {50, "L"}, {90, "XC"}, 
            {100, "C"}, {400, "CD"}, {500, "D"}, {900, "CM"}, 
            {1000, "M"}
        };
        vector<int> base{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

        string res = "";
        for (auto b : base)
        {
            if (!num) break;
            int cnt = num / b;
            num %= b;
            if (cnt)
            {
                for (int i = 0; i < cnt; i++)
                    res += dict[b];
            }
        }

        return res;
    }
};

13. 罗马数字转整数

class Solution {
public:
    int romanToInt(string s) {
        // 从右往左遍历，定义一个哈希表表示大小关系，正常情况下右边小于等于左边；
        // 如果右边大于左边，说明出现了特殊规则
        // unordered_map<char, int> pri{{'I', 1}, {'V', 2}, {'X', 3}, {'L', 4}, \
        // {'C', 5}, {'D', 6}, {'M', 7}}; /* 后记：val表的功能可以替代pri，故可以不用专门定义pri */
        unordered_map<char, int> val{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, \
        {'C', 100}, {'D', 500}, {'M', 1000}};
        int res = 0;
        for (int i = s.size() - 1; i >= 0;)
        {
            if (i && val[s[i]] > val[s[i - 1]]) // e.g. IV
            {
                res += val[s[i]] - val[s[i - 1]];
                i -= 2;
            }
            else
            {
                res += val[s[i]];
                i--;
            }
        }

        return res;
    }
};

14. 最长公共前缀

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string cp = strs[0];
        for (auto& s : strs)
            for (int i = 0; i < cp.size(); i++)
                if (cp[i] != s[i]) 
                {
                    cp.erase(cp.begin() + i, cp.end());
                    break;   
                }
     
        return cp;
    }
};

15. 三数之和（双指针 + 去重）

本题双指针算法的判定依据：

对于每一个固定的 i，当 j 增大时，k 必减小。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // sort是双指针算法和去重的前提
        vector<vector<int>> res;

        for (int i = 0; i < nums.size() - 2; i++)
        {
            if (i && nums[i] == nums[i - 1]) continue; // 对i去重
            for (int j = i + 1, k = nums.size() - 1; j < nums.size() - 1; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 对j去重
                while (j < k && nums[i] + nums[j] + nums[k] > 0) k--;
                if (j == k) break; // 注意：两指针不能重合！
                if (nums[i] + nums[j] + nums[k] == 0)
                    res.push_back({nums[i], nums[j], nums[k]});
            }
        }

        return res;
    }
};

16. 最接近的三数之和（双指针算法）

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        pair<int, int> res(INT_MAX, INT_MAX);
        for (int i = 0; i < nums.size() - 2; i++)
        {
            if (i && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1, k = nums.size() - 1; j < k; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;

                int sum = nums[i] + nums[j] + nums[k];
                res = min(res, make_pair(abs(sum - target), sum));
                if (j < k - 1)
                {
                    sum = nums[i] + nums[j] + nums[k - 1];
                    res = min(res, make_pair(target - sum, sum));
                }
            }
        }

        return res.second;
    }
};

17. 电话号码的字母组合（标准 DFS）

class Solution {
public:
    string s;
    unordered_map<char, string> dict{
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };
    vector<string> res;

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

        return res;
    }

    void dfs(string digits, int idx)
    {
        if (idx == digits.size())
        {
            res.push_back(s);
            return;
        }

        for (char c : dict[digits[idx]])
        {
            s += c;

            dfs(digits, idx + 1);

            s.pop_back();
        }
    }
};

18. 四数之和（双指针算法）

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if (nums.size() < 4) return res;

        sort(nums.begin(), nums.end());


        for (int i = 0; i < nums.size() - 3; i++)
        {
            if (i && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.size() - 2; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                for (int k = j + 1, m = nums.size() - 1; k < m; k++)
                {
                    if (k > j + 1 && nums[k] == nums[k - 1]) continue;
                    while (k < m - 1 && (long)nums[i] + nums[j] + nums[k] + nums[m - 1] >= target) 
                        m--; // 注意：不加long会有数据溢出问题，下同

                    if ((long)nums[i] + nums[j] + nums[k] + nums[m] == target)
                        res.push_back({nums[i], nums[j], nums[k], nums[m]});
                }
            }
        }

        return res;
    }
};

19. 删除链表的倒数第 N 个结点（前后双指针寻找结点 + dummy 避免特判）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* left = dummy;
        ListNode* right = head;
        for (int i = 0; i < n; i++)
            right = right->next;

        while (right != nullptr)
        {
            left = left->next;
            right = right->next;
        }

        left->next = left->next->next;

        ListNode* res = dummy->next;
        delete dummy; // 删除哑节点，释放内存

        return res;
    }
};

20. 有效的括号（栈的简单应用）

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (auto c : s)
        {
            if (c == '(' || c == '{' || c == '[')
                stk.push(c);
            else
            {
                // if (stk.empty() || (c == ')' && stk.top() != '(') || (c == '}' && stk.top() != '{') || (c == ']' && stk.top() != '['))
                if (stk.empty() || abs(stk.top() - c) > 2) // (){}[] = 40 41 123 125 91 93
                    return false;
                else 
                    stk.pop();
            }
        }

        return stk.empty();
    }
};

21. 合并两个有序链表（模拟归并排序中的二路归并操作）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        ListNode* p1 = list1;
        ListNode* p2 = list2;
        while (p1 && p2)
        {
            if (p1->val <= p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            
            p = p->next;
        }

        if (p1) p->next = p1;

        if (p2) p->next = p2;

        return dummy->next;
    }
};

22. 括号生成（DFS）

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

    vector<string> generateParenthesis(int n) {
        // 左括号用了i个，右括号用了j个，当i == j == n时，即可
        dfs(n, 0, 0);

        return res;
    }

    void dfs(int n, int left, int right)
    {
        if (left == n && right == n)
        {
            res.push_back(s);
            return;
        }

        // 左分支的条件如果满足，就转向左分支
        if (left < n)
        {
            s += '(';
            dfs(n, left + 1, right); // 在左分支里继续进行递归
            s.pop_back(); // 和回溯
        }

        //如果右分支的条件满足，就转向右分支
        if (right < left)
        {
            s += ')';
            dfs(n, left, right + 1); // 在右分支里继续进行递归
            s.pop_back(); // 和回溯
        }
    }
};

24. 两两交换链表中的节点（链表结点交换算法）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* p = dummy;
        while (p->next && p->next->next)
        {
            ListNode* left = p->next; // 必须要先用两个临时结点把p->next
            ListNode* right = p->next->next; // 和p->next->next保存起来
            p->next = right;
            left->next = right->next;
            right->next = left;
            p = left; // <=> p = p->next->next;
        }

        return dummy->next;
    }
};

26. 删除有序数组中的重复项（经典双指针算法）

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (!i || nums[i] != nums[i - 1])
                nums[k++] = nums[i];
        }

        return k;
    }
};

27. 移除元素（简单的双指针算法）

第一种实现方式：两个指针都从左往右走

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0; // k是新数组的长度，初始时为0
        for (int i = 0; i < nums.size(); i++)
            if (nums[i] != val)
                nums[k++] = nums[i];
        
        return k;
    }
};

第二种实现方式：两个指针从两头出发往中间走

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int i = -1, j = n;
        while (i < j)
        {
            do i++; while (i < j && nums[i] != val);
            do j--; while (i < j && nums[j] == val);
            if (i < j) swap(nums[i], nums[j]);
        }

        return i;
    }
};
// 注：这种实现方式可以应对以下两种边界情况：
// （1）nums为空；
// （2）nums仅含1个元素

31. 下一个排列：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();

        // 从后往前找到第一对升序的元素
        int i = n - 1;
        while (i >= 1 && nums[i - 1] >= nums[i]) i--;

        if (i == 0) // 如果不存在升序元素对，
            reverse(nums.begin(), nums.end()); // 直接将降序翻转为升序
        else // 如果存在升序元素对，
        {
            int j = i; i--; // 此时nums[i - 1], nums[i]即为从后往前第一对升序元素

            // 再次从后往前，寻找第一个大于nums[i]的元素
            int k = n - 1;
            while (k > i && nums[i] >= nums[k]) k--;

            // 找到后将nums[i]和nums[k]交换
            swap(nums[i], nums[k]);

            // 此时[j, end)必降序，将其翻转为升序即可
            reverse(nums.begin() + j, nums.end());
        }
    }
};

32. 最长有效括号

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

        for (int i = 0, start = -1; i < s.size(); i++)
        {
            if (s[i] == '(') stk.push(i);
            else // 来右括号
            {
                if (!stk.empty()) // 来右括号且栈不空，说明栈顶有左括号
                {
                    stk.pop(); // 将左括号弹出，
                    if (!stk.empty()) // 如果弹出后栈顶仍有左括号，
                        res = max(res, i - stk.top()); // 则左括号的下一个位置到i的长度即为当前i对应的最大有效括号长度
                    else 
                        res = max(res, i - start); // 如果将栈顶左括号弹出后栈空，则从start + 1到i皆为有效长度
                }
                else // 来右括号且栈空
                {
                    start = i;
                }
            }
        }

        return res;
    }
};

33.搜索旋转排序数组：

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

            // 我们要做的就是确定每次的mid到底是在左半段还是右半段中
            if (nums[l] <= nums[mid]) // 说明mid在左半段，则左半段可以二分
            {
                if (nums[l] <= target && target < nums[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            else // 说明mid在右半段，则右半段可以二分
            {
                if (nums[mid] < target && target <= nums[r])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }

        return -1;
    }
};

34.在排序数组中查找元素的第一个和最后一个位置：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.empty()) return {-1, -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[l] != target) return {-1, -1};
        else
        {
            res.push_back(l);

            int 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;
            }

            res.push_back(l);
        }

        return res;
    }
};

35.搜索插入位置：

// 找到从前往后第一个大于等于target的位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size(); // 注意：此处不再是nums.size() - 1
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};

36.有效的数独：

class Solution {
public:
    bool row[9][9], col[9][9], block[3][3][9];

    bool isValidSudoku(vector<vector<char>>& board) {
        memset(row, 0, sizeof row);
        memset(col, 0, sizeof col);
        memset(block, 0, sizeof block);

        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    if (row[i][t] || col[j][t] || block[i / 3][j / 3][t])
                        return false;
                    else
                        row[i][t] = col[j][t] = block[i / 3][j / 3][t] = true;
                }
        
        return true;
    }
};

37.解数独：

class Solution {
public:
    bool row[9][9], col[9][9], block[3][3][9];

    void solveSudoku(vector<vector<char>>& board) {
        memset(row, 0, sizeof row);
        memset(col, 0, sizeof col);
        memset(block, 0, sizeof block);

        int n = board.size(), m = board[0].size();

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = block[i / 3][j / 3][t] = true;
                }

        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>>& board, int x, int y)
    {
        int n = board.size(), m = board[0].size();

        if (y == m) { y = 0; x++; }
        if (x == n) return true;

        if (board[x][y] != '.') return dfs(board, x, y + 1);
        
        for (int num = 0; num < 9; num++)
        {
            if (!row[x][num] && !col[y][num] && !block[x / 3][y / 3][num])
            {
                board[x][y] = num + '1';
                row[x][num] = col[y][num] = block[x / 3][y / 3][num] = true;
                if (dfs(board, x, y + 1)) return true;
                board[x][y] = '.';
                row[x][num] = col[y][num] = block[x / 3][y / 3][num] = false;
            }
        }

        return false;
    }
};

38.外观数列：

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";

        for (int i = 0; i < n - 1; i++)
        {
            string tmp = "";
            for (int j = 0; j < s.size();)
            {
                int k = j + 1;
                while (k < s.size() && s[j] == s[k]) k++;
                tmp += to_string(k - j) + s[j];
                j = k;
            }

            s = tmp;
        }

        return s;
    }
};

39.组合总和：

第一种 DFS：逐数字枚举

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

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, target);

        return res;    
    }

    void dfs(vector<int>& candidates, int u, int target)
    {
        if (target == 0)
        {
            res.push_back(path);
            return;
        } // 注意：此if与后面if的顺序不能颠倒！

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

        // skip current position
        dfs(candidates, u + 1, target);

        // choose current position
        if (target - candidates[u] >= 0)
        {
            path.push_back(candidates[u]);
            dfs(candidates, u, target - candidates[u]);
            path.pop_back();
        }
    }
};

第二种 DFS：按第 i 个数选多少个来搜索

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

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, target);

        return res;    
    }

    void dfs(vector<int>& candidates, int u, int target)
    {
        if (target == 0)
        {
            res.push_back(path);
            return;
        } // 注意：此if与后面if的顺序不能颠倒！

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

        for (int i = 0; i * candidates[u] <= target; i++)
        {
            dfs(candidates, u + 1, target - i * candidates[u]);
            path.push_back(candidates[u]);
        }

        for (int i = 0; i * candidates[u] <= target; i++)
            path.pop_back();
    }
};

40.组合总和：

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

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);

        return res;    
    }

    void dfs(vector<int>& candidates, int idx, int target)
    {
        if (target == 0)
        {
            res.push_back(path);
            return;
        }

        if (idx == candidates.size()) return;

        int prev = -1;
        for (int i = idx; i < candidates.size(); i++)
        {
            if (prev != candidates[i] && candidates[i] <= target)
            {
                prev = candidates[i];
                path.push_back(candidates[i]);

                dfs(candidates, i + 1, target - candidates[i]);

                path.pop_back();
            }
        }
    }
};

41.缺失的第一个正数：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                swap(nums[nums[i] - 1], nums[i]);
        }

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

        return n + 1;
    }
};

42.接雨水：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int l = 0, r = height.size() - 1;
        int lmax = 0, rmax = 0;
        while (l < r)
        {
            lmax = max(lmax, height[l]);
            rmax = max(rmax, height[r]);
            if (lmax <= rmax)
            {
                ans += lmax - height[l];
                l++;
            }
            else
            {
                ans += rmax - height[r];
                r--;
            }
        }

        return ans;
    }
};

43.字符串相乘：

class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.size(), m = num2.size();
        vector<int> A, B;

        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];
        
        // 集中处理进位
        int t = 0;
        for (int i = 0; i < C.size(); i++)
        {
            t += C[i];
            C[i] = t % 10;
            t /= 10;
        }

        while (C.size() > 1 && C.back() == 0) C.pop_back();

        string res;
        for (int i = C.size() - 1; i >= 0; i--) res += C[i] + '0';

        return res;
    }
};

44.通配符匹配：

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++) // i必须从0开始，因为f[0][j]是有意义的
            for (int j = 1; j <= m; j++) // j可以从1开始，因为f[i][0]必为false
                if (p[j] == '*')
                    f[i][j] = f[i][j - 1] || (i && f[i - 1][j]);
                else
                    f[i][j] = (s[i] == p[j] || p[j] == '?') && (i && f[i - 1][j - 1]);
        
        return f[n][m];
    }
};

45.跳跃游戏 II：

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);

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

        return f[n - 1];
    }
};

46.全排列：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    bool st[10];
    
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);

        return res;
    }

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

        for (int i = 0; i < nums.size(); i++)
        {
            if (!st[i])
            {
                path.push_back(nums[i]);
                st[i] = true;

                dfs(nums, u + 1);

                path.pop_back();
                st[i] = false;
            }
        }
    }
};

47.全排列 II：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    bool st[10];

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> tmp = nums;
        sort(tmp.begin(), tmp.end());

        dfs(tmp, 0);

        return res;
    }

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

        int prev = -11;
        for (int i = 0; i < nums.size(); i++)
        {
            if (prev != nums[i] && !st[i])
            {
                prev = nums[i];
                path.push_back(nums[i]);
                st[i] = true;

                dfs(nums, u + 1);

                path.pop_back();
                st[i] = false;
            }
        }
    }
};

48.旋转图像：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        /* 两次对称即可：先沿反对角线对称，再沿中轴左右对称*/
        int n = matrix.size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                swap(matrix[i][j], matrix[j][i]);
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n / 2; j++)
                swap(matrix[i][j], matrix[i][n - 1 - j]);
    }
};

49.字母异位词分组：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (auto& str : strs)
        {
            string tmp = str;
            sort(tmp.begin(), tmp.end());
            map[tmp].push_back(str);
        }

        vector<vector<string>> res;
        for (auto& item : map) res.push_back(item.second);

        return res;
    }
};

50.Pow(x, n)：

class Solution {
public:
    double myPow(double x, int n) {
        typedef long long LL;
        bool is_minus = n < 0;
        double res = 1;
        for (LL k = abs(LL(n)); k; k >>= 1)
        {
            if (k & 1) res *= x;
            x *= x;
        }
        if (is_minus) res = 1 / res;
        return res;
    }
};

51. N 皇后（DFS）

class Solution {
public:
    bool col[10], dg[20], udg[20];
    vector<vector<string>> res;

    vector<vector<string>> solveNQueens(int n) {
        // 初始化棋盘
        vector<string> g;
        for (int i = 0; i < n; i++)
            g.push_back(string(n, '.'));

        dfs(0, n, g);

        return res;
    }

    void dfs(int u, int n, vector<string>& g)
    {
        if (u == n)
        {
            res.push_back(g);
            return;
        }

        for (int i = 0; i < n; i++)
        {
            if (!col[i] && !dg[u - i + n] && !udg[u + i])
            {
                g[u][i] = 'Q';
                col[i] = dg[u - i + n] = udg[u + i] = true;

                dfs(u + 1, n, g);

                g[u][i] = '.';
                col[i] = dg[u - i + n] = udg[u + i] = false;
            }
        }
    }
};

52. N 皇后 II（DFS，和 51 题完全一样，只是不需要记录方案是什么）

class Solution {
public:
    bool col[10], dg[20], udg[20];
    int res = 0;

    int totalNQueens(int n) {
        dfs(0, n);

        return res;
    }

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

        for (int i = 0; i < n; i++)
        {
            if (!col[i] && !dg[u - i + n] && !udg[u + i])
            {
                col[i] = dg[u - i + n] = udg[u + i] = true;

                dfs(u + 1, n);

                col[i] = dg[u - i + n] = udg[u + i] = false;
            }
        }
    }
};

53. 最大子数组和（动态规划）

从动态规划的角度去理解：（更推荐）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        for (int i = 0, last = 0; i < nums.size(); i++)
        {
            last = nums[i] + max(last, 0);
            res = max(res, last);
        }

        return res;
    }
};

// 动态规划：
// f[i] 表示所有以nums[i]结尾的连续子数组的最大和
// f[i] = max(nums[i], f[i - 1] + nums[i]) = nums[i] + max(f[i - 1], 0);
// 由于只用到了两个状态，因此可以用一个变量保存f[i - 1]，这样空间复杂度可以优化至O(1)

从贪心的角度去理解：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = -1e5, sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            if (sum < nums[i]) sum = nums[i];
            res = max(res, sum);
   
        }

        return res;
    }
};
// 贪心：
// 从左到右扫描，

54. 螺旋矩阵

方法一：（迭代）利用方向数组（推荐）

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> st(m, vector<bool>(n));
        for (int i = 0, x = 0, y = 0, d = 0; i < m * n; i++)
        {
            // 先判断上一步有没有走对，如果没有走对，就纠正上一步并让其走对
            if (x < 0 || x >= m || y < 0 || y >= n || st[x][y])
            {
                x -= dx[d], y -= dy[d];
                d = (d + 1) % 4;
                x += dx[d], y += dy[d];
            }
            
            // 如果走对的话就记录
            res.push_back(matrix[x][y]);
            st[x][y] = true;
            x += dx[d], y += dy[d]; // 并继续往前走
        }

        return res;
    }
};

方法二：（DFS）模拟

class Solution {
public:
    vector<int> res;
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        dfs(matrix, 0, 0, m - 1, n - 1); // 传入的是左上角和右下角的坐标(x1, y1)和(x2, y2)

        return res;
    }

    void dfs(vector<vector<int>>& matrix, int x1, int y1, int x2, int y2)
    {
        if (x1 > x2 || y1 > y2) return;

        int i = x1, j = y1;
        while (j <= y2)
        {
            res.push_back(matrix[i][j]);
            j++;
        }

        j--,i++;
        while (i <= x2)
        {
            res.push_back(matrix[i][j]);
            i++;
        }

        i--, j--;
        while (i > x1 && j >= y1) // i > x1的目的是防止出现回退，如第2个测试用例
        {
            res.push_back(matrix[i][j]);
            j--;
        }

        j++, i--;
        while (j < y2 && i > x1) // j < y2的目的也是防止出现回退，例如[[7], [9], [6]]
        {
            res.push_back(matrix[i][j]);
            i--;
        }

        dfs(matrix, x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    }
};

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 = max(j, i + nums[i]);
        }

        return true;
    }
};

56. 区间合并（模板：区间合并）

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end());
        int st = -1, ed = -1;
        for (auto seg : intervals)
        {
            if (ed < seg[0])
            {
                if (st != -1) res.push_back({st, ed});
                st = seg[0], ed = seg[1];
            }
            else ed = max(ed, seg[1]);
        }

        if (st != -1) res.push_back({st, ed});

        return res;
    }
};

57. 插入区间

方法一：先用二分查找找到插入位置，将新区间插入，再调用标准的区间合并算法

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        // 先二分找到插入位置
        int l = 0, r = intervals.size();
        while (l < r)
        {
            int mid = l + r >> 1;
            if (intervals[mid][0] >= newInterval[0]) r = mid;
            else l = mid + 1;
        }

        intervals.insert(intervals.begin() + l, newInterval);

        // 调用区间合并模板
        int st = -1, ed = -1;
        vector<vector<int>> res;
        for (int i = 0; i < intervals.size(); i++)
        {
            if (ed < intervals[i][0])
            {
                if (st != -1) res.push_back({st, ed});
                st = intervals[i][0], ed = intervals[i][1];
            }
            else ed = max(ed, intervals[i][1]);
        }
        if (st != -1) res.push_back({st, ed});

        return res;
    }
};

方法二：（Y总做法）模拟

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;

        // 首先寻找左侧没有交叠的区间
        int k = 0;
        while (k < intervals.size() && intervals[k][1] < newInterval[0])
        {
            res.push_back(intervals[k]);
            k++;
        }

        // 对中间有交叠的区间进行合并
        if (k < intervals.size()) // 这一条件可以处理intervals为空的情况
        {
            newInterval[0] = min(intervals[k][0], newInterval[0]);
            while (k < intervals.size() && intervals[k][0] <= newInterval[1])
            {
                newInterval[1] = max(intervals[k][1], newInterval[1]);
                k++;
            }
        }
        res.push_back(newInterval);


        // 右侧没有交叠的区间也照抄
        while (k < intervals.size())
        {
            res.push_back(intervals[k]);
            k++;
        }

        return res;
    }
};

58. 最后一个单词的长度（模拟题）

class Solution {
public:
    int lengthOfLastWord(string s) {
        int k = s.size() - 1;
        while (s[k] == ' ') k--;
        int j = k;
        while (j >= 0 && s[j] != ' ') j--;

        return k - j;
    }
};

59. 螺旋矩阵 II（方向数组的简单应用）

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
        for (int i = 1, x = 0, y = 0, d = 0; i <= n * n; i++)
        {
            if (x < 0 || x >= n || y < 0 || y >= n || res[x][y] != 0)
            {
                x -= dx[d], y -= dy[d];
                d = (d + 1) % 4;
                x += dx[d], y += dy[d];
            }

            res[x][y] = i;
            x += dx[d], y += dy[d];
        }

        return res;
    }
};