LeetCode——回溯篇(三)

刷题顺序及思路来源于代码随想录,网站地址:https://programmercarl.com

目录

46. 全排列

47. 全排列 II

332. 重新安排行程

51. N 皇后

37. 解数独


 

46. 全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author light
 * @Description 全排列
 * @create 2023-08-30 9:36
 */
public class PermuteTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] nums=new int[n];
		for (int i = 0; i < n; i++) {
			nums[i]=input.nextInt();
		}
		System.out.println(permute(nums));
	}
	public static List<List<Integer>> res=new ArrayList<>();
	public static List<Integer> path=new ArrayList<>();
	public static List<List<Integer>> permute(int[] nums) {
		int[] used=new int[nums.length]; //记录数组中哪个元素已经使用过了
		Arrays.fill(used,0);
		backtracking(nums,used);
		return res;
	}

	private static void backtracking(int[] nums,int[] used) {
		if(path.size()==nums.length){
			res.add(new ArrayList<>(path));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			if(used[i]==0){
				path.add(nums[i]);
				used[i]=1;
				backtracking(nums,used);
				//回溯
				path.remove(path.size()-1);
				used[i]=0;
			}
		}
	}
}

47. 全排列 II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

输入:nums = [1,1,2]
输出:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author light
 * @Description 全排列II
 *
 *给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
 *
 * (需要去重
 * @create 2023-08-30 9:59
 */
public class PermuteUniqueTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] nums=new int[n];
		for (int i = 0; i < n; i++) {
			nums[i]=input.nextInt();
		}
		System.out.println(permuteUnique(nums));
	}

	public static List<List<Integer>> res=new ArrayList<>();
	public static List<Integer> path=new ArrayList<>();

	public static List<List<Integer>> permuteUnique(int[] nums) {
		Arrays.sort(nums);
		int[] used=new int[nums.length]; //记录数组中哪个元素已经使用过了--同时去重
		Arrays.fill(used,0);
		backtracking(nums,used);
		return  res;
	}

	private static void backtracking(int[] nums, int[] used) {
		if(path.size()== nums.length){
			res.add(new ArrayList<>(path));
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			//去重逻辑
			if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){
				continue;
			}
			if(used[i]==0){ //数组元素还未使用
				path.add(nums[i]);
				used[i]=1;
				backtracking(nums,used);
				//回溯
				path.remove(path.size()-1);
				used[i]=0;
			}
		}
	}
}

332. 重新安排行程

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

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

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

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

 

public class FindItineraryTest {

	public LinkedList<String> res;
	public LinkedList<String> path=new LinkedList<>();

	public List<String> findItinerary(List<List<String>> tickets) {
		//对集合中元素降落地点排序
		Collections.sort(tickets, new Comparator<List<String>>() {
			@Override
			public int compare(List<String> o1, List<String> o2) {
				return o1.get(1).compareTo(o2.get(1));
			}
		});
		path.add("JFK"); //从JFK出发
		boolean[] used=new boolean[tickets.size()]; //判断元素是否重复
		Arrays.fill(used,false);
		backtracking((ArrayList)tickets,used);
		return res;
	}

	private boolean backtracking(ArrayList<List<String>> tickets, boolean[] used) {
		//终止条件
		if(path.size()==tickets.size()+1){
			res=new LinkedList<>(path);  //只有一条路径
			return true;
		}

		for (int i = 0; i < tickets.size(); i++) {
			//未使用重复元素并且path中最后一个元素的值等于tickets数组航班中的起飞航班,则将降落航班加入path中
			if(!used[i]&&tickets.get(i).get(0).equals(path.getLast())){
				path.add(tickets.get(i).get(1));
				used[i]=true;
				if(backtracking(tickets,used)){
					return true;
				}
				//回溯
				used[i]=false;
				path.removeLast();
			}

		}
		return false;
	}

}

51. N 皇后

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

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

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

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

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author light
 * @Description N皇后
 * @create 2023-08-30 11:13
 */
public class SolveNQueensTest {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		System.out.println(solveNQueens(n));
	}


	public static List<List<String>> res=new ArrayList<>();

	public static List<List<String>> solveNQueens(int n) {
		char[][] chessboard = new char[n][n];
		for (char[] c : chessboard) {
			Arrays.fill(c, '.');
		}
		backtracking(chessboard,n,0);
		return res;
	}

	//row:行--控制递归深度
	private static void backtracking(char[][] chessboard, int n, int row) {
		//终止条件--收获结果
		if(row==n){
			res.add(arrayToList(chessboard));
			return;
		}
		//单层递归逻辑
		for (int col = 0; col < n; col++) {
			//判断是否合法位置
			if(isValid(chessboard,row,col,n)){
				chessboard[row][col]='Q';
				backtracking(chessboard,n,row+1);
				//回溯
				chessboard[row][col]='.';
			}
		}
	}

	private static List<String> arrayToList(char[][] chessboard) {
		List<String> path=new ArrayList<>();
		for (int i = 0; i < chessboard.length; i++) {
			path.add(String.valueOf(chessboard[i]));
		}
		return path;
	}

	/*
	验证棋盘是否合法
		按照如下标准去重:
			1.不能同行
			2.不能同列
			3.不能同斜线 (45度和135度角)
	 */
	private static boolean isValid(char[][] chessboard, int row, int col, int n) {
		检查行  (可以不用检查行,每一次递归,row+1
		//for (int i = 0; i < col; i++) {
		//	if(chessboard[row][i]=='Q'){
		//		return false;
		//	}
		//}

		//检查列
		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;

	}

}

37. 解数独

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

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

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

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


/**
 * @author light
 * @Description 解数独
 *
 * @create 2023-08-30 12:19
 */
public class SolveSudokuTest {
	public static void solveSudoku(char[][] board) {
		backtracking(board);
	}

	private static boolean backtracking(char[][] board) {

		for (int i = 0; i < 9; i++) { //行
			for (int j = 0; j < 9; j++) { //列
				if(board[i][j]!='.'){
					continue;
				}else {

					for (char k = '1'; k <='9' ; k++) {
						if(isValid(i,j,k,board)){
							board[i][j]=k;
							if(backtracking(board)){
								return true;
							}
							//回溯
							board[i][j]='.';
						}
					}
					// 9个数都试完了,都不行,那么就返回false
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 判断棋盘是否合法有如下三个维度:
	 *     同行是否重复
	 *     同列是否重复
	 *     9宫格里是否重复
	 */
	private static boolean isValid(int row, int col, char val,char[][] board) {
		//同行是否重复
		for (int i = 0; i < 9; i++) {
			if(board[row][i]==val){
				return false;
			}
		}

		//同列是否重复
		for (int i = 0; i <9; i++) {
			if(board[i][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;
	}
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/97059.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux命令查看CPU、内存、IO使用情况简单介绍

文章目录 1. CPU相关介绍1.1 物理CPU1.2 物理CPU内核1.3 逻辑CPU1.4 几核几线程1.5 CPU设计图 2. top 查看系统负载、CPU使用情况2.1 系统整体的统计信息2.2 进程信息2.3 top命令使用 3. lscpu 显示有关 CPU 架构的信息4. free 查看内存信息5. iostat 查看io信息 1. CPU相关介绍…

雅思写作 三小时浓缩学习顾家北 笔记总结(一)

目录 饥饿网翻译100个句子记录 There are some economically deprived communities in large cities. there is no clear link between grouping student by ability and their levels of attainment. young people without tertiary education qualification normally hav…

python-数据可视化-下载数据-CSV文件格式

数据以两种常见格式存储&#xff1a;CSV和JSON CSV文件格式 comma-separated values import csv filename sitka_weather_07-2018_simple.csv with open(filename) as f:reader csv.reader(f)header_row next(reader)print(header_row) # [USW00025333, SITKA AIRPORT, A…

高等职业学校物联网实训室建设方案

一、概述 1.1专业背景 物联网&#xff08;Internet of Things&#xff09;被称为继计算机、互联网之后世界信息产业第三次浪潮&#xff0c;它并非一个全新的技术领域&#xff0c;而是现代信息技术发展到一定阶段后出现的一种聚合性应用与技术提升&#xff0c;是随着传感网、通…

解决博客不能解析PHP直接下载源码问题

背景&#xff1a; 在网站设置反向代理后&#xff0c;网站突然不能正常访问&#xff0c;而是会直接下载访问文件的PHP源码 解决办法&#xff1a; 由于在搞完反向代理之后&#xff0c;PHP版本变成了纯静态&#xff0c;所以网站不能正常解析&#xff1b;只需要把PHP版本恢复正常…

SQL注入漏洞复现(CVE-2017-8917)

文章目录 搭建环境启动环境漏洞复现报错注入使用sqlmap 前提条件&#xff1a; 1.安装docker docker pull medicean/vulapps:j_joomla_22.安装docker-compose docker run -d -p 8000:80 medicean/vulapps:j_joomla_23.下载vulhub Docker Compose是 docker 提供的一个命令行工具&…

springboot docker

在Spring Boot中使用Docker可以帮助你将应用程序与其依赖的容器化&#xff0c;并简化部署和管理过程。 当你在Spring Boot中使用Docker时&#xff0c;你的代码不需要特殊的更改。你可以按照通常的方式编写Spring Boot应用程序。 java示例代码&#xff0c;展示了如何编写一个基…

直播预告!生鲜与零售商品识别系统产业实践与部署详解

生鲜零售作为民生消费的重要一环&#xff0c;在促进行业新消费升级的进程中有着至关重要的作用。在超市等无人零售场景中&#xff0c;目前结算方式主要有以下几种&#xff1a; 但是以上几种方法存在如下缺点&#xff1a; 条形码方式&#xff1a;对于成品包装的商品较为成熟&a…

WPF_布局基础

布局容器 Grid 定义由列和行组成的灵活的网格区域。 行 <Grid.RowDefinitions><RowDefinition/><RowDefinition/></Grid.RowDefinitions> 列 <Grid.ColumnDefinitions><ColumnDefinition/><ColumnDefinition/></Grid.ColumnDe…

指针与空间按钮的交互

文章目录 原理案例&#xff1a;“直线指针”和“点击按钮”的交互1、效果2、步骤 原理 指针不能直接和空间按钮交互&#xff0c;得借助一个中间层——分发器——它分发指针的进入、退出、选择事件&#xff0c;空间按钮自动监听这些事件 案例&#xff1a;“直线指针”和“点击…

HTTPS安全通信和SSL Pinning

随着互联网的迅速发展&#xff0c;网络通信安全问题日益凸显。在这一背景下&#xff0c;HTTPS作为一种加密通信协议得到了广泛应用&#xff0c;以保障用户的数据隐私和信息安全。本文将介绍HTTPS的基本原理、发展历程&#xff0c;以及与之相关的中间人攻击和防护方法。 1. HTT…

1.RTKLIB环境配置和调试

1.源码下载 下载链接&#xff1a;rtklib 注&#xff1a;2.4.2 p13为稳定版本&#xff08;标识p代表稳定版本&#xff09;&#xff0c;2.4.3 b34为最新实验版本&#xff08;标识b&#xff09;。点击2.4.3 b34 的Source Programs and Data 链接下载源码。 2.环境配置 **集成…

深度剖析java类和对象

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【JavaSE_primary】 在Java中&#xff0c;一切皆对象。 目录 一、类的定义和使用1.1类的定义格式1.2定义学生类 二、类的实例化三、this引…

《Flink学习笔记》——第九章 多流转换

无论是基本的简单转换和聚合&#xff0c;还是基于窗口的计算&#xff0c;我们都是针对一条流上的数据进行处理的。而在实际应用中&#xff0c;可能需要将不同来源的数据连接合并在一起处理&#xff0c;也有可能需要将一条流拆分开&#xff0c;所以经常会有对多条流进行处理的场…

基于Jenkins构建生产CICD环境(第三篇)

目录 基于Jenkins自动打包并部署docker环境 1、安装docker-ce 2、阿里云镜像加速器 3、构建tomcat 基础镜像 4、构建一个Maven项目 基于Jenkins自动化部署PHP环境 基于rsync部署 基于Jenkins自动打包并部署docker环境 1、安装docker-ce 在192.168.2.123 机器上&#x…

SQLI-labs-第三关

目录 知识点&#xff1a;单括号)字符get注入 1、判断注入点&#xff1a; 2、判断当前表的字段数 3、判断回显位置 4、爆库名 5、爆表名 6、爆字段名&#xff0c;以users表为例 7、爆值 知识点&#xff1a;单括号)字符get注入 思路&#xff1a; 1、判断注入点&#xff1…

HTML学习笔记02

HTML笔记02 页面结构分析 元素名描述header标题头部区域的内容&#xff08;用于页面或页面中的一块区域&#xff09;footer标记脚部区域的内容&#xff08;用于整个页面或页面的一块区域&#xff09;sectionWeb页面中的一块独立区域article独立的文章内容aside相关内容或应用…

测试理论与方法----测试流程的第四个步骤:执行测试,提出缺陷

8、执行测试—–>提交缺陷报告 测试流程&#xff1a;执行测试—–>提交缺陷报告 1、缺陷的概述&#xff08;回顾&#xff09; 结果角度&#xff1a;实际结果和预期结果不一致 需求角度&#xff1a;所有不满足需求或超出需求的&#xff0c;都是缺陷 2、缺陷的相关属性…

Glide分析和总结

1. Glide概述 Glide是一款图片处理的框架&#xff0c;从框架设计的角度出发&#xff0c;最基本要实现的就是 加载图片 和 展示。 它把一个图片请求封装成一个Request对象&#xff0c;里面有开启、暂停、关闭、清除网络请求、以及载体生命周期的监听等操作。然后通过RequestBu…

【Java基础增强】Stream流

1.Stream流 1.1体验Stream流【理解】 案例需求 按照下面的要求完成集合的创建和遍历 创建一个集合&#xff0c;存储多个字符串元素 把集合中所有以"张"开头的元素存储到一个新的集合 把"张"开头的集合中的长度为3的元素存储到一个新的集合 遍历上一步得…