英文:
Design two possible ways
问题
今天我有一个面试，在面试中我被要求设计两种方法。
情境：
我们有六个球，其中有3种黑白球的组合。
X 代表黑色球
0 代表白色球
它们排列如 X0X0X0，在这六个球之前有4个空位。
因此，最终的输入排列如下：
_ _ _ _ X 0 X 0 X 0
问题是将相邻的两个球配对移动，使得白色球在左边，黑色球在右边，只能使用三个步骤。
我完成了以下步骤
_ _ 0 X X _ _ 0 X 0
_ _ 0 X X X 0 0 _ _
0 0 0 X X X
这是一个正确的答案，但需要两个答案。我想不出第二个答案。
需要帮助吗？要求用 Java 编写。
英文:
Today I had one interview where I was asked to design two ways.
Situation:
We have six balls where 3 combinations of black and white balls are present.
X is black ball
0 is while ball
They are placed like X0X0X0 and there are 4 blanks available before these six balls.
So final input placement is below
_ _ _ _ X 0 X 0 X 0
The question was to move balls in pairs of two adjacent balls, so that white balls end on left and balck on right using three steps only.
I did below
_ _ 0 X X _ _ 0 X 0
_ _ 0 X X X 0 0 _ _
0 0 0 X X X
It was one answer which was correct, but two answers was required. I couldnt think of second.
Any help ? It was required to write in java.
答案1
得分: 2
有点晚来参加派对，但无论如何，这是一个答案，很可能也符合你的公司想要看到的内容（除了我使用了Python的事实）：
from collections import deque as deq
def solve_rec():
visited = set()
q = deq()
q.append(('----X0X0X0', 0, []))
while q:
s, c, p = q.popleft()
print(s, c, p)
if s in visited:
continue
if c == 3:
continue
visited.add(s)
for n in gen_steps(s):
q.append((n, c + 1, p + 展开收缩))
def gen_steps(state):
state = list(state)
filled_pairs = [i for i in range(len(state) - 1) if state[i] != '-' and state[i + 1] != '-']
for i in filled_pairs:
tmp = state[:]
tmp[i:i + 2] = '--';
empty_pairs = [j for j in range(len(state) - 1) if tmp[j] == '-' and tmp[j + 1] == '-' and j != i]
for j in empty_pairs:
tmp[j:j + 2] = state[i:i + 2]
yield ''.join(tmp)
tmp[j:j + 2] = '--';
solve_rec()
使用正则表达式 ^-*(X-*){3}-*(0-*){3}-* 对输出进行筛选，我们得到两个解：
000XXX---- 3 ['----X0X0X0', '--0XX--0X0', '--0XXX00--']
000X--XX-- 3 ['----X0X0X0', '--0XX0X--0', '--0X--XX00']
这是在三个步骤内可达的唯一可能状态，因此 @Andis answer 是正确的。代码中使用的算法是 广度优先搜索（Breadth-First-Search）。
英文:
Bit late to the party, but anyways, here's an answer that is most likely also along the lines of what your company wanted to see (except for the fact that I used python):
from collections import deque as deq
def solve_rec():
visited = set()
q = deq()
q.append(('----X0X0X0', 0, []))
while q:
s, c, p = q.popleft()
print(s, c, p)
if s in visited:
continue
if c == 3:
continue
visited.add(s)
for n in gen_steps(s):
q.append((n, c + 1, p + 展开收缩))
def gen_steps(state):
state = list(state)
filled_pairs = [i for i in range(len(state) - 1) if state[i] != '-' and state[i + 1] != '-']
for i in filled_pairs:
tmp = state[:]
tmp[i:i + 2] = '--'
empty_pairs = [j for j in range(len(state) - 1) if tmp[j] == '-' and tmp[j + 1] == '-' and j != i]
for j in empty_pairs:
tmp[j:j + 2] = state[i:i + 2]
yield ''.join(tmp)
tmp[j:j + 2] = '--'
solve_rec()
Filtering the output with the regex ^-*(X-*){3}-*(0-*){3}-* we get two solutions:
000XXX---- 3 ['----X0X0X0', '--0XX--0X0', '--0XXX00--']
000X--XX-- 3 ['----X0X0X0', '--0XX0X--0', '--0X--XX00']
These are the only possible states reachable within three steps, so @Andis answer is correct. The algorithm used in the code is Breadth-First-Search.
答案2
得分: 1
如果允许间隙，您可以将8和9移动到3和4，将5和6移动到8和9，然后将9和10移动到1和2。
_ _ _ _ X 0 X 0 X 0
_ _ 0 X X 0 X _ _ 0
_ _ 0 X _ _ X X 0 0
0 0 0 X _ _ X X _ _
英文:
if gaps are allowed, you can move 8&9 to 3&4, 5&6 to 8&9 and then 9&10 to 1&2.
_ _ _ _ X 0 X 0 X 0
_ _ 0 X X 0 X _ _ 0
_ _ 0 X _ _ X X 0 0
0 0 0 X _ _ X X _ _
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论