算法leetcode

【贪心难题】力扣1054-距离相等的条形码

字数统计: 536字   |   阅读时长: 2分
,

摘要: 堆维护贪心算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来看一个用堆维护贪心算法的例子。

$1 题目

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

提示：

1
2
1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

示例 1：
输入：[1,1,1,2,2,2]
输出：[2,1,2,1,2,1]

示例 2：
输入：[1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]

$2 题解

算法：贪心

对每个出现过的字符计数，维护在 Item 结构体中。

用堆或者用排序的方式，每次取出当前计数最大的 item，往 result 数组中填数。

填数时先从 0 开始填下标为偶数的位置，填到尾之后再从 1 开始填下标为奇数的位置。

代码 (C++)

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
struct Item
{
    int v, cnt;
    Item(int v, int cnt):v(v),cnt(cnt){}
    Item():v(-1),cnt(0){}
};

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

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n = barcodes.size();
        if(n <= 2)
            return barcodes;
        const int MAX_VAL = 10000;
        vector<int> cnts(MAX_VAL + 1);
        for(int i: barcodes)
            ++cnts[i];
        priority_queue<Item, vector<Item>, HeapCmp> pq;
        for(int i = 1; i <= MAX_VAL; ++i)
        {
            if(cnts[i] == 0)
                continue;
            pq.push(Item(i, cnts[i]));
        }
        vector<int> result(n, -1);
        bool odd = true;
        int iter = 0;
        while(!pq.empty())
        {
            Item item = pq.top();
            int cnt = item.cnt;
            while(iter < n && cnt > 0)
            {
                result[iter] = item.v;
                iter += 2;
                --cnt;
            }
            if(iter >= n && odd)
            {
                odd = false;
                iter = 1;
                while(iter < n && cnt > 0)
                {
                    result[iter] = item.v;
                    iter += 2;
                    --cnt;
                }
            }
        }
        return result;
    }
};
Share