写在前面

国科大计算机算法分析与设计中贪心算法部分，主要是一些作业题。这些题目也是贪心算法方面比较经典的题目。贪心算法在经典算法里说简单简单，因为你看到那个算法之后，好像不需要怎么想就能明白，不像动态规划算法还需要理解。但是说难也难，因为这好像是很灵性的一种算法，动态规划算法还算有迹可循，多步决策，但是这个贪心好像蛮不讲理，想到了就是想到了，没想到就不知道怎么想到了。
听老师说，国外教材中动态规划是在贪心之前讲的，因为贪心就是那么不讲理，解释一个算法不难，但是解释怎么想到这个算法比较难。可能需要知识积累和沉淀吧。

作业1：填坑问题

The given string S is represented by “x” and “.”, “x” represents a pit, “.” represents a normal road. The cost of filling k consecutive pits is k+1, please obtain the maximum normal road ( It can be non-continuous. ) with budget M.
Input: S = “xxx…xxxx…xxxxx”, M = 11
Output: 16
解释：可以填中间4个×，需要5座桥，再填最后5个×，需要6座桥，正好11座桥，而形成的通路就是4+5，再加上已经有的3+4，总数就是16。
解答：x/(x+1)是一个递增函数，因此优先选择长的“x”串。

def fix(S, M):res = 0S = [len(s) for s in S.split(‘.’)]S.sort(reserve=True)for s in S:if M>s+1:res += sreturn res

时间复杂度O(nlogn)，空间复杂度O(1)。

作业2：重新排列数字

解答：任意2个数字x和y，如果拼起来”xy”比“yx”要小就将x放在y前面；否则将y放在x前面。

sort(nums.begin(), nums.end(), [](const int &x, const int &y) {int xy = stoi(to_string(x) + to_string(y));int yx = stoi(to_string(y) + to_string(x));return xy < yx;
});
string ret = "";
for (auto i: nums)ret += to_string(i);
return ret;

时间复杂度：排序算法的时间复杂度，O(nlogn)

作业3：会议室时间

There are n meetings, and the start time and end time of i-th meeting are si and ei. Please design a greedy algorithm to find the minimum number of meeting rooms required to arrange all meetings.
Input: [ [0, 20], [15, 20], [20, 23], [25, 30], [15, 25] ]
Output: 3
解答：对于每一个会议，它的结束时间是要大于开始时间的，假设从开始时间遍历到第k个会议，也就是到了begin_time[k]begin\_time[k]begin_time[k],那么在上一次遍历时，因为有while的循环，end_timeend\_timeend_time到了begin_time[k−1]begin\_time[k-1]begin_time[k−1]，这是由end_timeend\_timeend_time的指针endroomendroomendroom保证的，那么在这次循环中就只会找begin_time[k−1]begin\_time[k-1]begin_time[k−1]到begin_time[k]begin\_time[k]begin_time[k]这一时间段结束的会议，那么每结束一个会议（因为每个会议的结束时间会大于开始时间，所以在这个时间段结束的会议，之前已经开始了，已经申请会议室了），该会议所在的会议室就会空闲，也就是freeroom会加1，因为每次遍历都是新开一个会议，所以需要一个新的会议室，如果有空闲会议室，就会申请空闲会议室，freeroom减1，没有空闲会议室，就会申请新的会议室room加1。这样遍历之后，所有会议的开始时间和结束时间都过了一遍，保证了该算法的完备性和正确性。

作业4：删除数字得到最大数

N is a non-negative integer, remove k digits from it to obtain a new number. Find the biggest
possible output number.
Input: N= 147128, k = 3
Output: 728
解答：删除k个数字后，保证剩下的数字最大，就需要我们从前往后删除k个最靠前的最小的数字，也就是希望尽可能留下来的数字近似“单调递减”，因此可以用单调栈来解决。具体来说，维护一个栈，按照从左向右的顺序逐个将数组元素push进栈中，当发现“新添加元素 > 栈顶元素”的时候，就将栈之前的元素pop出来，直至“新添加元素 < 栈顶元素”或者“删除总元素数达到k”为止。当遍历数组结束，留在栈中的元素就是最终我们要的结果。

string num = to_string(N)
vector stk;
for (char c: num) {while (!stk.empty() && stk.back() < c && k) {stk.pop_back();k--;}stk.push_back(c);
}
// 如果遇到某一段已经为单调递减，则之前pop掉的数字不足k
while (k--) {stk.pop_back();
}
string ret = "";
bool isLeadingZero = true;
for (int i = 0; i < stk.size(); i++) {if (isLeadingZero && stk[i] == '0')continue;isLeadingZero = false;ret += string(1, stk[i]);
}
return ret == "" ? "0": ret;

作业5：跳跃的最远位置

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return “yes“ if you can reach the last index, or “no“ otherwise.
Input: nums = [2,3,1,1,4]
Output: “yes”
解答：遍历每个元素，记录可以到达的最远位置，如果本次可以到达更远，则更新最远位置。

class Solution: def canJump(self, nums: List[int]) -> bool: n, rightmost = len(nums), 0 for i in range(n): if i <= rightmost: rightmost = max(rightmost, i + nums[i]) if rightmost >= n - 1: return “yes“ return “no“ 

根据定义可以知道，在第k个位置的时候，k+nums[k]k+nums[k]k+nums[k]就代表了最远能够跳到的位置。k和k+nums[k]k+nums[k]k+nums[k]之间的位置都能达到。因此可以维护一个全局最大值max_mmax\_mmax_m，初始值为0，代表第0个位置可达。那么就计算0+nums[0]0+nums[0]0+nums[0]，如果大于max_mmax\_mmax_m，就更新max_mmax\_mmax_m。因为nums数组里是有序的，因此可以从第0个位置开始往后计算max_mmax\_mmax_m，如果到第k个位置，发现k>max_mk>max\_mk>max_m，代表前k-1个位置都到达不了k，因为max_mmax\_mmax_m代表的是最远跳跃的位置，自然k+1，k+2，…，n-1的位置也到达不了。最终只需要比较max_mmax\_mmax_m和n-1的大小，如果大于n-1，则说明最远可以跳到n-1后面的位置，自然也能跳到n-1位置。因为是从前往后依次遍历的，这个算法是正确完备的。

作业6：交换两个数字使交换之后整个数最大

There is a number k and you can swap two digits at most once.
Please design a greedy algorithm to find the maximum value you can get.
Input: k = 39748
Output: 93748

解答：假设交换j,k位 (0≤j

作业7：划分k个子集使子集的差最大

Given an array of integers nums, divide them to k subsets, find a division scheme to maximize the
sum of the ranges (极差) (i.e., max - min) of all subsets.
Input: nums=[1, 2, 3, 4, 5], k = 3
Output: 6 (Optimal division scheme: {1, 5}, {2, 4}, {3}, sum of ranges: 4 + 2 + 0 = 6)
解答：为了获得最大极差的分组，应当让尽量小的数字和尽量大的数字分在一组，因此先将数组排序，然后从两端开始各选取1个元素组成一组，直到组数达到k加上剩下的元素数 = 组数的时候停止。

int dis = 0;
sort(nums.begin(), nums.end());
deque dq(nums.begin(), nums.end());
for (int i = k; i > 0; i--) {if (dq.size() > i) {int x1 = dq.pop_front();int x2 = dq.pop_back();dis += (x2 - x1);} else break;
}
return dis;

参考：贪心算法答疑ppt