0765. Couples Holding Hands

765. Couples Holding Hands #

题目 #

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

  1. len(row) is even and in the range of [4, 60].
  2. row is guaranteed to be a permutation of 0...len(row)-1.

题目大意 #

N 对情侣坐在连续排列的 2N 个座位上,想要牵到对方的手。 计算最少交换座位的次数,以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人,让他们站起来交换座位。人和座位用 0 到 2N-1 的整数表示,情侣们按顺序编号,第一对是 (0, 1),第二对是 (2, 3),以此类推,最后一对是 (2N-2, 2N-1)。这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

说明:

  1. len(row) 是偶数且数值在 [4, 60]范围内。
  2. 可以保证 row 是序列 0…len(row)-1 的一个全排列。

解题思路 #

  • 给出一个数组,数组里面两两相邻的元素代表一对情侣。情侣编号是从 0 开始的:0 和 1 是情侣,2 和 3 是情侣……这些情侣坐在一排,但是并非成对坐着一起的,问如何用最小的次数交换座位以后,情侣能两两坐在一起。

  • 这道题的突破口是如何找到最小的交换次数。乍一想可能没有思路。直觉告诉我们,这种难题,很可能最后推出来的结论,或者公式是一个很简单的式子。(事实此题确实是这种情况)先不考虑最小交换次数,用正常的方法来处理这道题。举个例子:【3 1 4 0 2 5】,从数组 0 下标开始往后扫。

      初始状态
        
      集合 0:0,1
      集合 1:2,3
      集合 2:4,5
    

    3 和 1 不是情侣,将 3 和 1 所在集合 union() 起来。3 所在集合是 1 ,1 所在集合是 0,将 0 和 1 号集合 union() 起来。因为情侣 0 和情侣 1 是集合 0 ,情侣 2 和情侣 3 是集合 1,以此类推。

      集合 0 和 1:0,1,2,3
      集合 2:4,5
    
  • 继续往后扫,4 和 0 不在同一个集合,4 在集合 3,0 在集合 0,那么把它们 union() 起来。

      集合 0 和 1 和 2:0,1,2,3,4,5
    

    在上面集合合并的过程中,合并了 2 次。那么就代表最少需要交换 2 次。也可以通过 len(row)/2 - uf.count 来计算。len(row)/2 是初始集合总数,uf.count 是最后剩下的集合数,两者相减就是中间交换的次数。

  • 最后实现的代码非常简单。并查集先相邻的两两元素 union() 在一起。然后扫原数组,每次扫相邻的两个,通过这两个元素值所在集合,进行 union()。扫完以后就可以得到最后的答案。

  • 回过头来看这道题,为什么我们从数组开头往后依次调整每一对情侣,这样交换的次数是最少的呢?其实这个方法的思想是贪心思想。从头开始往后一对一对的调整,就是可以最终做到次数最少。(具体证明笔者不会)交换到最后,最后一对情侣一定是正确的,无须交换。(因为前面每一对都调整完了,最后一对一定是正确的)

代码 #


package leetcode

import (
	"github.com/halfrost/LeetCode-Go/template"
)

func minSwapsCouples(row []int) int {
	if len(row)&1 == 1 {
		return 0
	}
	uf := template.UnionFind{}
	uf.Init(len(row))
	for i := 0; i < len(row)-1; i = i + 2 {
		uf.Union(i, i+1)
	}
	for i := 0; i < len(row)-1; i = i + 2 {
		if uf.Find(row[i]) != uf.Find(row[i+1]) {
			uf.Union(row[i], row[i+1])
		}
	}
	return len(row)/2 - uf.TotalCount()
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者