首页 > 试题广场 >

解密

[编程题]解密

热度指数：3760 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

亮亮深吸一口气，小心地将盒子打开，里面是一张地图，地图上除了一些奇怪的字母以外没有任何路线信息，这可让亮亮犯了愁，这些字母代表了什么意思呢？亮亮绞尽脑汁也想不出什么思路，突然，亮亮眼前一亮，“我可以把这些字母所有的排列方式全部写出来，一定可以找到答案！” 于是，亮亮兴奋的开始寻找字母里的秘密。

输入描述:

每组数据输入只有一行，是一个由不同的大写字母组成的字符串，已知字符串的长度在1到9之间，我们假设对于大写字母有'A' < 'B' < ... < 'Y' < 'Z'。

输出描述:

输出这个字符串的所有排列方式，每行一个排列，要求字母序比较小的排列在前面。

示例1

输入

WHL

输出

HLW<br/> HWL<br/> LHW<br/> LWH<br/> WHL<br/> WLH<br/>

算法知识视频讲解

Python

华科平凡

python三行解法:

from itertools import permutations
for i in permutations(sorted(input())):
    print("".join(i))

编辑于 2017-09-12 14:53:17 回复(0)

饥饿的王者在刷题

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
//全排列的经典算法
void permulation(int step,string &str,vector<string> &ans){
	if(step == str.size()-1)
	ans.push_back(str);

	for (int i = step; i < str.size(); i++)
	{
		swap(str[step], str[i]);
		permulation(step+1, str, ans);
		swap(str[step], str[i]);
	}
}
int main()
{
	string str;
	while(cin>>str)
	{
		vector<string> ans;
		permulation(0, str, ans);
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++)
			cout<<ans[i]<<endl;
	}

	return 0;
}

发表于 2016-06-16 20:17:15 回复(1)

cycleof

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
void QPL(int x,int n,string str,vector<string> &strr){//把地址传入函数，则在函数中的改变是把变量本身改变了
    int i = x;
    if(i == n-1){
        strr.push_back(str);
    }
    else{
        for(i=x;i<n;i++){
            swap(str[x],str[i]);
            QPL(x+1,n,str,strr);
            swap(str[x],str[i]);
        }
    }
}
int main(){
    vector<string> strr;
    string str;
    while( cin >> str ){
        int i,l = str.size();
        QPL(0,l,str,strr);
        sort(strr.begin(),strr.end());//字符串排序是按其字典序排序的
        for(i=0;i<strr.size();i++){
            cout << strr[i] << endl;
        }
    }
}

发表于 2017-07-05 17:45:11 回复(0)

牛客欢迎

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s=in.nextLine();
            char[] cs=s.toCharArray();
            Arrays.sort(cs);
            List<String> ls=new ArrayList<String>();
            List<Character> lc=new ArrayList<Character>();
            addChar(ls, lc, cs);
            for(String str:ls){
            	System.out.println(str);
            }
        }
    }
	private static void addChar(List<String> ls, List<Character> lc, char[] cs) {
		// TODO Auto-generated method stub
		if(lc.size()==cs.length){
			StringBuffer sb=new StringBuffer();
			for(char c:lc){
				sb.append(c);
			}
			ls.add(sb.toString());
			return ;
		}
		for(int i=0;i<cs.length;i++){
			if(!lc.contains(cs[i])){
				lc.add(cs[i]);
				addChar(ls, lc, cs);
				lc.remove(lc.size()-1);
			}
		}
	}
}

这类遍历字符串的问题，我一直用这种方法

发表于 2016-09-22 12:13:24 回复(5)

Java

某同学

//之前获取排列组合方法有超出内存，做出来还是很开心的。希望有帮助
import java.util.*;
public class Main {
    static List<String> list=new ArrayList<String>();
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner=new Scanner(System.in);     
        while (scanner.hasNext())
            {
             String input=scanner.nextLine();
           permutation(input.toCharArray(), 0); //获取排列组合
             Collections.sort(list,new Comparator<String>() //按照字母排序
      {
                @Override
                public int compare(String o1, String o2)
                {  return compare1(o2,o1,0);
                } });
             for (String string : list)
                    System.out.println(string);
             }
        scanner.close();
    }
    
    public static int compare1(String o1, String o2,int n)
    {
     if (o2.charAt(n)-o1.charAt(n)==0)
        {
            return compare1(o1,o2,n+1);
        }
     else {
            return o2.charAt(n)-o1.charAt(n);
        }
    }
    public static void permutation(char[] str, int i) {
        if (i >= str.length)
            return;
        if (i == str.length - 1) {
            list.add(String.valueOf(str));
        } else {
            for (int j = i; j < str.length; j++) {
                char temp = str[j];
                str[j] = str[i];
                str[i] = temp;
                permutation(str, i + 1);
                temp = str[j];
                str[j] = str[i];
                str[i] = temp;
            }
        }
    }
}

发表于 2016-07-29 17:46:48 回复(0)

老石基

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {//注意while处理多个case
        	String[] a = in.next().split("");
        	List<String> list = get(a,a.length);
        	Set<String> set = new TreeSet<String>(list);
        	for (String string : set) {
				System.out.println(string);
			}
        }
        in.close();
	}
	
	public static List<String> get(String[] a,int n){
		List<String> list = new ArrayList<String>();
		if(n==1){
			for(int i = 0;i<a.length;i++){
				list.add(a[i]);
			}
			return list;
		}
		List<String> temp = get(a,n-1);
		for(int i = 0;i<a.length;i++){
			
			for(int j = 0;j<temp.size();j++){
				if(temp.get(j).indexOf(a[i])<0)
					list.add(a[i]+temp.get(j));
			}
		}
		
		return list;
	}
}

发表于 2016-04-12 09:37:47 回复(3)

闷声发财00

#include <iostream>
#include <algorithm>
using namespace std;
string s;
void dfs(string res, string &s, int u, int state){
    if(u == s.size()){
        cout << res << endl;
        return;
    }
    for(int i=0; i<s.size(); ++i){
        if((state>>i & 1) == 0){
            res[u] = s[i];
            dfs(res, s, u+1, state|(1<<i));
        }
    }
}
int main(){
    while(cin >> s){
        sort(s.begin(), s.end());
        string res = s;
        dfs(res, s, 0, 0);
    }
    return 0;
}

常规dfs

发表于 2019-08-12 10:23:11 回复(0)

VagrantYang

package com.special.first;

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

/**
 * 楚楚街01-解密
 *
 * 其实就是：无重复字符的全排列问题
 * dfs思想可过，因为问题可以转化为子问题
 * 比如全排列 123 132 213 231 312 321
 * 我们可以发现123的全排列其实是 1 加上 23 的全排列， 2 加上 13的全排列，3 加上 1 2的全排列
 * 之后又是 2 加上 3的全排列（就是3本身）， 3 加上 2的全排列（就是2本身）
 *
 * 所以我们不断深搜，直到最后一个点（因为最后一个点全排列是本身），即可构成一个排列，
 * 然后再次回溯到上层的子问题（2个数的全排列问题）
 *
 * 注意：1.因为我们的算法递归保证了如果原字符串是有序的，那么产生的排列也会是从小到大，
 * 因为我们用了一个访问数组控制了要从小的字符开始选取
 * 2.基于以上，应该先对原字符串排序
 * 3.用一个list存放最终的结果
 *
 * Create by Special on 2018/3/7 11:32
 */
public class Pro051 {
    static char[] origin;
    static boolean[] visited;
    static int length;
    static List<String> results;

    public static void dfs(int index, char[] chars){
        if(index == length){
            results.add(new String(chars));
            return;
        }
        for(int i = 0; i < length; i++){
            if(!visited[i]){
                visited[i] = true;
                chars[index] = origin[i];
                dfs(index + 1, chars);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            String str = input.nextLine();
            origin = str.toCharArray();
            Arrays.sort(origin);
            length = str.length();
            visited = new boolean[length];
            results = new ArrayList<>();
            dfs(0, new char[length]);
            for(String item : results){
                System.out.println(item);
            }
        }
    }
}

发表于 2018-03-07 14:28:30 回复(0)

认真做毕设的男孩子

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
void combine(string &s,string temp,vector<string> &result)
{
    if(temp.size()==s.size())
    {
        result.push_back(temp);
        return;
    }
    for(auto i:s)
    {
        auto flag=find(temp.begin(),temp.end(),i);
        if(flag==temp.end())
        {
            temp.push_back(i);
            combine(s,temp,result);
            temp.pop_back();
        }
    }
}

int main()
{
    string s;
    while(cin>>s)
    {
        vector<string> result;
        combine(s,"",result);
        sort(result.begin(),result.end());
        for(int i=0;i<result.size();i++)
            cout<<result[i]<<endl;
    }
    return 0;
}

发表于 2018-02-14 11:28:13 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     string s;     while(cin>>s)     {         sort(s.begin(), s.end());         do{             cout<<s<<endl;         }while(next_permutation(s.begin(),s.end()));     }     return 0;
}

发表于 2017-11-29 00:35:24 回复(0)

nineteen.

本题其实考察一个经典算法：全排列算法

同时最后的顺序是字典顺序（STL中对字符串排序默认就是字典顺序）

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

void permulation(int start, string& s, vector<string>& v) {
    if (start == s.length() - 1) {
        v.push_back(s);
    } else {
        for (int i = start; i < s.length(); i++) {
            swap(s[start], s[i]);
            permulation(start + 1, s, v);
            swap(s[start], s[i]);
        }
    }
}

int main(int argc, const char * argv[]) {
    string s;
    while (cin >> s) {
        vector<string> result;
        permulation(0, s, result);
        sort(result.begin(), result.end());
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << endl;
        }
    }
}

发表于 2017-09-08 13:52:55 回复(0)

i-i

每次递归在之前得到的结果后面增加一个字符，增加的顺序是按字典序，因此最终结果不需要排序

import java.util.*;

public class Main {
    static void findPermutation(Queue<String> queue, int n, char[] chars) {
        if (n == chars.length)
            return;
        int size = queue.size();
        while (size-- > 0) {
            String s = queue.poll();
            for (int i = 0; i < chars.length; i++) {
                if (s.indexOf(chars[i]) < 0) {
                    queue.add(s + chars[i]);
                }
            }
        }
        findPermutation(queue, n + 1, chars);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String string = scanner.nextLine();
            char[] chars = string.toCharArray();
            Arrays.sort(chars);
            Queue<String> queue = new LinkedList<>();
            queue.add(new String(new StringBuffer()));
            findPermutation(queue, 0, chars);
            while (!queue.isEmpty())
                System.out.println(queue.poll());
        }
    }
}

发表于 2017-09-05 19:28:06 回复(0)

tan313

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

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext())
		{
			List<String> list = new ArrayList<String>();
			String input = scanner.nextLine();
			char[] arr = input.toCharArray();
			for(int i=0;i<arr.length;i++)
			{
				list.add(String.valueOf(arr[i]));
			}
			Collections.sort(list);
			//排序
			sort(list, new ArrayList<String>(), list.size());
		}
		
	}
	
	private static void sort(List<String> datas, List<String> target, int nums) {   
        if (target.size() == nums) {   
           for (String str : target)   
                System.out.print(str);   
            System.out.println(); 
            return;   
        }   
        for (int i = 0; i < datas.size(); i++) {   
            List<String> newDatas = new ArrayList<String>(datas);   
            List<String> newTarget = new ArrayList<String>(target);   
            newTarget.add(newDatas.get(i));   
            newDatas.remove(i);   
            sort(newDatas, newTarget, nums);   
        }
    }
}

发表于 2016-05-27 22:53:04 回复(1)

C/C++

kakaan

// 偷懒解法，直接使用STL的next_permutation()
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    while (cin >> s)
    {
        sort(s.begin(), s.end());
        do{
            cout << s << endl;
        } while (next_permutation(s.begin(), s.end()));
    }
    return 0;
}

编辑于 2016-08-27 22:51:39 回复(0)

Python3

TS9527

全排列

class MainActivity:

    def main(self):
        # Read the data
        s = input()
        # Calculate
        results = self.__traverse(s)
        results.sort()
        for result in results:
            print(result)
    
    def __traverse(self, s):
        if len(s) == 1:
            return [s]
        results = set()
        for ptr, char in enumerate(s):
            tmpResults = self.__traverse(s[:ptr] + s[ptr + 1:])
            for result in tmpResults:
                results.add(char + result)
        return list(results)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-24 13:48:40 回复(0)

C++

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
int main()
{
string a;cin>>a;
sort(a.begin(),a.end());
do cout<<a<<endl;
while(next_permutation(a.begin(), a.end()));
}

发表于 2022-01-24 04:01:11 回复(0)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
void dfs(int cur,int n,string& tmp,string s,vector<int>& used,vector<string>& ans)
{
    if(cur==n)
    {
        ans.push_back(tmp);
        return;
    }
    for(int i=0;i<n;++i)
    {
        if(!used[i])
        {
            used[i] = 1;
            tmp.push_back(s[i]);
            dfs(cur+1,n,tmp,s,used,ans);
            used[i]=0;
            tmp.pop_back();
        }
    }
}
int main()
{
    // 递归回溯
    string s;
    while(cin>>s)
    {
        int n = s.size();
        vector<string>ans;
        string tmp;
        vector<int>used(n,0);
        dfs(0,n,tmp,s,used,ans);
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();++i)
            cout<<ans[i]<<endl;

    }
    return 0;
}

发表于 2020-04-17 23:44:13 回复(0)

Python

离疏

import itertools
s=input()
ans=[]
ans.extend(list(itertools.permutations(s,len(s))))#全排列
for i in range(len(ans)):#连接成字符串
    ans[i]=''.join(x for x in ans[i])
ans.sort()#排序
for x in ans:
    print(x)

发表于 2018-09-04 18:30:38 回复(0)

吾生有你

全排列题目

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            String str=input.next();
            TreeSet<String> tre=new TreeSet<>();
            allPiont(0 ,str.toCharArray(), tre);
            for(String elem: tre)
                System.out.println(elem);
        }
    }
    public static void allPiont(int start, char[] ch, TreeSet<String> tre){
        if(start==ch.length-1)
            tre.add(String.valueOf(ch));
        else{
            for(int i=start; i<ch.length; i++){
                swap(start, i, ch);
                allPiont(start+1, ch, tre);
                swap(i, start, ch);
            }
        }
    }
    public static void swap(int start, int i, char[] ch){
        char temp=ch[start];
        ch[start]=ch[i];
        ch[i]=temp;
    }
}

编辑于 2018-06-08 17:08:16 回复(0)

C/C++

NB响当当

一道经典全排列题目。由于C++的STL库加持，可以不用自己写底层代码直接调用库函数完成，在笔试中还是非常省时间的。参考代码如下：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(void)
{
    string str;
    while (cin >> str)
    {
        sort(str.begin(), str.end());
        do
        {
            cout << str << endl;
        } while (next_permutation(str.begin(), str.end()));
    }
    return 0;
}

发表于 2018-05-31 09:59:07 回复(0)