华为OD机试真题 Java 实现【分糖果】【2022Q2 200分】，附详细解题思路

在这里插入图片描述

一、题目描述

小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。

当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。

小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。

二、输入描述

抓取的糖果数（<10000000000）：

三、输出描述

最少分至一颗糖果的次数：

啥意思呢？

27+1=28
28/2=14
14/2=7
7+1=8
8/2=4
4/2=2
2/2=1

懂了？

四、解题思路

读取输入的糖果数量 sum；
调用递归函数 count(sum, 0)，传入糖果数量和初始操作次数 0；
在递归函数中，首先判断糖果数量是否小于等于 1，如果是，则返回当前的操作次数；
如果糖果数量是偶数，递归调用 count(sum/2, count + 1)，糖果数量除以 2，操作次数加一；
如果糖果数量是奇数，递归调用 Math.min(count(sum + 1, count + 1), count(sum - 1, count + 1))，分别对糖果数量加一和减一进行递归调用，取操作次数较少的结果；
返回最终的操作次数。

五、Java算法源码

public static void main(String[] args) throws Exception {
    Scanner scanner = new Scanner(System.in);
    long sum = scanner.nextLong();
    System.out.println(count(sum, 0));
}

private static int count(long sum, int count){
    if(sum <= 1){
        return count;
    }
    if(sum%2==0){
        return count(sum/2, count + 1);
    }
    return Math.min(count(sum + 1, count + 1), count(sum - 1,count + 1));
}