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 twoSum(vector& nums, int target) {
                unordered_map dict; // val : index
                for (int i = 0; i  
        （注：本题也可以用双指针算法。）
        （图片来源网络，侵删）
         
        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 ht; // ht: hashtable
                for (int l = 0, r = 0; 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 = 0 && r = 0 && r  
        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  
        7.整数反转
         
        class Solution {
        public:
            int reverse(int x) {
                int res = 0;
                bool is_minus = (x  (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  (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  
        11.盛水最多的容器（贪心（基于双指针来实现））
         
        class Solution {
        public:
            int maxArea(vector& height) {
                int res = 0;
                int i = 0, j = height.size() - 1;
                while (i  
        12. 整数转罗马数字
         
        class Solution {
        public:
            string intToRoman(int num) {
                unordered_map 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 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  
        13. 罗马数字转整数
         
        class Solution {
        public:
            int romanToInt(string s) {
                // 从右往左遍历，定义一个哈希表表示大小关系，正常情况下右边小于等于左边；
                // 如果右边大于左边，说明出现了特殊规则
                // unordered_map pri{{'I', 1}, {'V', 2}, {'X', 3}, {'L', 4}, \
                // {'C', 5}, {'D', 6}, {'M', 7}}; /* 后记：val表的功能可以替代pri，故可以不用专门定义pri */
                unordered_map 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& strs) {
                string cp = strs[0];
                for (auto& s : strs)
                    for (int i = 0; i  
        15. 三数之和（双指针 + 去重）
         
        本题双指针算法的判定依据：
         
        对于每一个固定的 i，当 j 增大时，k 必减小。
        （图片来源网络，侵删）
         
        class Solution {
        public:
            vector threeSum(vector& nums) {
                sort(nums.begin(), nums.end()); // sort是双指针算法和去重的前提
                vector res;
                for (int i = 0; i  i + 1 && nums[j] == nums[j - 1]) continue; // 对j去重
                        while (j  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& nums, int target) {
                sort(nums.begin(), nums.end());
                pair res(INT_MAX, INT_MAX);
                for (int i = 0; i  i + 1 && nums[j] == nums[j - 1]) continue;
                        while (j = target) k--;
                        int sum = nums[i] + nums[j] + nums[k];
                        res = min(res, make_pair(abs(sum - target), sum));
                        if (j  
        17. 电话号码的字母组合（标准 DFS）
         
        class Solution {
        public:
            string s;
            unordered_map dict{
                {'2', "abc"},
                {'3', "def"},
                {'4', "ghi"},
                {'5', "jkl"},
                {'6', "mno"},
                {'7', "pqrs"},
                {'8', "tuv"},
                {'9', "wxyz"}
            };
            vector res;
            vector 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 fourSum(vector& nums, int target) {
                vector res;
                if (nums.size()  i + 1 && nums[j] == nums[j - 1]) continue;
                        for (int k = j + 1, m = nums.size() - 1; k  j + 1 && nums[k] == nums[k - 1]) continue;
                            while (k = 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 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 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 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 res;
            vector 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  
        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& nums) {
                int k = 0;
                for (int i = 0; i  
        27. 移除元素（简单的双指针算法）
         
        第一种实现方式：两个指针都从左往右走
         
        class Solution {
        public:
            int removeElement(vector& nums, int val) {
                int k = 0; // k是新数组的长度，初始时为0
                for (int i = 0; i  
        第二种实现方式：两个指针从两头出发往中间走
         
        class Solution {
        public:
            int removeElement(vector& nums, int val) {
                int n = nums.size();
                int i = -1, j = n;
                while (i  
        31. 下一个排列：
         
        class Solution {
        public:
            void nextPermutation(vector& 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 stk;
                for (int i = 0, start = -1; i  
        33.搜索旋转排序数组：
         
        class Solution {
        public:
            int search(vector& nums, int target) {
                int l = 0, r = nums.size() - 1;
                while (l 
                    int mid = l + r > 1;
                    if (nums[mid] == target) return mid;
                    // 我们要做的就是确定每次的mid到底是在左半段还是右半段中
                    if (nums[l] 
                        if (nums[l] 
                        if (nums[mid] > 1;
                        if (nums[mid] 
        public:
            int searchInsert(vector
                int l = 0, r = nums.size(); // 注意：此处不再是nums.size() - 1
                while (l  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& board) {
                memset(row, 0, sizeof row);
                memset(col, 0, sizeof col);
                memset(block, 0, sizeof block);
                for (int i = 0; i  
        37.解数独：
         
        class Solution {
        public:
            bool row[9][9], col[9][9], block[3][3][9];
            void solveSudoku(vector& 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  
        38.外观数列：
         
        class Solution {
        public:
            string countAndSay(int n) {
                string s = "1";
                for (int i = 0; i  
        39.组合总和：
         
        

        • 第一种 DFS：逐数字枚举

          class Solution {
          public:
              vector path;
              vector res;
              vector combinationSum(vector& candidates, int target) {
                  dfs(candidates, 0, target);
                  return res;    
              }
              void dfs(vector& 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 path;
                vector res;
                vector combinationSum(vector& candidates, int target) {
                    dfs(candidates, 0, target);
                    return res;    
                }
                void dfs(vector& 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] 
                        dfs(candidates, u + 1, target - i * candidates[u]);
                        path.push_back(candidates[u]);
                    }
                    for (int i = 0; i * candidates[u] 
            public:
                vector
                    sort(candidates.begin(), candidates.end());
                    dfs(candidates, 0, target);
                    return res;    
                }
                void dfs(vector
                    if (target == 0)
                    {
                        res.push_back(path);
                        return;
                    }
                    if (idx == candidates.size()) return;
                    int prev = -1;
                    for (int i = idx; i  
            44.通配符匹配：
             
            class Solution {
            public:
                bool isMatch(string s, string p) {
                    int n = s.size(), m = p.size();
                    s = ' ' + s, p = ' ' + p;
                    vector f(n + 1, vector(m + 1));
                    f[0][0] = true;
                    for (int i = 0; i 
            public:
                int jump(vector
                    int n = nums.size();
                    vector
                        while (j + nums[j]  
            51. N 皇后（DFS）
             
            class Solution {
            public:
                bool col[10], dg[20], udg[20];
                vector res;
                vector solveNQueens(int n) {
                    // 初始化棋盘
                    vector g;
                    for (int i = 0; i  
            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  
            53. 最大子数组和（动态规划）
             
            从动态规划的角度去理解：（更推荐）
             
            class Solution {
            public:
                int maxSubArray(vector& nums) {
                    int res = INT_MIN;
                    for (int i = 0, last = 0; i  
            从贪心的角度去理解：
             
            class Solution {
            public:
                int maxSubArray(vector& nums) {
                    int res = -1e5, sum = 0;
                    for (int i = 0; i  
            54. 螺旋矩阵
             
            方法一：（迭代）利用方向数组（推荐）
             
            class Solution {
            public:
                vector spiralOrder(vector& matrix) {
                    vector res;
                    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
                    int m = matrix.size(), n = matrix[0].size();
                    vector st(m, vector(n));
                    for (int i = 0, x = 0, y = 0, d = 0; i = m || 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 res;
                vector spiralOrder(vector& 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& matrix, int x1, int y1, int x2, int y2)
                {
                    if (x1 > x2 || y1 > y2) return;
                    int i = x1, j = y1;
                    while (j 
                        res.push_back(matrix[i][j]);
                        j++;
                    }
                    j--,i++;
                    while (i 
                        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  x1) // j  
            55.跳跃游戏：
             
            class Solution {
            public:
                bool canJump(vector& nums) {
                    for (int i = 0, j = 0; i  
            56. 区间合并（模板：区间合并）
             
            class Solution {
            public:
                vector merge(vector& intervals) {
                    vector res;
                    sort(intervals.begin(), intervals.end());
                    int st = -1, ed = -1;
                    for (auto seg : intervals)
                    {
                        if (ed  
            57. 插入区间
             
            方法一：先用二分查找找到插入位置，将新区间插入，再调用标准的区间合并算法
             
            class Solution {
            public:
                vector insert(vector& intervals, vector& newInterval) {
                    // 先二分找到插入位置
                    int l = 0, r = intervals.size();
                    while (l > 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 res;
                    for (int i = 0; i  
            方法二：（Y总做法）模拟
             
            class Solution {
            public:
                vector insert(vector& intervals, vector& newInterval) {
                    vector res;
                    // 首先寻找左侧没有交叠的区间
                    int k = 0;
                    while (k  
            59. 螺旋矩阵 II（方向数组的简单应用）
             
            class Solution {
            public:
                vector generateMatrix(int n) {
                    vector res(n, vector(n));
                    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
                    for (int i = 1, x = 0, y = 0, d = 0; i 
                        if (x = 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;
                }
            };