Skip to content

Latest commit

 

History

History
134 lines (104 loc) · 3.72 KB

028-字符串的排列.md

File metadata and controls

134 lines (104 loc) · 3.72 KB
Raw

面试题28 字符串的排列

题目：

输入一个字符串，打印出该字符串中字符的所有排列。 例如输入字符串 abc，则打印出 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

package algorithm.foroffer.top30;

/**
 * Created by liyazhou on 2017/5/29.
 * 面试题28：字符串的排列 
 *
 * 题目：
 *      输入一个字符串，打印出该字符串中字符的所有排列。
 *      例如输入字符串 abc，则打印出 a、b、c 所能排列出来的所有字符串
 *      abc、acb、bac、bca、cab 和 cba。
 *
 * 问题：
 *      1. 递归求解
 *
 * 思路：
 *      1. 把字符串分为两部分，一部分是字符串的第一个字符，另一部分是第一个字符以后的所有字符
 *         求第二部分字符串的排列
 *      2. 第一个字符和它后面的字符交换位置
 *
 *
 */
public class Test28 {

    public static void permutation(char[] chars){
        if (chars == null) return;
        permutation(chars, 0);
    }

    private static void permutation(char[] chars, int start) {
        if (start == chars.length) {
            System.out.println(chars);
        }

        for (int idx = start; idx < chars.length; idx++){
            char tmp = chars[idx];
            chars[idx] = chars[start];
            chars[start] = tmp;

            permutation(chars, start+1);

            tmp = chars[idx];
            chars[idx] = chars[start];
            chars[start] = tmp;
        }
    }


    public static void main(String[] args){
        String str = "abc";
        char[] chars = str.toCharArray();
        permutation(chars);
    }

}

集合的所有子集

思路

类似位操作。思路:假设集合有4个元素{a,b,c,d}，那么做一个for循环从0到15，每次输出一个子集。0(0000)表示空子集，1(0001)因为最低位为1，所以在集合四个元素中取第一个元素{a}作为一个子集，2(0010)因为次低位为1，所以在集合四个元素中取第二个元素{b}作为一个子集，3(0011)因为最低位和次低位都为1，所以在集合四个元素中取第一、第二个元素{a,b}作为一个子集......，依次类推15(1111)表示{a,b,c,d}。再举个详细例子： 假设有集合{a,b,c}，则：迭代0到2^n-1==0到7 0(000)：{} 1(001)：{a} 2(010)：{b} 3(011)：{ab} 4(100)：{c} 5(101)：{a,c} 6(110)：{b,c} 7(111)：{a,b,c}

程序

import java.util.HashSet;
import java.util.Set;

public class SubSet {

	public static void main(String[] args) {
		int[] set = new int[]{1,2};
		Set<Set<Integer>> result = getSubSet(set);	//调用方法
		
		//输出结果
		for(Set<Integer> subSet: result){
			for(Integer num: subSet)
				System.out.print(num);
			
			System.out.println("");
		}
	}
	
	public static Set<Set<Integer>> getSubSet(int[] set){
		Set<Set<Integer>> result = new HashSet<Set<Integer>>();	//用来存放子集的集合，如{{},{1},{2},{1,2}}
		int length = set.length;
		int num = length==0 ? 0 : 1<<(length);	//2的n次方，若集合set为空，num为0；若集合set有4个元素，那么num为16.
		
		//从0到2^n-1（[00...00]到[11...11]）
		for(int i = 0; i < num; i++){		
			Set<Integer> subSet = new HashSet<Integer>();
			
			int index = i;
			for(int j = 0; j < length; j++){
				if((index & 1) == 1){		//每次判断index最低位是否为1，为1则把集合set的第j个元素放到子集中
					subSet.add(set[j]);
				}
				index >>= 1;		//右移一位
			}
			
			result.add(subSet);		//把子集存储起来
		}
		return result;
	}

}

作者：zo chen 链接：https://www.zhihu.com/question/29985661/answer/46501393 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。