y******s
发帖数: 92 | 1 问一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么
样用minimum swap把情侣排在一起
比如：
开始：aba -> 1次
abbca-> 1次
acdaec -> 2次 |
d******b
发帖数: 73 | |
z*********8
发帖数: 2070 | 3 link?
【在 d******b 的大作中提到】
: 停车位 变体， O(n) 可以解决。
|
k**l
发帖数: 2966 | 4 abbccddeea
岂不很惨
【在 y******s 的大作中提到】
: 问一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么
: 样用minimum swap把情侣排在一起
: 比如：
: 开始：aba -> 1次
: abbca-> 1次
: acdaec -> 2次
|
b**********5
发帖数: 7881 | 5 i dont think he's correct...
【在 z*********8 的大作中提到】
: link?
|
r*******g
发帖数: 1335 | |
x********o
发帖数: 25 | 7 那个是有空车位吧?
【在 d******b 的大作中提到】
: 停车位 变体， O(n) 可以解决。
|
g*******d
发帖数: 495 | 8 abbca-> 1次
可以在一次交换当中交换任意两个？不是必须相邻座位交换？ |
y******s
发帖数: 92 | 9 对，可以随意交换
【在 g*******d 的大作中提到】
: abbca-> 1次
: 可以在一次交换当中交换任意两个？不是必须相邻座位交换？
|
k**l
发帖数: 2966 | 10 我的brutal想法是建立三个pool
pool1: singles's position
pool2: misplaced pairs a->i1, j1; b->i2, j2,不相邻
pool3: inplaced pairs
目标消灭pool2，从a开始 i1 +/-1，j1+/-1位置可以放另一个a, 这四个位置里先看有
没有singles（pool1),有就换来；如果没有，看有没有其他misplace pairs (pool2);
最后再看pool3．用pool3里的元素会导致pool3减一又加一，得弄个从左到右的固定顺
序防止死循环．
【在 y******s 的大作中提到】
: 问一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么
: 样用minimum swap把情侣排在一起
: 比如：
: 开始：aba -> 1次
: abbca-> 1次
: acdaec -> 2次
|
|
|
C*7
发帖数: 234 | 11 比较暴力的方法：两个指针分别找到对应元素，然后比较交换方式的优先级（配出两对
>不拆对>配出一对），交换元素。持续走到最后。优先级比较这块是常数级别，所以双
指针查询是O(n^2) |
x********o
发帖数: 25 | 12 这样怎么保证是一定minimum的次数?
【在 C*7 的大作中提到】
: 比较暴力的方法：两个指针分别找到对应元素，然后比较交换方式的优先级（配出两对
: >不拆对>配出一对），交换元素。持续走到最后。优先级比较这块是常数级别，所以双
: 指针查询是O(n^2)
|
x********o
发帖数: 25 | |
n****5
发帖数: 81 | 14 狗家店面都这么难了？是烙印吗？
【在 y******s 的大作中提到】
: 问一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么
: 样用minimum swap把情侣排在一起
: 比如：
: 开始：aba -> 1次
: abbca-> 1次
: acdaec -> 2次
|
n****5
发帖数: 81 | 15 狗家店面都这么难了？是烙印吗？
【在 y******s 的大作中提到】
: 问一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么
: 样用minimum swap把情侣排在一起
: 比如：
: 开始：aba -> 1次
: abbca-> 1次
: acdaec -> 2次
|
C*7
发帖数: 234 | 16 首先两个分离元素换到一起至少执行一次交换，该交换配成两对的情况一定是包含在最
优解的。唯一有更优解的情况可能是，当前交换只配成一对，而先进行其他交换可以使
当前交换配成两对。这种情况的模式为ab。。。cbca，如果用我的方法先配a对，变成
aa。。。cbcb，第二次交换可配成两对，依然是最优解。感觉要用到什么定律法则，暂
时说不上来，不是很严格的证明。当然也可能考虑不全，欢迎指正
【在 x********o 的大作中提到】
: 这样怎么保证是一定minimum的次数?
|
b**w
发帖数: 78 | 17 感觉那个算法不对吧
比如考虑abbda，应该一次就行了。但是按照它那个回朔条件或者是先换成aabdb，要不
就是bbada，然后再recurse，怎么着都得两次
【在 x********o 的大作中提到】
: http://www.geeksforgeeks.org/minimum-number-of-swaps-required-f
: 稍微修改一下回溯的条件, 考虑第一个或第二个没有配对元的情况.
|
b**w
发帖数: 78 | 18 不过好像稍微改一下，check数组的两头再来recurse就能解决了
【在 b**w 的大作中提到】
: 感觉那个算法不对吧
: 比如考虑abbda，应该一次就行了。但是按照它那个回朔条件或者是先换成aabdb，要不
: 就是bbada，然后再recurse，怎么着都得两次
|
n****5
发帖数: 81 | 19 geeksforgeeks 这个算法是O（N）的吗？swap 后对后面的做完递归，就backtrack不了
，除非把swap前的vector保留一个local拷贝，那这样递归函数的参数就不是传array的
引用而是传值了。大牛说说看我的理解错了吗？谢谢！
【在 x********o 的大作中提到】
: http://www.geeksforgeeks.org/minimum-number-of-swaps-required-f
: 稍微修改一下回溯的条件, 考虑第一个或第二个没有配对元的情况.
|
x********o
发帖数: 25 | 20 不需要存local copy，只存这个swap，backtrack要revert这个swap回到原来的样子。
前面也说了要两头都check，然后取minimum。
geeksforgeeks 这个算法是O（N）的吗？swap 后对后面的做完递归，就backtrack不了
，除非把swap前的vector保留一个local拷贝，那这样递归函数........
【在 n****5 的大作中提到】
: geeksforgeeks 这个算法是O（N）的吗？swap 后对后面的做完递归，就backtrack不了
: ，除非把swap前的vector保留一个local拷贝，那这样递归函数的参数就不是传array的
: 引用而是传值了。大牛说说看我的理解错了吗？谢谢！
|
|
|
R******e
发帖数: 94 | 21 greedy应该就可以了。
每两个配对，然后如果两个不一样就把右边那个换一下。 |
d*******s
发帖数: 65 | |
r******l
发帖数: 10760 | 23 这个不对吧？a不一定非得往i1+/-1,j1+/-1那四个位置换，有可能两个a一起换到别的
地方去呢。比如bbccaddeeaggffxy其实只需要两次就可以了，不需要拆任何对。
【在 k**l 的大作中提到】
: 我的brutal想法是建立三个pool
: pool1: singles's position
: pool2: misplaced pairs a->i1, j1; b->i2, j2,不相邻
: pool3: inplaced pairs
: 目标消灭pool2，从a开始 i1 +/-1，j1+/-1位置可以放另一个a, 这四个位置里先看有
: 没有singles（pool1),有就换来；如果没有，看有没有其他misplace pairs (pool2);
: 最后再看pool3．用pool3里的元素会导致pool3减一又加一，得弄个从左到右的固定顺
: 序防止死循环．
|
q*****q
发帖数: 100 | |
R***Z
发帖数: 1167 | 25 能否解释一下greedy怎么换这种情况：abbccddxyeeffa？目测最少只需换两次
【在 R******e 的大作中提到】
: greedy应该就可以了。
: 每两个配对，然后如果两个不一样就把右边那个换一下。
|
r******l
发帖数: 10760 | 26 扩展一下可以有好几个变种：
* 如果每个字母不一定只出现最多两次，而是可以任意多次，怎样交换让相同的字母全
都挨着？
* 如果操作不是仅限于两个字母交换，而是可以拿出任意多个字母，然后按照任意顺序
放回去。怎样才能动最少的字母达到所有相同字母都挨着的目的？ |
l*3
发帖数: 2279 | 27 作为一个刷完了leetcode的人我想说两句。
看到楼上一水的在用一些奇奇怪怪的方法解这个问题，我觉得真是一些国人的悲哀。看
到楼主这个问题，我第一反应是这样的：
电面就搞这一套？出的这什么鬼东西？是不是存心不让过？是不是哪个烙印看到老中就
开始出题乱卡人？还是哪个国人面试官想装逼故意为难同胞？以后国人碰到这种奇葩电
面怎么破解？
真心的，楼上一水的在仔细的讨论这个问题，而且很多人发言还都很不靠谱，让我十分
痛心。。。。。 |
r******l
发帖数: 10760 | 28 what's your point?
【在 l*3 的大作中提到】
: 作为一个刷完了leetcode的人我想说两句。
: 看到楼上一水的在用一些奇奇怪怪的方法解这个问题，我觉得真是一些国人的悲哀。看
: 到楼主这个问题，我第一反应是这样的：
: 电面就搞这一套？出的这什么鬼东西？是不是存心不让过？是不是哪个烙印看到老中就
: 开始出题乱卡人？还是哪个国人面试官想装逼故意为难同胞？以后国人碰到这种奇葩电
: 面怎么破解？
: 真心的，楼上一水的在仔细的讨论这个问题，而且很多人发言还都很不靠谱，让我十分
: 痛心。。。。。
|
r*******g
发帖数: 1335 | 29 然并卵
【在 l*3 的大作中提到】
: 作为一个刷完了leetcode的人我想说两句。
: 看到楼上一水的在用一些奇奇怪怪的方法解这个问题，我觉得真是一些国人的悲哀。看
: 到楼主这个问题，我第一反应是这样的：
: 电面就搞这一套？出的这什么鬼东西？是不是存心不让过？是不是哪个烙印看到老中就
: 开始出题乱卡人？还是哪个国人面试官想装逼故意为难同胞？以后国人碰到这种奇葩电
: 面怎么破解？
: 真心的，楼上一水的在仔细的讨论这个问题，而且很多人发言还都很不靠谱，让我十分
: 痛心。。。。。
|
R******e
发帖数: 94 | 30 sorry，我看题没看仔细
我以为都是成对出现不会有落单的
如果有落单的greedy确实没办法做，直接breadth first search暴力吧
【在 R***Z 的大作中提到】
: 能否解释一下greedy怎么换这种情况：abbccddxyeeffa？目测最少只需换两次
|
|
|
q*****q
发帖数: 100 | 31 他的意思是，看到大家被面试人直接或间接地涮成这样，感到很纠结。
【在 r******l 的大作中提到】
: what's your point?
|
l*3
发帖数: 2279 | 32 深得我心
【在 q*****q 的大作中提到】
: 他的意思是，看到大家被面试人直接或间接地涮成这样，感到很纠结。
|
r******l
发帖数: 10760 | 33 他说了半天话，一点有用的都没有。
【在 q*****q 的大作中提到】
: 他的意思是，看到大家被面试人直接或间接地涮成这样，感到很纠结。
|
q*****q
发帖数: 100 | 34 哥哥耐心点。。。看他写的这个，你得从稀的里捞点干的出来。
你理解能力欠佳！哈哈哈哈！
【在 r******l 的大作中提到】
: 他说了半天话，一点有用的都没有。
|
q*****q
发帖数: 100 | 35 嗯，你表达能力欠佳，他理解能力欠佳。。。
哈哈哈哈 开心！
【在 l*3 的大作中提到】
: 深得我心
|
