Znajdź wszystkie możliwe kombinacje znaków reprezentujący numer

Question

Given mapowanie:

A: 1 
B: 2 
C: 3 
... 
... 
... 
Z: 26 

Znajdź wszystkie możliwe sposoby liczba może być reprezentowana. Na przykład. Dla wejścia: „121”, możemy reprezentować go jako:

ABA [using: 1 2 1] 
LA [using: 12 1] 
AU [using: 1 21] 

próbowałem myśleć o użyciu jakiegoś dynamicznego podejścia do programowania, ale nie jestem pewien, jak postępować. Zadano mi to pytanie w wywiadzie technicznym.

Oto rozwiązanie mogłem pomyśleć, proszę dać mi znać, jeśli to wygląda dobrze: [? Mi brakuje czegoś]

A[i]: Total number of ways to represent the sub-array number[0..i-1] using the integer to alphabet mapping. 

Rozwiązanie:

A[0] = 1 // there is only 1 way to represent the subarray consisting of only 1 number 
for(i = 1:A.size): 
    A[i] = A[i-1] 
    if(input[i-1]*10 + input[i] < 26): 
     A[i] += 1 
    end 
end 
print A[A.size-1] 

Answer 1

po prostu uzyskać zliczania, programowanie dynamiczne podejście jest całkiem prosta:

A[0] = 1 
for i = 1:n 
    A[i] = 0 
    if input[i-1] > 0       // avoid 0 
    A[i] += A[i-1]; 
    if i > 1 &&       // avoid index-out-of-bounds on i = 1 
     10 <= (10*input[i-2] + input[i-1]) <= 26 // check that number is 10-26 
    A[i] += A[i-2]; 

Jeśli zamiast tego chcesz wymienić wszystkie reprezentacje, programowanie dynamiczne nie jest szczególnie dobrze nadaje się do tego, ty” lepiej z prostym algorytmem rekursywnym.

Answer 2

Wystarczy nam wszerz Szukaj.

na przykład 121

Rozpocznij od pierwszej liczby całkowitej, rozważyć całkowitą 1 pierwszego znaku, mapa 1 do a, pozostawić 21 następnie 2 całkowitą mapę znaków 12 L do urlopu 1.

Answer 3

pierwsze, musimy znaleźć intuicyjny sposób wyliczenia wszystkich możliwości. Moja prosta konstrukcja jest podana poniżej.

let us assume a simple way to represent your integer in string format. 

    a1 a2 a3 a4 ....an, for instance in 121 a1 -> 1 a2 -> 2, a3 -> 1 

Teraz

Musimy dowiedzieć się szereg możliwości umieszczenia + znak pomiędzy dwoma znakami. + oznacza tu łączenie znaków.

a1 - a2 - a3 - .... - an, - shows the places where '+' can be placed. So, number of positions is n - 1, where n is the string length. 

Przyjmij, że pozycja może mieć lub nie znak +, będzie reprezentowana jako bit. Sprowadza się to do tego, ile różnych ciągów bitów jest możliwych z długością n-1, co jest oczywiście 2^(n-1). Teraz, aby wyliczyć możliwości przejść przez każdy ciągu bitów i umieścić odpowiednie znaki + w odpowiednich pozycjach, aby uzyskać co reprezentacje,

Dla przykładu, 121

Four bit strings are possible 00 01 10 11 
    1 2 1 
    1 2 + 1 
    1 + 2 1 
    1 + 2 + 1 

    And if you see a character followed by a +, just add the next char with the current one and do it sequentially to get the representation, 

x + y z a + b + c d 

would be (x+y) z (a+b+c) d 

Nadzieję, że to pomaga.

I będziesz musiał zająć się poważnymi przypadkami, w których rozmiar pewnej liczby całkowitej> 26, oczywiście.

Answer 4

myślę, rekurencyjne trawers przez wszystkie możliwe kombinacje zrobi dobrze:

mapping = {"1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G", 
"8":"H", "9":"I", "10":"J", 
"11":"K", "12":"L", "13":"M", "14":"N", "15":"O", "16":"P", 
"17":"Q", "18":"R", "19":"S", "20":"T", "21":"U", "22":"V", "23":"W", 
"24":"A", "25":"Y", "26":"Z"} 

def represent(A, B): 
    if A == B == '': 
     return [""] 
    ret = [] 
    if A in mapping: 
     ret += [mapping[A] + r for r in represent(B, '')] 
    if len(A) > 1: 
     ret += represent(A[:-1], A[-1]+B) 
    return ret 

print represent("121", "") 

Answer 5

Zakładając, wystarczy policzyć liczbę kombinacji.

Zakładając 0, a następnie przez liczbę całkowitą w [1,9] nie jest ważny konkatenacji, a strategia siłowych będzie:

Count(s,n) 
    x=0 
    if (s[n-1] is valid) 
     x=Count(s,n-1) 
    y=0 
    if (s[n-2] concat s[n-1] is valid) 
     y=Count(s,n-2) 
    return x+y 

Lepszą strategią byłoby użyć dziel i przejęcie roztwór do

Count(s,start,n) 
    if (len is even) 
    { 
     //split s into equal left and right part, total count is left count multiply right count 
     x=Count(s,start,n/2) + Count(s,start+n/2,n/2); 
     y=0; 
     if (s[start+len/2-1] concat s[start+len/2] is valid) 
     { 
      //if middle two charaters concatenation is valid 
      //count left of the middle two characters 
      //count right of the middle two characters 
      //multiply the two counts and add to existing count 
      y=Count(s,start,len/2-1)*Count(s,start+len/2+1,len/2-1); 
     } 
     return x+y; 
    } 
    else 
    { 
     //there are three cases here: 

     //case 1: if middle character is valid, 
     //then count everything to the left of the middle character, 
     //count everything to the right of the middle character, 
     //multiply the two, assign to x 
     x=... 

     //case 2: if middle character concatenates the one to the left is valid, 
     //then count everything to the left of these two characters 
     //count everything to the right of these two characters 
     //multiply the two, assign to y 
     y=... 

     //case 3: if middle character concatenates the one to the right is valid, 
     //then count everything to the left of these two characters 
     //count everything to the right of these two characters 
     //multiply the two, assign to z 
     z=... 

     return x+y+z; 
    } 

siłowych ma czas złożoność T(n)=T(n-1)+T(n-2)+O(1) który jest wykładniczy.

Rozwiązanie typu "dziel i zwyciężaj" ma złożoność czasową wynoszącą T(n)=3T(n/2)+O(1), która wynosi O (n ** lg3).

Mam nadzieję, że to jest poprawne.

Answer 6

Coś takiego? Kod

Haskell:

import qualified Data.Map as M 
import Data.Maybe (fromJust) 

combs str = f str [] where 
    charMap = M.fromList $ zip (map show [1..]) ['A'..'Z'] 
    f []  result = [reverse result] 
    f (x:xs) result 
    | null xs = 
     case M.lookup [x] charMap of 
      Nothing -> ["The character " ++ [x] ++ " is not in the map."] 
      Just a -> [reverse $ a:result] 
    | otherwise = 
     case M.lookup [x,head xs] charMap of 
      Just a -> f (tail xs) (a:result) 
       ++ (f xs ((fromJust $ M.lookup [x] charMap):result)) 
      Nothing -> case M.lookup [x] charMap of 
         Nothing -> ["The character " ++ [x] 
           ++ " is not in the map."] 
         Just a -> f xs (a:result) 

wyjściowa:

*Main> combs "121" 
["LA","AU","ABA"] 

Answer 7

Oto rozwiązanie oparte na mojej dyskusji tutaj:

private static int decoder2(int[] input) { 
    int[] A = new int[input.length + 1]; 
    A[0] = 1; 

    for(int i=1; i<input.length+1; i++) { 
     A[i] = 0; 
     if(input[i-1] > 0) { 
     A[i] += A[i-1]; 
     } 
     if (i > 1 && (10*input[i-2] + input[i-1]) <= 26) { 
     A[i] += A[i-2]; 
     } 
     System.out.println(A[i]); 
    } 
    return A[input.length]; 
} 

Answer 8

Problem ten można zrobić w czasie O (fib (n + 2)) czasu ze standardowym algorytmem DP. Mamy dokładnie n podrzędnych problemów i przycisk do góry możemy rozwiązać każdy problem o rozmiarze i w o (fib (i)) czasie. Podsumowując serię daje fib (n + 2).

Jeśli weźmiesz pod uwagę to pytanie, zobaczysz, że jest to seria Fibonacciego. Wziąłem standardowy kod Fibonacciego i po prostu zmieniłem go, aby pasował do naszych warunków.

Miejsce jest oczywiście związane z rozmiarem wszystkich rozwiązań o (fib (n)).

Rozważmy następujący pseudo kod:

Map<Integer, String> mapping = new HashMap<Integer, String>(); 

List<String > iterative_fib_sequence(string input) { 
    int length = input.length; 
    if (length <= 1) 
    { 
     if (length==0) 
     { 
      return ""; 
     } 
     else//input is a-j 
     { 
      return mapping.get(input); 
     } 
    } 
    List<String> b = new List<String>(); 
    List<String> a = new List<String>(mapping.get(input.substring(0,0)); 
    List<String> c = new List<String>(); 

    for (int i = 1; i < length; ++i) 
    { 
     int dig2Prefix = input.substring(i-1, i); //Get a letter with 2 digit (k-z) 
     if (mapping.contains(dig2Prefix)) 
     { 
      String word2Prefix = mapping.get(dig2Prefix);   
      foreach (String s in b) 
      { 
       c.Add(s.append(word2Prefix)); 
      } 
     } 

     int dig1Prefix = input.substring(i, i); //Get a letter with 1 digit (a-j) 
     String word1Prefix = mapping.get(dig1Prefix);   
     foreach (String s in a) 
     { 
      c.Add(s.append(word1Prefix)); 
     } 

     b = a; 
     a = c; 
     c = new List<String>(); 
    } 
    return a; 
}