最短的字符串嘗試所有3位數字鎖

我在最近的一次採訪中被問到了這個問題。三位數的鎖可以具有在「000」 - 「999」範圍之間的鍵值。所以基本上有1000個組合必須嘗試打開鎖。所以我必須生成最短的字符串，以便檢查所有可能的組合（即在「000」 - 「999」之間）。例如，如果我們有字符串「」，那麼它會檢查組合「012」，「123」和「234」。所以我必須生成一個可以檢查所有組合的字符串。我嘗試使用一個哈希集來實現這一點，我從「000」開始，然後把字符串中的最後兩個字符，即「00」，然後附加一個從0到9的新數字，並檢查它是否存在於哈希集中。如果沒有，我將該數字附加到輸出字符串並重復該過程。有沒有其他有效和乾淨的方法來解決這個問題。最短的字符串嘗試所有3位數字鎖

來源

2015-10-13 Ram Swami

https://en.wikipedia.org/wiki/De_Bruijn_sequence（Python程序出現在文章的末尾。） – rici

除非那項工作是在一個非常具體的環境中，那對我來說這似乎是一個奇怪的面試問題。在幾分鐘內提出並不是一個簡單的算法，因此問題只是測試，看看您是否在教育的某個階段偶然發現了這個概念。當然，在組合學中有實際的應用，所以如果工作涉及到這個領域，我想看看申請人是否認識到這種模式可能很有趣。（雖然你可以直接問:)） – rici

是的De_Bruijn序列看起來與問題陳述類似。謝謝 –

您描述的過程是基於這樣的假設，即最短的字符串只有一次代碼。事實證明，這個假設是正確的。下面是一個簡單的回溯實現（C++）：

#include <stdio.h> 

bool used[1000]; 
int digits[33333]; 

bool backtrack(int index, int total) 
{ 
    if (total == 1000) 
    { 
     printf("%d\n", index); 
     for (int i = 0; i < index; ++i) { 
      printf("%d", digits[i]); 
     } 
     printf("\n"); 
     return true; 
    } 

    for (int d = 0; d < 10; ++d) 
    { 
     int prev = 100*digits[index-2]+10*digits[index-1]+d; 
     if (!used[prev]) { 
      digits[index] = d; 
      used[prev] = true; 
      if (backtrack(index+1, total+1)) 
       return true; 
      used[prev] = false; 
     } 
    } 
} 

int main(void) { 
    digits[0] = 0; 
    backtrack(2, 0); 
    return 0; 
}

輸出：

1002 
00010020030040050060070080090110120130140150160170\ 
18019021022023024025026027028029031032033034035036\ 
03703803904104204304404504604704804905105205305405\ 
50560570580590610620630640650660670680690710720730\ 
74075076077078079081082083084085086087088089091092\ 
09309409509609709809911121131141151161171181191221\ 
23124125126127128129132133134135136137138139142143\ 
14414514614714814915215315415515615715815916216316\ 
41651661671681691721731741751761771781791821831841\ 
85186187188189192193194195196197198199222322422522\ 
62272282292332342352362372382392432442452462472482\ 
49253254255256257258259263264265266267268269273274\ 
27527627727827928328428528628728828929329429529629\ 
72982993334335336337338339344345346347348349354355\ 
35635735835936436536636736836937437537637737837938\ 
43853863873883893943953963973983994445446447448449\ 
45545645745845946546646746846947547647747847948548\ 
64874884894954964974984995556557558559566567568569\ 
57657757857958658758858959659759859966676686696776\ 
78679687688689697698699777877978878979879988898999\ 
00

的過程是有效的。

來源

2015-10-13 21:24:35 svs

最短的字符串嘗試所有3位數字鎖

回答

相關問題