leetcode_1742盒子中小球的最大数量

1. 题意

给定一个数字范围，把每个数根据数位和放到相应的盒子中；求有最多数字的盒子编号。

2. 题解

这题比较简单，但有较多的解法。

2.1 哈希表

由于最大数为 100000 100000 100000，因此最大的数位和为 45 45 45。我们只需要开一个大小 46 46 46的更加方便，然后遍历这个范围，计算数位和，相应表项增加，最后求一个最大值就好了。

class Solution { public: int countBalls(int lowLimit, int highLimit) { auto digitSum = [](int v) { int ans = 0; while (v) { ans += v % 10; v /= 10; } return ans; }; vector<int> hs(46, 0); for (int i = lowLimit;i <= highLimit;i++) { hs[digitSum(i)]++; } return *max_element(hs.begin(), hs.end()); } }; 2.2 前缀和

数据范围为 1 − 100000 1-100000 1−100000，可以预处理出前 k k k个数每个数位和的状态，对于范围 [ a , b ] [a,b] [a,b]的 数位和就可以由 m e m [ b ] − m e m [ a − 1 ] mem[b] -mem[a-1] mem[b]−mem[a−1]得到。

class Solution { public: int countBalls(int lowLimit, int highLimit) { array<array<int,46>, 100001> mem{}; auto digitSum = [](int v) { int ans = 0; while (v) { ans += v % 10; v /= 10; } return ans; }; for (int i = 1;i <= 100000;i++) { mem[i] = mem[i - 1]; mem[i][digitSum(i)]++; } int ans = 0; for (int i = 1; i <= 45;i++) { ans = max(ans, mem[highLimit][i] - mem[lowLimit - 1][i]); } return ans; } }; 2.3 数位dp

数位dp入门见数位dp。

这个题目的状态转移方程为 m = ⌊ lg ⁡ n ⌋ a m = ⌊ n / ( 1 0 m ) ⌋ d p [ m ] [ k ] = ∑ i = 0 min ⁡ { a m − 1 , k } d p [ 1 0 m − 1 ] [ k − i ] + d p [ m − a m 1 0 m ] [ k − a m ] m =\lfloor \lg n \rfloor \\ a_m =\lfloor n /(10^{m}) \rfloor \\ dp[m][k]=\sum_{i=0}^{\min\{a_{m}-1,k\}}dp[10^{m-1}][k-i]+dp[m-a_m10^{m}][k-a_{m}] m=⌊lgn⌋am​=⌊n/(10m)⌋dp[m][k]=i=0∑min{am​−1,k}​dp[10m−1][k−i]+dp[m−am​10m][k−am​]

我们可以预先求出 d p [ 1 0 d − 1 ] [ k ] dp[10^{d}-1][k] dp[10d−1][k]

令 d p [ 1 0 d − 1 ] = T [ d ] dp[10^d-1]=T[d] dp[10d−1]=T[d]

T [ d ] [ k ] = ∑ i = 0 min ⁡ { k , 9 } T [ d − 1 ] [ k − i ] T[d][k] = \sum_{i=0}^{\min \{k, 9\}}T[d-1][k-i] T[d][k]=i=0∑min{k,9}​T[d−1][k−i]

下面是递归的代码，看之后能不能补一下递推的。

class Solution { public: static constexpr int MAXPOW = 5; static constexpr int BASE = 10; static constexpr int MAXSUM = MAXPOW * (BASE - 1); int getRes(int v, int k, const std::array<std::array<int, MAXSUM + 1>, MAXPOW + 1> &dp) { if ( v < 10) { return v >= k ? 1 : 0; } int ans = 0; int digitMost = 1; int ts = BASE; while (ts <= v) { ts *= BASE; digitMost++; } digitMost--; int msb = v / (ts / BASE); int lm = std::min(msb - 1, k) ; for (int i = 0;i <= lm; i++) ans += dp[digitMost][k - i]; int ret = 0; if (msb <= k) { ret += getRes(v - msb * (ts / BASE), k - msb, dp); } return ans + ret; } int countBalls(int lowLimit, int highLimit) { std::array<std::array<int,MAXSUM + 1>, MAXPOW + 1> dp{}; for (int i = 0; i < BASE; i++) dp[1][i] = 1; for (int i = 2;i <= MAXPOW; i++) { for (int j = 0; j <= MAXSUM; ++j) { int bd = std::min(BASE - 1, j); for (int k = 0; k <= bd; ++k) { dp[i][j] += dp[i - 1][j - k]; } } } int ans = 0; for (int i = 1; i <= MAXSUM;i++) { int nums = getRes(highLimit, i, dp) - getRes(lowLimit - 1, i, dp); ans = std::max(ans, getRes(highLimit, i, dp) - getRes(lowLimit - 1, i, dp)); } return ans; } }; Ref

03xf