【算法】六一·给小朋友们分糖果

Quibbler 1月前 130

【算法】六一·给小朋友们分糖果


        每日一题,今天六一,LeetCode今天出的题很有意思。

给你两个正整数 n 和 limit 。请你将 n 颗糖果分给 3 位小朋友,确保没有任何小朋友得到超过 limit 颗糖果,请你返回满足此条件下的 总方案数 。


示例 1:输入:n = 5, limit = 2输出:3解释:总共有 3 种方法分配 5 颗糖果,且每位小朋友的糖果数不超过 2 :(1, 2, 2) ,(2, 1, 2) 和 (2, 2, 1) 。

示例 2:输入:n = 3, limit = 3输出:10解释:总共有 10 种方法分配 3 颗糖果,且每位小朋友的糖果数不超过 3 :(0, 0, 3) ,(0, 1, 2) ,(0, 2, 1) ,(0, 3, 0) ,(1, 0, 2) ,(1, 1, 1) ,(1, 2, 0) ,(2, 0, 1) ,(2, 1, 0) 和 (3, 0, 0) 。


         小技巧,LeetCode上绝大多数题目可以无脑暴力解决,留意一下这题的输入限制1 <= n <= 50和1 <= limit <= 50。先暴力完成任务,拿到今天的积分:

    class Solution {
        public int distributeCandies(int n, int limit) {
           int count = 0;
           for (int a = 0; a <= n && a <= limit; ++a) {
               for (int b = 0; b <= n - a && b <= limit; ++b) {
                   if (n - a - b <= limit) {
                       ++count;
                   }
               }
           }
           return count;
       }
    }

         解题不是最终目的,暴力解决这题就没有意义了,有个巧妙的方法:枚举中间小朋友获得的糖果数量,O(1)计算左右两边的方案数:

    class Solution {
        public int distributeCandies(int n, int limit) {
            int ans = 0;
            int hi = Math.min(limit, n);
            for (int mid = 0; mid <= hi; mid++) {
                int m = n - mid, l = Math.max(0, m - hi), r = Math.min(hi, m);
                ans += Math.max(r - l + 1, 0);
            }
            return ans;
        }
    }


不忘初心的阿甘
最新回复 (0)
    • 安卓笔记本
      2
        登录 注册 QQ
返回
仅供学习交流,切勿用于商业用途。如有错误欢迎指出:fluent0418@gmail.com