LeetCode 刷题记录：第 31 至 40 题 | 极客日志

C++算法

LeetCode 刷题记录：第 31 至 40 题

本文整理了 LeetCode 第 31 至 40 题的解题思路与代码实现，涵盖 C++ 语言。主要涉及数组双指针、栈、动态规划、二分查找、回溯及哈希表等核心算法技巧。内容包括下一个排列、最长有效括号、搜索旋转排序数组、在排序数组中查找元素的第一个和最后一个位置、搜索插入位置、有效的数独、解数独、外观数列、组合总和及其变体。提供了多种解法对比，如动态规划与栈处理括号问题，以及不同场景下的二分查找策略。

PgDevote发布于 2026/3/280 浏览

31. 下一个排列

难度：中等

标签：数组、双指针

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) j--;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

32. 最长有效括号

难度：困难

标签：栈、字符串、动态规划

解法一：动态规划

class Solution {
public:
    int longestValidParentheses(string s) {
        int ret = 0;
        int n = s.size();
        vector<int> dp(n, 0);
        for (int i = ; i < n; ++i) {
             (s[i] == ) {
                 (s[i - ] == ) {
                    dp[i] = (i >=  ? dp[i - ] : ) + ;
                }   (i - dp[i - ] >  && s[i - dp[i - ] - ] == ) {
                    dp[i] = dp[i - ] + ((i - dp[i - ]) >=  ? dp[i - dp[i - ] - ] : ) + ;
                }
                ret = (ret, dp[i]);
            }
        }
         ret;
    }
};

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

class Solution {
public:
    int longestValidParentheses(string s) {
        int ret = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    ret = max(ret, i - stk.top());
                }
            }
        }
        return ret;
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = (int)s.size() - 1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
};

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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) { return {-1, -1}; }
        int left = 0, right = nums.size() - 1;
        int begin = 0, end = 0;
        // 二分左端点
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 判断结果
        if (nums[right] != target) { return {-1, -1}; }
        else { begin = left; }
        // 二分右端点
        left = 0; right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        end = left;
        return {begin, end};
    }
};

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

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool row[9][10];
        bool col[9][10];
        bool grid[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    // 是否是有效的
                    if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) {
                        return false;
                    }
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        return true;
    }
};

class Solution {
private:
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
    bool dfs(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    // 填数
                    for (int num = 1; num <= 9; num++) {
                        if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {
                            board[i][j] = '0' + num;
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                            if (dfs(board) == true) { return true; }
                            // 恢复现场
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        // 初始化
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(board);
    }
};

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for (int i = 1; i < n; i++) {
            string tmp;
            int len = ret.size();
            for (int left = 0, right = 0; right < len;) {
                while (right < len && ret[left] == ret[right]) {
                    right++;
                }
                tmp += to_string(right - left) + ret[left];
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

class Solution {
private:
    vector<vector<int>> ret;
    vector<int> path;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, target);
        return ret;
    }
    void dfs(vector<int>& candidates, int pos, int target) {
        if (target == 0) {
            ret.push_back(path);
            return;
        }
        if (target < 0) { return; }
        for (int i = pos; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            dfs(candidates, i, target - candidates[i]);
            path.pop_back();
        }
    }
};

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> solutions;
        vector<int> solution;
        int curSum = 0;
        dfs(solutions, solution, curSum, 0, target, candidates);
        return solutions;
    }
    void dfs(vector<vector<int>>& solutions, vector<int>& solution, int curSum, int preIdx, int target, vector<int>& candidates) {
        if (curSum >= target) {
            if (curSum == target) { // 保存当前组合
                solutions.push_back(solution);
            }
            return;
        }
        // 从后选一个数字累加
        for (int i = preIdx; i < candidates.size(); i++) {
            solution.push_back(candidates[i]);
            dfs(solutions, solution, curSum + candidates[i], i, target, candidates);
            // 回溯
            solution.pop_back();
        }
    }
};

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ret;
    vector<int> path;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num : candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ret;
    }
    void dfs(int pos, int target) {
        if (target == 0) {
            ret.push_back(path);
            return;
        }
        if (pos == freq.size() || target < freq[pos].first) { return; }
        dfs(pos + 1, target);
        int most = min(target / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; i++) {
            path.push_back(freq[pos].first);
            dfs(pos + 1, target - i * freq[pos].first);
        }
        for (int i = 1; i <= most; i++) {
            path.pop_back();
        }
    }
};

LeetCode 刷题记录：第 31 至 40 题

31. 下一个排列

32. 最长有效括号

解法一：动态规划

更多推荐文章

相关免费在线工具

解法二：栈

解法三：无需额外空间

33. 搜索旋转排序数组

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

35. 搜索插入位置

36. 有效的数独

37. 解数独

38. 外观数列

39. 组合总和

40. 组合总和 Ⅱ

LeetCode 刷题记录：第 31 至 40 题

31. 下一个排列

32. 最长有效括号

解法一：动态规划

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

解法二：栈

解法三：无需额外空间

33. 搜索旋转排序数组

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

35. 搜索插入位置

36. 有效的数独

37. 解数独

38. 外观数列

39. 组合总和

40. 组合总和 Ⅱ