极客算法

LeetCode-1742.盒子中小球的最大数量(Maximum Number of Balls in a Box)

2021-02-06

1742. 盒子中小球的最大数量

你在一家生产小球的玩具厂工作,有 n 个小球,编号从 lowLimit 开始,到 highLimit 结束(包括 lowLimit 和 highLimit ,即 n == highLimit - lowLimit + 1)。另有无限数量的盒子,编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中,其中盒子的编号应当等于小球编号上每位数字的和。例如,编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子,而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ,返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球,只需返回其中任一盒子的小球数量。

示例 1:

输入:lowLimit = 1, highLimit = 10
输出:2
解释:
盒子编号:1 2 3 4 5 6 7 8 9 10 11 ...
小球数量:2 1 1 1 1 1 1 1 1 0  0  ...
编号 1 的盒子放有最多小球,小球数量为 2 。

示例 2:

输入:lowLimit = 5, highLimit = 15
输出:2
解释:
盒子编号:1 2 3 4 5 6 7 8 9 10 11 ...
小球数量:1 1 1 1 2 2 1 1 1 0  0  ...
编号 5 和 6 的盒子放有最多小球,每个盒子中的小球数量都是 2 。

示例 3:

输入:lowLimit = 19, highLimit = 28
输出:2
解释:
盒子编号:1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量:0 1 1 1 1 1 1 1 1 2  0  0  ...
编号 10 的盒子放有最多小球,小球数量为 2 。

提示:

1 <= lowLimit <= highLimit <= 10^5

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/maximum-number-of-balls-in-a-box

Link:https://leetcode.com/problems/maximum-number-of-balls-in-a-box/

暴力破解

把球的各个数位(10进制)加起来,放入到对应的盒子中, 例如编号365 = 3 + 6 + 5 = 14, 也就是将365号球放入到14盒子中

from collections import Counter
class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        
        counter = Counter()
        for num in range(lowLimit, highLimit + 1):
            
            box = 0
            while num > 0:
                box += num % 10
                num = num // 10
                
            counter[box] += 1
            
        return max(counter.values())

动态规划

记忆化计算

在暴力计算过程中,还是有很多重复计算的,并且一个数字可以拆解左边 + 右边的和, 而且可以把子树的结果保存起来,达到去掉重复计算的目的

     365
     / \
   36   5
  / \
 3   6

然鹅,这个时间复杂度更高了

from functools import lru_cache
class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        
        counter = [0 for i in range(46)]
        for num in range(lowLimit, highLimit + 1):
            
            box = self.boxNumber(num)                
            counter[box] += 1
            
        return max(counter)
    
    @lru_cache(maxsize=None)
    def boxNumber(self, num: int) -> int:
        if 0 <= num <= 9:
            return num
        
        # 计算位数
        tmp = num
        digits = 0
        while tmp > 0:
            tmp = tmp // 10
            digits += 1
            
        zeros = 10 ** (digits >> 1)
        # 分成左右两部分
        left_num = num // zeros
        right_num = num - left_num * zeros
        
        return self.boxNumber(left_num) + self.boxNumber(right_num)

另一种思路, 是把一个数的末尾单独拆出来,2365 = 236 + 5

      2365
      /  \
    236   5
    / \
  23   6
 / \
2   3

缓存命中率明显提高了, 但依旧没有暴力破解快

from functools import lru_cache
class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        
        counter = [0 for i in range(46)]
        for num in range(lowLimit, highLimit + 1):
            
            box = self.boxNumber(num)                
            counter[box] += 1
            
        return max(counter)
    
    @lru_cache(maxsize=None)
    def boxNumber(self, num: int) -> int:
        if 0 <= num <= 9:
            return num
                 
        zeros = 10 
        # 分成左右两部分
        left_num = num // zeros
        right_num = num - left_num * zeros
        
        return self.boxNumber(left_num) + right_num

递推公式

O(N)

数字的范围 1 ~ 9999 + 1, 所以一共45盒子就足够了

一个数只要在上一个基础上+1,就可以了。但有些特殊的数字例外

9 到 10 可以看出盒子的编号减少了8 即 + 1 - 9,
99 到 100 可以看出盒子的编号减少了17 即 + 1 - 9 * 2,
999 到 1000 可以看出盒子的编号减少了26 即 + 1 - 9 * 3

代码如下

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        
        counter = [0 for i in range(46)]
        pre = 0
        
        # 计算第一个
        tmp = lowLimit
        while tmp > 0:
            pre += 1
            tmp = tmp // 10
        
        counter[pre] = 1
        
        for num in range(lowLimit + 1, highLimit + 1):

            tmp = num
            zeros = 0
            while tmp % 10 == 0:
                zeros += 1
                tmp = tmp // 10
                
            cur = pre + 1 - 9 * zeros
            
            counter[cur] += 1
            pre = cur
            
        return max(counter)

–End–


相关推荐

评论

内容: