Bloomberg继续跪

dbg_lucas 发表于 2017-8-19 04:01
"久实依"

感谢 祝offer多多~~

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

dbg_lucas 发表于 2017-8-19 05:33
大神威武 如果返回要求是所有可能解码的vector，DP还能用么？

能吧。。。先用dp数组记录prev index，然后逆向dfs。思路有点像word break II

1. void helper(vector<vector<int> >& dp, vector<string>& res, string& s, int cur, const string& ss) {
   
2.   if (cur == 0) {
   
3.     string tmp = s;
   
4.     reverse(tmp.begin(), tmp.end());
   
5.     res.push_back(tmp);
   
6.     return;
   
7.   }
   
8.   for (auto prevIdx: dp[cur]) {
   
9.     int offset = stoi(ss.substr(prevIdx, cur - prevIdx));
   
10.     char c = 'a' - 1 + offset;
    
11.     s.push_back(c);
    
12.     helper(dp, res, s, prevIdx, ss);
    
13.     s.pop_back();
    
14.   }
    
15. }
    
16. 
    
17. vector<string> decode(const string& s) {
    
18.   if (s.empty() || s[0] == '0')
    
19.     return {};
    
20.   vector<vector<int> > dp(s.size() + 1, {});
    
21.   dp[1].push_back(0);
    
22.   for (int i = 0; i < s.size() - 1; ++i) {
    
23.     char a = s[i];
    
24.     char b = s[i + 1];
    
25.     if (b == '0') {
    
26.       if (a == '0' || a >= '3') {
    
27.         return {};
    
28.       }
    
29.       dp[i + 2].push_back(i);
    
30.     }
    
31.     else if (a == '1' || (a == 2 && b <= '6')) {
    
32.       dp[i + 2].push_back(i + 1);
    
33.       dp[i + 2].push_back(i);
    
34.     }
    
35.     else {
    
36.       dp[i + 2].push_back(i + 1);
    
37.     }
    
38.   }
    
39. 
    
40.   vector<string> res;
    
41.   string ss;
    
42.   helper(dp, res, ss, s.size(), s);
    
43.   return res;
    
44. }

复制代码