首页 > 编程语言 >【教3妹学编程-算法题】765. 情侣牵手

【教3妹学编程-算法题】765. 情侣牵手

时间:2023-11-12 10:04:53浏览次数:43  
标签:parent int 情侣 妹学 牵手 座位 765 public row

【教3妹学编程-算法题】765. 情侣牵手_数组

3妹:2哥2哥,你看到新闻了吗?襄阳健桥医院院长 公然“贩卖出生证明”, 真是太胆大包天了吧。
2哥 : 我也看到新闻了,7人被采取刑事强制措施。 就应该好好查查他们, 一查到底!
3妹:真的是太可气了, 白衣天使,本应该治病救人,没想到竟然能干出这种事情。
2哥 :哎,真相会迟到,但是不会缺席。 幸亏好很多像上官大人这样的打拐志愿者,帮助我们揭开面纱,还原事情的真相,他们是伟大的。
3妹:我一直觉得医生是个伟大的职业,小时候的愿望还是当一名医生, 结果上大学没有报考上医学院, 误打误撞进了计算机。 没想到医院也有这么黑暗的角落。
2哥:说到计算机,岔开个话题, 3妹,今天是不是还没刷题呢?我这里有个题很有意思。

 1题目: 

n 对情侣坐在连续排列的 2n 个座位上,想要牵到对方的手。

人和座位由一个整数数组 row 表示,其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号,第一对是 (0, 1),第二对是 (2, 3),以此类推,最后一对是 (2n-2, 2n-1)。

返回 最少交换座位的次数,以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人,让他们站起来交换座位。

示例 1:

输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换row[1]和row[2]的位置即可。
示例 2:

输入: row = [3,2,0,1]
输出: 0
解释: 无需交换座位,所有的情侣都已经可以手牵手了。

提示:

2n == row.length
2 <= n <= 30
n 是偶数
0 <= row[i] < 2n
row 中所有元素均无重复

 2思路: 

【教3妹学编程-算法题】765. 情侣牵手_并查集_02

并查集
「首尾相连」这件事情可以使用 并查集 表示,将输入数组相邻位置的两个 编号 在并查集中进行合并。编写代码基于了下面的事实:

如果一对情侣恰好坐在了一起,并且坐在了成组的座位上,其中一个下标一定是偶数,另一个一定是奇数,并且「偶数的值 + 1 = 奇数的值」。例如编号数对 [2, 3]、[9, 8],这些数对的特点是除以 2(下取整)得到的数相等。
详见代码:

 3java代码: 

public class Solution {


    public int minSwapsCouples(int[] row) {
        int len = row.length;
        int N = len / 2;
        UnionFind unionFind = new UnionFind(N);
        for (int i = 0; i < len; i += 2) {
            unionFind.union(row[i] / 2, row[i + 1] / 2);
        }
        return N - unionFind.getCount();
    }


    private class UnionFind {


        private int[] parent;


        private int count;


        public int getCount() {
            return count;
        }


        public UnionFind(int n) {
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }


        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }


        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }


            parent[rootX] = rootY;
            count--;
        }
    }
}

标签:parent,int,情侣,妹学,牵手,座位,765,public,row
From: https://blog.51cto.com/u_6813689/8325068

相关文章

  • 商城系统 “牵手” 淘宝 API 接口 php java sdk
    随着互联网的快速发展,网络购物已成为人们日常生活中不可或缺的一部分。淘宝作为中国最大的电商平台之一,其商城系统中详情页面的重要性日益凸显。本文将阐述淘宝详情在商城系统中的重要性,从用户角度、商家角度和商城运营角度进行分析,并探讨如何优化详情页面,提升用户转化率和购物体验......
  • MTK联发科MT6762/MT6763/MT6765安卓核心板参数规格比较
    MT6762安卓核心板MTK6762安卓核心板是一款工业级高性能、可运行android9.0操作系统的4G智能模块。CPU:4xCortex-A53upto2.0Ghz/4xCortex-A53upto1.5GhzGraphics:IMGGE8320Upto650MhzProcess:12nmMemory:1xLP3933MHz,upto4GB/2xLP4x1600MHz,upto6GB/eMMC5.1Came:21M......
  • CF765E
    分享一种我认为很优美的解法。首先发现,如果有一个点\(root\)使得以它为根,所有叶子深度相等,那么这一定是可行的。可以想象成将它拎出来并且把其他点横向拍扁。然后,容易发现两个\(root\)相同的,满足上面要求的树组合在一起也是可以的,即分成上下两部分分别拍扁。所以可以想到,如......
  • /var/lib/docker/overlay2/41a765b3cfaa278a67414c5b89234adfdebac7182d4bcd1e7c8a2c6
    现象:Error:Errorresponsefromdaemon:errorcreatingoverlaymountto/var/lib/docker/overlay2/41a765b3cfaa278a67414c5b89234adfdebac7182d4bcd1e7c8a2c6ac250dfb7-init/merged:nosuchfileordirectory原因:由于Docker存储空间中的一些残留文件或损坏的文件系统引......
  • 【教3妹学编程-算法题】使数组变美的最小增量运算数
    2哥 :3妹,脸上的豆豆好了没呢。3妹:好啦,现在已经没啦2哥 :跟你说很快就会消下去的,还不信~既然你的容颜和心情都如此美丽,那我们就再做一道关于美丽的题吧。3妹:切,2哥就会取笑我,伤心时让我做题,开心时也让我做题! 1题目: 给你一个下标从0开始、长度为n的整数数组nums,和一个整......
  • 【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II
    2哥 :3妹,听说你昨天去面试了,怎么样啊?3妹:嗨,别提了,让我回去等通知,估计是没有通知了,还浪费我请了一天假。2哥 :你又请假了啊,你是怎么跟你那个严厉的老板请假的。3妹:我说我2哥生病了,嘿嘿~2哥:一猜就是说我生病了,自从你找工作,我这一年都病了十几回了……3妹:没办法,假不好请嘛,我尽快......
  • 教3妹学编程-算法题】2914. 使二进制字符串变美丽的最少修改次数
    3妹:呜呜,烦死了,脸上长了一个痘2哥 :不要在意这些细节嘛,不用管它,过两天自然不就好了。3妹:切,你不懂,影响这两天的心情哇。2哥 :我看你是不急着找工作了啊,工作那么辛苦,哪还有时间想这些啊。3妹:说到找工作,我又要去刷题了。2哥:我给你出一道关于美丽的题吧,让你的心情美丽美丽~ 1题目......
  • 【教3妹学编程-算法题】数组中两个数的最大异或值
    3妹:“太阳当空照,花儿对我笑,小鸟说早早早,你为什么背上炸药包”2哥 :3妹,什么事呀这么开心呀。3妹:2哥你看今天的天气多好啊,阳光明媚、万里无云、秋高气爽,适合秋游。2哥:是啊,都快立冬了,天气还是这么热。今年的冬天比以往来的要晚一些。3妹:晚来也是要来的,看天气预报下周要降温,估计没几......
  • 【算法题】2765. 最长交替子序列
    题目:给你一个下标从0开始的整数数组nums。如果nums中长度为m的子数组s满足以下条件,我们称它是一个交替子序列:m大于1。s1=s0+1。下标从0开始的子数组s与数组[s0,s1,s0,s1,…,s(m-1)%2]一样。也就是说,s1-s0=1,s2-s1=-1,s3-s2=1,s4-s3......
  • 基于高性能Cortex®-M7内核STM32F765VGT7、STM32F745IET6嵌入式微控制器
    STM32F732位MCU+FPU基于高性能的ARM®Cortex-M732位RISC内核®,工作频率高达216MHz。Cortex®-M7内核具有单浮点单元(SFPU)精度,支持所有ARM®单精度数据处理指令与数据类型。同时执行全套DSP指令和存储保护单元(MPU),增强应用安全性。1、STM32F765VGT7ICMCU32BIT1MB......