首页 > 华为8.19笔试第二题java的思路,求指点
头像
Fenxian
编辑于 2020-08-22 15:37
+ 关注

华为8.19笔试第二题java的思路,求指点

看了题以后试了下java,求大佬指点。
除了各种边界的检查之外,大致思路是:
1.当前深度d可以摆放的node的最大值由上层node数量*2得到
2.当前深度数量为n的node的可摆放的种类可以简化为:n个苹果放入m个盘子里,每个盘子只能最多放一个苹果
3.把每层的可以摆放node的可能性相乘得到最后结果
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int nodeSize = n;
        // save <depth, number of nodes at its depth> to map
        Map<Integer, Integer> map = new HashMap<>();
        int maxDepth = Integer.MIN_VALUE;
        int mod = 1000000007;
        while (nodeSize-- != 0) {
            int node = sc.nextInt();
            maxDepth = Math.max(maxDepth, node);
            if (map.containsKey(node)) {
                map.put(node, map.get(node) + 1);
            } else {
                map.put(node, 1);
            }
        }
        if (!map.containsKey(0) || map.get(0) != 1) {
            System.out.println("0");
            return;
        }
        int d = 1;
        int result = 1;
        while (map.containsKey(d)) {
            int curr = map.get(d);
            int last = map.get(d - 1) * 2;
            if (curr > last) {
                System.out.println("0");
                return;
            }
            result = (result*combination(curr,last))%mod;
            d++;
        }
        System.out.println(result);
    }
    // m apple put into n plate, each plate can have max 1 apple
    private static int combination(int curr, int last) {
        if(curr == last || curr==0)
            return 1;
        return combination(curr-1,last-1) + combination(curr,last-1);
    }
}


全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐