20240312-2-贪心算法

贪心算法

是每次只考虑当前最优，目标证明每次是考虑当前最优能够达到局部最优，这就是贪心的思想，一般情况下贪心和排序一起出现，都是先根据条件进行排序，之后基于贪心策略得到最优结果。
面试的时候面试官一般不会出贪心算法，如果可能贪心一般都可以使用动态规划解决，面试官很喜欢出动态规划的题目。

1. 最大连续子序列

题目: 给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
扩展1: 给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
扩展2: 给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
分析: 使用这个s表示当前可能满足的最大和，如果s>0,我们认为s对接下来的加操作有帮助，基于s+=nums[i]，if s < 0, 认为s只会对后面造成负影响，两s=nums[i]。
扩展问题: 可以将 数组从每个位置k分开，分别结算[1,i]和[i+1, n)的最值，记录的过程中可以使用数组保存下来的已经计算好的值。

int maxSubArray(vector<int> &nums) {
    int s = 0, ans = -1000000;
    for(int i = 0; i < nums.size(); i ++) {
        if(s > 0) s += nums[i];
        else s = nums[i];
        ans = max(s, ans);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9

2. 删除数字

题目: 给定一个以字符串表示的非负整数，从该数字中移除掉k个数位，让剩余数位组成的数字尽可能小，求可能的最小结果。
分析: 从左到右遍历字符串，找到第一个不满足递增的数字删除，一定会保证当前操作之后剩下的数字最小。

string removeKdigits(string &num, int k) {
    int i;
    while(k --) {
        for(i = 0; i < num.size() - 1 && num[i] <= num[i+1]; i ++);
        num.erase(num.begin() + i);
    }
    // remove 0
    auto it = num.begin();
    while(it != num.end() && *it == '0') {
        num.erase(it);
        it = num.begin();
    }
    if(num.size() == 0) num = "0";
    return num;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 无重叠区间

题目: 给定一些区间，找到需要移除的最小区间数，以使其余的区间不重叠。
分析: 贪心一般伴随着排序一起出现，我们根据区间的结束使用升序排序，之后进行遍历，如果发现不满足条件，则移除这个不满足的区间。

classs Interval {
    int start, end;
    Interval(int start, int end) {
        this->start = start;
        this->end = end;
    }
}
bool cmp(Interval a, Interval b) {
    if(a.end < b.end) return 1;
    else return 0;
}     
int eraseOverlapIntervals(vector<Interval> &intervals) {
    sort(intervals.begin(), intervals.end(), cmp);    
    int cnt = 0;
    Interval tmp = intervals[0];
    for(int i = 1; i < intervals.size(); i ++) {
        if(tmp.end <= intervals[i].start) tmp = intervals[i];
        else {
            cnt ++;
        }
    }
    return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 合并数字

题目: 给出n个数，现在要将这n个数合并成一个数，每次只能选择两个数a,b合并，每次合并需要消耗a+b的能量，输出将这n个数合并成一个数后消耗的最小能量。
分析: 参考哈夫曼树的构造，每一次合并两个最小的数，直到剩下一个数字，因为每次要选择两个最小的，需要用到最小堆来实现，可以使用C++SLT中的优先队列.
根据这个题目，请大家自行补上哈夫曼树。

int mergeNumber(vector<int> &numbers) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 0; i < numbers.size(); i ++) {
        pq.push(numbers[i]);
    }
    int cost = 0;
    while(pq.size() > 1) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        cost += (a + b);
        pq.push(a + b);
    }
    return cost;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5. 最小支撑树

题目: 使用kruskal算法，构造最小支撑树。
分析: 详见百度百科或者wikipedia.
代码: kruskal code

struct Edge { 
    int src, dest, weight; 
}; 
struct Graph { 
    int V, E;   
    struct Edge* edge; 
}; 
struct Graph* createGraph(int V, int E) { 
    struct Graph* graph = new Graph; 
    graph->V = V; 
    graph->E = E;   
    graph->edge = new Edge[E]; 
    return graph; 
} 
struct subset { 
    int parent; 
    int rank; 
}; 
int find(struct subset subsets[], int i) { 
    if (subsets[i].parent != i) 
        subsets[i].parent = find(subsets, subsets[i].parent); 
    return subsets[i].parent; 
} 
void Union(struct subset subsets[], int x, int y) { 
    int xroot = find(subsets, x); 
    int yroot = find(subsets, y);   
    if (subsets[xroot].rank < subsets[yroot].rank) 
        subsets[xroot].parent = yroot; 
    else if (subsets[xroot].rank > subsets[yroot].rank) 
        subsets[yroot].parent = xroot;   
    else { 
        subsets[yroot].parent = xroot; 
        subsets[xroot].rank++; 
    } 
} 
int myComp(const void* a, const void* b) { 
    struct Edge* a1 = (struct Edge*)a; 
    struct Edge* b1 = (struct Edge*)b; 
    return a1->weight > b1->weight; 
} 
void KruskalMST(struct Graph* graph) { 
    int V = graph->V; 
    struct Edge result[V];  
    int e = 0; 
    int i = 0; 
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);   
    struct subset *subsets = 
        (struct subset*) malloc( V * sizeof(struct subset) ); 
    for (int v = 0; v < V; ++v) { 
        subsets[v].parent = v; 
        subsets[v].rank = 0; 
    }   
    while (e < V - 1) { 
        struct Edge next_edge = graph->edge[i++];   
        int x = find(subsets, next_edge.src); 
        int y = find(subsets, next_edge.dest);   
        if (x != y) { 
            result[e++] = next_edge; 
            Union(subsets, x, y); 
        } 
    }   
    return; 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

6. 补齐数组

题目: 给出一个正整数数组nums和一个整数n，向数组添加patch元素，使得范围[1, n]包含的任何数字都可以由数组中某些元素的总和形成。返回所需的最少补齐数。
分析：

1. 升序排序，
2. 使用r表示目前可以表示的右边界，如果当前值 > r, 超出范围，又因为 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示，那么只需要有n/2以及 [1, n/2] 区间内任何数字都可以用 nums 中某几个数字的和来表示即可。所有我们将r扩大一倍，继续判断是否满足。
3. 直到 r >= n。

int minPatches(vector<int> &nums, int n) {
    sort(nums.begin(), nums.end());
    long long r = 1;
    int i = 0;
    int cnt = 0;
    while(r <= n) {
        if(i < nums.size() && nums[i] <= r) r += nums[i++];
        else {
            cnt ++;
            r *= 2;
        }
    }
    return cnt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7. 买卖股票的最佳时机

题目: 假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
分析: 先低价买入，再高价卖出，因此从前向后，记录最小值并且更新最有结果，

int maxProfit(vector<int> &prices) {
    int minp = prices[0];
    int ans = 0;
    for(int i = 1; i < prices.size(); i ++) {
        ans = max(ans, prices[i] - minp);
        minp = min(minp, prices[i]);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9

8. 买卖股票的最佳时机II

题目: 假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
分析: 多次买卖，我们可以尽可能多的买卖股票，如果满足prices[i+1] > price[i]，就进行一次买卖，其实我们知道如果是一个递增序列，(prices[i+1] - prices[i]) + (prices[i] - prices[i-1]) = prices[i+1] - prices[i]，可以保证我们将所有可能的买卖识别出来。

int maxProfit(vector<int> &prices) {
    int sum = 0;
    for(int i=1;i<prices.size();i++){
        if(prices[i] > prices[i-1]){
            sum += prices[i] - prices[i-1];
        }
    }
    return sum;
}
1
2
3
4
5
6
7
8
9

9. 买卖股票的最佳时机含手续费

题目: 给定一个数组，其中第i个元素是一支股票在第i天的价格，以及一个非负数 fee 代表了交易手续费。（只需要在卖出时支付 fee）。你可以进行任意次交易，而每次交易都必须付手续费，而且你不能持有超过1支数量的股票（也就是说，你在买入之前需要先把之前买入的卖出）。返回可以获得的最大利润。
分析:

• 我们考虑最朴素的方法，对于每一天，如果当前有股票，考虑出售或者保留，如果没股票，考虑购买或者跳过，进行dfs搜索。每天都有两种操作，时间复杂度为O(2^n).
• 如何优化呢？我们用动态规划的思想来解决这个问题，考虑每一天同时维护两种状态：拥有股票(own)状态和已经售出股票(sell)状态。用own和sell分别保留这两种状态到目前为止所拥有的最大利润。 对于sell，用前一天own状态转移，比较卖出持有股是否能得到更多的利润，即sell = max(sell , own + price - fee)， 而对于own , 我们考虑是否买新的股票更能赚钱(换言之，更优惠），own=max( own, sell-price).
• 初始化我们要把sell设为0表示最初是sell状态且没有profit，把own设为负无穷因为最初不存在该状态，我们不希望从这个状态进行转移.
• 因为我们保存的都是最优状态，所以在买卖股票时候取max能保证最优性不变.
• 最后直接返回sell即可.
• 来自(https://www.jiuzhang.com/solution/best-time-to-buy-and-sell-stock-with-transaction-fee/#tag-highlight-lang-cpp)

int maxProfit(vector<int> &prices, int fee) {
    int sell = 0, buy = -prices[0];
    for (int price : prices) {
        int sellOld = sell;
        sell = max(sell, buy + price - fee);
        buy = max(buy, sellOld - price);
    }
    return sell;
}
1
2
3
4
5
6
7
8
9

10. 最后的猫

题目: 给你一个n只猫，每一个猫都有一个初始化的萌系数，当一只猫的萌系数变成0它就会离开你。现在你实在受不了这n只萌猫，想要只留下一只猫，并且使它的萌系数最低。每一个你可以选择任意一只猫A去消耗另外一只猫B的萌系数，这样的话猫B的萌系数就会减去猫A的萌系数，当猫A的萌系数不变。通过多次回合之后，最后剩下的猫的萌系数最小是多少。
分析: 我们的目的是留下一只猫，使它的萌系数最小，从这个角度出发，我们可以选择最小萌系数的猫，去消耗其他的猫，如果其他的猫萌系数变成0，就离开了。例如最小萌系数的猫的系数是a，对于其他的猫，如果b%a == 0，则经过多次消耗之后，b就会离开，如果b%a!=0, 则结果是经过多轮消耗之后变成(b%a, a)，直到一方变成0，我们可以发现这是一个求最大公约的算式。因此，最后的猫萌系数是gcd(h[0],h[0],…,h[n-1]);

int gcd(int a, int b) {
    if(a == 0) return b;
    return gcd(b % a, a);
}
int solve(vector<int> &h) {
    if(h.size() == 1) return h[0];
    int ans = gcd(h[0], h[1]);
    for(int i = 2; i < h.size(); i ++) {
        ans = gcd(ans, h[i]);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12