一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2158|回复: 12
收起左侧

Amazon phone interview

[复制链接] |试试Instant~ |关注本帖
lea82 发表于 2016-6-7 07:34:09 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Amazon - 猎头 - 技术电面 |Fail在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
decode:.1point3acres缃
A-1
B-2
C-3. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
...
Z-26
Given an interger (for example 2634157819), return all its possible original String .鏈枃鍘熷垱鑷1point3acres璁哄潧
List<String> decode(int n)

评分

1

查看全部评分

lfzh123 发表于 2016-6-7 08:26:01 | 显示全部楼层
这个是decode ways 变种吧,需要把所有的可能的结果都返回。pat pat,楼主能说一下怎么挂的吗?
回复 支持 反对

使用道具 举报

taffyyang 发表于 2016-6-8 05:36:30 | 显示全部楼层
求问这题该怎么做啊?
我能想到的是可以把数字两两分组,再排列组合。
比如2634157819, 可以分为26, 34, 15, 78, 19.然后可以decode为 (2, 6)||(26) ,  (3,4),  (1,5)||(15),  (7,8),  (1,9)||(19),然后按位置坐组合。
因为在第一次分组的交界处也有可能出现两个数组组合的情况,所以再按 2,63,41,57,81,9 再分组做一次上面同样的操作。
第二次分组的排列组合只有一种情况会和第一次分组中的重复,就是交界处一个小于26的数字都没有,刚好是例子中的情况。这种情况可以在分组的时候就检查一遍,如果第二次分组的时候每个两位数都大于26,就不用考虑第二种的组合了。. 1point 3acres 璁哄潧
不知道这么想对不对,求大神指导
回复 支持 反对

使用道具 举报

NEO_FISH 发表于 2016-6-8 07:18:53 | 显示全部楼层
taffyyang 发表于 2016-6-8 05:36
求问这题该怎么做啊?
我能想到的是可以把数字两两分组,再排列组合。
比如2634157819, 可以分为26, 34, ...

最自然地想法肯定是DP,先把int转化为String,从最右位s.charAt(ength()-1)开始往左遍历到最高位s.charAt(0),循环内容是:如果第n位和第n+1位组成的两位数如果小于27那么,右边的数字串可能会有两种情况,一种是n位的decode加上n-1位的结果,第二种是n和n+1位组合的decode加上n-2位的结果;如果第n位是0或者和第n+1位组成的两位数大于27那么都是只有一种结果:0的话直接左移,大于27的话只用decode当前位+n-1位结果。。大概思路是这样,保持三位的结果String类型List。不过LC原题只要算总数,只要保持3个int就行了。。如果要列出所有可能性确实烦了点。。尤其还要写对应的解码, 一个一个case?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-6-8 07:20):
写错了。。。里面的n-1和n-2全部换成n+1和n+2。

补充内容 (2016-6-8 07:26):
你的方法应该会少结果。。比如212121这个你的方法里没有2,12,1,21这种情况,另外还要考虑奇偶问题,大概很难写出来。不过你可以试试。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-8 07:42:39 | 显示全部楼层
so f***ing hard!
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-8 08:21:12 | 显示全部楼层
额。。。 会错帖子。。。。 这个题不难。。
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <vector>. Waral 鍗氬鏈夋洿澶氭枃绔,
  4. #include <string>
  5. using namespace std;

  6. void decodeWays(string str, int pos, string path, vector<string>& res, unordered_map<string, char>& dict) {
  7.   if(pos > str.size()) return;
  8.   if(pos == str.size()) {
  9.     res.push_back(path);
  10.     return;
  11.   }
  12.   for(int i = 1; i <= 2; ++i) {. From 1point 3acres bbs
  13.     string tmp = str.substr(pos, i);
  14.     if(dict.count(tmp)) {.1point3acres缃
  15.       decodeWays(str, pos + i, path + dict[tmp], res, dict);
  16.     }
  17.   }
  18. }

  19. vector<string> decodeWays(int input, unordered_map<string, char>& dict) {
  20.   string str = to_string(input);
  21.   if(str.size() == 0) return {};
  22.   vector<string> res;.1point3acres缃
  23.   string path = "";
  24.   decodeWays(str, 0, path, res, dict);
  25.   return res;
  26. }
  27. int main(void) {
  28.   unordered_map<string, char> dict {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.     {"1", 'A'},
  30.     {"2", 'B'},
  31.     {"3", 'C'},
  32.     {"4", 'D'},
    . 鍥磋鎴戜滑@1point 3 acres
  33.     {"5", 'E'},
  34.     {"6", 'F'},.鐣欏璁哄潧-涓浜-涓夊垎鍦
  35.     {"7", 'G'},. 鍥磋鎴戜滑@1point 3 acres
  36.     {"8", 'H'},.鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.     {"9", 'I'},
  38.     {"10", 'J'},
  39.     {"11", 'K'},. visit 1point3acres.com for more.
  40.     {"12", 'M'},
  41.     {"13", 'N'},
  42.     {"14", 'O'},. more info on 1point3acres.com
  43.     {"15", 'P'},
  44.     {"16", 'Q'},
  45.     {"17", 'R'},.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.     {"18", 'S'},
  47.     {"19", 'T'},. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  48.     {"20", 'U'},
  49.     {"21", 'V'},
  50.     {"22", 'W'},
  51.     {"23", 'X'}, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  52.     {"24", 'Y'},
  53.     {"25", 'Z'}};
  54.   vector<string> res = decodeWays(123, dict);
  55.   for(int i = 0; i < res.size(); ++i) cout << res[i] << endl;
  56. }
  57.               
复制代码
回复 支持 反对

使用道具 举报

MCwong 发表于 2016-6-8 08:48:52 | 显示全部楼层
递归, 每当当前两个数10~26的范围内就分出两个分支(一条挪1个digit, 另一条挪两个), 最后把每条分支的有效结果汇总即可。有点类似爬楼梯问题,求所有爬行路线。
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-6-8 11:12:41 | 显示全部楼层
I think  it is  dfs    like

                                   1
             1 2 3  ........................26
1,2,3,........... 26 ...................1.2.3...........26

All the   possible  path  that get  total  is  n   

the code will like
List<String> result  = new ArrayList<>();
helper(result new Arraylist<Character>(), n )

helper() {. visit 1point3acres.com for more.
if(n == 0) {
result. add(list.toString )
}
for( int i  = 1; i <=26; i++){
   
list.add( i ). visit 1point3acres.com for more.
  helper(result , list , n - 26 based caculate list  of value )
listy.move( list.size() - 1)


if you go this way  even you don't finish your code   You will pass


    helper(result )
}


回复 支持 反对

使用道具 举报

头像被屏蔽
chenren03 发表于 2016-7-30 13:09:57 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-7-30 22:06:08 | 显示全部楼层
要返回all possible solutions,应该用dfs做吧
回复 支持 反对

使用道具 举报

z165153 发表于 2016-7-30 22:22:06 | 显示全部楼层
如果真的就直接来个DP,也太厉害了。
回复 支持 反对

使用道具 举报

pupuchan1116 发表于 2016-8-1 05:57:46 | 显示全部楼层
z165153 发表于 2016-7-30 22:22
如果真的就直接来个DP,也太厉害了。
. 1point 3acres 璁哄潧
我第一反应是backtracking+dp,因为2634157819,走2在走6和先走26到后面碰到的34157819这个分支的结果是一样的,所以在2->6到34157819产生的List<String>,可以保存到hashmap里面,这样走26的时候就能直接用结果,如此类推,这样就能保证每一个分支只会走一次。不过这个方法应该也不是最优。
回复 支持 反对

使用道具 举报

chinabigtou 发表于 7 天前 | 显示全部楼层
可以用hashmap,存n每一位所对应的list<Stirng>, 比如给的数字是12120,hashmap就是

<0, [1]>. 1point 3acres 璁哄潧
<1, [1,2], [12]>
<2, [1,2,1], [1,21], [12,1]>
<3, [1,2,1,2], [1,2,12], [1,21,2], [12,1,2], [12,12]>
<4, [1,2,1,20], [1,21,20],[12,1,20]>
. 鍥磋鎴戜滑@1point 3 acres
最后4对应的list就是结果,我用数字表示的这样比较直观,做的时候转换一下就好了。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
初始化map第一层,然后遍历数字n的每一位,获取上一层的list,遍历这个list里面的string, 然后根据当前位的数字,判断是1-9,就可以在stirng后面加,如果和上一位组成10-26,则可以把string的最后一位删除,加上新的字符。一层一层执行即可
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 16:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表