G电面一题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

G电面一题

G电面一题# JobHunting - 待字闺中

D*n2012-09-10 07:09

1 楼

给一个数字串，比如 12259 , map到 char数组或者 String. 1 -> a 2-> b,
... 12 -> l ... 26-> z.
12259 -> lyi : abbei : lbei : abyi
输入一个数字串，判断是否能转换成 String,如果能，则打印所以有可能的string.

f*e2012-09-10 07:09

2 楼

总可以转成子串啊？都取1位数，否则DP。

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

: 给一个数字串，比如 12259 , map到 char数组或者 String. 1 -> a 2-> b,
: ... 12 -> l ... 26-> z.
: 12259 -> lyi : abbei : lbei : abyi
: 输入一个数字串，判断是否能转换成 String,如果能，则打印所以有可能的string.

D*n2012-09-10 07:09

3 楼

30 就不行。。。 0之前的数字必须是 1 or 2. 10-> j 20 -> t.
必须打印所有可能的映射。

w*x2012-09-10 07:09

4 楼

F家的题吧, 如果只算多少种组合的话O(1)空间的DP, 要打印就用递归了

f*e2012-09-10 07:09

5 楼

那先把0找出来，和前面的digit配对，配不了对的就不是，这些x0's把整个string分成
几个
substring，然后对substringDP。

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

: 30 就不行。。。 0之前的数字必须是 1 or 2. 10-> j 20 -> t.
: 必须打印所有可能的映射。

z*e2012-09-10 07:09

6 楼

public class Test {
public static void main(String[] args) {
test("12023456", "", 0);
}
public static void test(String nums, String out, int start) {
if (nums == null || start == nums.length()) {
System.out.println(out);
return;
}
int i = nums.charAt(start) - '0';
if (i != 0) {
test(nums, out + (char) (i + 64), start + 1);
if (start + 1 < nums.length()) {
i = Integer.parseInt(nums.substring(start, start + 2));
if (i <= 26) {
test(nums, out + (char) (i + 64), start + 2);
}
}
}
}
}
Output:
-----------------
ATBCDEF
ATWDEF

N*n2012-09-10 07:09

7 楼

给你个反例，90，你给我转个字符串看看

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

: 总可以转成子串啊？都取1位数，否则DP。

g*n2012-09-10 07:09

8 楼

如果不用recursion的话代码太长是不是面试的时候不能用？
public ArrayList numString2Char(String num) {
//map to store all the previous possibilities
HashMap> map = new HashMapArrayList>();
int[] numbers = new int[num.length()];
for (int i = 0; i < num.length(); i++) {
numbers[i] = Integer.parseInt(num.charAt(i) + "");
}
if(numbers[0]==0) return null;
ArrayList tempList;
StringBuffer sb;

for(Integer i=0;iArrayList last = map.get(i-1);
// number is in 1 - 9
if(numbers[i]>0&&numbers[i]<=9){
if(last==null){
tempList= new ArrayList();
sb = new StringBuffer().append((char)('a'-1+numbers[i]));
tempList.add(sb);
map.put(i,tempList);
}
else{
tempList = map.get(i);
if(tempList==null){
tempList = new ArrayList();
for(StringBuffer tempSb:last){
sb = new StringBuffer().append(tempSb).append((
char)('a'-1+numbers[i]));
tempList.add(sb);
}
map.put(i,tempList);
}
else{
for(StringBuffer tempSb:last){
sb = new StringBuffer().append(tempSb).append((
char)('a'-1+numbers[i]));
tempList.add(sb);
}
map.put(i,tempList);
}
}
}
if(i==0) continue;
// list of i-2
ArrayList last2 = map.get(i-2);
//cannot parse
if(numbers[i]==0&&(numbers[i-1]!=1&&numbers[i-1]!=2))
return null;

int number = numbers[i-1]*10+numbers[i];
if(number<1 || number>26) continue;
// test if a 2-number digit is ok
if(last2==null){
ArrayList temp = map.get(i);
if(temp==null)
temp = new ArrayList();
StringBuffer tempSb = new StringBuffer().append((char)('a'-1
+number));
temp.add(tempSb);
map.put(i,temp);
}
else{
ArrayList temp = map.get(i);
if(temp==null)
temp = new ArrayList();
for(StringBuffer tempSb:last2){
sb = new StringBuffer().append(tempSb).append((char)('a'
-1+number));
temp.add(sb);
}
map.put(i,temp);
}
}
ArrayList result = new ArrayList();
for (StringBuffer tempSb : map.get(numbers.length - 1)) {
result.add(tempSb.toString());
}
return result;
}

p*n2012-09-10 07:09

9 楼

随便写了一下，用递归
String maps = "abcdefghijklmnopqrstuvwxyz";
public ConvertNumberToString(int num) {
String numStr = String.valueOf(num);
if (false == getCombination(numStr, "")) {
System.out.println("NO");
}
}
private boolean getCombination(String remain, String result) {
if (remain.length() == 0) {
System.out.println(result);
return true;
}
int n = Integer.parseInt(remain.substring(0, 1)) - 1;
if (n < 0){
return false;
}
char ch = maps.charAt(n);
boolean one = getCombination(remain.substring(1), result + ch);
boolean two = false;
if (remain.length() >= 2) {
n = Integer.parseInt(remain.substring(0, 2)) - 1;
if (n > 26) {
return false;
}
ch = maps.charAt(n);
two = getCombination(remain.substring(2), result + ch);
}
return one || two;
}

C*n2012-09-10 07:09

10 楼

正解

【在 w****x 的大作中提到】

: F家的题吧, 如果只算多少种组合的话O(1)空间的DP, 要打印就用递归了

t*a2012-09-10 07:09

11 楼

; quick clojure solution: dp with memoize function.
(use 'clojure.string)
;; define the map
(def alphabet (map #(str (char %)) (range 97 123)))
(def number (map #(str (inc %)) (range 26)))
(def n2a (apply assoc {} (interleave number alphabet)))
;; implement dp with memoize function
(def number-translate (memoize (fn [long]
(cond (blank? long) [""]
(= (count long) 1) (if (contains? n2a long)
[(n2a long)]
[])
:else (let [len (count long)
last1 (subs long (dec len))
last2 (subs long (- len 2) len)
rest1 (subs long 0 (dec len))
rest2 (subs long 0 (- len 2))
a1 (n2a last1)
a2 (n2a last2)
o1 (number-translate rest1)
o2 (number-translate rest2)
n1 (if (nil? a1)
[]
(map #(str % a1) o1))
n2 (if (nil? a2)
[]
(map #(str % a2) o2))
n (concat n1 n2)]
n)))))
(number-translate "12259") ; ("abbei" "lbei" "avei" "abyi" "lyi")

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

t*a2012-09-10 07:09

12 楼

Really? I think DP can also do print job.

【在 w****x 的大作中提到】

: F家的题吧, 如果只算多少种组合的话O(1)空间的DP, 要打印就用递归了

w*o2012-09-10 07:09

13 楼

我来试试，只有递归，没有DP，可以加HashMap来记住阶段性成果。只返回多少种可能。
int count(int n) {
if (n == 0)
return 0;
if (n <= 10 || n == 20)
return 1;
if (n <= 26)
return 2;

int ret = 0;
int m = n % 10;
if (m != 0)
ret += count(n / 10);
m = n % 100;
if (m >= 10 && m <= 26)
ret += count(n / 100);

return ret;
}

a*a2012-09-10 07:09

14 楼

请指教。我的解答
#include "stdafx.h"
#include
using namespace std;
void transform(char* ,char* ,int ,int,int );
int _tmain(int argc, _TCHAR* argv[])
{

char b[100];
char a[100];
cin.getline(a,100);
int length;
for( length=0;length<100;length++)
if(a[length]=='\0')
break;
transform( a, b, length,0,0);
return 0;
}
void transform(char* a,char* b,int length,int loca,int locb)
{
char x,y[2];
x=*(a+loca);
*(b+locb)=static_cast(atoi(&x)+97);
if (loca==(length -1))
{*(b+locb+1)='\0';
cout <return;
}
else if(locatransform(a,b,length,loca+1,locb+1);
y[0]=*(a+loca);
y[1]=*(a+loca+1);
if(atoi(y)<26)
{
*(b+locb)=static_cast(atoi(y)+97);
if (loca==(length -2))
{
*(b+locb+1)='\0';
cout <return;
}
else if(locatransform(a,b,length,loca+2,locb+1);
}
}