代码随想录算法训练营第三十天 | 332.重新安排行程、51. N皇后、37. 解数独

本文主要是介绍代码随想录算法训练营第三十天 | 332.重新安排行程、51. N皇后、37. 解数独,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

332.重新安排行程

题目链接:332.重新安排行程

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

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

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

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

文章讲解/视频讲解:https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html

思路

采用回溯的方法解决,最暴力的方法就是直接回溯,通过判断路径是否是否等于tickets.size() + 1来决定是否结束。

为了获得字典序最小的结果,我将tickets排了序,并在找到结果时提前剪枝,但是在第80/81样例处超时了。

可以用unordered_map<string, map<string, int>> targets:unordered_map<出发机场, map<到达机场, 航班次数>> targets这个数据结构来构造,这样就不会超时了。

C++实现

// 原写法
class Solution {
public:vector<string> results;vector<int> used;bool finded;vector<string> findItinerary(vector<vector<string>>& tickets) {auto cmp = [](vector<string> a, vector<string> b){return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];};sort(tickets.begin(), tickets.end(), cmp);string curr = "JFK";used.resize(tickets.size(), false);finded = false;vector<string> path;path.push_back(curr);backtracking(path, curr, tickets);path.pop_back();return results;}void backtracking(vector<string>& path, string curr, const vector<vector<string>>& tickets){if(finded) return;if(path.size() == tickets.size() + 1){results = path;finded = true;return;}for(int i = 0;i<tickets.size();i++){if(tickets[i][0] == curr){if(!used[i]){path.push_back(tickets[i][1]);used[i] = true;backtracking(path, tickets[i][1], tickets);path.pop_back();used[i] = false;}}}}
// 用哈希表加速遍历
class Solution {
public:unordered_map<string, map<string,int>> targets;vector<string> findItinerary(vector<vector<string>>& tickets) {for(const vector<string>& ticket : tickets){targets[ticket[0]][ticket[1]]++;}string curr = "JFK";vector<string> results;results.push_back(curr);backtracking2(results, tickets.size());return results;}bool backtracking2(vector<string>& results, int ticket_size){if(results.size() == ticket_size + 1){return true;}string curr = results[results.size() - 1];for(auto& des : targets[curr]){if(des.second > 0){results.push_back(des.first);des.second--;if(backtracking2(results, ticket_size)) return true;des.second++;results.pop_back();}}return false;}
};

51. N皇后

题目链接:51. N皇后

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

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

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

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

文章讲解/视频讲解:https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html

思路

采用回溯方法解决,在使用回溯之前,提前做一下处理:

建立存储每一行是否有Q的hash表,每一列是否有Q的hash表,每一个正斜线是否有Q的hash表,每一个反斜线是否有Q的hash表。

由于我回溯函数里的纵向遍历是根据每一行递归处理的,因此这里存储每一行是否有Q的hash表并不需要。

C++实现

class Solution {
public:vector<vector<string>> results;vector<bool> rowHash, columnHash, slashHash, backslashHash;vector<vector<string>> solveNQueens(int n) {//rowHash.resize(n, false);columnHash.resize(n, false);slashHash.resize(2*n-1, false);backslashHash.resize(2*n-1, false);vector<string> current;for(int i = 0;i<n;i++){string tmp(n, '.');current.push_back(tmp);}backtracking(current, 0, n);return results;}void backtracking(vector<string>& current, int curri, int n){if(curri == n){results.push_back(current);return;}for(int j = 0;j<n;j++){int slashIdx = curri + j;int backslashIdx = curri + (n - j - 1);if(!columnHash[j] && !slashHash[slashIdx] && !backslashHash[backslashIdx]){columnHash[j] = true;slashHash[slashIdx] = true;backslashHash[backslashIdx] = true;current[curri][j] = 'Q';            backtracking(current, curri + 1, n);current[curri][j] = '.';columnHash[j] = false;slashHash[slashIdx] = false;backslashHash[backslashIdx] = false;}}}
};

37. 解数独

题目链接:37. 解数独

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

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

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

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

文章讲解/视频讲解:https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html

思路

首先找到每一个空白格’.',之后遍历这些空白格来进行回溯解决。

在回溯之前需要一些处理,需要9 + 9 + 9个哈希表,分别表示每一行的哈希表,每一列的哈希表,每一个小方格的哈希表。

之后进行回溯操作便可。

C++实现

class Solution {
public:vector<unordered_set<char>> rowHash; // 行vector<unordered_set<char>> columnHash; // 列vector<unordered_set<char>> blockHash; // 3x3方格vector<vector<int>> blanks;void solveSudoku(vector<vector<char>>& board) {rowHash.resize(board.size());columnHash.resize(board.size());blockHash.resize(board.size());for(int i = 0;i<board.size();i++){for(int j = 0;j<board[i].size();j++){int k = 3 * (i / 3) + (j / 3);if(board[i][j] != '.'){rowHash[i].insert(board[i][j]);columnHash[j].insert(board[i][j]);blockHash[k].insert(board[i][j]);}else{blanks.push_back({i, j, k});}}}backtracking(0, board);}bool backtracking(int curri, vector<vector<char>>& board){if(curri == blanks.size()){return true;}vector<int> index = blanks[curri];for(int i = 1;i<=9;i++){char num = '0' + i;if(rowHash[index[0]].find(num) == rowHash[index[0]].end() &&columnHash[index[1]].find(num) == columnHash[index[1]].end() &&blockHash[index[2]].find(num) == blockHash[index[2]].end()){rowHash[index[0]].insert(num);columnHash[index[1]].insert(num);blockHash[index[2]].insert(num);board[index[0]][index[1]] = num;if(backtracking(curri + 1, board)) return true;board[index[0]][index[1]] = '.';rowHash[index[0]].erase(num);columnHash[index[1]].erase(num);blockHash[index[2]].erase(num);}}return false;}
};

回溯总结

https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

这篇关于代码随想录算法训练营第三十天 | 332.重新安排行程、51. N皇后、37. 解数独的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/594741

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义