首页 > 其他分享 >DFS进阶——全排列

DFS进阶——全排列

时间:2024-03-22 11:00:13浏览次数:31  
标签:排列 进阶 int dfs queue book DFS ArrayDeque queueTemp

通过后续的题目希望大家明白,dfs不仅仅是对图的遍历,他还有很多用法。

DFS进阶1——回溯

先说一下回溯的板子

dfs(){
for(......){
    标记信息
    dfs()
    撤销标记
}
}
回溯模板——递归实现排列型枚举
题目分析

其实就是对1~n的数字全排列,这里就可以用dfs去做,1~n全排列我其实是确定每一个位置我应该放哪一个数字,那么dfs的时候就是对位置dfs,dfs(1)表示我现在要选择一个数放在第一个位置,那么可以选择的范围是1~n,

for(int i = 1;i <= n;i++)

且这个数之前没有被选过,那么我们就要用一个数组book[i]标记一下,book[i]=1表示这个数已经被选走了,那么我就不能再选这个数了。

for(int i = 1;i <= n;i++){
    if(book[i]==1) continue;
}

当我遍历到dfs(n+1)时说明我前n个位置都安排完了,那么我就要输出此时的一个排列,我需要知道我此时选出来的数的排列,那么也可以考虑用一个变量保存,这里我使用的是队列。

if(k==n+1) {
		ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();
		queueTemp.addAll(queue);
		while(!queueTemp.isEmpty()) {
			System.out.print(queueTemp.pollFirst() + " ");
		}
		System.out.println();
		return;
	}

当我选择数i作为当前位置的数时,我要标记这个数已经被选择了并且把它放入队列,这个位置选好后,我要继续选择下一个位置,所以dfs(k+1)

for(int i = 1;i <= n;i++) {
		if(book[i]==1) continue;
		book[i]=1;
		queue.addLast(i);
		dfs(k+1);
	}

当我从dfs退出后再次回来,说明我要尝试选择其它数了,那么我要把选这个数做的标记都撤销,包括,book数组对应位置置为0和把这个数从队列里面拿出来。

for(int i = 1;i <= n;i++) {
		if(book[i]==1) continue;
		book[i]=1;
		queue.addLast(i);
		dfs(k+1);
		book[i]=0;
		queue.pollLast();
	}
题目代码
import java.util.ArrayDeque;
import java.util.Scanner;
public class Main{
	static ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
	static int book[];
	static int n;
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	n = scanner.nextInt();
	book = new int[n+1];
	dfs(1);
}

private static void dfs(int k) {
	if(k==n+1) {
		ArrayDeque<Integer> queueTemp = new ArrayDeque<Integer>();
		queueTemp.addAll(queue);
		while(!queueTemp.isEmpty()) {
			System.out.print(queueTemp.pollFirst() + " ");
		}
		System.out.println();
		return;
	}
	for(int i = 1;i <= n;i++) {
		if(book[i]==1) continue;
		book[i]=1;
		queue.addLast(i);
		dfs(k+1);
		book[i]=0;
		queue.pollLast();
	}
}
}

代码执行过程模拟

因为初学者对递归不理解,再加上回溯更难理解,所以这里对这个代码进行模拟。以n=3为例,也就是待排列的数字为1,2,3。

上图没有写完,只写了一部分,下图是另一种形式,全都写了完了。

在这里插入图片描述

标签:排列,进阶,int,dfs,queue,book,DFS,ArrayDeque,queueTemp
From: https://blog.csdn.net/qq_53237241/article/details/136934338

相关文章

  • HDFSRPC安全认证Token篇推广
    本文主要阐述HDFSRPC安全认证相关的实现。主要介绍Token相关的实现。写在前面相关bloghttps://blog.csdn.net/hncscwc/article/details/124722784https://blog.csdn.net/hncscwc/article/details/124958357Token由来在探究完Kerberos,我一直在想一个问题,rpcConnection已经完......
  • (45/60)爬楼梯进阶、零钱兑换、完全平方数
    day45爬楼梯进阶卡码网:爬楼梯(第八期模拟笔试)动态规划代码实现/*总和为j总共有dp[j]种方法(可重复选取、排列)dp[j]+=dp[j-nums[i]dp[0]=1;其余为0先背包再物品,正序*/#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){......
  • <爬虫部署,进阶Docker>----第十章 探究一下Docker Compose
    前言:        DockerCompose是一个用于定义和运行多容器应用程序的工具,它提供了一种简化和自动化容器编排的方式。在理解DockerCompose的背景之前,让我们先回顾一下容器化技术的发展。容器化技术的出现使得应用程序的部署和管理变得更加轻松和灵活。容器化通过......
  • 代码随想录算法训练营day29 | leetcode 491. 非递减子序列、46. 全排列、47. 全排列 I
    目录题目链接:491.非递减子序列-中等题目链接:46.全排列-中等题目链接:47.全排列II-中等题目链接:491.非递减子序列-中等题目描述:给你一个整数数组nums,找出并返回所有该数组中不同的递增子序列,递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重......
  • LLM进阶——预训练语言模型
    文章目录一、概念二、GPT1、概念2、自回归3、zero-shot三、bert1、概念2、maskedLM一、概念最早的预训练语言模型(plms)是word2vec,现在的模型(gpt&bert)都是基于transformer以下是一些常见的预训练语言模型分类:基于Transformer的模型:BERT(BidirectionalEncoder......
  • Java 面向对象编程进阶四(多态、抽象方法抽象类)
    目录多态(polymorphism)多态和类型转换对象的转型(casting) 类型转换异常向下转型中使用instanceof final关键字抽象方法和抽象类抽象类和抽象方法的基本用法多态(polymorphism)        多态指的是同一个方法调用,由于对象不同可能会有不同的行为。现实......
  • Java 面向对象编程进阶六(内部类 )
    目录内部类内部类的概念内部类的分类1、非静态内部类(外部类里使用非静态内部类和平时使用其他类没什么不同)2、静态内部类3、匿名内部类4、局部内部类内部类        内部类是一类特殊的类,指的是定义在一个类的内部的类。实际开发中,为了方便的使用外部类的相......
  • Java 面向对象编程进阶七(字符串 String )
    目录字符串StringString基础String类和常量池String类常用的方法String类常用方法一String类常用方法二字符串相等的判断字符串String        String是我们开发中最常用的类,我们不仅要掌握String类常见的方法,对于String的底层实现也需要掌握好......
  • Kotlin,简直是 Java 的 Pro Max!(笔记3 进阶篇)
    目录拓展拓展函数拓展属性运算符重载operator高阶函数通过高阶函数,模拟实现标准函数apply内联函数inlinenoinlinecrossinline泛型泛型类泛型方法限定泛型类型模拟实现apply标准函数(泛型版)泛型高级特性回顾Java中的协变和逆变Kotlin的协变和逆变委托......
  • 【力扣】岛屿数量(体会一下dfs和bfs思路的实质)
    题目描述注意,需要求的是岛屿的数量,而不是岛屿的总面积,这道题很考验对dfs思路的理解,而不是简单地套用模版。可以用dfs和bfs两种方法做。深度优先搜索版本首先看代码:classSolution{private:intdir[4][2]={0,1,1,0,-1,0,0,-1};//四个方向voiddfs(ve......