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 的大作中提到】 : 深得我心
|