洛谷 P1706 全排列问题Java

浅浅的花香味﹌ 2022-10-25 14:28 168阅读 0赞

# 洛谷 P1706 全排列问题 #

[题目链接][Link 1]

## 题目描述 ##

> 输出自然数 1 到 nn 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

## 输入格式 ##

> 一个整数 n。

## 输出格式 ##

> 由1∼n 组成的所有不重复的数字序列，每行一个序列。  
> 每个数字保留 5 个场宽。

## 输入输出样例 ##

### 输入 ###

### 输出 ###

1    2    3
        1    3    2
        2    1    3
        2    3    1
        3    1    2
        3    2    1

## 解题思路 ##

此题目是一个简单的**字典序**的全排列问题,只需要简单的使用回溯法即可实现。  
对于Java用户来说，需要注意的是对于输出的处理。本人一开始使用PrintWrite快速输出(其实也不算太快)，但是奈何该输出方式太吃内存，因此在125MB的内存限制下根本不够用，因此尝试使用字符串来缓存结果，成功AC。

## 代码描述 ##

import java.io.*;
    import java.util.*;
    public class Main {
        
    	static int n;
    	static int[] res;
    	static short[] visited;
    	static PrintWriter pr;
    	static StringBuilder printTemp;
    	public static void main(String[] args) throws IOException {
        
    		Scanner sc=new Scanner(System.in);
    		PrintWriter pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    		n=sc.nextInt();
    		res=new int[n];
    		visited=new short[10];
    		printTemp=new StringBuilder();
    		BackTrack(0);
    		pr.print(printTemp);
    		pr.flush();
    		return;
    	}
    	
    	static void BackTrack(int index) {
        
    		if(index==n) {
        
    			//开始缓存结果
    			for(int i=0;i<n;i++) {
        
    				printTemp.append("    "+res[i]);
    			}
    			printTemp.append("\n");  //回车
    			return;
    		}
    		for(int i=1;i<=n;i++) {
        
    			if(visited[i]==1) continue;
    			visited[i]=1;
    			res[index]=i;
    			BackTrack(index+1);
    			visited[i]=0;
    		}
    		return;
    	}
    }

## 另外一种输出方式 ##

之后,本人经过测试原来PrintWrite吃内存是输出格式的原因。  
本人之前的输出格式(很吃内存):

for(int i=0;i<n;i++) {
        
    				pr.print(String.format("%5d", res[i]));
    			}
    			pr.println();  //回车

改完之后便可以AC了:

for(int i=0;i<n;i++) {
        
    				pr.print("    "+res[i]);
    			}
    			pr.println();  //回车

### 另一种代码 ###

import java.io.*;
    import java.util.*;
    public class Main {
        
    	static int n;
    	static int[] res;
    	static short[] visited;
    	static PrintWriter pr;
    	static StringBuilder printTemp;
    	public static void main(String[] args) throws IOException {
        
    		Scanner sc=new Scanner(System.in);
    		pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    		n=sc.nextInt();
    		res=new int[n];
    		visited=new short[10];
    		printTemp=new StringBuilder();
    		BackTrack(0);
    		pr.flush();
    		return;
    	}
    	
    	static void BackTrack(int index) {
        
    		if(index==n) {
        
    			//输出
    			for(int i=0;i<n;i++) {
        
    				pr.print("    "+res[i]);
    			}
    			pr.println();  //回车
    			return;
    		}
    		for(int i=1;i<=n;i++) {
        
    			if(visited[i]==1) continue;
    			visited[i]=1;
    			res[index]=i;
    			BackTrack(index+1);
    			visited[i]=0;
    		}
    		return;
    	}
    }

[Link 1]: https://www.luogu.com.cn/problem/P1706