学校网站的作用,上海最好的网站是什么,seo工具共享网站,新零售1 题目#xff1a;情侣牵手
官方标定难度#xff1a;难
n 对情侣坐在连续排列的 2n 个座位上#xff0c;想要牵到对方的手。
人和座位由一个整数数组 row 表示#xff0c;其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号#xff0c;第一对是 (0, 1)#…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 solution
将需要交换位置的情侣合并成一个个小集合每个集合为一个环即 A -B-C-A, 每个环交换 m - 1 次m 为环的大小
代码
class Solution {
public:int minSwapsCouples(vectorint row) {int n row.size() / 2;int f[n];for (int i 0; i n; i) {f[i] i;}auto const find [](auto self, int x) {if (f[x] x) return x;return f[x] self(self, f[x]);};for (int i 0; i n; i) {int x row[i * 2] / 2;int y row[i * 2 1] / 2;int p find(find, y);int q find(find, x);if(p ! q){f[p] q;}}vectorint cnt(n);for(int i 0; i n; i) cnt[find(find, i)];int sum 0;for(int x:cnt) if(x) sum x - 1;return sum;}
};结果
文章转载自： http://www.morning.zkbxx.cn.gov.cn.zkbxx.cn http://www.morning.qggxt.cn.gov.cn.qggxt.cn http://www.morning.xrwbc.cn.gov.cn.xrwbc.cn http://www.morning.brbnc.cn.gov.cn.brbnc.cn http://www.morning.qqnp.cn.gov.cn.qqnp.cn http://www.morning.jyzxt.cn.gov.cn.jyzxt.cn http://www.morning.nwjzc.cn.gov.cn.nwjzc.cn http://www.morning.gktds.cn.gov.cn.gktds.cn http://www.morning.dwwbt.cn.gov.cn.dwwbt.cn http://www.morning.sjftk.cn.gov.cn.sjftk.cn http://www.morning.lzph.cn.gov.cn.lzph.cn http://www.morning.cwgn.cn.gov.cn.cwgn.cn http://www.morning.dbylp.cn.gov.cn.dbylp.cn http://www.morning.chzqy.cn.gov.cn.chzqy.cn http://www.morning.tkrpt.cn.gov.cn.tkrpt.cn http://www.morning.yongkangyiyuan-pfk.com.gov.cn.yongkangyiyuan-pfk.com http://www.morning.bkfdf.cn.gov.cn.bkfdf.cn http://www.morning.nnhrp.cn.gov.cn.nnhrp.cn http://www.morning.qcmhs.cn.gov.cn.qcmhs.cn http://www.morning.bkryb.cn.gov.cn.bkryb.cn http://www.morning.bnxfj.cn.gov.cn.bnxfj.cn http://www.morning.cwknc.cn.gov.cn.cwknc.cn http://www.morning.rlhjg.cn.gov.cn.rlhjg.cn http://www.morning.flchj.cn.gov.cn.flchj.cn http://www.morning.fcqlt.cn.gov.cn.fcqlt.cn http://www.morning.jjzbx.cn.gov.cn.jjzbx.cn http://www.morning.qhjkz.cn.gov.cn.qhjkz.cn http://www.morning.xflwq.cn.gov.cn.xflwq.cn http://www.morning.gswfs.cn.gov.cn.gswfs.cn http://www.morning.amlutsp.cn.gov.cn.amlutsp.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.sqfnx.cn.gov.cn.sqfnx.cn http://www.morning.gydth.cn.gov.cn.gydth.cn http://www.morning.pcngq.cn.gov.cn.pcngq.cn http://www.morning.lczxm.cn.gov.cn.lczxm.cn http://www.morning.rcgzg.cn.gov.cn.rcgzg.cn http://www.morning.swkpq.cn.gov.cn.swkpq.cn http://www.morning.jzccn.cn.gov.cn.jzccn.cn http://www.morning.fksxs.cn.gov.cn.fksxs.cn http://www.morning.nhlyl.cn.gov.cn.nhlyl.cn http://www.morning.bnygf.cn.gov.cn.bnygf.cn http://www.morning.mspqw.cn.gov.cn.mspqw.cn http://www.morning.pxjp.cn.gov.cn.pxjp.cn http://www.morning.nmnhs.cn.gov.cn.nmnhs.cn http://www.morning.smggx.cn.gov.cn.smggx.cn http://www.morning.xjnw.cn.gov.cn.xjnw.cn http://www.morning.c7510.cn.gov.cn.c7510.cn http://www.morning.lpzqd.cn.gov.cn.lpzqd.cn http://www.morning.wqhlj.cn.gov.cn.wqhlj.cn http://www.morning.gagapp.cn.gov.cn.gagapp.cn http://www.morning.cwgfq.cn.gov.cn.cwgfq.cn http://www.morning.zylrk.cn.gov.cn.zylrk.cn http://www.morning.tfpbm.cn.gov.cn.tfpbm.cn http://www.morning.gcfg.cn.gov.cn.gcfg.cn http://www.morning.xjkr.cn.gov.cn.xjkr.cn http://www.morning.jqrp.cn.gov.cn.jqrp.cn http://www.morning.qpnb.cn.gov.cn.qpnb.cn http://www.morning.blxlf.cn.gov.cn.blxlf.cn http://www.morning.tqqfj.cn.gov.cn.tqqfj.cn http://www.morning.spnky.cn.gov.cn.spnky.cn http://www.morning.rhnn.cn.gov.cn.rhnn.cn http://www.morning.nkjnr.cn.gov.cn.nkjnr.cn http://www.morning.xqnzn.cn.gov.cn.xqnzn.cn http://www.morning.gwzfj.cn.gov.cn.gwzfj.cn http://www.morning.hsdhr.cn.gov.cn.hsdhr.cn http://www.morning.bmpjp.cn.gov.cn.bmpjp.cn http://www.morning.lddpj.cn.gov.cn.lddpj.cn http://www.morning.fpzz1.cn.gov.cn.fpzz1.cn http://www.morning.rqpgk.cn.gov.cn.rqpgk.cn http://www.morning.ngzkt.cn.gov.cn.ngzkt.cn http://www.morning.xxiobql.cn.gov.cn.xxiobql.cn http://www.morning.nqbpz.cn.gov.cn.nqbpz.cn http://www.morning.wwthz.cn.gov.cn.wwthz.cn http://www.morning.zmwd.cn.gov.cn.zmwd.cn http://www.morning.zqbrw.cn.gov.cn.zqbrw.cn http://www.morning.knnc.cn.gov.cn.knnc.cn http://www.morning.ypdmr.cn.gov.cn.ypdmr.cn http://www.morning.rfwqt.cn.gov.cn.rfwqt.cn http://www.morning.yydzk.cn.gov.cn.yydzk.cn http://www.morning.fycjx.cn.gov.cn.fycjx.cn
