【每日一题/哈希表运用题】1054. 距离相等的条形码

这篇具有很好参考价值的文章主要介绍了【每日一题/哈希表运用题】1054. 距离相等的条形码。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

⭐️前面的话⭐️

本篇文章介绍【距离相等的条形码】题解,题目标签【哈希表】, 【贪心】,【优先级队列】,展示语言c++/java。

📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创,CSDN首发!
📆首发时间:🌴2023年5月14日🌴
✉️坚持和努力一定能换来诗与远方!
💭推荐书籍:📚《算法》,📚《算法导论》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!



【每日一题/哈希表运用题】1054. 距离相等的条形码


⭐️1054. 距离相等的条形码⭐️

🔐题目详情

1054. 距离相等的条形码

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

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

示例 1:

输入:barcodes = [1,1,1,2,2,2]
输出:[2,1,2,1,2,1]

示例 2:

输入:barcodes = [1,1,1,1,2,2,3,3]
输出:[1,3,1,3,2,1,2,1]

提示:

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

💡解题思路

思路1: 利用哈希表计数,然后将哈希表转换为数组,按照频率从高到低进行排序,将元素按照隔空遍历的方式进行插入。

思路2:

第一步,使用哈希表计数。

第二步,将元素和数量绑定放入优先级队列当中。

第三步,每次取出出现次数最多的元素,和次多的元素插入到答案数组。

🔑源代码

思路1: 利用哈希表计数,然后将哈希表转换为数组,按照频率从高到低进行排序,将元素按照隔空遍历的方式进行插入。

代码:

c++

class Solution {
public:
    static bool cmp(const pair<int, int>& e1, const pair<int, int>& e2) 
    {
        if (e1.first != e2.first) return e1.first > e2.first;
        else return e1.second < e2.second;
    }
    vector<int> rearrangeBarcodes(vector<int>& barcodes) 
    {
        int size = barcodes.size();
        //哈希表
        unordered_map<int, int> cnt;
        //统计每个数字出现的数量
        for (int x : barcodes) 
        {
            cnt[x]++;
        }
        //排序,模拟隔一个数插入一个数
        vector<pair<int, int>> elems;
        for (auto x : cnt) 
        {
            elems.push_back({x.second, x.first});
        }

        //排序
        sort(elems.begin(), elems.end(), cmp);
        //模拟隔空插入
        int index = 0;
        vector<int> ans(size);
        int ans_index = 0;
        while (index < elems.size()) 
        {
            //优先插入元素个数最多的元素
            if (elems[index].first > 0) 
            {
                ans[ans_index] = elems[index].second;
                elems[index].first--;
                ans_index += 2;
                if (ans_index >= size) ans_index = 1;
            } else {
                index++;
            }
        }
        return ans;
    }
};

java

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int size = barcodes.length;

        //哈希表计数
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : barcodes) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        //转换为数组进行排序
        List<int[]> list = new ArrayList<>();
        for (Integer x : map.keySet()) {
            list.add(new int[]{map.get(x), x});
        }
        //排序
        Collections.sort(list, (a, b) -> {
            if (b[0] != a[0]) return b[0] - a[0];
            else return a[1] - b[1];
        });
        //模拟隔空插入
        int index = 0;
        int[] ans = new int[size];
        int ansIndex = 0;
        while (index < list.size()) {
            if (list.get(index)[0] > 0) {
                ans[ansIndex] = list.get(index)[1];
                ansIndex += 2;
                list.get(index)[0]--;
                if (ansIndex >= size) ansIndex = 1;
            } else index++;
        }
        return ans;
    }
}

思路2:

第一步,使用哈希表计数。

第二步,将元素和数量绑定放入优先级队列当中。

第三步,每次取出出现次数最多的元素,和次多的元素插入到答案数组。

代码:

c++

class Solution {
public:
    static bool cmp(const pair<int, int>& e1, const pair<int, int>& e2) 
    {
        if (e1.first != e2.first) return e1.first > e2.first;
        else return e1.second < e2.second;
    }
    vector<int> rearrangeBarcodes(vector<int>& barcodes) 
    {
        int size = barcodes.size();
        //哈希表计数
        unordered_map<int, int> hash_map;
        for (int x : barcodes) hash_map[x]++;
        //加入优先级队列,大根堆
        priority_queue<pair<int, int>> pq;
        for (auto x: hash_map) pq.push({x.second, x.first});
        //每次取出现频率最高的数插入
        vector<int> ans;
        while (pq.size() > 0) 
        {
            pair<int, int> top1 = pq.top(); pq.pop();
            if (pq.size() == 0) 
            {
                ans.push_back(top1.second);
                continue;
            }
            pair<int, int> top2 = pq.top(); pq.pop();
            ans.push_back(top1.second);
            ans.push_back(top2.second);

            top1.first--; top2.first--;
            if (top1.first > 0) pq.push(top1);
            if (top2.first > 0) pq.push(top2);
        }
        return ans;
    }
};

java

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        //计数
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int x : barcodes) hash.put(x, hash.getOrDefault(x, 0) + 1);
        //放入优先级队列,使用大根堆
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) return b[0] - a[0];
            else return a[1] - b[1];
        });
        for (int x : hash.keySet()) {
            pq.offer(new int[]{hash.get(x), x});
        }
        int[] ans = new int[barcodes.length];
        int index = 0;
        while (!pq.isEmpty()) {
            int[] top1 = pq.poll();
            if (pq.isEmpty()) {
                ans[index++] = top1[1];
                continue;
            }
            int[] top2 = pq.poll();
            ans[index++] = top1[1];
            ans[index++] = top2[1];

            top1[0]--;
            top2[0]--;
            if (top1[0] > 0) pq.offer(top1);
            if (top2[0] > 0) pq.offer(top2);
        }

        return ans;
    }
}

🌱总结

贪心,哈希表计数,优先级队列。


觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!

【每日一题/哈希表运用题】1054. 距离相等的条形码文章来源地址https://www.toymoban.com/news/detail-444395.html

到了这里,关于【每日一题/哈希表运用题】1054. 距离相等的条形码的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • uniapp生成条形码?

    首先先在插件市场找到条形码 链接:https://ext.dcloud.net.cn/search?q= 下载到项目里面 三、在pages.json中写入以下: 四、在html页面 这样就已经差不多了 条形码可以出来了

    2024年02月04日
    浏览(45)
  • java代码实现生成条形码

    2024年02月20日
    浏览(43)
  • 【Java】批量生成条形码-itextpdf

    批量生成条形码 Controller Service

    2024年02月12日
    浏览(37)
  • opencv_04条形码区域分割

    基于OpenCV的条形码区域分割 要基于OpenCV实现条形码区域分割,可以按照以下步骤进行: 加载图像:使用OpenCV中的imread函数读取待处理图像。 灰度化:使用OpenCV中的cvtColor函数将彩色图像转换为灰度图像。 边缘检测:使用OpenCV中的Canny函数对灰度图像进行边缘检测,得到二值

    2024年02月06日
    浏览(42)
  • JS 生成条形码(一维码)jsBarcode

    script 引入 地址:https://cdn.jsdelivr.net/npm/jsbarcode@3.11.5/dist/JsBarcode.all.min.js 也可以进官网查看地址。 npm方式 安装: 页面引入: HTML部分加入svg容器 JS 代码部分 三、结果 参数设置(options) option 默认值 类型 说明 format “auto” (CODE128) String 条形码的类型 width 2 Number 每个条条的宽

    2024年01月20日
    浏览(41)
  • 【MAUI】条形码,二维码扫描功能

    本系列文章面向移动开发小白,从零开始进行平台相关功能开发,演示如何参考平台的官方文档使用MAUI技术来开发相应功能。 移动端的扫描条形码、二维码的功能已经随处可见,已经很难找到一个不支持扫描的App了,但是微软的MAUI竟然没有提供,那么我们应该如何实现呢?

    2024年02月04日
    浏览(43)
  • 如何使用 Python 生成和读取条形码

    条形码在我们的日常生活中很常见。只需几个简单的步骤,您就可以使用 Python 轻松生成和扫描条形码。 当您从商店购买商品时,您所购买的物品上的平行黑条纹,具有不同宽度,被称为条形码。条形码是一种将数据以视觉、机器可读的方式表示的方法。条形码被用于存储有

    2024年02月04日
    浏览(32)
  • opencv检测二维码和条形码

    使用excel可以实现制作二维码,但只能实现做英文和数字类型的,步骤如下: 在任意单元格输入内容 选项卡里找到开发工具—插入—点击ActiveX控件的最右下角。 弹出的窗口内,往下滑动选择Microsoft BarCode Control 16.0后,点击确定。 在任意区域,摁住鼠标左键不放,拖动鼠标,

    2024年02月10日
    浏览(55)
  • java生成、识别条形码和二维码

    使用 zxing 开源库 Zxing主要是Google出品的,用于识别一维码和二维码的第三方库 主要类: BitMatrix 位图矩阵 MultiFormatWriter 位图编写器 MatrixToImageWriter 写入图片 可以生成、识别条形码和二维码 内置三种尺寸: enum Size {SMALL, MIDDLE, BIG} 依赖 将宽度不等的多个黑条和白条,按照一定

    2024年02月08日
    浏览(52)
  • LeetCode·每日一题·822. 翻转卡片游戏·哈希

    作者:小迅 链接:https://leetcode.cn/problems/card-flipping-game/solutions/2368969/ha-xi-zhu-shi-chao-ji-xiang-xi-by-xun-ge-7ivj/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 根据题意,只要有数字满足 fronts[i]=backs[i],那么 fronts[i] 绝对不可能是

    2024年02月14日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包