【 数据结构 & 算法 】—— 贪心算法
2020-10-21 本文已影响0人
Du1in9
< 思维导图 >
预备知识：钞票支付问题（贪心法）
- 预备知识_钞票支付.cpp
#include <stdio.h>
int main(){
const int RMB[] = {100, 50, 20, 10, 5, 2, 1};
const int NUM = 7;
int X = 628;
int count = 0;
// 面值从大到小遍历
for (int i = 0; i < NUM; i++){
int use = X / RMB[i];
count += use;
X = X - RMB[i] * use;
printf("需要面额为 %d 的 %d 张, ", RMB[i], use);
printf("还需要支付 RMB %d.\n", X);
}
printf("总共需要 %d 张 RMB\n", count);
return 0;
}
分糖果（排序、贪心）（★）
- LeetCode 455.Assign Cookies.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
class Solution {
public:
// 需求因子数组 g，糖果大小数组 s
int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
// 对数组 g 排序
std::sort(g.begin(), g.end());
// 对数组 s 排序
std::sort(s.begin(), s.end());
int child = 0; // 满足孩子的个数
int cookie = 0; // 尝试糖果的个数
// 若两数组均未尝试完
while(child < g.size() && cookie < s.size()){
// 若糖果满足孩子，指针 child 后移
if (g[child] <= s[cookie]){
child++;
}
// 糖果只尝试一次，指针 cookie 后移
cookie++;
}
// 返回满足的孩子个数
return child;
}
};
int main(){
Solution solve;
std::vector<int> g;
std::vector<int> s;
g.push_back(5);
g.push_back(10);
g.push_back(2);
g.push_back(9);
g.push_back(15);
g.push_back(9);
s.push_back(6);
s.push_back(1);
s.push_back(20);
s.push_back(3);
s.push_back(8);
printf("需求因子：");
for(int i=0; i<g.size(); i++){
printf("%d ", g[i]);
}
printf("\n糖果大小：");
for(int j=0; j<s.size(); j++){
printf("%d ", s[j]);
}
printf("\n最多能满足孩子个数：%d\n", solve.findContentChildren(g, s));
return 0;
}
摇摆序列（贪心）（★★）
- LeetCode 376.Wiggle Subsequence.cpp
#include <stdio.h>
#include <vector>
class Solution {
public:
int wiggleMaxLength(std::vector<int>& nums) {
// 序列个数小于 2 时，直接为摇摆序列
if (nums.size() < 2){
return nums.size();
}
// 描述序列的三种状态
static const int BEGIN = 0;
static const int UP = 1;
static const int DOWN = 2;
int STATE = BEGIN;
// 序列个数至少为 1
int max_length = 1;
for (int i = 1; i < nums.size(); i++){
switch(STATE){
case BEGIN:
// 初始化状态
if (nums[i-1] < nums[i]){
STATE = UP;
max_length++;
}
// 初始化状态
else if (nums[i-1] > nums[i]){
STATE = DOWN;
max_length++;
}
break;
case UP:
// 若状态切换，max_length++ ，否则不变
if (nums[i-1] > nums[i]){
STATE = DOWN;
max_length++;
}
break;
case DOWN:
// 若状态切换，max_length++ ，否则不变
if (nums[i-1] < nums[i]){
STATE = UP;
max_length++;
}
break;
}
}
// 返回最长摇摆序列个数
return max_length;
}
};
int main(){
std::vector<int> nums;
nums.push_back(1);
nums.push_back(17);
nums.push_back(5);
nums.push_back(10);
nums.push_back(13);
nums.push_back(15);
nums.push_back(10);
nums.push_back(5);
nums.push_back(16);
nums.push_back(8);
printf("原序列：");
for (int i = 1; i < nums.size(); i++){
printf("%d, ", nums[i]);
}
Solution solve;
printf("\n最长摇摆序列个数：%d\n", solve.wiggleMaxLength(nums));
return 0;
}
移除 K 个数字（栈、贪心）（★★）
- LeetCode 402.Remove K Digits.cpp
#include <stdio.h>
#include <string>
#include <vector>
class Solution {
public:
std::string removeKdigits(std::string num, int k) {
// 使用 vector 当作栈
std::vector<int> S;
// 存储结果的字符串 result
std::string result = "";
// 从高位开始遍历 num
for (int i = 0; i < num.length(); i++){
// 将字符串转为整型
int number = num[i] - '0';
// 当栈不为空，栈顶数字大于 number，还可移除数字时
while(S.size() != 0 && S[S.size()-1] > number && k > 0){
// 弹出栈顶数字
S.pop_back();
k--;
}
// 栈顶数字变为 number
if (number != 0 || S.size() != 0){
S.push_back(number);
}
}
// 当遍历到末尾，还可移除数字时
while(S.size() != 0 && k > 0){
// 弹出栈顶数字
S.pop_back();
k--;
}
// 遍历栈中整型数字
for (int i = 0; i < S.size(); i++){
// 存储至字符串 result
result.append(1, '0' + S[i]);
}
return result;
}
};ING
int main(){
Solution solve;
std::string result = solve.removeKdigits("1432219", 3);
printf("num = 1432219, k = 3，");
printf("移除 k 个数字后最小为：%s\n", result.c_str());
std::string result2 = solve.removeKdigits("100200", 1);
printf("num = 100200, k = 1，");
printf("移除 k 个数字后最小为：%s\n", result2.c_str());
return 0;
}
跳跃游戏（贪心）（★★）
- LeetCode 55.Jump Game.cpp
#include <stdio.h>
#include <vector>
class Solution {
public:
bool canJump(std::vector<int>& nums) {
// 最远可跳至的位置
std::vector<int> index;
// 计算 index 数组
for (int i = 0; i < nums.size(); i++){
index.push_back(i + nums[i]);
}
// 初始化 jump
int jump = 0;
// 初始化 max_index
int max_index = index[0];
// 若满足条件，继续 jump ，同时更新 max_index
while(jump < nums.size() && jump <= max_index){
if (max_index < index[jump]){
max_index = index[jump];
}
jump++;
}
// 若 jump 到了最后，返回成功
if (jump == nums.size()){
return true;
}
// 若 jump 没到最后，返回失败
return false;
}
};
int main(){
std::vector<int> nums;
nums.push_back(2);
nums.push_back(3);
nums.push_back(1);
nums.push_back(1);
nums.push_back(4);
Solution solve;
for (int i = 0; i < nums.size(); i++){
printf("%d ", nums[i]);
}
if (solve.canJump(nums)){
printf("\n可以跳到最后");
}
else{
printf("\n不可以跳到最后");
}
return 0;
}
跳跃游戏2（贪心）（★★★）
- LeetCode 45.Jump Game II.cpp
#include <stdio.h>
#include <vector>
class Solution {
public:
int jump(std::vector<int>& nums) {
// 当前位置可到达的最远位置
int current_max_index = nums[0];
// 遍历各个位置可到达的最远位置
int pre_max_max_index = nums[0];
// 最小跳跃次数
int jump_min = 1;
for (int i = 1; i < nums.size(); i++){
// 如果无法再向前移动，就跳跃
if (i > current_max_index){
// 更新跳跃次数
jump_min++;
// 更新当前可到达的最远位置
current_max_index = pre_max_max_index;
}
if ( nums[i] + i > pre_max_max_index){
pre_max_max_index = nums[i] + i;
}
}
return jump_min;
}
};
int main(){
std::vector<int> nums;
nums.push_back(2);
nums.push_back(3);
nums.push_back(1);
nums.push_back(1);
nums.push_back(4);
Solution solve;
printf("最少跳跃次数：%d\n", solve.jump(nums));
return 0;
}
射击气球（排序、贪心）（★★）
- LeetCode 452.Minimum Number of Arrows to Burst Balloons.cpp
#include <stdio.h>
#include <algorithm>
#include <vector>
// 比较左端点大小
bool cmp(const std::pair<int, int> &a, const std::pair<int ,int> &b) {
return a.first < b.first;
}
class Solution {
public:
int findMinArrowShots(std::vector< std::pair<int,int> > & points) {
// 对气球按照左端点从小到大排序
std::sort(points.begin(), points.end(), cmp);
// 初始化弓箭手为 1
int shoot_num = 1;
// 初始化射击区间为第一个气球区间
int shoot_begin = points[0].first;
int shoot_end = points[0].second;
// 按照左端点从小到大遍历气球
for (int i = 1; i < points.size(); i++){
// 若气球区间左端点 <= 射击区间右端点，即有交集
if (points[i].first <= shoot_end){
// 更新射击区间左端点
shoot_begin = points[i].first;
// 若气球区间右端点 <= 射击区间右端点
if (points[i].second <= shoot_end){
// 更新射击区间右端点
shoot_end = points[i].second;
}
}
// 若气球区间左端点 > 射击区间右端点，即无交集
else{
// 增加弓箭手
shoot_num++;
// 更新射击区间
shoot_begin = points[i].first;
shoot_end = points[i].second;
}
}
return shoot_num;
}
};
int main(){
std::vector< std::pair<int,int> > points;
// 随机输入各个气球区间
points.push_back(std::make_pair(10, 16));
points.push_back(std::make_pair(2, 8));
points.push_back(std::make_pair(1, 6));
points.push_back(std::make_pair(7, 12));
Solution solve;
printf("至少需要弓箭手：%d\n", solve.findMinArrowShots(points));
return 0;
}
最优加油法（堆、贪心）（★★★）
- poj2431 Expedition.cpp
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
// 根据 d 从大到小排序
bool cmp(const std::pair<int, int> &a, const std::pair<int ,int> &b) {
return a.first > b.first;
}
// L 为起点距终点距离，P 为起点汽油量
int get_minimum_stop(int L, int P, std::vector< std::pair<int,int> > & stop){
// Q 为存储油量的最大堆
std::priority_queue<int> Q;
// result 为加油次数
int result = 0;
// 将终点 (0,0) 作为停靠点输入
stop.push_back(std::make_pair(0, 0));
// 以停靠点至终点距离从大到小排序
std::sort(stop.begin(), stop.end(), cmp);
// 遍历各个停靠点
for (int i = 0; i < stop.size(); i++){
// d 为到下一站距离，d(这一站) = L(这一站) - d(下一站)
int d = L - stop[i].first;
// 若当前汽油量到不了下一站
while (!Q.empty() && P < d){
// 更新加油次数
result++;
// 更新当前油量
P += Q.top();
// 更新存储油量的最大堆
Q.pop();
}
// 若当前汽油量到得了下一站
if (Q.empty() && P < d){
return -1;
}
// 更新当前汽油量
P = P - d;
// 更新距终点距离 d，即 stop[i].first
L = stop[i].first;
// 更新堆里油量 fuel, 即 stop[i].second
Q.push(stop[i].second);
}
return result;
}
int main(){
// 存储各个站距终点距离，各个站汽油量的堆 stop
std::vector<std::pair<int, int> > stop;
int N, L, P, d, fuel;
printf(" 请输入加油站数量 (起点不算)：\n");
scanf("%d", &N);
printf(" 请输入各个站距终点距离，各个站汽油量：\n");
for (int i = 0; i < N; i++){
scanf("%d %d", &d, &fuel);
stop.push_back(std::make_pair(d, fuel));
}
printf("请输入起点距终点距离，起点汽油量：\n");
scanf("%d %d", &L, &P);
printf("从起点到终点最少加油次数：%d", get_minimum_stop(L, P, stop));
return 0;
}
