热乎Google昂赛

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

题都出来了应该就差不多了吧

老哥⛽️

foryousee 发表于 2018-10-30 14:50
你会写dp当然可以，但这道题dp不好写。

sry 我以为是predict the winner那道题。

请问 family tree找两个人有没有血缘关系 用了bi-directional BFS了吗？

简单写了一下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. }
    

复制代码

问一下楼主 题目拍照是什么意思是查重吗

foryousee 发表于 2018-10-30 14:52
我现在也在纠结要不要准备一下DAG的几个特别变态的算法。但是估计准备了上去换题还是懵逼。第四题我写的最 ...

求解法，我只想到尽可能往后扫t，但是复杂度很高

请问什么叫pa啊