欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

华为面试:给定一个只包含大写英文字母的字符串S,进行排列组合

程序员文章站 2024-03-18 10:34:10
...
import java.util.HashSet;

public class Arrange { 
 public static void main(String[] args) { 
  char[] chs = {'A','B','A'}; 
  HashSet<String> set  = new  HashSet<String>();
  arrange(chs, 0, chs.length,set); 
  System.out.print(set);

 } 

	public static void arrange(char[] chs, int start, int len, HashSet<String> set) {
		if (start == len - 1) {
			String aString = "";
			for (int i = 0; i < chs.length; ++i){
				aString =aString +String.valueOf(chs[i]);
			}
			set.add(aString);
			System.out.println();
			return;
		}

		for (int i = start; i < len; i++) {
			char temp = chs[start];
			chs[start] = chs[i];
			chs[i] = temp;
			arrange(chs, start + 1, len, set);
			temp = chs[start];
			chs[start] = chs[i];
			chs[i] = temp;
		}
	}
} 

华为面试:给定一个只包含大写英文字母的字符串S,进行排列组合

全排列:还是abc三个字符,全排列即字符不能重复。最后 3*2 =6种结果

可以利用1中的方法,只要判断3个字符是否相等,都不相等的才是需要的全排列里的一个。这样的时间复杂度为n^n,而全排列的种类为n!所以需要设计一种n!的算法。

也可以利用递归,第一个字符串一共有n种选择,剩下的变成一个n-1规模的递归问题。而第一个字符的n种选择,都是字符串里面的。因此可以使用第一个字符与1-n的位置上进行交换,得到n中情况,然后递归处理n-1的规模,只是处理完之后需要在换回来,变成原来字符的样子。

 

 

相关标签: java面试宝典