• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode765.情侣牵手|CouplesHoldingHands

原作者: [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:

  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:

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

示例 2:

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

说明:

  1. len(row) 是偶数且数值在 [4, 60]范围内。
  2. 可以保证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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap