黑马程序员技术交流社区

标题: 一道华为上机题 [打印本页]

---

作者: ciying88    时间: 2017-3-15 21:35
标题: 一道华为上机题
有一个字符串，根据输入参数m，找出字符串的m个字符的所有字符串

String str ="abc", m=2  得到结果是 "ab" "ac" "bc"
String str ="abcd" , m=3 得到结果是"abc" "acd" "bcd" "abd"





code:

/**
* 分治思想
*
* @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;
}

---

作者: a469517790    时间: 2017-3-15 21:52
这递归调用的。。。。。

---

作者: 明明凯凯归归    时间: 2017-3-15 23:53
很好,学习了

---

作者: 豆子先生    时间: 2017-3-16 00:34
收藏了，学到后面再看

---

作者: 陈大仙…    时间: 2017-3-16 08:23
这题不错哦

---

作者: lvshen9    时间: 2017-3-16 08:27
可以用数学的排列组合

---

作者: lvshen9    时间: 2017-3-16 08:29
就是字符串长度的阶乘除以m的阶乘

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2