LintCode 629 · 最小生成树【困难 并查集 Java】

题目

在这里插入图片描述
在这里插入图片描述

题目链接:
https://www.lintcode.com/problem/629/

思路

核心1:对connections进行排序,根据开销升序排序
核心2:并查集,合并集合,记录下合并的边缘
核心3:如果合并完后,集合数是一个,说明是一棵树,返回边缘集合,否则发你空集合

Java答案

/**
 * Definition for a Connection.
 * public class Connection {
 *   public String city1, city2;
 *   public int cost;
 *   public Connection(String city1, String city2, int cost) {
 *       this.city1 = city1;
 *       this.city2 = city2;
 *       this.cost = cost;
 *   }
 * }
 */
public class Solution {
    /**
     * @param connections given a list of connections include two cities and cost
     * @return a list of connections from results
     */
    public List<Connection> lowestCost(List<Connection> connections) {
        //核心1:排序,根据开销排序
           Collections.sort(connections,(a,b)->{
                if(a.cost == b.cost){
                    if(a.city1.equals(b.city1)){
                        return a.city2.compareTo(b.city2);
                    }else{
                        return a.city1.compareTo(b.city1);
                    }
                }else{
                    return a.cost-b.cost;
                }
            });
            UF uf = new UF();
            List<Connection> ans = new ArrayList<>();
            int mincost=0; //本题中没用,统计最小生成树的最小花开销,比如牛客上相同的题目就是求开销
            for (Connection v : connections) {
                String f = v.city1;
                String t = v.city2;
                
                String f1 = uf.finx(f);
                String f2 = uf.finx(t);
                
                if(!f1.equals(f2)){
                    ans.add(v);
                    mincost+= v.cost;
                    
                    uf.union(f,t);
                }
            }
            
            if(uf.sets==1){ //集合不止一个,说明不能连通
                return ans;
            }else{
                return new ArrayList<>();
            }
        }

        static class UF{
            public Map<String,String> parents = new HashMap<>();
            public Map<String,Integer> size = new HashMap<>();
            public Map<Integer,String> help = new HashMap<>();

            int sets =0;

            public  String finx(String x){
                if(!parents.containsKey(x)){
                    parents.put(x,x);
                    size.put(x,1);
                    sets++;
                }

                int hi=0;
                while (!x.equals(parents.get(x))){
                    help.put(hi++,x);
                    x= parents.get(x);
                }

                for(hi--;hi>=0;hi--){
                    parents.put(help.get(hi),x);
                }

                return x;
            }

            public void union(String a,String b){
                String f1 = finx(a);
                String f2 = finx(b);

                if(!f1.equals(f2)){
                    int s1 = size.get(f1);
                    int s2 = size.get(f2);

                    int sum = s1+s2;
                    if(s1>=s2){
                        size.put(f1,sum);
                        parents.put(f2,f1);
                    }else{
                        size.put(f2,sum);
                        parents.put(f1,f2);
                    }

                    sets--;
                }
            }

        }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/797571.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java 中的正则表达式

转义字符由反斜杠\x组成&#xff0c;用于实现特殊功能当想取消这些特殊功能时可以在前面加上反斜杠\ 例如在Java中当\出现时是转义字符的一部分&#xff0c;具有特殊意义&#xff0c;前面加一个反斜可以取消其特殊意义&#xff0c;表示1个普通的反斜杠\&#xff0c;\\\\表示2个…

《python程序语言设计》2018版第5章第55题利用turtle黑白棋盘。可读性还是最重要的。

今天是我从2024年2月21日开始第9次做《python程序语言设计》作者梁勇 第5章 从2019年夏天的偶然了解python到2020年第一次碰到第5章第一题。彻底放弃。再到半年后重新从第一章跑到第五章&#xff0c;一遍一遍一直到今天2024.7.14日第9次刷第五章。 真的每次刷完第五章感觉好像…

【题解】42. 接雨水(动态规划 预处理)

https://leetcode.cn/problems/trapping-rain-water/description/ class Solution { public:int trap(vector<int>& height) {int n height.size();// 预处理数组vector<int> lefts(n, 0);vector<int> rights(n, 0);// 预处理记录左侧最大值lefts[0] …

Python应用 | 基于flask-restful+AntDesignVue实现的一套图书管理系统

本文将分享个人自主开发的一套图书管理系统&#xff0c;后端基于Python语言&#xff0c;采用flask-restful开发后端接口&#xff0c;前端采用VueAntDesignVue实现。对其他类似系统的实现&#xff0c;比如学生管理系统等也有一定的参考作用。有问题欢迎留言讨论~ 关注公众号&am…

最新Wireshark查看包中gzip内容

虽然是很简单的事情&#xff0c;但是网上查到的查看gzip内容的方法基本都是保存成zip文件&#xff0c;然后进行二进制处理。 其实现在最新版本的Wireshark已经支持获取gzip内容了。 选中HTTP协议&#xff0c;右键选择[追踪流]->[HTTP Stream] 在弹出窗口中&#xff0c;已…

mavsdk_server安卓平台编译

1.下载好mavsdk并进入mavsdk目录 2.生成docker安卓平台文件 docker run --rm dockcross/android-arm64 >./dockcross-android-arm64 3.生成makefile ./dockcross-android-arm64 cmake -DCMAKE_BUILD_TYPERelease -DBUILD_MAVSDK_SERVERON -DBUILD_SHARED_LIBSOFF -Bbuild/…

专业条码二维码扫描设备和手机二维码扫描软件的区别?

条码二维码技术已广泛应用于我们的日常生活中&#xff0c;从超市结账到公交出行&#xff0c;再到各类活动的入场验证&#xff0c;条码二维码的便捷性不言而喻&#xff0c;而在条码二维码的扫描识别读取过程中&#xff0c;专业扫描读取设备和手机二维码扫描软件成为了两大主要工…

【计算机毕业设计】003基于weixin小程序教学辅助

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

【Java】字符与字符串

1.字符char 字符数据类型用于表示单个字符。 字符数据类型char用于表示单个字符。字符型字面值用单引号括住。 char a A; char b 4; char c \u041; // A的Unicode字符串字面值必须括在双引号中。而字符字面值是括在单引号中的单个字符。因此"A"是一个字符串&…

视频号里的视频怎么下载保存?推荐5种方法!

很多人不知道视频号里的视频怎么下载保存&#xff0c;其实视频号下载提取方式比较多常见的有缓存、查看源代码、抓包、录屏、自动提取工具。 1&#xff1a;缓存 安卓手机特性将需要的视频观看完并缓存到手机&#xff0c;并将视频另外存为mp4文件&#xff0c;不过该方式最安卓1…

【扩散模型】【图像生成】FreeU:扩散 U-Net 模型的免费午餐(CVPR 2024 Oral))

论文名称&#xff1a;FreeU: Free Lunch in Diffusion U-Net (CVPR 2024 Oral) 论文地址&#xff1a;https//arxiv.org/pdf/2309.11497 项目链接&#xff1a;https//chenyangsi.top/FreeU/ 文章目录 摘要一、 扩散 U-Net 中的低频和高频分量二、扩散 U-Net 是如何执行去噪过程…

excel、word、ppt 下载安装步骤整理

请按照我的步骤开始操作&#xff0c;注意以下截图红框标记处&#xff08;往往都是需要点击的地方&#xff09; 第一步&#xff1a;下载 首先进入office下载网址&#xff1a; otp.landian.vip 然后点击下载 拉到下方 下载站点&#xff08;这里根据自己的需要选择下载&#x…

VLM技术介绍

1、背景 视觉语言模型&#xff08;Visual Language Models&#xff09;是可以同时从图像和文本中学习以处理许多任务的模型&#xff0c;从视觉问答到图像字幕。 视觉识别&#xff08;如图像分类、物体保护和语义分割&#xff09;是计算机视觉研究中一个长期存在的难题&#xff…

Excel第31享:基于left函数的截取式数据裂变

1、需求描述 如下图所示&#xff0c;在“Excel第30享”中统计2022年YTD各个人员的“上班工时&#xff08;a2&#xff09;”&#xff0c;需要基于工时明细表里的“日期”字段建立辅助列&#xff0c;生成“年份”字段&#xff0c;本文说明“年份”字段是怎么裂变而来的。 下图为…

前端web性能统计

前端web性能统计 1. 背景2. 业界方案2.1 腾讯2.2 蚂蚁金服2.3 字节跳动2.4 美团 3. 相关观念3.1 RAIL模型3.2 性能指标3.3 真实用户监控3.4 performance 4. 性能监控工具介绍5. 推荐采用方案 1. 背景 在如今的数字时代&#xff0c;网站和应用程序的性能对用户体验至关重要。用…

13_Shell系统函数

13_Shell系统函数和自定义函数 一、系统函数 basename 获取文件名 #!/bin/bash#basename 相对路径文件名 basename ./1.sh#basename 绝对路径文件名 basename /tmp/1.sh#basename 去除文件后缀名 basename /tmp/1.sh .shdirname 获取文件所在目录名 #!/bin/bash#dirname 相对路…

【web】-sql注入-login

根据网址提示打开如图&#xff1a; 查看源代码前台并没有过滤限制、扫描后台也没有发现特殊文件。看到标题显示flag is in database&#xff0c;尝试sql注入。 由于post,bp抓包如下&#xff1a; 运行python sqlmap.py -r 1.txt --dump 获取flag 42f4ebc342b6ed4af4aadc1ea75f…

在word中删除endnote参考文献之间的空行

如图&#xff0c;在References中&#xff0c;每个文献之间都有空行。不建议手动删除。打开Endnote。 打开style manager 删除layout中的换行符。保存&#xff0c;在word中更新参考文献即可。

【自学网络安全】二、防火墙NAT智能选路综合实验

任务要求&#xff1a; &#xff08;衔接上一个实验所以从第七点开始&#xff0c;但与上一个实验关系不大&#xff09; 7&#xff0c;办公区设备可以通过电信链路和移动链路上网(多对多的NAT&#xff0c;并且需要保留一个公网IP不能用来转换) 8&#xff0c;分公司设备可以通过总…

中小学校园EasyCVR视频综合监管方案:构建安全、智能的校园环境

一、背景需求分析 随着科技的快速发展&#xff0c;校园安全问题日益受到社会各界的关注。尤其是在中小学校园中&#xff0c;学生的安全更是牵动着每一个家庭的心。为了更有效地保障学生的安全&#xff0c;提高校园安全管理水平&#xff0c;视频监控系统在中小学中的应用越来越…