有一道华为上机题,求指导啊

J2EE 码拜 5年前 (2016-05-17) 514次浏览
有一个字符串,根据输入参数m,找出字符串的m个字符的全部字符串
例如
String str =”abc”, m=2  得到结果是 “ab” “ac” “bc”
String str =”abcd” , m=3 得到结果是”abc” “acd” “bcd” “abd”
求指导啊,谢谢
解决方案

20

/**
 * 分治思想
 * 
 * @param target
 * @param num
 * @return
 */
public static List<String> choose(String target, int num) {
	List<String> resultList = new LinkedList<>();
	if (num > target.length()) {
		return resultList;
	}
	if (num == target.length()) {
		resultList.add(target);
		return resultList;
	}
	// 将target均分(0 ~ bound - 1与bound ~ end)
	int bound = target.length() / 2;
	String left = target.substring(0, bound);
	String right = target.substring(bound, target.length());
	// 要选择的num个元素可能全部来自left
	resultList.addAll(choose(left, num));
	// 可能全部来自right
	resultList.addAll(choose(right, num));
	// 可能两边都有,这时对num做划分:num = l + r(l表示来自left的元素的个数,r表示来自right的元素的个数)
	for (int l = 1; l < num; l++) {
		int r = num - l;
		// 从left中挑选l个元素
		List<String> fromLeftList = choose(left, l);
		// 从right中挑选r个元素
		List<String> fromRightList = choose(right, r);
		// 组合起来
		for (String fromLeft : fromLeftList) {
			for (String fromRight : fromRightList) {
				// 添加到结果集里面
				resultList.add(fromLeft + fromRight);
			}
		}
	}
	return resultList;
}

20

字符串拆成单个字符的集合  然后是组合算法

package org.tianfang.dcball;
/*
 * 
 * 组合的形式,n个球放在m个位置
 * 
 */
public class Combination {
    /**
     * 子集个数
     */
    int selected = 1;
    /**
     * 总集合个数
     */
    int total = 1;
    /**
     * 记录组合状态的数组
     */
    int[] set = null;
    public Combination() {
        super();
    }
    public void init(int n, int m) {
        /*
         * 初始化组合,带参数
         */
        if (n >= m) {
            this.selected = m;
            this.total = n;
        } else {
            this.selected = n;
            this.total = m;
        }
        this.set = new int[this.total];
        for (int i = 0; i < this.total; i++) {
            if (i < this.selected) {
                set[i] = 1;
            } else {
                set[i] = 0;
            }
        }
    }
    public void init() {
        /*
         * 初始化组合
         */
        this.set = new int[this.total];
        for (int i = 0; i < this.total; i++) {
            if (i < this.selected) {
                set[i] = 1;
            } else {
                set[i] = 0;
            }
        }
    }
    public boolean next() {
        /*
         * 下一个组合,假如没有下一个返回false
         */
        int i = 0, j = 0, count = 0;
        for (i = 0; i < total - 1; i++) {
            if (this.set[i] == 1 && this.set[i + 1] == 0) {
                this.set[i] = 0;
                this.set[i + 1] = 1;
                for (j = 0; j < i; j++) {
                    if (this.set[j] == 1) {
                        count++;
                    }
                }
                for (j = 0; j < i; j++) {
                    if (j < count) {
                        this.set[j] = 1;
                    } else {
                        this.set[j] = 0;
                    }
                }
                return true;
            }
        }
        return false;
    }
    public int total() {
        /*
         * 组合的个数
         */
        int total = this.total;
        int select = this.selected;
        int result = 1;
        for (int i = 0; i < select; i++) {
            result *= (total - i);
        }
        for (int i = 2; i <= select; i++) {
            result /= i;
        }
        return result;
    }
    void todcball(Dcball dcb) {
        int count = 0, c = 0;
        // 组合转换为红球
        do {
            if (this.set[c] == 1) {
                dcb.reds[count] =(byte) (c + 1);
                count++;
            }
            c++;
        } while (count < 6);
    }
    public int[] firstInit() {
        int[] ret = { 1, 2, 3, 4, 5, 6 };
        int count = 0, c = 0;
        do {
            if (this.set[c] == 1) {
                ret[count] = c + 1;
                count++;
            }
            c++;
        } while (count < 6);
        return ret;
    }
    public static void main(String[] args) {
        test();
    }
    static void test() {
    	long begin=System.currentTimeMillis();
    
        Combination combination = new Combination();
        combination.init(6, 33);
        Dcball dcb = new Dcball();
        System.out.println("this Combination has " + combination.total() + " selection");
        do {
            combination.todcball(dcb);
            // dcb.blueball=1;
            dcb.calculateAll();
//            dcb.println();
        } while (combination.next());
        long end=System.currentTimeMillis();
        
        System.out.print("total time is "+(end-begin)+" ms");
    }
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明有一道华为上机题,求指导啊
喜欢 (0)
[1034331897@qq.com]
分享 (0)