三种颜色的球排列# JobHunting - 待字闺中
j*r
1 楼
有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
解法已有, 但想看看大家的想法.
如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
解法已有, 但想看看大家的想法.
a*s
2 楼
// Say you have the following
typedef enum {
red,
yellow,
blue
} Color;
const Color expectedColors[] = {Red, Yellow, Blue};
// The main loop should be something like:
for (int i = 0; i < 3N; i++) {
Color expectedColor = expectedColors[i%3];
if (getColor(i) != expectedColor) {
exchange(i, findNext(i+1, expectedColor));
}
}
int findNext(int start, Color expectedColor) {
while(getColor[start++] != expectedColor);
return start;
}
【在 j*****r 的大作中提到】
: 有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
: 如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
: 解法已有, 但想看看大家的想法.
typedef enum {
red,
yellow,
blue
} Color;
const Color expectedColors[] = {Red, Yellow, Blue};
// The main loop should be something like:
for (int i = 0; i < 3N; i++) {
Color expectedColor = expectedColors[i%3];
if (getColor(i) != expectedColor) {
exchange(i, findNext(i+1, expectedColor));
}
}
int findNext(int start, Color expectedColor) {
while(getColor[start++] != expectedColor);
return start;
}
【在 j*****r 的大作中提到】
: 有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
: 如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
: 解法已有, 但想看看大家的想法.
j*r
3 楼
这样的话, 相当于选择排序. 复杂度是O(N^2).
这问题有O(N)时间的in-place算法. 我当时想到解法, 但是写代码时加入一些防止越界
的条件判断, 代码显得冗余. 回来整理出代码, 做了测试.
不过我想知道别人在没有见过这问题的情况下, 多长时间能写出正确解答来.
【在 a**********s 的大作中提到】
: // Say you have the following
: typedef enum {
: red,
: yellow,
: blue
: } Color;
: const Color expectedColors[] = {Red, Yellow, Blue};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
这问题有O(N)时间的in-place算法. 我当时想到解法, 但是写代码时加入一些防止越界
的条件判断, 代码显得冗余. 回来整理出代码, 做了测试.
不过我想知道别人在没有见过这问题的情况下, 多长时间能写出正确解答来.
【在 a**********s 的大作中提到】
: // Say you have the following
: typedef enum {
: red,
: yellow,
: blue
: } Color;
: const Color expectedColors[] = {Red, Yellow, Blue};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
q*m
4 楼
感觉可以先sort 三色旗
【在 j*****r 的大作中提到】
: 有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
: 如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
: 解法已有, 但想看看大家的想法.
【在 j*****r 的大作中提到】
: 有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
: 如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
: 解法已有, 但想看看大家的想法.
j*r
5 楼
呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
【在 q****m 的大作中提到】
: 感觉可以先sort 三色旗
不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
【在 q****m 的大作中提到】
: 感觉可以先sort 三色旗
H*l
6 楼
sort的话in place只用exchange（i,j)有复杂度O(N)的方法么
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
o*g
7 楼
排序和排成题目要求的顺序是一样的
特点是你事先知道每个位置应该是什么颜色的。
跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
拿到位置的球，如果这个位置就应该放这个球，就看下一个。
如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
还是需要3N次就好了。
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
特点是你事先知道每个位置应该是什么颜色的。
跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
拿到位置的球，如果这个位置就应该放这个球，就看下一个。
如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
还是需要3N次就好了。
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
j*r
8 楼
算法的确如此.
不知道这个题的出处是哪里.
【在 o***g 的大作中提到】
: 排序和排成题目要求的顺序是一样的
: 特点是你事先知道每个位置应该是什么颜色的。
: 跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
: 解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
: 然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
: 拿到位置的球，如果这个位置就应该放这个球，就看下一个。
: 如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
: 交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
: 次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
: 还是需要3N次就好了。
不知道这个题的出处是哪里.
【在 o***g 的大作中提到】
: 排序和排成题目要求的顺序是一样的
: 特点是你事先知道每个位置应该是什么颜色的。
: 跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
: 解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
: 然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
: 拿到位置的球，如果这个位置就应该放这个球，就看下一个。
: 如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
: 交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
: 次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
: 还是需要3N次就好了。
f*8
9 楼
楼上的算法比较清晰，但是因为EXCHANGE的COST高于SCAN的COST，而这种算法里面
EXCHANGE的次数多了一些，可以做一些优化：
1. 针对三种颜色保存其分别在findNext中返回的位置（start[color]），并将start[
color]+1作为下次搜索的起始点；
2. 在findNext中，如果找到的下一个颜色原本就在其最终应该呆的位置上，就跳过它
，找到一个“放错位置”的该颜色的球。
【在 a**********s 的大作中提到】
: // Say you have the following
: typedef enum {
: red,
: yellow,
: blue
: } Color;
: const Color expectedColors[] = {Red, Yellow, Blue};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
EXCHANGE的次数多了一些，可以做一些优化：
1. 针对三种颜色保存其分别在findNext中返回的位置（start[color]），并将start[
color]+1作为下次搜索的起始点；
2. 在findNext中，如果找到的下一个颜色原本就在其最终应该呆的位置上，就跳过它
，找到一个“放错位置”的该颜色的球。
【在 a**********s 的大作中提到】
: // Say you have the following
: typedef enum {
: red,
: yellow,
: blue
: } Color;
: const Color expectedColors[] = {Red, Yellow, Blue};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
w*r
10 楼
先排红的， 第k个红的和位置 3k的球交换
拍黄的， 第k个黄的和位置 3k+1的球交换
拍黄的， 第k个黄的和位置 3k+1的球交换
j*r
11 楼
algorithmics的算法也可以, 不过是O(N^2).
orang的算法是O(N).
【在 f****8 的大作中提到】
: 楼上的算法比较清晰，但是因为EXCHANGE的COST高于SCAN的COST，而这种算法里面
: EXCHANGE的次数多了一些，可以做一些优化：
: 1. 针对三种颜色保存其分别在findNext中返回的位置（start[color]），并将start[
: color]+1作为下次搜索的起始点；
: 2. 在findNext中，如果找到的下一个颜色原本就在其最终应该呆的位置上，就跳过它
: ，找到一个“放错位置”的该颜色的球。
orang的算法是O(N).
【在 f****8 的大作中提到】
: 楼上的算法比较清晰，但是因为EXCHANGE的COST高于SCAN的COST，而这种算法里面
: EXCHANGE的次数多了一些，可以做一些优化：
: 1. 针对三种颜色保存其分别在findNext中返回的位置（start[color]），并将start[
: color]+1作为下次搜索的起始点；
: 2. 在findNext中，如果找到的下一个颜色原本就在其最终应该呆的位置上，就跳过它
: ，找到一个“放错位置”的该颜色的球。
j*r
12 楼
差不多. 你知道这个问题的来源吗?
【在 w****r 的大作中提到】
: 先排红的， 第k个红的和位置 3k的球交换
: 拍黄的， 第k个黄的和位置 3k+1的球交换
【在 w****r 的大作中提到】
: 先排红的， 第k个红的和位置 3k的球交换
: 拍黄的， 第k个黄的和位置 3k+1的球交换
o*g
13 楼
不知道出处
【在 j*****r 的大作中提到】
: 算法的确如此.
: 不知道这个题的出处是哪里.
【在 j*****r 的大作中提到】
: 算法的确如此.
: 不知道这个题的出处是哪里.
w*r
14 楼
一起循环似乎不可以，需要一个颜色一个颜色来， 而且只需要排2个颜色就可以了
color = ["B", "R", "R", "R", "B", "B", "G", "G", "G"]
def exchange(color, i, j):
temp = color[i]
color[i] = color[j]
color[j] = temp
def arrange(color, c, pos):
j = pos
for k in range(len(color)):
if ((color[k] == c) & (k%3 != pos)):
while (color[j] == c):
j += 3
exchange(color, k, j)
arrange(color, "R", 0)
arrange(color, "G", 1)
【在 o***g 的大作中提到】
: 排序和排成题目要求的顺序是一样的
: 特点是你事先知道每个位置应该是什么颜色的。
: 跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
: 解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
: 然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
: 拿到位置的球，如果这个位置就应该放这个球，就看下一个。
: 如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
: 交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
: 次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
: 还是需要3N次就好了。
color = ["B", "R", "R", "R", "B", "B", "G", "G", "G"]
def exchange(color, i, j):
temp = color[i]
color[i] = color[j]
color[j] = temp
def arrange(color, c, pos):
j = pos
for k in range(len(color)):
if ((color[k] == c) & (k%3 != pos)):
while (color[j] == c):
j += 3
exchange(color, k, j)
arrange(color, "R", 0)
arrange(color, "G", 1)
【在 o***g 的大作中提到】
: 排序和排成题目要求的顺序是一样的
: 特点是你事先知道每个位置应该是什么颜色的。
: 跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
: 解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
: 然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
: 拿到位置的球，如果这个位置就应该放这个球，就看下一个。
: 如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
: 交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
: 次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
: 还是需要3N次就好了。
j*r
15 楼
一个颜色一个颜色的确排2个颜色, 剩下的颜色就也对了.
一起循环也可以, 我有代码, 而且用所有全排列测试过. 可能的情况应该是:
N permutations
----------------
1 6
2 90
3 1679
4 34650
【在 w****r 的大作中提到】
: 一起循环似乎不可以，需要一个颜色一个颜色来， 而且只需要排2个颜色就可以了
: color = ["B", "R", "R", "R", "B", "B", "G", "G", "G"]
: def exchange(color, i, j):
: temp = color[i]
: color[i] = color[j]
: color[j] = temp
: def arrange(color, c, pos):
: j = pos
: for k in range(len(color)):
: if ((color[k] == c) & (k%3 != pos)):
一起循环也可以, 我有代码, 而且用所有全排列测试过. 可能的情况应该是:
N permutations
----------------
1 6
2 90
3 1679
4 34650
【在 w****r 的大作中提到】
: 一起循环似乎不可以，需要一个颜色一个颜色来， 而且只需要排2个颜色就可以了
: color = ["B", "R", "R", "R", "B", "B", "G", "G", "G"]
: def exchange(color, i, j):
: temp = color[i]
: color[i] = color[j]
: color[j] = temp
: def arrange(color, c, pos):
: j = pos
: for k in range(len(color)):
: if ((color[k] == c) & (k%3 != pos)):
j*u
16 楼
这个跟Leetcode上那道sort color是基本一样的吧..
j*r
17 楼
mm, 这个满不一样.
【在 j*******u 的大作中提到】
: 这个跟Leetcode上那道sort color是基本一样的吧..
【在 j*******u 的大作中提到】
: 这个跟Leetcode上那道sort color是基本一样的吧..
j*u
18 楼
啊，是呢，尴尬，没好好看题... :)
【在 j*****r 的大作中提到】
: mm, 这个满不一样.
【在 j*****r 的大作中提到】
: mm, 这个满不一样.
a*s
19 楼
这个很简单，findNext(i, expectedColor)的调用稍微改变一下：
// The start indices where we should look for a particular color:
int lookupIndices[] = {-1, -1, -1};
// The main loop should be something like:
for (int i = 0; i < 3N; i++) {
Color expectedColor = expectedColors[i%3];
if (getColor(i) != expectedColor) {
int indexOfExpected = findNext(
max(lookupIndices[expectedColor], i+1),
expectedColor);
exchange(i, indexOfExpected);
lookupIndices[expectedColor] = indexOfExpected + 1;
}
}
【在 j*****r 的大作中提到】
: 这样的话, 相当于选择排序. 复杂度是O(N^2).
: 这问题有O(N)时间的in-place算法. 我当时想到解法, 但是写代码时加入一些防止越界
: 的条件判断, 代码显得冗余. 回来整理出代码, 做了测试.
: 不过我想知道别人在没有见过这问题的情况下, 多长时间能写出正确解答来.
// The start indices where we should look for a particular color:
int lookupIndices[] = {-1, -1, -1};
// The main loop should be something like:
for (int i = 0; i < 3N; i++) {
Color expectedColor = expectedColors[i%3];
if (getColor(i) != expectedColor) {
int indexOfExpected = findNext(
max(lookupIndices[expectedColor], i+1),
expectedColor);
exchange(i, indexOfExpected);
lookupIndices[expectedColor] = indexOfExpected + 1;
}
}
【在 j*****r 的大作中提到】
: 这样的话, 相当于选择排序. 复杂度是O(N^2).
: 这问题有O(N)时间的in-place算法. 我当时想到解法, 但是写代码时加入一些防止越界
: 的条件判断, 代码显得冗余. 回来整理出代码, 做了测试.
: 不过我想知道别人在没有见过这问题的情况下, 多长时间能写出正确解答来.
j*r
20 楼
这个没有什么变化吧, 和刚才的算法差不多.
而且findNext()不是必要的, 直接用lookupIndices[expectedColor]就可以.
【在 a**********s 的大作中提到】
: 这个很简单，findNext(i, expectedColor)的调用稍微改变一下：
: // The start indices where we should look for a particular color:
: int lookupIndices[] = {-1, -1, -1};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
: if (getColor(i) != expectedColor) {
: int indexOfExpected = findNext(
: max(lookupIndices[expectedColor], i+1),
: expectedColor);
而且findNext()不是必要的, 直接用lookupIndices[expectedColor]就可以.
【在 a**********s 的大作中提到】
: 这个很简单，findNext(i, expectedColor)的调用稍微改变一下：
: // The start indices where we should look for a particular color:
: int lookupIndices[] = {-1, -1, -1};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
: if (getColor(i) != expectedColor) {
: int indexOfExpected = findNext(
: max(lookupIndices[expectedColor], i+1),
: expectedColor);
m*e
21 楼
先三色旗，再RGBRGB...可以的吧
从RRRRGGGGBBBB变到RGBRGBRGBRGB可以这样：
RRRRGGGGBBBB=>
RGRRRGGGBBBB=>
RGBRRGGGRBBB=>
RGBRRRGGGBBB
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
从RRRRGGGGBBBB变到RGBRGBRGBRGB可以这样：
RRRRGGGGBBBB=>
RGRRRGGGBBBB=>
RGBRRGGGRBBB=>
RGBRRRGGGBBB
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
T*u
22 楼
就是sort吧，三个指针，总指针，红指针，黄指针，总指针不能动红指针黄指针动过的
，从头开始扫，把红得放到k*3,黄的放到1+k*3，扫倒头就好了。
，从头开始扫，把红得放到k*3,黄的放到1+k*3，扫倒头就好了。
a*s
23 楼
再想想
【在 j*****r 的大作中提到】
: 这个没有什么变化吧, 和刚才的算法差不多.
: 而且findNext()不是必要的, 直接用lookupIndices[expectedColor]就可以.
【在 j*****r 的大作中提到】
: 这个没有什么变化吧, 和刚才的算法差不多.
: 而且findNext()不是必要的, 直接用lookupIndices[expectedColor]就可以.
j*r
24 楼
对, 这也可以. 算法代码已经测试通过了.
【在 m******e 的大作中提到】
: 先三色旗，再RGBRGB...可以的吧
: 从RRRRGGGGBBBB变到RGBRGBRGBRGB可以这样：
: RRRRGGGGBBBB=>
: RGRRRGGGBBBB=>
: RGBRRGGGRBBB=>
: RGBRRRGGGBBB
【在 m******e 的大作中提到】
: 先三色旗，再RGBRGB...可以的吧
: 从RRRRGGGGBBBB变到RGBRGBRGBRGB可以这样：
: RRRRGGGGBBBB=>
: RGRRRGGGBBBB=>
: RGBRRGGGRBBB=>
: RGBRRRGGGBBB
l*h
25 楼
这个题目的来源就是荷兰旗问题吧。
做荷兰旗swap的时候,保持直接插到从尾巴倒回去走的正确位置.
【在 j*****r 的大作中提到】
: 对, 这也可以. 算法代码已经测试通过了.
做荷兰旗swap的时候,保持直接插到从尾巴倒回去走的正确位置.
【在 j*****r 的大作中提到】
: 对, 这也可以. 算法代码已经测试通过了.
相关阅读
招物理的大公司有哪些？面试结束老板主动给名片[合集] 有投过GE global research的前辈么？Leetcode problems' difficultyOffer Letter 问题求解[合集] 纯谈钱，码工和教授！CPT是不是一般的学期也能申请full time的新年快乐leetcode上的populate next node I and II求facebook refer问个关于BB的问题敲程序歌请教用CPT覆盖H1-B空档的问题CPT/OPT 一问,多谢啦!备考google onsite, 讨论堆排序的时间复杂度帮着看到G家题爸说，没想到你就当了个程序员 (转载)Bloomberg电面题目+ 攒RP for onsiteamazon SDE1算什么职位？还是contractor，是难还是entry level？请问公司会不经本人同意和前雇主联系吗