[Swift]LeetCode765.情侣牵手|CouplesHoldingHands

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10533329.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 swapconsists 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:

len(row) is even and in the range of [4, 60].
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:

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

示例 2:

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

说明:

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

Runtime: 8 ms

Memory Usage: 19.1 MB

 1 class Solution {
 2     func minSwapsCouples(_ row: [Int]) -> Int {
 3         var row = row
 4         var res:Int = 0
 5         var n:Int = row.count
 6         for i in stride(from:0,to:n,by:2)
 7         {
 8             if row[i + 1] == (row[i] ^ 1)
 9             {
10                 continue            
11             }
12             res += 1
13             for j in (i + 1)..<n
14             {
15                 if row[j] == (row[i] ^ 1)
16                 {
17                     row[j] = row[i + 1]
18                     row[i + 1] = row[i] ^ 1
19                     break
20                 }
21             }
22         }
23         return res
24     }
25 }

8ms

 1 class Solution {
 2     func minSwapsCouples(_ row: [Int]) -> Int {
 3         guard row.count > 2 else {
 4             return 0 
 5         }
 6         var row = row 
 7         var numberOfSwaps: Int = 0 
 8         for seat in stride(from:0, to: row.count - 1, by: 2) {
 9             let current = row[seat]
10             let other = row[seat + 1]
11             if current == other ^ 1 { continue }
12             numberOfSwaps += 1 
13             for j in (seat+2)..<row.count {
14                 if row[j] == current ^ 1 {
15                     row.swapAt(j, seat + 1)
16                 }
17             }
18         }
19         return numberOfSwaps
20     }
21 }

12ms

 1 class Solution {
 2     func minSwapsCouples(_ row: [Int]) -> Int {
 3         var row = row
 4         var res = 0
 5         for i in 0..<row.count {
 6             guard i % 2 == 0 else { continue }
 7             let target = row[i] % 2 == 0 ? row[i] + 1 : row[i] - 1
 8             if row[i + 1] == target { continue }
 9             for j in i+2..<row.count {
10                 if row[j] == target {
11                     (row[i+1], row[j]) = (row[j], row[i+1])
12                     res += 1
13                 }
14             }
15         }
16         return res
17     }
18 }