热乎Google昂赛

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

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

补充内容 (2018-11-17 09:54):
11.14过hc开始pa match，求后面不出岔子。。。。。

简单写了一下Q3的做法，有不太好的地方求指点：

1. 
   
2. string rotate180(string s, unordered_map<char, char>& nums) {
   
3.     string r = s;
   
4.     for (int i = 0; i<s.size(); i++)
   
5.         r[s.size()-1-i] = nums[s[i]];
   
6.     return r;
   
7. }
   
8. 
   
9. void helper(string& cur, int start, const string& low, const string& high, vector<string>& res, unordered_map<char, char>& nums) {
   
10.     if (start==cur.size()) {
    
11.         if ((cur.size()==low.size() && cur<low) || (cur.size()==high.size() && cur>high) || cur.back()=='0')
    
12.             return;
    
13.         string ans = rotate180(cur, nums);
    
14.         if ((ans.size()==low.size() && ans<low) || (ans.size()==high.size() && ans>high) || ans == cur)
    
15.             return;
    
16.         res.push_back(ans);
    
17.         return;
    
18.     }
    
19.     for (auto item : nums) {
    
20.         cur[start] = item.first;
    
21.         if (start==0 && item.first=='0')
    
22.             continue;
    
23.         helper(cur, start+1, low, high, res, nums);
    
24.     }
    
25. }
    
26. 
    
27. vector<string> stroNumInRange(string low, string high) {
    
28.     vector<string> res;
    
29.     unordered_map<char, char> nums = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
    
30.     for (int sz = low.size(); sz <= high.size(); sz++) {
    
31.         string cur = string(sz, ' ');
    
32.         helper(cur, 0, low, high, res, nums);
    
33.     }
    
34.     return res;
    
35. }
    
36. 
    
37. int main() {
    
38.     vector<string> ra = stroNumInRange("0", "20");
    
39.     for (auto r : ra)
    
40.         cout << r << " ";
    
41.     cout << endl;
    
42. 
    
43.     vector<string> rb = stroNumInRange("50", "100");
    
44.     for (auto r : rb)
    
45.         cout << r << " ";
    
46.     cout << endl;
    
47.    
    
48.     return 0;
    
49. }
    

复制代码

第4题扫一遍T是要对S的所有后缀建trie吧。感觉这种题一定有用神奇字符串数据结构的无敌做法，凡人用trie就好了。。。

给我铁加油~

有戏 祝LZ好运

请问一下第四题用greedy是怎么做呀 还有就是是subsequence不是substring嘛 感谢楼主祝楼主拿offer！

感谢分享，祝lz好运。。我也刚onsite完不久 题比这个还简单

给你点个赞！

楼主可以详细说一下第一题是什么输入输出么，感觉最近出了很多这个题，但是不知道具体给的什么条件。谢谢楼主，已加米

第二轮can i win可以用for loop 写吗

nhqgoal 发表于 2018-10-30 13:10
第二轮can i win可以用for loop 写吗

你会写dp当然可以，但这道题dp不好写。

我现在也在纠结要不要准备一下DAG的几个特别变态的算法。但是估计准备了上去换题还是懵逼。第四题我写的最优解是O(mlog(highest frequency character)), m 是S的长度。感觉应该是理论最优解了