java算法第30天 | ● 332.重新安排行程 ● 51. N皇后 ● 37. 解数独

2024-03-22 09:44

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

今天是三道困难题,一刷可以先跳过。

332.重新安排行程

本题的重点是使用Map<String,Map<String,Integer>>存储路径以便递归中根据上一个地点检索接下来的选择。注意,因为要求按字母顺序排列优先级,所以内层的Map要用TreeMap<String,Integer>。并且回溯的递归函数要有返回值(因为最终只需要获取一个路径)。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {private Deque<String> res;private Map<String, Map<String, Integer>> map;private boolean backTracking(int ticketNum){if(res.size() == ticketNum + 1){return true;}String last = res.getLast();if(map.containsKey(last)){//防止出现nullfor(Map.Entry<String, Integer> target : map.get(last).entrySet()){int count = target.getValue();if(count > 0){res.add(target.getKey());target.setValue(count - 1);if(backTracking(ticketNum)) return true;res.removeLast();target.setValue(count);}}}return false;}public List<String> findItinerary(List<List<String>> tickets) {map = new HashMap<String, Map<String, Integer>>();res = new LinkedList<>();for(List<String> t : tickets){Map<String, Integer> temp;if(map.containsKey(t.get(0))){temp = map.get(t.get(0));temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);}else{temp = new TreeMap<>();//升序Maptemp.put(t.get(1), 1);}map.put(t.get(0), temp);}res.add("JFK");backTracking(tickets.size());return new ArrayList<>(res);}
}

51. N皇后

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

该题递归的深度是n,每一层递归是遍历当前行每个位置放皇后是否合法,树枝向下是行的增加,横向向右是列位置的遍历。
需要自定义一个判断当前位置是否合法的函数。

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chessboard = new char[n][n];for (char[] c : chessboard) {Arrays.fill(c, '.');}backTrack(n, 0, chessboard);return res;}public void backTrack(int n, int row, char[][] chessboard) {if (row == n) {res.add(Array2List(chessboard));return;}for (int col = 0;col < n; ++col) {if (isValid (row, col, n, chessboard)) {chessboard[row][col] = 'Q';backTrack(n, row+1, chessboard);chessboard[row][col] = '.';}}}public List Array2List(char[][] chessboard) {List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}public boolean isValid(int row, int col, int n, char[][] chessboard) {// 检查列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-1; i--, j++) {if (chessboard[i][j] == 'Q') {return false;}}return true;}
}

37. 解数独

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

这道题需要再递归函数里进行两次for循环,第一层遍历行,第二层遍历列。
因为只需要找到一条符合条件的结果,因此只要找到了就返回true,因此返回值是boolean类型。

class Solution {public void solveSudoku(char[][] board) {solveSudokuHelper(board);}private boolean solveSudokuHelper(char[][] board){//「一个for循环遍历棋盘的行,一个for循环遍历棋盘的列,// 一行一列确定下来之后,递归遍历这个位置放9个数字的可能性!」for (int i = 0; i < 9; i++){ // 遍历行for (int j = 0; j < 9; j++){ // 遍历列if (board[i][j] != '.'){ // 跳过原始数字continue;}for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适if (isValidSudoku(i, j, k, board)){board[i][j] = k;if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回return true;}board[i][j] = '.';}}// 9个数都试完了,都不行,那么就返回falsereturn false;// 因为如果一行一列确定下来了,这里尝试了9个数都不行,说明这个棋盘找不到解决数独问题的解!// 那么会直接返回, 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去!」}}// 遍历完没有返回false,说明找到了合适棋盘位置了return true;}/*** 判断棋盘是否合法有如下三个维度:*     同行是否重复*     同列是否重复*     9宫格里是否重复*/private boolean isValidSudoku(int row, int col, char val, 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;}}// 9宫格里是否重复int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++){for (int j = startCol; j < startCol + 3; j++){if (board[i][j] == val){return false;}}}return true;}
}

这篇关于java算法第30天 | ● 332.重新安排行程 ● 51. N皇后 ● 37. 解数独的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ