【贪心算法】（第八篇）

目录

分发饼⼲（easy）

题目解析

讲解算法原理

编写代码

最优除法（medium）

题目解析

讲解算法原理

编写代码

分发饼⼲（easy）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

假设你是⼀位很棒的家⻓，想要给你的孩⼦们⼀些⼩饼⼲。但是，每个孩⼦最多只能给⼀块饼⼲。对每个孩⼦ i ，都有⼀个胃⼝值 g[i] (，)这是能让孩⼦们满⾜胃⼝的饼⼲的最⼩尺⼨；并且每块
饼⼲ j ，都有⼀个尺⼨ s[j] ()。如果 s[j] >= g[i] ，我们可以将这个饼⼲ j 分配给孩⼦
i ，这个孩⼦会得到满⾜。你的⽬标是尽可能满⾜越多数量的孩⼦，并输出这个最⼤数值。
⽰例1:
输⼊:g=[1,2,3],s=[1,1]
输出:1
解释:
你有三个孩⼦和两块⼩饼⼲，3个孩⼦的胃⼝值分别是：1,2,3。虽然你有两块⼩饼⼲，由于他们的尺⼨都是1，你只能让胃⼝值是1的孩⼦满⾜。所以你应该输出1。
⽰例2:
输⼊:g=[1,2],s=[1,2,3]
输出:2
解释:
你有两个孩⼦和三块⼩饼⼲，2个孩⼦的胃⼝值分别是1,2。你拥有的饼⼲数量和尺⼨都⾜以让所有孩⼦满⾜。
所以你应该输出2.

提⽰：
◦ 1 <= g.length <= 3 * 10(4)
◦ 0 <= s.length <= 3 * 10(4)
◦ 1 <= g[i], s[j] <= 2(31) - 1

讲解算法原理

解法（贪⼼）：
（既然是很棒的家⻓，为什么不多买⼀些饼⼲呢）

贪⼼策略：
先将两个数组排序。
针对胃⼝较⼩的孩⼦，从⼩到⼤挑选饼⼲：
i. 如果当前饼⼲能满⾜，直接喂（最⼩的饼⼲都能满⾜，不要浪费⼤饼⼲）；ii. 如果当前饼⼲不能满⾜，放弃这个饼⼲，去检测下⼀个饼⼲（这个饼⼲连最⼩胃⼝的孩⼦都
⽆法满⾜，更别提那些胃⼝⼤的孩⼦了）。

编写代码

c++算法代码：

class Solution
{
public:
 int findContentChildren(vector<int>& g, vector<int>& s) 
 {
 // 先排序
 sort(g.begin(), g.end());
 sort(s.begin(), s.end());
 // 利⽤双指针找答案
 int ret = 0, n = s.size();
 for(int i = 0, j = 0; i < g.size() && j < n; i++, j++)
 {
 while(j < n && s[j] < g[i]) j++; // 找饼⼲
 if(j < n) ret++;
 }
 return ret;
 }
};

java算法代码：

class Solution
{
 public int findContentChildren(int[] g, int[] s) 
 {
 // 排序
 Arrays.sort(g);
 Arrays.sort(s);
 // 利⽤双指针找答案
 int ret = 0, m = g.length, n = s.length;
 for(int i = 0, j = 0; i < m && j < n; i++, j++)
 {
 while(j < n && s[j] < g[i]) j++; // 找饼⼲
 if(j < n) ret++;
 }
 return ret;
 }
}

最优除法（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀正整数数组 nums ， nums 中的相邻整数将进⾏浮点除法。例如，[2,3,4]->2/3/4。• 例如， nums = [2,3,4] ，我们将求表达式的值 "2/3/4" 。
但是，你可以在任意位置添加任意数⽬的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最⼤值。
以字符串格式返回具有最⼤值的对应表达式。
注意：你的表达式不应该包含多余的括号。

⽰例1：
输⼊:[1000,100,10,2]
输出:"1000/(100/10/2)"
解释:1000/(100/10/2)=1000/((100/10)/2)=200
但是，以下加粗的括号"1000/((100/10)/2)"是冗余的，
因为他们并不影响操作的优先级，所以你需要返回"1000/(100/10/2)"。
其他⽤例:
1000/(100/10)/2=50
1000/(100/(10/2))=50
1000/100/10/2=0.5
1000/100/(10/2)=2

⽰例2:
输⼊:nums=[2,3,4]
输出:"2/(3/4)"
解释:(2/(3/4))=8/3=2.667
可以看出，在尝试了所有的可能性之后，我们⽆法得到⼀个结果⼤于2.667的表达式。
说明:
◦ 1 <= nums.length <= 10
◦ 2 <= nums[i] <= 1000
◦ 对于给定的输⼊只有⼀种最优除法。

讲解算法原理

解法（贪⼼）：
贪⼼策略：
在最终的结果中，前两个数的位置是⽆法改变的。
因为每⼀个数的都是⼤于等于 2 的，为了让结果更⼤，我们应该尽可能的把剩下的数全都放在「分⼦」上。

编写代码

c++算法代码：

class Solution
{
public:
 string optimalDivision(vector<int>& nums) 
 {
 int n = nums.size();
 // 先处理两个边界情况
 if(n == 1)
 {
 return to_string(nums[0]);
 }
 if(n == 2)
 {
 return to_string(nums[0]) + "/" + to_string(nums[1]);
 }
 string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
 for(int i = 2; i < n; i++)
 {
 ret += "/" + to_string(nums[i]);
 }
 ret += ")";
 return ret;
 }
};

java算法代码：

class Solution
{
 public String optimalDivision(int[] nums) 
 {
 int n = nums.length;
 StringBuffer ret = new StringBuffer();
 // 先处理两个边界情况
 if(n == 1)
 {
 return ret.append(nums[0]).toString();
 }
 if(n == 2)
 {
 return ret.append(nums[0]).append("/").append(nums[1]).toString();
 }
 ret.append(nums[0]).append("/(").append(nums[1]);
 for(int i = 2; i < n; i++)
 {
 ret.append("/").append(nums[i]);
 }
 ret.append(")");
 return ret.toString();
 }
}