332.重新安排行程 , 51. N皇后 ,37. 解数独

简介: 本文介绍了三道经典的回溯算法问题及其解决方案。第一题“重新安排行程”要求根据给定的航班列表,从 JFK 出发规划行程,并按字典序返回最小的行程组合。通过构建映射关系并使用深度优先搜索(DFS)与回溯法解决第二题“N 皇后”探讨如何在 n×n 的棋盘上放置 n 个皇后,使彼此不互相攻击。采用递归和剪枝技术验证每一步的合法性,确保行、列及对角线无冲突。第三题“解数独”需填充空格以满足数独规则:每行、每列及每个 3x3 宫内的数字 1-9 不重复。利用双重循环遍历棋盘,递归尝试每个空格的可能数字,结合有效性检查完成求解。以上题目均通过回溯法实现,体现了该算法在复杂约束条件下的强大适用性。

 题目:332. 重新安排行程

给你一份航线列表 tickets ,其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。

例如,行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小,排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1:

输入:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

输出:["JFK","MUC","LHR","SFO","SJC"]

示例 2:

输入:tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

输出:["JFK","ATL","JFK","SFO","ATL","SFO"]

解释:另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ,但是它字典排序更大更靠后。

提示:

1 <= tickets.length <= 300

tickets[i].length == 2

fromi.length == 3

toi.length == 3

fromi 和 toi 由大写英文字母组成

fromi != toi

思考历程与知识点:  

这道题目有几个难点:

一个行程中,如果航班处理不好容易变成一个圈,成为死循环

有多种解法,字母序靠前排在前面,让很多同学望而退步,如何该记录映射关系呢 ?

使用回溯法(也可以说深搜) 的话,那么终止条件是什么呢?

搜索的过程中,如何遍历一个机场所对应的所有机场。

题解:

class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
    if (result.size() == ticketNum + 1) {
        return true;
    }
    for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
        if (target.second > 0 ) { // 记录到达机场是否飞过了
            result.push_back(target.first);
            target.second--;
            if (backtracking(ticketNum, result)) return true;
            result.pop_back();
            target.second++;
        }
    }
    return false;
}
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const vector<string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

 题目:51. N 皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1:

输入:n = 4

输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1

输出:[["Q"]]

提示:

1 <= n <= 9

题解:  

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯,撤销皇后
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

 题目:37. 解数独

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则:

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

数独部分空格内已填入了数字,空白格用 '.' 表示。

示例 1:

输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

提示:

board.length == 9

board[i].length == 9

board[i][j] 是一位数字或者 '.'

题目数据 保证 输入数独仅有一个解

思考历程与知识点:  

一个for循环遍历棋盘的行,一个for循环遍历棋盘的列,一行一列确定下来之后,递归遍历这个位置放9个数字的可能性

题解:

class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] == '.') {
                for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                    if (isValid(i, j, k, board)) {
                        board[i][j] = k;                // 放置k
                        if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                        board[i][j] = '.';              // 回溯,撤销k
                    }
                }
                return false;  // 9个数都试完了,都不行,那么就返回false
            }
        }
    }
    return true; // 遍历完没有返回false,说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) { // 判断行里是否重复
        if (board[row][i] == val) {
            return false;
        }
    }
    for (int j = 0; j < 9; j++) { // 判断列里是否重复
        if (board[j][col] == val) {
            return false;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == val ) {
                return false;
            }
        }
    }
    return true;
}
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};


相关文章
|
4月前
|
人工智能 程序员 API
别再被昂贵 SEO 订阅费拿捏了:3.5k Star OpenSEO,直接做 Semrush/Ahrefs 开源替代
OpenSEO 是 Semrush / Ahrefs 的开源替代方向:自托管、按量 SEO 数据、MCP 和 Agent Skills,把关键词、外链、审计和 AI 工作流连起来。
674 0
|
5月前
|
消息中间件 弹性计算 Cloud Native
从单机崩溃到全球代购:我用云原生重构了跨境物流系统
代购转运系统曾因订单队列卡死、DB连接爆满饱受大促之苦。去年以“解耦、异步、弹性、可观测”八字方针重构:拆为7个独立服务,订单创建后异步发MQ,按CPU/QPS自动扩缩容,修复连接池泄漏、优化分布式事务(本地消息表+补偿),日志分级治理。平稳扛过多次大促。
287 1
|
5月前
|
JSON 自然语言处理 前端开发
谷歌深夜发布 Gemini 3.5:多模态能力再升级,开发者该怎么抓住这波机会?
Gemini 3.5 Flash于2026年5月发布,主打原生多模态与实时智能体能力:支持图文音视一体化理解、帧级视频诊断、100万token长上下文,并在编码(76.2%)、Agent任务(83.6%)等实测中超越前代。速度快4倍、成本更低,已免费开放。
|
机器学习/深度学习 人工智能 运维
运维不只是“修电脑”:聊聊运维如何助力 AI 优化服务质量
运维不只是“修电脑”:聊聊运维如何助力 AI 优化服务质量
719 9
|
11月前
|
传感器 存储 人工智能
AI智能体:实现AGI的关键一步与未来展望
AI智能体是能自主感知、决策与行动的“数字大脑”,它让AI从只会回答问题进化为能动手解决问题。相比传统工具,它具备自主性、反应性、前瞻性、交互性和迭代性,可像助手一样主动完成复杂任务。如今已在政务、医疗、教育、金融等领域落地,成为提升效率的“数字员工”。2025年被视为“AI智能体元年”,技术、资本与政策合力推动其迈向规模化应用,开启人机协同新阶段。
1589 4
|
11月前
|
传感器 人工智能 算法
解析支持二次开发的移动机器人关键设备与平台选型
本文解析支持二次开发的移动机器人关键设备与平台选型,涵盖服务机器人、通用底盘、科研教育、工业AMR、导航算法及桌面级平台六大类别。重点分析猎户星空、松灵、九号、Clearpath、斯坦德等主流平台的技术特点,对比其在开放性、实时性、仿真支持与场景适配上的优势,为开发者提供选型参考。(238字)
|
机器学习/深度学习 敏捷开发 人工智能
2025产品需求管理最佳实践:从流程优化到工具选型 详解项目需求管理实战
本文深入探讨产品需求管理的核心概念与全流程优化方法,涵盖需求采集、分析、优先级排序及落地实现等关键环节。通过多维度需求采集、科学评估与敏捷迭代,结合团队角色分工,确保需求价值最大化。同时对比评测板栗看板、Jira、Axosoft等管理工具,并展望AI赋能下的智能生成、预测性分析与自动化流程新趋势,助力企业精准把握市场动态,打造爆款产品。掌握需求管理精髓,是产品成功的关键驱动力。
|
运维
JumpServer的会话管理及命令过滤器应用案例
文章展示了JumpServer的会话管理功能,包括查看命令记录、在线会话和历史会话,并介绍了命令过滤器的创建和应用案例。
1013 2
JumpServer的会话管理及命令过滤器应用案例
|
机器学习/深度学习 自然语言处理 搜索推荐
深度学习中的多头注意力机制及其应用探索
深度学习中的多头注意力机制及其应用探索
1420 2
|
安全 网络安全 数据安全/隐私保护
智能家居系统的安全性分析与改进策略
随着科技的飞速发展,智能家居系统已成为现代生活的一部分。然而,随之而来的安全问题亦日益凸显。本文将深入探讨智能家居系统面临的主要安全挑战,包括数据保护、设备安全性和网络攻击等方面,并提出相应的改进措施。通过增强加密技术、采用多因素认证和定期更新软件等方法,旨在提高智能家居系统的整体安全性,确保用户隐私和数据的安全。
645 26