There is a donuts shop that bakes donuts in batches of batchSize. They have a rule where they must serve all of the donuts of a batch before serving any donuts of the next batch. You are given an integer batchSize and an integer array groups, where groups[i] denotes that there is a group of groups[i] customers that will visit the shop. Each customer will get exactly one donut.
When a group visits the shop, all customers of the group must be served before serving any of the following groups. A group will be happy if they all get fresh donuts. That is, the first customer of the group does not receive a donut that was left over from the previous group.
You can freely rearrange the ordering of the groups. Return the maximum possible number of happy groups after rearranging the groups.
Example 1:
Input: batchSize = 3, groups = [1,2,3,4,5,6] Output: 4 Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1st, 2nd, 4th, and 6th groups will be happy.
Example 2:
Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6] Output: 4
Constraints:
1 <= batchSize <= 91 <= groups.length <= 301 <= groups[i] <= 109
Solution 0: Binary Mask DP
Time complexity: O(n*2n) TLE
Space complexity: O(2n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, TLE, 42/67 Passed class Solution { public: int maxHappyGroups(int b, vector<int>& groups) { const int n = groups.size(); vector<int> dp(1 << n); for (int mask = 0; mask < 1 << n; ++mask) { int s = 0; for (int i = 0; i < n; ++i) if (mask & (1 << i)) s = (s + groups[i]) % b; for (int i = 0; i < n; ++i) if (!(mask & (1 << i))) dp[mask | (1 << i)] = max(dp[mask | (1 << i)], dp[mask] + (s == 0)); } return dp[(1 << n) - 1]; } }; |
Solution 1: Recursion w/ Memoization
State: count of group size % batchSize
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 888 ms, 61.9 MB class Solution { public: int maxHappyGroups(int b, vector<int>& groups) { int ans = 0; vector<int> count(b); for (int g : groups) ++count[g % b]; map<vector<int>, int> cache; function<int(int)> dp = [&](int s) { auto it = cache.find(count); if (it != cache.end()) return it->second; int ans = 0; for (int i = 1; i < b; ++i) { if (!count[i]) continue; --count[i]; ans = max(ans, (s == 0) + dp((s + i) % b)); ++count[i]; } return cache[count] = ans; }; return count[0] + dp(0); } }; |
C++/Hashtable
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Author: Huahua 380 ms, 59.2 MB struct VectorHasher { size_t operator()(const vector<int>& V) const { size_t hash = V.size(); for (auto i : V) hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2); return hash; } }; class Solution { public: int maxHappyGroups(int b, vector<int>& groups) { int ans = 0; vector<int> count(b); for (int g : groups) ++count[g % b]; unordered_map<vector<int>, int, VectorHasher> cache; function<int(int)> dp = [&](int s) { auto it = cache.find(count); if (it != cache.end()) return it->second; int ans = 0; for (int i = 1; i < b; ++i) { if (!count[i]) continue; --count[i]; ans = max(ans, (s == 0) + dp((s + b - i) % b)); ++count[i]; } return cache[count] = ans; }; return count[0] + dp(0); } }; |
C++/OPT
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua, 0 ms, 8.1 MB class Solution { public: int maxHappyGroups(int b, vector<int>& groups) { int ans = 0; vector<int> count(b); for (int g : groups) { const int r = g % b; if (r == 0) { ++ans; continue; } if (count[b - r]) { --count[b - r]; ++ans; } else { ++count[r]; } } map<vector<int>, int> cache; function<int(int, int)> dp = [&](int r, int n) { if (n == 0) return 0; auto it = cache.find(count); if (it != cache.end()) return it->second; int ans = 0; for (int i = 1; i < b; ++i) { if (!count[i]) continue; --count[i]; ans = max(ans, (r == 0) + dp((r + b - i) % b, n - 1)); ++count[i]; } return cache[count] = ans; }; const int n = accumulate(begin(count), end(count), 0); return ans + (n ? dp(0, n) : 0); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment