957 2018-12-20 2020-06-25

前言：记CVTE一道算法题。

一、题目描述

大概是这么个意思：给定几个不重复的随机数和一个正整数，求出所有和为目标数的随机数集合，数可以重复使用。例如[2, 3, 6] 6，那么2 2 2， 3 3， 6都是所求集合。

二、我的思路

一开始我是这么想的：首先要排序，然后可以去掉一些大于目标数的值。然后就可以使用动态规划 + 回溯法来求解了。但笔试的时候由于时间关系，没有做出来，考完后也是花了一天才做出来的，索性笔试迷迷糊糊过了，开心。

这题有点像剑指Offer第27题，求abc的全排列，怎么说呢，还是上代码吧。

三、我的代码

package site.xiaokui.common.hk.offer;

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

/**
 * CVTE算法题，大概是这么个意思：给定几个不重复的随机数和一个正整数，求出所有和为目标数的随机数集合，数可以重复使用
 * 例如[2,3] 6，那么2 2 2， 3 3， 6都是所求集合
 *
 * @author HK
 * @date 2018-12-20 11:45
 */
public class Cvte {

    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    /**
     * 假设给定1,2,3,4,5,6,7 6。那么结果应为
     * 6
     * 15  24  33
     * 114  123  222
     * 1113  1122
     * 11112
     * 111111
     */
    public List<List<Integer>> find(int[] sets, int target) {
        if (sets.length == 0 || target <= 0) {
            return lists;
        }
        // 排序
        Arrays.sort(sets);
        int newLength = 0;
        // 去掉不必要的值
        for (int i = sets.length - 1; i >= 0; i--) {
            if (sets[i] <= target) {
                newLength = i;
                break;
            }
        }
        // 开始递归求解
        find(0, newLength, sets, target);
        // 对子列表排序
        for (List<Integer> l : lists) {
            Collections.sort(l);
        }
        // 标记需要清除的项
        boolean[] delIndex = new boolean[lists.size()];
        for (int i = 0; i < lists.size() - 1; i++) {
            for (int j = i + 1; j < lists.size(); j++) {
                if (lists.get(i).size() == lists.get(j).size()) {
                    int size = lists.get(i).size();
                    boolean isSame = lists.get(i).get(0).equals(lists.get(j).get(0))
                            && lists.get(i).get(size - 1).equals(lists.get(j).get(size - 1));
                    if (isSame) {
                        delIndex[j] = true;
                    }
                }
            }
        }
        // 清除重复项
        int delCount = 0;
        for (int i = 0; i < delIndex.length; i++) {
            if (delIndex[i]) {
                lists.remove(i - delCount);
                delCount++;
            }
        }
        return lists;
    }

    private void find(int start, int end, int[] sets, int target) {
        // 当前temp已经满足
        if (target == 0) {
            lists.add(new ArrayList<>(temp));
            System.out.println("添加记录temp" + temp);
            return;
        }
        // 不合法验证
        if (start > end || target < 0 || sets[start] > target) {
            return;
        }
        System.out.println("在" + start + "和" + end + "之间寻找" + target + ",当前temp" + temp);
        // 找到目标
        if (sets[start] == target) {
            temp.add(sets[start]);
            System.out.println("在" + start + "和" + end + "之间发现" + target + "，添加记录" + temp);
            lists.add(new ArrayList<>(temp));
            temp.remove(temp.size() - 1);
            return;
        }
        // 关键代码，自己走一遍理解更佳
        for (int i = 0; i <= end; i++) {
            temp.add(sets[i]);
            System.out.println("-此时参数i=" + i + ",target=" + target + ",目标数为" + (target - sets[i]) + "," + "temp为" + temp);
            find(i, end, sets, target - sets[i]);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] sets = new int[]{1, 2, 3, 4, 5, 6, 7};
        Cvte cvte = new Cvte();
        cvte.find(sets, 6);
        System.out.println(cvte.lists);

        sets = new int[] {2, 3, 6};
        cvte = new Cvte();
        cvte.find(sets, 6);
        System.out.println(cvte.lists);
    }
}

这里难点是如何选择递归，我是这么做的：

1. 以数据[2，3，6] 6为例。
2. 首先对每个数递归，递归的target = target - 当前数，即问题分解为求4、3、0。
3. 对于4递归（2入temp在前），于是问题分解成求2、1、-2。对于2递归（2入temp在前），找到第一个数2，此时又把2入temp，添加记录temp[2, 2, 2]。其他递归以空返回结束。
4. 清除temp原有数据。
5. 对于3递归（3入temp在前），其他省略....

四、总结

感觉这题出的很奇妙，虽然做出来之后感觉好简单，但是初次看到还是感觉有点难度的。稍稍总结一下吧，如下

1. 对于开始排序、去掉较大值，感觉是常规操作。
2. 首先是对递归方法参数的确定，一个好的参数能省不少力；其次是对于结束条件的判断，这点也至关重要；最后就是递归的条件及add、remove操作的使用了。
3. 最后就是去重了，这里就不多说了。

写博客记录一下，算是一番炫技了，哈哈。我会常来的，手动笑脸。

总访问次数: 373次, 一般般帅 创建于 2018-12-20, 最后更新于 2020-06-25