2 日後に面接がありますが、この質問の解決策を見つけるのに非常に苦労しています。私がやりたいことは、.. 任意の電話番号について.. プログラムは、それが表すすべての可能な文字列を出力する必要があります。例) 数字の 2 は 'a' または 'b' または 'c' に、3 は 'd' 'e' 'f' などに置き換えることができます。与えられた電話番号。誰にもコードを書いてほしくありません...優れたアルゴリズムまたは疑似コードがあれば素晴らしいでしょう。
ありがとうございました
11137 次
10 に答える
8
これは一般的な対応表です。
d = { '2': "ABC",
'3': "DEF",
'4': "GHI",
'5': "JKL",
'6': "MNO",
'7': "PQRS",
'8': "TUV",
'9': "WXYZ",
}
これまたはその他dの (実行可能な) 擬似コードを指定して、数字の文字列を可能なすべての文字列に変換します。
def digstolets(digs):
if len(digs) == 0:
yield ''
return
first, rest = digs[0], digs[1:]
if first not in d:
for x in digstolets(rest): yield first + x
return
else:
for x in d[first]:
for y in digstolets(rest): yield x + y
2間にない入力文字列内の文字に対して何をしたいかによって微調整できます9(このバージョンはそれらをエコーアウトするだけです!-)。
例えば、
print list(digstolets('1234'))
このバージョンでは
['1ADG', '1ADH', '1ADI', '1AEG', '1AEH', '1AEI', '1AFG', '1AFH', '1AFI',
'1BDG', '1BDH', '1BDI', '1BEG', '1BEH', '1BEI', '1BFG', '1BFH', '1BFI',
'1CDG', '1CDH', '1CDI', '1CEG', '1CEH', '1CEI', '1CFG', '1CFH', '1CFI']
編集：OPはさらに説明を求めます。ここに試みがあります。関数digstolets(数字から文字へ) は数字の文字列を取り、digs文字または「数字以外」の一連の文字列を生成します。 0スペースや1句読点がそうでないのと同じように、数字は文字に展開されないため、ここでは数字以外としてカウントされます。数字のみが文字2に展開9されます (ほとんどの場合、それぞれ 3 つの可能性があり、2 つの場合は 4 つです。および7のいずれかに展開できます)。PQRS9WXYZ
まず、基本的なケース: 何も残っていない (文字列digsが空である) 場合、可能な結果は空の文字列だけであり、それだけで、この再帰呼び出しは完了し、終了し、kaput になります。
が空でない場合digs、最初の文字である「頭」と残りのすべて (最初の文字の後に 0 文字以上) の「尾」に分割できます。
「頭」は、数字以外の場合、出力にそのまま残ります。または、数字の場合、3 つまたは 4 つの可能性のいずれかに展開されます。どちらの場合でも、頭の 1 つ、3 つ、または 4 つの可能な展開を、可能なすべての尾部の展開と連結する必要があります。つまり、再帰呼び出しで、可能なすべての尾部の展開を取得します (したがって、可能なすべての展開をループします)。テールの拡張、およびテールの各可能な拡張と連結されたヘッドの 1 つ、3 つ、または 4 つの可能な拡張のそれぞれを生成します)。そして、もう一度、これで終わりです。
これをこれ以上初歩的な言葉で表現する方法がわかりません.OPがこの後も失われている場合は、再帰に関するすべての真剣で完全なレビューをお勧めすることしかできません. 明示的に維持されたスタックを優先して再帰を削除しても、この概念的な説明を単純化することはできません-関連する言語によっては (OP が完全に快適な言語について聞いてみるのもいいでしょう!)、再帰の削除は重要な最適化になる可能性がありますが、それは決して概念的な単純化ではありません...!-)
于 2009-12-05T05:55:02.450 に答える
2
Java の別のバージョン。
最初に、電話番号の各桁に基づいて文字配列を選択します。次に、再帰を使用して、可能なすべての順列を生成します。
public class PhonePermutations {
public static void main(String[] args) {
char[][] letters =
{{'0'},{'1'},{'A','B','C'},{'D','E','F'},{'G','H','I'},{'J','K','L'},
{'M','N','O'},{'P','Q','R','S'},{'T','U','V'},{'W','X','Y','Z'}};
String n = "1234";
char[][] sel = new char[n.length()][];
for (int i = 0; i < n.length(); i++) {
int digit = Integer.parseInt("" +n.charAt(i));
sel[i] = letters[digit];
}
permutations(sel, 0, "");
}
public static void permutations(char[][] symbols, int n, String s) {
if (n == symbols.length) {
System.out.println(s);
return;
}
for (int i = 0; i < symbols[n].length; i ++) {
permutations(symbols, n+1, s + symbols[n][i]);
}
}
}
于 2012-05-19T13:38:27.983 に答える
2
インタビューでこれを聞かれたら、まず問題を分解するところから始めます。あなたが解決しなければならない問題は何ですか？
まず、数字を一連の文字にマップする必要があります。一部の数字は、異なる文字数にマップされます。そのため、そのデータを保存する方法を理解することから始めます。基本的に、文字のコレクションへの数字のマップが必要です。
1 桁の数字のすべての「単語」をどのように生成しますか? 基本的に、特定の数値にマップされたコレクションを反復処理する方法。また、可能性はいくつありますか？
OK、次のステップは、2 つの数字があり、すべての単語を生成したいということです。手動で行う場合、これをどのように行いますか? 最初の数字は最初の文字から、2 番目の数字は最初の文字から始めます。次に、2 番目の数字の次の文字に移動し、最初の文字を最初の文字として保持します (基本的に、それぞれが 3 文字にマップされる 2 つの数字のコレクションへのインデックス)。
00,01,02,10,11,12,20,21,22
では、その一連の数字をコードでどのように生成するのでしょうか?
それができたら、それをコードに変換するのは簡単です。
幸運を！
于 2009-12-06T05:10:03.027 に答える
1
これが私が思いついたものです：
import java.util.*;
public class PhoneMmemonics {
/**
* Mapping between a digit and the characters it represents
*/
private static Map<Character,List<Character>> numberToCharacters = new HashMap<Character,List<Character>>();
static {
numberToCharacters.put('0',new ArrayList<Character>(Arrays.asList('0')));
numberToCharacters.put('1',new ArrayList<Character>(Arrays.asList('1')));
numberToCharacters.put('2',new ArrayList<Character>(Arrays.asList('A','B','C')));
numberToCharacters.put('3',new ArrayList<Character>(Arrays.asList('D','E','F')));
numberToCharacters.put('4',new ArrayList<Character>(Arrays.asList('G','H','I')));
numberToCharacters.put('5',new ArrayList<Character>(Arrays.asList('J','K','L')));
numberToCharacters.put('6',new ArrayList<Character>(Arrays.asList('M','N','O')));
numberToCharacters.put('7',new ArrayList<Character>(Arrays.asList('P','Q','R')));
numberToCharacters.put('8',new ArrayList<Character>(Arrays.asList('T','U','V')));
numberToCharacters.put('9',new ArrayList<Character>(Arrays.asList('W','X','Y','Z')));
}
/**
* Generates a list of all the mmemonics that can exists for the number
* @param phoneNumber
* @return
*/
public static List<String> getMmemonics(int phoneNumber) {
// prepare results
StringBuilder stringBuffer = new StringBuilder();
List<String> results = new ArrayList<String>();
// generate all the mmenonics
generateMmemonics(Integer.toString(phoneNumber), stringBuffer, results);
// return results
return results;
}
/**
* Recursive helper method to generate all mmemonics
*
* @param partialPhoneNumber Numbers in the phone number that haven't converted to characters yet
* @param partialMmemonic The partial word that we have come up with so far
* @param results total list of all results of complete mmemonics
*/
private static void generateMmemonics(String partialPhoneNumber, StringBuilder partialMmemonic, List<String> results) {
// are we there yet?
if (partialPhoneNumber.length() == 0) {
//Printing the pnemmonics
//System.out.println(partialMmemonic.toString());
// base case: so add the mmemonic is complete
results.add(partialMmemonic.toString());
return;
}
// prepare variables for recursion
int currentPartialLength = partialMmemonic.length();
char firstNumber = partialPhoneNumber.charAt(0);
String remainingNumbers = partialPhoneNumber.substring(1);
// for each character that the single number represents
for(Character singleCharacter : numberToCharacters.get(firstNumber)) {
// append single character to our partial mmemonic so far
// and recurse down with the remaining characters
partialMmemonic.setLength(currentPartialLength);
generateMmemonics(remainingNumbers, partialMmemonic.append(singleCharacter), results);
}
}
}
于 2009-12-06T21:40:16.720 に答える
1
これは数え上げの問題なので、通常は小さな問題の解決策を見つけてから、それが一般的なケースにどのように展開されるかを考えると役立ちます。
1桁の電話番号がある場合、可能性はいくつありますか? 2桁だったら？どのようにして一方から他方へ移動したのですか? n桁についてそれを解く方法を思いつきましたか?
于 2009-12-05T05:41:46.450 に答える
0
#include <sstream>
#include <map>
#include <vector>
map< int, string> keyMap;
void MakeCombinations( string first, string joinThis , vector<string>& eachResult )
{
if( !first.size() )
return;
int length = joinThis.length();
vector<string> result;
while( length )
{
string each;
char firstCharacter = first.at(0);
each = firstCharacter;
each += joinThis[length -1];
length--;
result.push_back(each);
}
first = first.substr(1);
vector<string>::iterator begin = result.begin();
vector<string>::iterator end = result.end();
while( begin != end)
{
eachResult.push_back( *begin);
begin++;
}
return MakeCombinations( first, joinThis, eachResult);
}
void ProduceCombinations( int inNumber, vector<string>& result)
{
vector<string> inputUnits;
vector<string> finalres;
int number = inNumber;
while( number )
{
int lastdigit ;
lastdigit = number % 10;
number = number/10;
inputUnits.push_back( keyMap[lastdigit]);
}
if( inputUnits.size() == 2)
{
MakeCombinations(inputUnits[0], inputUnits[1], result);
}
else if ( inputUnits.size() > 2 )
{
MakeCombinations( inputUnits[0] , inputUnits[1], result);
vector<string>::iterator begin = inputUnits.begin();
vector<string>::iterator end = inputUnits.end();
begin += 2;
while( begin != end )
{
vector<string> intermediate = result;
vector<string>::iterator ibegin = intermediate.begin();
vector<string>::iterator iend = intermediate.end();
while( ibegin != iend)
{
MakeCombinations( *ibegin , *begin, result);
//resultbegin =
ibegin++;
}
begin++;
}
}
else
{
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
keyMap[1] = "";
keyMap[2] = "abc";
keyMap[3] = "def";
keyMap[4] = "ghi";
keyMap[5] = "jkl";
keyMap[6] = "mno";
keyMap[7] = "pqrs";
keyMap[8] = "tuv";
keyMap[9] = "wxyz";
keyMap[0] = "";
string inputStr;
getline(cin, inputStr);
int number = 0;
int length = inputStr.length();
int tens = 1;
while( length )
{
number += tens*(inputStr[length -1] - '0');
length--;
tens *= 10;
}
vector<string> r;
ProduceCombinations(number, r);
cout << "[" ;
vector<string>::iterator begin = r.begin();
vector<string>::iterator end = r.end();
while ( begin != end)
{
cout << *begin << "," ;
begin++;
}
cout << "]" ;
return 0;
}
于 2012-06-02T11:53:49.877 に答える
0
再帰と適切なデータ構造を使用して、可能な文字を保持します。数値を話しているので、配列の配列が機能します。
char[][] toChar = {{'0'}, {'1'}, {'2', 'A', 'B', 'C'}, ..., {'9', 'W' 、 'バツ'。'Y'} };
この配列の配列の i 番目の配列は、電話の i 番目のボタンに対応する文字を保持していることに注意してください。つまり、tochar[2][0] は「2」、tochar[2][1] は「A」などです。
再帰関数はインデックスをパラメーターとして受け取ります。置換文字を反復処理する for ループがあり、そのインデックスの文字を配列の文字に置き換えます。長さが入力文字列の長さと等しい場合、文字列を出力します。
Java または C# では、変化する文字列を保持するために文字列バッファーを使用する必要があります。
function recur(index)
if (index == input.length) output stringbuffer
else
for (i = 0; i < tochar[input[index]].length; i++)
stringbuffer[index] = tochar[input[index]][i]
recur(index + 1)
于 2009-12-05T06:55:25.127 に答える
0
私の頭に浮かぶ質問は、そのようなシステムで 0 と 1 がどうなるかという質問です。そうでなければ、あなたが持っているものは、基本的に2から9の範囲の各値の文字を再帰的に調べて、単純な力ずくの方法ですべての値を大量生産することができるものです.
北米内の通常の電話番号の長さを想定し、最初に特別な市外局番を無視すると、7 と 9 はしばしば使用されない文字 Q と Z を取得する傾向があるため、3 ではなく 4 の値を表す桁数の問題もあります。 3^10 = 59,049 から 4^10 = 1,048,576。後者は 1024 の 2 乗です。
于 2009-12-09T19:33:46.827 に答える
0
C プログラム:
char *str[] = {"0", "1", "2abc", "3def", "4ghi", "5jkl", "6mno", "7pqrs", "8tuv", "9wxyz"};
const char number[]="2061234569";
char printstr[15];
int len;
printph(int index)
{
int i;
int n;
if (index == len)
{
printf("\n");
printstr[len] = '\0';
printf("%s\n", printstr);
return;
}
n =number[index] - '0';
for(i = 0; i < strlen(str[n]); i++)
{
printstr[index] = str[n][i];
printph(index +1);
}
}
電話
printph(0);
于 2012-12-12T16:52:57.170 に答える
0
OPは、上記の疑似コードを理解するのに苦労しているため、実装を求めているようです。おそらく、次の Tcl スクリプトが役立ちます。
array set d {
2 {a b c}
3 {d e f}
4 {g h i}
5 {j k l}
6 {m n o}
7 {p q r s}
8 {t u v}
9 {w x y z}
}
proc digstolets {digits} {
global d
set l [list]
if {[string length $digits] == 0} {
return $l
}
set first [string index $digits 0]
catch {set first $d($first)}
if {[string length $digits] == 1} {
return $first
}
set res [digstolets [string range $digits 1 end]]
foreach x $first {
foreach y $res {
lappend l $x$y
}
}
return $l
}
puts [digstolets "1234"]
于 2011-02-21T19:30:18.667 に答える