arrays - 面试题，递归+回溯

Question

这个问题是在面试中被问到的，涉及递归/回溯。假设我们有两个 bool 数组:bool* source 和 bool* target，每个数组的长度都相同 n(source/target/n作为参数给出)。该问题的目标是使用操作 switch 将source 转换为target。

• 如果有多个变换:呈现其中任何一个
• 如果无解:断言无解

定义操作 switch(int i, bool* arr) 反转 arr[i] 和 arr[i-1] 和 arr[i+1] 处的值](如果这些索引在 0...n-1 范围内)。

换句话说，switch 操作通常会翻转三个位(i 和它的邻居)，但只有两个在末尾。

例如:

• switch(0,arr) 只会切换arr[0]和arr[1]的值
• switch(n-1,arr) 只会切换arr[n-1]和arr[n-2]的值

预先感谢您对算法的建议。

Answer 1

使用回溯你可以得到 O(n) 的解决方案。为什么？

1. 在单个索引中，你最多只有一个开关
2. Swicth at index 只能改变自己和两个邻居。

从左边开始向右移动并回溯是最好的方法。

任何时候你最多只能后退两步。例如，如果您位于索引 n，则您只能更改索引 n-1，但不能更改索引 n-2，并且一次或更准确地说，当您到达索引 n+2 时，您只需检查索引 n。

您最多可以有 2 个解决方案。

解决方案(python)

def light(arr,n):
    for i in range(max([0,n-1]),min([len(arr),n+2])):
        arr[i] = not arr[i]
    return arr

goal = [True]*500
def trackback(arr,index,moves):
    if index == len(arr):
        if arr == goal:
            print(moves)
        return

    if index > 1:
        if arr[index-2] != goal[index-2]:
            return
    #print(arr,index,moves)
    #do not make switch
    trackback(arr,index+1,moves)
    #make switch
    moves=moves+[index]
    arr=light(arr,index)
    trackback(arr,index+1,moves)
    arr=light(arr,index) #undo move


arr=[False]*500
trackback(arr,0,[])

输出

[1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139, 142, 145, 148, 151, 154, 157, 160, 163, 166, 169, 172, 175, 178, 181, 184, 187, 190, 193, 196, 199, 202, 205, 208, 211, 214, 217, 220, 223, 226, 229, 232, 235, 238, 241, 244, 247, 250, 253, 256, 259, 262, 265, 268, 271, 274, 277, 280, 283, 286, 289, 292, 295, 298, 301, 304, 307, 310, 313, 316, 319, 322, 325, 328, 331, 334, 337, 340, 343, 346, 349, 352, 355, 358, 361, 364, 367, 370, 373, 376, 379, 382, 385, 388, 391, 394, 397, 400, 403, 406, 409, 412, 415, 418, 421, 424, 427, 430, 433, 436, 439, 442, 445, 448, 451, 454, 457, 460, 463, 466, 469, 472, 475, 478, 481, 484, 487, 490, 493, 496, 499]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 204, 207, 210, 213, 216, 219, 222, 225, 228, 231, 234, 237, 240, 243, 246, 249, 252, 255, 258, 261, 264, 267, 270, 273, 276, 279, 282, 285, 288, 291, 294, 297, 300, 303, 306, 309, 312, 315, 318, 321, 324, 327, 330, 333, 336, 339, 342, 345, 348, 351, 354, 357, 360, 363, 366, 369, 372, 375, 378, 381, 384, 387, 390, 393, 396, 399, 402, 405, 408, 411, 414, 417, 420, 423, 426, 429, 432, 435, 438, 441, 444, 447, 450, 453, 456, 459, 462, 465, 468, 471, 474, 477, 480, 483, 486, 489, 492, 495, 498]

您可以看到最简单的解决方案就是运行两个 for 循环。第一个解决方案设置第一个灯/开关，第二个没有。然后决定所有剩余的切换

#do not switch first light
for i in range(1,len(goal)+1):
    if goal[n-1] != arr[n-1]:
        light(arr,n)
check_solution()

#switch first light
switch(arr,n)
for i in range(1,len(goal)+1):
    if goal[n-1] != arr[n-1]:
        light(arr,n)
check_solution()