seo是什么东西_天津建设工程信息网登录不了_广告投放网站平台_百度竞价渠道代理

LeetCode2305

目录

• 题目描述
• 示例
• 思路分析
• 代码段
• 代码逐行讲解
• 复杂度分析
• 总结的知识点
• 整合
• 总结

---

题目描述

给定一个整数数组 cookies，其中 cookies[i] 表示第 i 个孩子的饼干数量。你需要将这些饼干分配给 k 个孩子，使得每个孩子至少获得一块饼干，并且所有孩子获得的饼干数量的最大值最小化。

返回这个最大值的最小值。

---

示例

示例 1

输入:

cookies = [8, 15, 10, 20], k = 2

输出:

31

解释:

• 一种最优分配方式是：
  • 第一个孩子获得 [8, 15, 10]，总和为 33。
  • 第二个孩子获得 [20]，总和为 20。
• 最大值为 33，但这不是最优解。
• 另一种最优分配方式是：
  • 第一个孩子获得 [8, 20]，总和为 28。
  • 第二个孩子获得 [15, 10]，总和为 25。
• 最大值为 28，这是更优的解。

---

示例 2

输入:

cookies = [5, 8, 6, 10], k = 3

输出:

10

解释:

• 一种最优分配方式是：
  • 第一个孩子获得 [5, 5]，总和为 10。
  • 第二个孩子获得 [8]，总和为 8。
  • 第三个孩子获得 [6]，总和为 6。
• 最大值为 10。

---

思路分析

问题核心

我们需要将饼干分配给 k 个孩子，使得每个孩子至少获得一块饼干，并且所有孩子获得的饼干数量的最大值最小化。

思路拆解

1. 回溯算法：
   • 使用回溯算法尝试所有可能的分配方式。
2. 剪枝：
   • 如果当前分配方式的最大值已经大于已知的最小值，则跳过。
3. 递归终止条件：
   • 如果所有饼干都已分配，则更新最小值。
4. 分配饼干：
   • 对于每块饼干，尝试将其分配给每个孩子，并递归处理下一块饼干。

---

代码段

class Solution {int ans = Integer.MAX_VALUE;public int distributeCookies(int[] cookies, int k) {int[] dp = new int[k];func(cookies, dp, k, 0, 0);return ans;}private void func(int[] cookies, int[] dp, int k, int i, int max) {if (i == cookies.length) {ans = Math.min(ans, max);return;}for (int j = 0; j < k; j++) {if (j > 0 && dp[j] == dp[j - 1]) {continue;}dp[j] += cookies[i];func(cookies, dp, k, i + 1, Math.max(max, dp[j]));dp[j] -= cookies[i];}}
}

---

代码逐行讲解

1. 初始化最小值：

   • ans 用于存储当前的最小最大值，初始值为 Integer.MAX_VALUE。

2. 主函数：

   • 初始化一个数组 dp，用于记录每个孩子获得的饼干数量。
   • 调用递归函数 func，开始回溯。

3. 递归终止条件：

   • 如果所有饼干都已分配，则更新 ans 为当前最大值和 ans 的较小值。

4. 剪枝：

   • 如果当前孩子与前一个孩子获得的饼干数量相同，则跳过，避免重复计算。

5. 分配饼干：

   • 将当前饼干分配给当前孩子，并递归处理下一块饼干。

6. 回溯：

   • 撤销当前饼干的分配，尝试其他分配方式。

---

复杂度分析

时间复杂度

• 最坏情况下需要尝试所有可能的分配方式，时间复杂度为 O(k^n)，其中 n 是饼干的数量。

空间复杂度

• 递归栈的深度为 n，因此空间复杂度为 O(n)。

---

总结的知识点

1. 回溯算法：

   • 使用回溯算法尝试所有可能的分配方式。

2. 剪枝：

   • 通过跳过重复的分配方式，减少不必要的计算。

3. 递归：

   • 使用递归处理每块饼干的分配。

4. 最小值更新：

   • 在递归终止时更新最小值。

---

整合

class Solution {int ans = Integer.MAX_VALUE;public int distributeCookies(int[] cookies, int k) {int[] dp = new int[k];func(cookies, dp, k, 0, 0);return ans;}private void func(int[] cookies, int[] dp, int k, int i, int max) {if (i == cookies.length) {ans = Math.min(ans, max);return;}for (int j = 0; j < k; j++) {if (j > 0 && dp[j] == dp[j - 1]) {continue;}dp[j] += cookies[i];func(cookies, dp, k, i + 1, Math.max(max, dp[j]));dp[j] -= cookies[i];}}
}

---

总结

通过回溯算法和剪枝，能够高效地找到将饼干分配给 k 个孩子的最小最大值。