当前位置： 首页 > article >正文

LeetCode Hot 100：回溯

article 2024/10/27 4:31:54

LeetCode Hot 100：回溯

46. 全排列

class Solution {
private:
    vector<vector<int>> ans;

public:
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.empty())
            return {};

        backtrace(nums, 0, (int)nums.size());
        return ans;
    }
    void backtrace(vector<int>& path, int level, int n) {
        if (level == n) {
            ans.push_back(path);
            return;
        }

        for (int i = level; i < n; i++) {
            swap(path[i], path[level]);
            backtrace(path, level + 1, n);
            swap(path[i], path[level]);
        }
    }
};

78. 子集

class Solution {
private:
    vector<vector<int>> ans;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty())
            return {};

        vector<int> path;
        backtrace(nums, 0, (int)nums.size(), path);

        return ans;
    }
    void backtrace(vector<int>& nums, int level, int n, vector<int> path) {
        if (level == n) {
            ans.push_back(path);
            return;
        }

        path.push_back(nums[level]);
        backtrace(nums, level + 1, n, path);
        path.pop_back();
        backtrace(nums, level + 1, n, path);
    }
};

17. 电话号码的字母组合

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

    vector<string> ans;

public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty())
            return {};

        int n = digits.length();
        string path;
        backtrace(digits, 0, n, path);

        return ans;
    }
    void backtrace(string& digits, int level, int n, string path) {
        if (level == n) {
            ans.push_back(path);
            return;
        }

        char digit = digits[level];
        string s = dict[digit];

        for (char& c : s) {
            path.push_back(c);
            backtrace(digits, level + 1, n, path);
            path.pop_back();
        }
    }
};

39. 组合总和

class Solution {
private:
    vector<vector<int>> ans;

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if (candidates.empty())
            return {};

        int n = candidates.size();
        vector<int> path;
        backtrace(candidates, 0, n, target, path);

        return ans;
    }
    void backtrace(vector<int>& nums, int level, int n, int target,
                   vector<int> path) {
        if (level == n)
            return;
        if (accumulate(path.begin(), path.end(), 0) == target) {
            ans.push_back(path);
            return;
        }

        // 选 nums[level]
        if (accumulate(path.begin(), path.end(), 0) + nums[level] <= target) {
            path.push_back(nums[level]);
            backtrace(nums, level, n, target, path);
            path.pop_back();
        }
        // 不选 nums[level]
        backtrace(nums, level + 1, n, target, path);
    }
};

22. 括号生成

思路 1：回溯

class Solution {
private:
    vector<string> ans;

public:
    vector<string> generateParenthesis(int n) {
        if (n == 0)
            return {};

        string path;
        backtrace(0, 2 * n, path);

        return ans;
    }
    void backtrace(int level, int n, string path) {
        if (level == n) {
            if (isValid(path))
                ans.push_back(path);
            return;
        }

        path.push_back('(');
        backtrace(level + 1, n, path);
        path.pop_back();

        path.push_back(')');
        backtrace(level + 1, n, path);
        path.pop_back();
    }
    // 辅函数 - 判断字符串 s 是否有效
    bool isValid(const string& s) {
        int balance = 0;
        for (const char& c : s) {
            if (c == '(')
                balance++;
            else
                balance--;
            if (balance < 0)
                return false;
        }
        return balance == 0;
    }
};

思路 2：深度优先搜索

class Solution {
private:
    vector<string> ans;

public:
    vector<string> generateParenthesis(int n) {
        if (n == 0)
            return {};

        function<void(int, int, string)> dfs = [&](int left, int right, string str) {
            if (left < 0 || right < 0 || left > right)
                return;
            if (left == 0 && right == 0) {
                ans.push_back(str);
                return;
            }

            dfs(left - 1, right, str + '(');
            dfs(left, right - 1, str + ')');
        };

        dfs(n, n, "");

        return ans;
    }
};

79. 单词搜索

/*
 * @lc app=leetcode.cn id=79 lang=cpp
 *
 * [79] 单词搜索
 */

// @lc code=start
class Solution {
private:
    const int dx[4] = {0, 0, 1, -1};
    const int dy[4] = {1, -1, 0, 0};

public:
    // 主函数
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty())
            return false;

        int m = board.size(), n = m ? board[0].size() : 0;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        bool find = false;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                backtrack(i, j, 0, board, word, find, visited);

        return find;
    }
    // 辅函数（注意传引用，否则TLE）
    void backtrack(int i, int j, int level, vector<vector<char>>& board,
                   string& word, bool& find, vector<vector<bool>>& visited) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
            return;
        if (visited[i][j] || find || board[i][j] != word[level])
            return;
        if (level == word.size() - 1) {
            find = true;
            return;
        }

        visited[i][j] = true; // 修改当前节点状态
        // 递归子节点
        for (int k = 0; k < 4; k++) {
            int r = i + dx[k];
            int c = j + dy[k];
            backtrack(r, c, level + 1, board, word, find, visited);
        }
        visited[i][j] = false; // 回改当前节点状态
    }
};
// @lc code=end

131. 分割回文串

/*
 * @lc app=leetcode.cn id=131 lang=cpp
 *
 * [131] 分割回文串
 */

// @lc code=start

// 回溯

class Solution {
private:
    vector<vector<string>> ans;

public:
    vector<vector<string>> partition(string s) {
        int n = s.length();

        vector<string> path;
        backtrack(s, 0, n, 0, path);

        return ans;
    }
    void backtrack(string s, int level, int n, int start, vector<string> path) {
        if (level == n) {
            ans.push_back(path);
            return;
        }

        if (level < n - 1) {
            // 跳过当前字符 s[level]
            backtrack(s, level + 1, n, start, path);
        }

        if (isPalindrome(s, start, level)) {
            // s[start, level] 是一个回文串
            string tmp = s.substr(start, level - start + 1);
            path.push_back(tmp);
            // 下一个回文串从 level+1 开始
            backtrack(s, level + 1, n, level + 1, path);
            // 回溯
            path.pop_back();
        }
    }
    // 辅函数 - 判断字符串 s 的 [left, right] 部分是否回文
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }
};
// @lc code=end

51. N 皇后

class Solution {
private:
    vector<vector<string>> ans;

public:
    vector<vector<string>> solveNQueens(int n) {
        if (n == 0)
            return {};

        // 初始化棋局
        vector<string> board(n, string(n, '.'));
        // 每行每行放置皇后
        backtrack(board, 0, n);

        return ans;
    }
    void backtrack(vector<string> board, int row, int n) {
        if (row == n) {
            ans.push_back(board);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (check(board, row, col, n) == false)
                continue;
            board[row][col] = 'Q';
            backtrack(board, row + 1, n);
            board[row][col] = '.';
        }
    }
    bool check(const vector<string>& board, int row, int col, int n) {
        // 同一列
        for (int i = 0; i < row; i++)
            if (board[i][col] == 'Q')
                return false;

        // 斜上方
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q')
                return false;

        for (int i = row, j = col; i >= 0 && j <= n; i--, j++)
            if (board[i][j] == 'Q')
                return false;

        return true;
    }
};

http://www.kler.cn/news/366788.html

相关文章：

  • 【NodeJS】NodeJS+mongoDB在线版开发简单RestfulAPI (七)：MongoDB的设置
  • 基于大模型的招聘智能体：从创意到MVP
  • 高级java每日一道面试题-2024年10月24日-JVM篇-说一下JVM有哪些垃圾回收器?
  • HivisionIDPhoto Docker部署以及Springboot接口对接(AI证件照制作)
  • Nginx14-Lua基础
  • 安全见闻（9-完结）
  • 基于微信小程序的智能社区服务管理系统
  • 阻塞队列——Java
  • SQL SERVER 2005/2008/2012/2016/2020 数据库状态为“可疑”的解决方法（亲测可用）
  • LeetCode - #127 单词接龙
  • 在 MySQL 中，添加索引后，插入、更新和删除操作的性能通常会变慢的原因
  • 2.插入排序（斗地主起牌）
  • 强化学习数学原理学习(一)
  • golang开发alertmanagerWebhook,实现prometheus+alertmanagerWebhook告警
  • 1.Linux按键驱动
  • AI绘画开源王者归来，Stable Diffusion 3.5 AI绘画模型开源发布
  • 矩阵的可解性：关于Ax=b的研究
  • WeakHashMap详解
  • 谷粒商城の订单服务分布式事务
  • 京准电钟：NTP网络授时服务器应用航管自控系统
  • jmeter学习（6）逻辑控制器
  • 【Python】Whoosh：全流程自建搜索引擎
  • 【c++篇】：从基础到实践--c++内存管理技巧与模版编程基础
  • 免费的CMS系统有哪些？
  • windows中的tracert命令
  • Apache Paimon介绍