腾讯笔试第五题花匠小q

import java.util.HashMap;
import java.util.Scanner;

public class Main32 {
    private static HashMap<Integer, Long> map = new HashMap<>();

    private static long modNumber = (long) 1e9 + 7;

    public static void main(String[] args){
        System.out.println(modNumber);
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        int k = scanner.nextInt();

        for (int i = 0; i < t; i++){
            int ai = scanner.nextInt();
            int bi = scanner.nextInt();

            System.out.println(numberOfPlan(k, ai, bi));
        }
        scanner.close();
    }

    public static long numberOfPlan(int k, int ai, int bi){
        long count = 0;
        for (int i = ai; i <= bi; i++){
            if (map.get(i) != null){
                count = (count + map.get(i)) % modNumber;
            }
            else {
                long tempNumber = numberOfPlanOfFixFlowerNumber1(k, i);
                map.put(i, tempNumber);
                count = (count + tempNumber) % modNumber ;
                System.out.println(map);
            }
        }
        return count % modNumber;
    }

    public static long numberOfPlanOfFixFlowerNumber(int k, int numberOfFlowers){
        if (numberOfFlowers < 1){
            return 1;
        }
        if (map.get(numberOfFlowers) != null){
            return map.get(numberOfFlowers);
        }
        int numberOfSerialWhiteFlowerNumber = (numberOfFlowers / k + 1);
        //System.out.println(numberOfSerialWhiteFlowerNumber + "  flowerNumber: " + numberOfFlowers);
        long count = 0;
        for (int i = 0; i < numberOfSerialWhiteFlowerNumber; i++){
            int numberOfWhite = k * i;
            //放k*i朵白花和1朵红花
            long tempNumber = numberOfPlanOfFixFlowerNumber(k, numberOfFlowers - numberOfWhite - 1);
            map.put(numberOfFlowers - numberOfWhite - 1, tempNumber);
            count = (count + tempNumber) % modNumber;
        }

        return count;
    }

    public static long numberOfPlanOfFixFlowerNumber1(int k, int numberOfFlowers){
        if (numberOfFlowers == 0){
            return 1;
        }
        if (numberOfFlowers < 0){
            return 0;
        }
        if (map.get(numberOfFlowers) != null){
            return map.get(numberOfFlowers);
        }
        long count = 0, tempNumber;
        //System.out.println(numberOfSerialWhiteFlowerNumber + "  flowerNumber: " + numberOfFlowers);
        //放1朵红花
        tempNumber = numberOfPlanOfFixFlowerNumber1(k, numberOfFlowers - 1);
        map.put(numberOfFlowers - 1, tempNumber);
        count = (count + tempNumber) % modNumber;

        //放k朵白花
        tempNumber = numberOfPlanOfFixFlowerNumber1(k, numberOfFlowers - k);
        map.put(numberOfFlowers - k, tempNumber);
        count = (count + tempNumber) % modNumber;

        return count;
    }
}

考试时提交用的numberOfPlanOfFixFlowerNumber()函数，考试结束才想到numberOfPlanOfFixFlowerNumber1()，但两者输出应该是一样的

k = 2时的map如下，map的key表示一共放key朵花，value表示有value种放法

不知道哪里错了，通过率为0，提示"请检查是否存在数组越界等非法访问情况"，实在想不到什么输入情况下会数组越界

腾讯笔试第五题 花匠小q

全站热榜

腾讯笔试第五题花匠小q