PIE题: Phone number to words iterative 解法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

PIE题: Phone number to words iterative 解法

PIE题: Phone number to words iterative 解法# JobHunting - 待字闺中

l*n2012-12-18 08:12

1 楼

amazon价格回到110$了
爽

R*y2012-12-18 08:12

2 楼

题目如下，要求recursive 和 non recursive解法
write a program that given a 7 digit telephone number, could print all
possible combinations of letters that each number could represent.
second part: if the telephone number changes to 12 digits one
recursive 解法很清晰，建立一个字典，然后递归就好了。
iterative 解法，我就卡住了，google了一下，有一个解法如下:
private static ArrayList processOneNumber(ArrayList input, int[] phoneNum,
int currentNum) {
ArrayList output = new ArrayList();
int numberToProcess = phoneNum[currentNum];
char c;
// process 1st number
if (input.isEmpty()) {
if (TelephoneWords.isOneOrZero(numberToProcess)) {
c = TelephoneWords.getCharKey(numberToProcess, 0);
output.add(Character.toString(c));
} else {
for (int i = 0; i < 3; i++) {
c = TelephoneWords.getCharKey(numberToProcess, i);
output.add(Character.toString(c));
}
}
} else { // process rest of the number
for (String result : input) {
if (TelephoneWords.isOneOrZero(numberToProcess)) {
c = TelephoneWords.getCharKey(numberToProcess, 0);
output.add(result.concat(Character.toString(c)));
} else {
for (int i = 0; i < 3; i++) {
c = TelephoneWords.getCharKey(numberToProcess, i);
output.add(result.concat(Character.toString(c)));
}
}
}
return output;
}
这个解法每次处理一个digit然后存储当前结果，下一次调用将新的char 附加到后面。
这样的解法下来，arraylist 巨大无比，而且有很多中间的结果，比如A，B,C 这样的
不是最终结果的过渡字符。
原书的解法貌似错了,希望各位大神多多指教

d*f2012-12-18 08:12

3 楼

ft, ebay上ritz,wolf的dealer常年卖50 shipped

【在 l******n 的大作中提到】

: amazon价格回到110$了
: 爽

j*y2012-12-18 08:12

4 楼

搞个 for循环就可以了吧

【在 R**y 的大作中提到】

: 题目如下，要求recursive 和 non recursive解法
: write a program that given a 7 digit telephone number, could print all
: possible combinations of letters that each number could represent.
: second part: if the telephone number changes to 12 digits one
: recursive 解法很清晰，建立一个字典，然后递归就好了。
: iterative 解法，我就卡住了，google了一下，有一个解法如下:
: private static ArrayList processOneNumber(ArrayList input, int[] phoneNum,
: int currentNum) {
: ArrayList output = new ArrayList();
: int numberToProcess = phoneNum[currentNum];

l*n2012-12-18 08:12

5 楼

靠，不要打击我好不？
in了不少，555555

【在 d********f 的大作中提到】

: ft, ebay上ritz,wolf的dealer常年卖50 shipped

c*a2012-12-18 08:12

6 楼

import java.util.Hashtable;
public class Solution {
Hashtable Dict = new Hashtable ()
;
public ArrayList letterCombinations(String digits) {
ArrayList res = new ArrayList();
if(digits.length()==0){
res.add("");
return res;
}
Dict.put(2, new String[]{"a", "b", "c"});
Dict.put(3, new String[]{"d", "e", "f"});
Dict.put(4, new String[]{"g", "h", "i"});
Dict.put(5, new String[]{"j", "k", "l"});
Dict.put(6, new String[]{"m", "n", "o"});
Dict.put(7, new String[]{"p", "q", "r", "s"});
Dict.put(8, new String[]{"t", "u", "v"});
Dict.put(9, new String[]{"w", "x", "y", "z"});

permute(res,digits, "", digits.length());

return res;
}
public void permute(ArrayList res, String digits, String buffer,
int size){
if(buffer.length()==size){
res.add(buffer);
return;
}
for(int i =0; ifor(String c: Dict.get(digits.charAt(i)-48))
permute(res, digits.substring(i+1), buffer + c,size);
}
}
}
刚刚写的，跟subset of string差不多,写法一样,就加了一个for loop..
//subset of string eg, ab: a, b , ab
public static void subset(String s){
if(s.length()==0) return;
subset(s, "");
}
public static void subset(String s,String res){
System.out.println(res);
for(int i =0;isubset(s.substring(i+1), res+s.charAt(i));
}

g*72012-12-18 08:12

7 楼

常年？不会把，我今天没抢到还捶胸顿足哭天抢地呢

R*y2012-12-18 08:12

8 楼

一个for循环够么？一个数字对应三个letter，然后最少有7个数字，这里就是两重循
环了。

【在 j*****y 的大作中提到】

: 搞个 for循环就可以了吧

m*32012-12-18 08:12

9 楼

挺朋友说那个镜头是买机器自带的。有机器的人都有那个头。

R*y2012-12-18 08:12

10 楼

这个解法是recursion吧。

()

【在 c*****a 的大作中提到】

: import java.util.Hashtable;
: public class Solution {
: Hashtable Dict = new Hashtable ()
: ;
: public ArrayList letterCombinations(String digits) {
: ArrayList res = new ArrayList();
: if(digits.length()==0){
: res.add("");
: return res;
: }

p*n2012-12-18 08:12

11 楼

是啊，没销量

【在 m******3 的大作中提到】

: 挺朋友说那个镜头是买机器自带的。有机器的人都有那个头。

j*y2012-12-18 08:12

12 楼

之前要搞一个 vectorv 记录每个 key对应的字母
for(int i = 0; i < digits.length(); ++i)
{
for(int j = 0; j < v[digits[i] - '1'].length(); ++j)
{
}
}
我这里假设数字 1 和 0 不会用到，因为 key board里面没有对应这两个数字的字母

【在 R**y 的大作中提到】

: 一个for循环够么？一个数字对应三个letter，然后最少有7个数字，这里就是两重循
: 环了。