没有输出的输入是不完整的

0%

leetcode-765-CouplesHoldingHands

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

情侣换座位手牵手的题目。
思想有点像打气球那个题目：处理好当下的问题，慢慢往后遍历，以后的问题也会变得很顺利，回头还会发现这其实就是最好的方法。

题目描述

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

Example 1

1
2
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

1
2
Input: row = [3, 2, 0, 1]
Output: 0

Explanation: All couples are already seated side by side.

解题思路

贪心算法。

详细解释

如果我们仔细看就会发现，其实我们在判断的时候只要确定了两个数中的一个，那么另外一个数是多少其实就是已经确定好了的，然后我们将这个数本身所在的位置替换掉就可以了。比如说下面的例子，第一个元素是5，那么第二个元素必然是6，我们只要找到6，然后将6本身所在的位置的数字替换成第二个元素本身的元素4就可以了。
以题目中的某个用例来进行说明

1
2
3
4
5
6
7
初始数组：[5,6,4,0,2,1,9,3,8,7,10,11]
i= 0: 5 4   6   0   2   1   9   3   8   7   10  11  
i= 2: 5 4   6   7   2   1   9   3   8   0   10  11  
i= 4: 5 4   6   7   2   3   9   1   8   0   10  11  
i= 6: 5 4   6   7   2   3   9   8   1   0   10  11  
i= 8: 5 4   6   7   2   3   9   8   1   0   10  11  
i=10: 5 4   6   7   2   3   9   8   1   0   10  11

巧妙之处

  1. 大道至简，大智若愚。从头开始，每次都做好当前元素的判断，那么后面的元素都会依次的处理好。
  2. 对于当前位置要进行奇偶判断，因为不确定配偶的左右情况，所以要自行判断。
  3. 要会使用stl中的各种比较巧妙的方法，比如本题目中用到的find和distance。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        if(row.size() <=  2) return 0;
        int res = 0;
        for(int i = 0; i < row.size(); i += 2){
            if(row[i]%2 == 0){
                if(row[i+1] == row[i]+1){
                    continue;
                }else{
                    res++;
                    auto a = find(row.begin(),row.end(),row[i]+1);
                    int index = distance(row.begin(),a);
                    row[index] = row[i+1];
                    row[i+1] = row[i]+1;
                }
            }else{
                if(row[i+1] == row[i]-1){
                    continue;
                }else{
                    res++;
                    auto a = find(row.begin(),row.end(),row[i]-1);
                    int index = distance(row.begin(),a);
                    row[index] = row[i+1];
                    row[i+1] = row[i]-1;
                }
            }
        }
        return res;
    }
};

以上，本题结束！