11

与えられたマッピング:

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

数値を表現できるすべての可能な方法を見つけます。たとえば、入力「121」の場合、次のように表すことができます。

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

ある種の動的計画法のアプローチを使用することを考えてみましたが、どのように進めればよいかわかりません。技術面接でこんな質問をされました。

これが私が考えることができる解決策です、これが良さそうなら私に知らせてください：

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

解決策 [何か不足していますか?]:

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]
4

11 に答える 11

5

カウントを取得するためだけに、動的計画法のアプローチは非常に簡単です。

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];

代わりにすべての表現をリストしたい場合、動的計画法はこれには特に適していません。単純な再帰アルゴリズムを使用する方がよいでしょう。

于 2013-07-31T11:48:19.330 に答える
1

ここでの私の議論に基づく解決策は次のとおりです。

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];
}
于 2013-08-05T02:22:35.930 に答える
1

このようなもの？

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)

出力：

*Main> combs "121"
["LA","AU","ABA"]
于 2013-08-01T18:33:55.750 に答える
0

私たちだけが幅優先検索です。

たとえば 121

最初の整数から開始し、最初に 1 つの整数文字を考慮し、1 を a にマップし、21 を残し、次に 2 つの整数文字を L にマップし、1 を残します。

于 2013-07-31T06:00:02.837 に答える