题解 | #牛群分组II#

牛群分组II

https://www.nowcoder.com/practice/9ebc32fee9b54bfa9f9c3deca80febb0

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    public static LinkedList<LinkedList<Integer>> lists = new LinkedList<>();
    public int[][] cowCombinationSum2 (int[] candidates, int target) {
       // write code here
        Boolean[] flags = new Boolean[candidates.length];
        Arrays.fill(flags,false);
        search(candidates,target,0,flags,new LinkedList<>());
        int[][] arr = new int[lists.size()][];
        for(int i=0;i<arr.length;i++){
            arr[i] = new int[lists.get(i).size()];
            for(int j=0;j<lists.get(i).size();j++){
                arr[i][j] = lists.get(i).get(j);
            }
        }
        return arr;
    }

    public void search(int[] nums,int target,int cur,Boolean[] flags,LinkedList<Integer> arrayList){
        if(cur==target){
            lists.add(new LinkedList<>(arrayList));
            return;
        }
        for(int i=0;i<flags.length;i++){
            if(!flags[i]){
                if(arrayList.size()!=0 && nums[i]<arrayList.get(arrayList.size()-1)){
                    continue;
                }
                arrayList.add(nums[i]);
                flags[i]=true;
                search(nums,target,cur+nums[i],flags,arrayList);
                arrayList.remove(arrayList.size()-1);
                flags[i] = false;
            }
        }
    }

}

本题考察的知识点主要N叉树的建立,所用编程语言为java.本题建立N叉树之后,需要考虑剪枝条件,不然含有重复的组合。重复的组合比如是(2,3,5),(3,5,2),(5,3,2),但是我们只能选择第一个,其余两个与第一个重复不应该算在满足条件的组合中。剪枝时我们考虑满足条件的组合,第一个元素如果比第二个元素大时,我们应该结束继续递归,进行剪枝。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 14:45
bg是二本双一流硕,目标是Java后端开发岗,投暑期实习0大厂面试,只有极少的大厂测开,可能投的晚加上简历太烂加上0实习?求大佬们给个建议
程序员小白条:别去小厂,初创或者外包,尽量去中小,100-499和500-999,专门做互联网产品的,有公司自研的平台和封装的工具等等,去学习一些业务相关的,比如抽奖,积分兑换,SSO认证,风控,零售等等,目标 Java 后端开发吗?你要不考虑直接走大厂测开?如果技术不行的话,有面试你也很难过的
实习,不懂就问
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务