算法基础算法

贪心-疑难杂症

字数统计: 4k字   |   阅读时长: 20分

Ref:

  • 比赛问题
  • 分配问题

406. 根据身高重建队列

先排序再插入，排序 $O(N\log N)$，插入 $O(N^{2})$，自定义排序法则难想，Ref: 非主流排序和自定义排序

860. 柠檬水找零

当收到 20 的时候，优先找一个 10 和一个 5，如果不行再考虑找 3 个 5.

649. Dota2 参议院

每个R阵营的参议员禁止下一个离他最近的D阵营的参议员，反之亦然。

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
class Solution {
public:
    string predictPartyVictory(string senate) {
        int n = senate.size();
        int nd = 0;
        for(int i: senate)
            if(i == 'D')
                ++nd;
        int nr = n - nd;
        if(nr == 0) return "Dire";
        if(nd == 0) return "Radiant";
        stack<int> st_d, st_r; // 有权利尚未使用
        while(true)
        {
            for(int i = 0; i < n; ++i)
            {
                int cur = senate[i];
                if(cur == ' ') continue;
                if(cur == 'R')
                {
                    // 看 R 是否被限制权力
                    if(!st_d.empty())
                    {
                        // 被限制
                        senate[i] = ' ';
                        --nr;
                        if(nr == 0)
                            return "Dire";
                        st_d.pop();
                    }
                    else
                    {
                        // 未被限制
                        st_r.push(i);
                    }
                }
                else
                {
                    // 看 D 是否被限制权利
                    if(!st_r.empty())
                    {
                        // 被限制
                        senate[i] = ' ';
                        --nd;
                        if(nd == 0)
                            return "Radiant";
                        st_r.pop();
                    }
                    else
                    {
                        // 未被限制
                        st_d.push(i);
                    }
                }
            }
        }
    }
};

330. 按要求补齐数组

问题

给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

分析

记 miss 是缺失数字中最小的，[1, miss) 已经被覆盖

为了覆盖 miss，必须加入某个 x <= miss 的数字，此时 [x, miss + x) 已经覆盖

因此希望选择尽可能大的 x，这样的话增加一个数之后，可以确定覆盖的范围可以达到最大。因此取 x = miss

这个贪心的思路与区间覆盖问题有点像。

1
2
3
4
5
6
7
8
9
10
初始化 miss = 0, i = 0, cnt = 0
迭代 miss 直到 miss > n:
    检查 nums，若 nums[i] <= miss:
        miss += nums[i]
        ++i
    否则:
        加入 miss, miss *= 2
        ++cnt;

贪心地取补充的数为 x = miss，有点区间覆盖问题的意思

代码

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
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int m = nums.size();
        using ll = long long;
        ll miss = 1;
        int i = 0;
        int ans = 0;
        while(miss <= n)
        {
            if(i < m && nums[i] <= miss)
            {
                // 取到 [1, miss) 时尚未用到 nums[i]
                miss += nums[i];
                ++i;
            }
            else
            {
                miss *= 2;
                ++ans;
            }
        }
        return ans;
    }
};

乘船问题 : 881. 救生艇

有 n 个人，第 i 个人重量为 w[i]，每艘船的最大载重量为 C，且最多只能乘 2 个人。用最少的船装载所有人。

分析

1
按照题中从轻到重考虑：给当前人应该选择能和他一起坐船的人中最重的一个，如果不能找到这样的人，则他一个人坐船。

910. 最小差值 II

问题

给定一个整数数组 A，对于每个整数 A[i]，我们可以选择 x = -K 或是 x = K，并将 x 加到 A[i] 中。

在此过程之后，我们得到一些数组 B。

返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

分析

每个数必须做出 +K 或 -K 的选择，不能不变。

排序后的数组中，一定有一个位置 i，[0..i] 上 +K,[i+1..n-1] 上 -K。此时整个数组的最大值是 A[n-1]-K 或 A[i]+K，最小值是 A[0]+K 或 A[i+1]-K。遍历一遍(i=0..n-2)维护这 4 个值

i=n-1 为基准值，即所有数均采用 +K 的结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int n = A.size();
        int d = A[n - 1] - A[0]; // 全 + 的极差
        for(int i = 0; i < n - 1; ++i)
        {
            // [0..i] +K, [i+1..n-1] -K
            int min_l = min(A[i + 1] - K, A[0] + K);
            int max_h = max(A[i] + K, A[n - 1] - K);
            d = min(d, max_h - min_l);
        }
        return d;
    }
};

927. 三等分

分析

记所有 1 的位置 idxs

若 (int)idxs.size() % 3 != 0 则不行。返回 {-1, -1}，否则记 t = (int)idxs.size() / 3 为每个子串中 1 的个数

记分成的三个子串为 s1, s2, s3，其中 s3 = A[idxs[t * 2]..n-1] 是固定的了。通过 s3 的末尾 0 可以推导出 i，j 的候选位置。

记 s3 的末尾 0 个数为 tail_zero = n - 1 - idxs[t * 3 - 1]，s1, s2 的末尾 0 个数也必须为 tail_zero。因此 i 和 j 的候选如下(如果可行，则 i, j 只能是以下计算出的位置)。

1
2
j = idxs[t * 2 - 1] + tail_zero + 1;
i = idxs[t - 1] + tail_zero;

验证计算出的 i, j 是否成立，记 s3 的长度为 len = n - idxs[t * 2]

首先验证 i, j 位置的合法性，以及三个串的长度相等。

1
2
3
4
if(i >= idxs[t] || i - idxs[0] + 1 != len)
    return {-1, -1};
if(j > idxs[t * 2] || j - idxs[t] != len)
    return {-1, -1};

然后验证 s1 与 s2 子串、s1 与 s3 子串是否相等。

代码

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
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& A) {
        int n = A.size();
        vector<int> idxs;
        for(int i = 0; i < n; ++i)
            if(A[i] == 1)
                idxs.push_back(i);
        if(idxs.empty())
            return {0, (int)A.size() - 1};
        if((int)idxs.size() % 3 != 0)
            return {-1, -1};
        int t = (int)idxs.size() / 3;
        int tail_zero = n - 1 - idxs[t * 3 - 1];
        int len = n - idxs[2 * t];
        int i = idxs[t - 1] + tail_zero;
        if(i >= idxs[t] || i - idxs[0] + 1 != len)
            return {-1, -1};
        int j = idxs[t * 2 - 1] + tail_zero + 1;
        if(j > idxs[t * 2] || j - idxs[t] != len)
            return {-1, -1};
        if(check(A, n - 1, i, len) && check(A, n - 1, j - 1, len))
            return {i, j};
        else
            return {-1, -1};
    }

private:
    bool check(const vector<int>& A, int r1, int r2, int len)
    {
        for(int d = 0; d < len; ++d)
        {
            int i1 = r1 - d, i2 = r2 - d;
            if(A[i1] != A[i2])
                return false;
        }
        return true;
    }
};

948. 令牌放置

排序后贪心

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
class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        int n = tokens.size();
        sort(tokens.begin(), tokens.end());
        int left = 0, right = n - 1;
        int ans = 0;
        while(left <= right)
        {
            while(left <= right && tokens[left] <= P)
            {
                P -= tokens[left++];
                ++ans;
            }
            if(left >= right || ans < 1)
                break;
            // left < right
            // P += token[right] 之后一定能 cover token[left]
            if(ans >= 1)
            {
                P += tokens[right--];
                --ans;
            }
        }
        return ans;
    }
};

1007. 行相等的最少多米诺旋转

分析

1
2
3
4
up[i] := 上半部分，数 i 出现个个数
down[i] := 下半部分，数 i 出现个个数

idxs[i] := 数字 i 出现过的位置下标(A[i] == B[i] 时只记一次)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minDominoRotations(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> up(7), down(7);
        vector<vector<int>> idxs(7);
        for(int i = 0; i < n; ++i)
        {
            ++up[A[i]];
            ++down[B[i]];
            idxs[A[i]].push_back(i);
            if(A[i] != B[i])
                idxs[B[i]].push_back(i);
        }
        for(int t = 1; t <= 6; ++t)
            if((int)idxs[t].size() == n)
                return min(up[t], down[t]) - (up[t] + down[t] - n);
        return -1;
    }
};

1029. 两地调度

代码

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
struct Person
{
    int a, b;
    Person(int a, int b):a(a),b(b){}
};

struct Cmp
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        return (p1.a - p1.b) < (p2.a - p2.b);
    }
};

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<Person> persons;
        for(int i = 0; i < n; ++i)
        {
            persons.push_back(Person(costs[i][0], costs[i][1]));
        }
        sort(persons.begin(), persons.end(), Cmp());
        int ans = 0;
        for(int i = 0; i < n / 2; ++i)
            ans += persons[i].a;
        for(int i = n / 2; i < n; ++i)
            ans += persons[i].b;
        return ans;
    }
};

1247. 交换字符使得字符串相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int n = s1.size();
        int cntxy = 0, cntyx = 0;
        for(int i = 0; i < n; ++i)
        {
            if(s1[i] == 'x' && s2[i] == 'y')
                ++cntxy;
            if(s1[i] == 'y' && s2[i] == 'x')
                ++cntyx;
        }
        if((cntxy + cntyx) & 1)
            return -1;
        int ans = 0;
        if(cntxy % 2 == 1)
            ans += 2;
        ans += cntxy / 2;
        ans += cntyx / 2;
        return ans;
    }
};

1338. 数组大小减半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        unordered_map<int, int> mapping;
        for(int a: arr)
            ++mapping[a];
        priority_queue<int> pq;
        for(auto item: mapping)
            pq.push(item.second);
        int n = arr.size();
        int K = n - n / 2;
        int ans = 0;
        while(K > 0)
        {
            K -= pq.top();
            pq.pop();
            ++ans;
        }
        return ans;
    }
};

1386. 安排电影院座位

分析

位掩码

代码

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
class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        using PII = pair<int, int>;
        unordered_map<int, int> mapping;
        for(const vector<int>& ij: reservedSeats)
        {
            mapping[ij[0]] ^= (1 << (ij[1] - 1));
        }
        int N = mapping.size();
        int cnt = 0;
        for(const PII &row: mapping)
        {
            int state = ~(row.second);
            if((state & (0b11111111 << 1)) == (0b11111111 << 1))
            {
                cnt += 2;
                continue;
            }
            if(((state & (0b1111 << 1))) == (0b1111 << 1)
                    || ((state & (0b1111 << 3))) == (0b1111 << 3)
                    || ((state & (0b1111 << 5))) == (0b1111 << 5))
                ++cnt;
        }
        return n * 2 - N * 2 + cnt;
    }
};

1400. 构造 K 个回文字符串

1
2
3
s.size() < k: False
出现奇数次的字符个数为 c1: 至少 c1 个回文串才能消化掉，c1 > k 则 False
其余情况 True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canConstruct(string s, int k) {
        int n = s.size();
        if(n < k)
            return false;
        vector<int> cnts(26);
        for(const char &ch: s)
        {
            ++cnts[ch - 'a'];
        }
        int c1 = 0;
        for(int i = 0; i< 26; ++i)
            if(cnts[i] & 1)
                ++c1;
        if(c1 > k)
            return false;
        return true;
    }
};

1403. 非递增顺序的最小子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        int sum = 0;
        for(int i: nums) sum += i;
        vector<int> result;
        int s = 0;
        for(int i: nums)
        {
            s += i;
            result.push_back(i);
            if(s > sum / 2)
                return result;
        }
        return {};
    }
};

1578. 避免重复字母的最小删除成本

分析

结果 += 重复元素成本之和 - 本次重复最大元素

另：可以动态规划

1567. 乘积为正数的最长子数组长度

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
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        int left_odd = -1, left_even = -1;
        int cnt = 0;
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] == 0)
            {
                left_odd = -1;
                left_even = i;
                cnt = 0;
                continue;
            }
            if(nums[i] < 0)
                cnt ^= 1;
            if(left_odd == -1 && nums[i] < 0 && (cnt & 1) == 1)
            {
                left_odd = i;
            }
            if(cnt & 1)
            {
                if(left_odd != -1)
                    ans = max(ans, i - left_odd);
            }
            else
            {
                ans = max(ans, i - left_even);
            }
        }
        return ans;
    }
};

1488. 避免洪水泛滥

贪心：没雨的日期，抽干当前满水的湖中下一场雨来的最早的

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
class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        unordered_map<int, vector<int>> mapping;
        for(int i = 0; i < n; ++i)
        {
            if(rains[i] != 0)
                mapping[rains[i]].push_back(i);
        }
        vector<int> result(n, -1);
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        for(int i = 0; i < n; ++i)
        {
            if(rains[i] != 0)
            {
                int id = rains[i];
                if(!pq.empty() && pq.top().second == id)
                    return {};
                // 湖 id 下一次下雨是 t
                auto it = upper_bound(mapping[id].begin(), mapping[id].end(), i);
                if(it != mapping[id].end())
                {
                    // t, id 入堆
                    // 堆中都是后续还会下雨的，堆头是最早的，如果 pq.top().t 到来是仍为出堆，则返回 []
                    pq.push(PII(*it, id));
                }
            }
            else
            {
                if(!pq.empty())
                {
                    result[i] = pq.top().second;
                    pq.pop();
                }
                else
                    result[i] = 1;
            }
        }
        return result;
    }

private:
    using PII = pair<int, int>;
};

1616. 分割两个字符串得到回文串

相遇问题

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
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        return check(a, b) || check(b, a);
    }

private:
    bool check(const string& a, const string& b)
    {
        int n = a.size();
        // 从 a 中心扩散，直至不能扩散的位置 idx : a[idx] != a[n - 1 - idx]
        // b.substr(0, idx + 1) + a.substr(idx + 1)
        // a.substr(0, n - 1 - idx) + b.substr(n - 1 - idx)
        int idx = n / 2 - 1;
        while(idx >= 0 && a[idx] == a[n - 1 - idx])
            --idx;
        if(idx == -1)
            return true;
        int iter = idx;
        while(iter >= 0 && b[iter] == a[n - 1 - iter])
            --iter;
        if(iter == -1)
            return true;
        iter = idx;
        while(iter >= 0 && a[iter] == b[n - 1 - iter])
            --iter;
        if(iter == -1)
            return true;
        return false;
    }
};

1183. 矩阵中 1 的最大数量

【贪心难题】力扣1183-矩阵中1的最大数量

334. 递增的三元子序列

  • 双指针，始终维护 l, r 两个指针，l 为某个子序列的最小值，r 为某个子序列的第二小
  • 迭代规程中始终尽量使得 A[r] 尽量小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        int l = INT_MAX, r = INT_MAX;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] <= l)
                l = nums[i];
            else if(nums[i] <= r)
                r = nums[i];
            else
                return true;
        }
        return false;
    }
};

1647. 字符频次唯一的最小删除次数

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
class Solution {
public:
    int minDeletions(string s) {
        vector<int> cnts(26);
        for(char ch: s)
            ++cnts[ch - 'a'];
        sort(cnts.begin(), cnts.end());
        int prev = cnts[25];
        int ans = 0;
        for(int i = 24; i >= 0; --i)
        {
            if(cnts[i] >= prev)
            {
                if(prev == 0)
                {
                    ans += cnts[i];
                }
                else
                {
                    ans += cnts[i] - prev + 1;
                    --prev;
                }
            }
            else
                prev = cnts[i];
        }
        return ans;
    }
};

1648. 销售价值减少的颜色球

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
64
65
66
67
68
69
70
71
72
73
using ll = long long;
const int MOD = 1e9 + 7;

struct Item
{
    ll cnt; // 个数
    ll kind; // 种类数
    Item(ll c, ll k):cnt(c),kind(k){}
};

struct HeapCmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.cnt < i2.cnt;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& inventory, int orders) {
        unordered_map<int, int> mapping; // cnt -> kinds
        for(int i: inventory)
            ++mapping[i];
        priority_queue<Item, vector<Item>, HeapCmp> pq;
        for(auto i: mapping)
            pq.push(Item(i.first, i.second));
        ll ans = 0;
        ll K = orders;
        while(K > 0)
        {
            Item cur = pq.top();
            pq.pop();
            if(pq.empty())
            {
                // 剩余选择均由 cur 提供
                ll x = K / cur.kind; // 完整的层
                // cur.kind * cur.cnt, cur.kind * (cur.cnt - 1) ... cur.kind * (cur.cnt - x + 1)
                ll y = K % cur.kind; // 最后一层的个数
                // y * (cur.cnt - x)
                ans = (ans + ((cur.kind * cur.cnt) + (cur.kind * ((ll)cur.cnt - x + 1))) * x / 2) % MOD;
                ans = (ans + y * (cur.cnt - x)) % MOD;
                K = 0;
            }
            else
            {
                Item nxt = pq.top();
                ll all = (cur.cnt - nxt.cnt) * cur.kind;
                if(all >= K)
                {
                    // 剩余选择均由 cur 提供
                    ll x = K / cur.kind; // 完整的层
                    // cur.kind * cur.cnt, cur.kind * (cur.cnt - 1) ... cur.kind * (cur.cnt - x + 1)
                    ll y = K % cur.kind; // 最后一层的个数
                    // y * (cur.cnt - x)
                    ans = (ans + ((cur.kind * cur.cnt) + (cur.kind * ((ll)cur.cnt - x + 1))) * x / 2) % MOD;
                    ans = (ans + y * (cur.cnt - x)) % MOD;
                    K = 0;
                }
                else
                {
                    ll x = cur.cnt - nxt.cnt;
                    ans = (ans + ((cur.kind * cur.cnt) + (cur.kind * ((ll)cur.cnt - x + 1))) * x / 2) % MOD;
                    K -= all;
                    pq.pop();
                    nxt.kind += cur.kind;
                    pq.push(nxt);
                }
            }
        }
        return ans;
    }
};

比赛问题

N 个学生 K 个赛场，第 i 个赛场最多 Ni 名学生参赛 sum(Ni) = N，每个赛场有一个等级值 Q，每个学生有一个能力值 p 和权重 w

安排每个学生参赛，当且仅当一个学生的 p 值大于一个赛场的 Q 值，参赛后可以有 w[i] 的收益，每个学生只能参加一个比赛，求收益最大方案

分析

N 个物品, K 个背包
物品 i 有体积 v[i]，价值 w[i]
但对物品 i 放入背包 j 的约束不是的容量，而是物品 i 的体积 v[i] 大于 Q[j] 能放入。

贪心方案

1
将学生按照权重排序，从权重最大的人考试考虑，将其放入他所能参加的等级制要求最大的考场。

分配问题

M 个物品分配 N 个人，第 i 个人应该拿 M(X[i]/Y) 个物品，sum(X[i]) = Y

但因为 X[i]/Y 可能不是整数，因此考虑折中方案：第 i 个人分 K[i] 个物品，Sum(K[i]) = M

求一种折中方案，使得 $\sum\limits_{i=1}\limits^{N}(|K[i]/M-X[i]/Y|)$ 最小

分析

首先设 K[i] = M * X[i] / Y，这样可能会多出一些剩余的物品，可以加在一些物品上。

贪心方案

1
优先分配 M * X[i] / Y - K[i] 较大的

Share