N 对情侣坐在连续排列的 2N 个座位上,想要牵到对方的手。 计算最少交换座位的次数,以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人,让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示,情侣们按顺序编号,第一对是 (0, 1),第二对是 (2, 3),以此类推,最后一对是 (2N-2, 2N-1)。
leetcode第一题c语言?这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
示例 1:
输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。
示例 2:
输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位,所有的情侣都已经可以手牵手了。
leetcode c++,说明:
贪心算法
我们依次遍历偶数下标的位置,我们每次移动都保证让当前情侣进行牵手。详细过程见代码
int minSwapsCouples(vector<int>& row) {int n = row.size();int ans = 0;for(int i=0; i<n; i+=2){int id = row[i]^1; //row[i]的情侣idif(row[i+1] == id) continue; //本来就牵手了,不需要移动ans++;for(int j=i+2; j<n; j++){ //让id坐到i+1的位置上if(row[j] == id){row[j] = row[i+1];row[i+1] = id;break;}}}return ans;}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/couples-holding-hands
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态