得到新鲜甜甜圈的最多组数

1815. 得到新鲜甜甜圈的最多组数

有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前所有甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。

当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。

你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多有多少组人会感到开心。

示例 1：

输入：batchSize = 3, groups = [1,2,3,4,5,6]
输出：4
解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。

示例 2：

输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出：4

提示：

1 <= batchSize <= 9
1 <= groups.length <= 30
1 <= groups[i] <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxHappyGroups(int batchSize, vector<int>& groups) { } };

java 解法, 执行用时: 2 ms, 内存消耗: 39.9 MB, 提交时间: 2023-01-22 20:34:57

class Solution {
    private int m;
    private int[] val;
    private final Map<Integer, Integer> cache = new HashMap<>();

    public int maxHappyGroups(int batchSize, int[] groups) {
        m = batchSize;
        int ans = 0;
        int[] cnt = new int[m];
        for (int x : groups) {
            x %= m;
            if (x == 0) ++ans; // 直接排在最前面
            else if (cnt[m - x] > 0) {
                --cnt[m - x]; // 配对
                ++ans;
            } else ++cnt[x];
        }

        int mask = 0, n = 0;
        for (int c : cnt) if (c > 0) ++n;
        val = new int[n];
        for (int x = 1; x < m; ++x)
            if (cnt[x] > 0) {
                val[--n] = x; // val 越靠后的，在 mask 中的比特位越高
                mask = mask << 5 | cnt[x];
            }

        return ans + dfs(mask);
    }

    private int dfs(int mask) {
        if (cache.containsKey(mask)) return cache.get(mask);
        int res = 0, left = mask >> 20, msk = mask & ((1 << 20) - 1);
        for (int i = 0, j = 0; i < val.length; ++i, j += 5) // 枚举顾客
            if ((msk >> j & 31) > 0) // cnt[val[i]] > 0
                res = Math.max(res, (left == 0 ? 1 : 0) + dfs((left + val[i]) % m << 20 | msk - (1 << j)));
        cache.put(mask, res);
        return res;
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 15.6 MB, 提交时间: 2023-01-22 20:33:45

# Python 代码只添加优化的逻辑，位运算见其他语言
class Solution:
    def maxHappyGroups(self, m: int, groups: List[int]) -> int:
        ans = 0
        cnt = [0] * m
        for x in groups:
            x %= m
            if x == 0:
                ans += 1  # 直接排在最前面
            elif cnt[-x]:
                cnt[-x] -= 1  # 配对
                ans += 1
            else:
                cnt[x] += 1

        @cache  # 记忆化
        def dfs(left: int, cnt: Tuple[int]) -> int:
            res = 0
            cnt = list(cnt)
            for x, c in enumerate(cnt):  # 枚举顾客
                if c:  # cnt[x] > 0
                    cnt[x] -= 1
                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt)))  # x 从 0 开始，这里要 +1
                    cnt[x] += 1
            return res
        return ans + dfs(0, tuple(cnt[1:]))  # 转成 tuple 这样能记忆化

golang 解法, 执行用时: 4 ms, 内存消耗: 2.3 MB, 提交时间: 2023-01-22 14:26:35

func maxHappyGroups(m int, groups []int) (ans int) {
    cnt := make([]int, m)
    for _, x := range groups {
        x %= m
        if x == 0 {
            ans++ // 直接排在最前面
        } else if cnt[m-x] > 0 {
            cnt[m-x]-- // 配对
            ans++
        } else {
            cnt[x]++
        }
    }

    val, mask := []int{}, 0
    for x, c := range cnt {
        if c > 0 {
            val = append(val, x)
            mask = mask<<5 | c
        }
    }
    // 上面加入 val 的顺序和拼接 mask 的顺序是相反的，reverse 后就对上了
    for i, n := 0, len(val); i < n/2; i++ {
        val[i], val[n-1-i] = val[n-1-i], val[i]
    }

    // 直接用 pair 当作 key，更方便
    type pair struct{ left, mask int }
    cache := map[pair]int{}
    var dfs func(int, int) int
    dfs = func(left, mask int) (res int) {
        p := pair{left, mask}
        if v, ok := cache[p]; ok {
            return v
        }
        for i, x := range val { // 枚举顾客
            i *= 5
            if mask>>i&31 > 0 { // cnt[x] > 0
                r := dfs((left+x)%m, mask-1<<i)
                if left == 0 {
                    r++
                }
                res = max(res, r)
            }
        }
        cache[p] = res
        return
    }
    return ans + dfs(0, mask)
}

func max(a, b int) int { if b > a { return b }; return a }

上一题

下一题

详情