uber电面面经

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

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

第一题Follow up: 给出所有能够组成的palindrome
能想到两头插的做法。感觉还挺烦啊 LZ咋做的? 能上代码不？

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. /**
   
5. * If a given string can be permutated to form a palindrome string
   
6. * I - string
   
7. * O - bool, true/false
   
8. */
   
9. int is_palindrome(string &str) {
   
10.   unordered_map<char, int> table;
    
11.   for (char c : str)
    
12.     table[c]++;
    
13.   int o=0, e=0;
    
14.   for (auto p : table) {
    
15.     if (p.second&1) o++;
    
16.     else            e++;
    
17.   }
    
18.   return o<2;
    
19. }
    
20. 
    
21. /**
    
22. * Extract all even chars
    
23. * I - string
    
24. * O - chars of first half of the potential palindrome string
    
25. */
    
26. vector<char> half_string(string &str, char &mid) {
    
27.   unordered_map<char, int> table;
    
28.   for (char c : str)
    
29.     table[c]++;
    
30.   vector<char> ret;
    
31.   for (auto p : table) {
    
32.     if (!(p.second&1))
    
33.       for (int i=0; i<p.second/2; i++)
    
34.         ret.push_back(p.first);
    
35.     else
    
36.       mid=p.first;
    
37.   }
    
38.   return ret;
    
39. }
    
40. 
    
41. /**
    
42. * Generate all possible palindrome strings.
    
43. * I - string
    
44. */
    
45. void generate_palindrome(int c, int n, vector<char> &a, string &p, int v[], char &mid) {
    
46.   if (c==n) {
    
47.     string pr=p;
    
48.     reverse(pr.begin(), pr.end());
    
49.     if (mid)
    
50.       pr=mid+pr;
    
51.     pr=p+pr;
    
52.     cout<<pr<<endl;
    
53.   } else {
    
54.     for (int i=0; i<n; i++) if (!v[a[i]]) {
    
55.       v[a[i]]=1;
    
56.       p[c]=a[i];
    
57.       generate_palindrome(c+1, n, a, p, v, mid);
    
58.       v[a[i]]=0;
    
59.       while (i<n-1 && a[i+1]==a[i]) i++;
    
60.     }
    
61.   }
    
62. }
    
63. 
    
64. int main(void) {
    
65.   string str;
    
66.   cin>>str;
    
67.   if (is_palindrome(str)) {
    
68.     char mid=0;
    
69.     auto half=half_string(str, mid);
    
70.     sort(half.begin(), half.end());
    
71.     int n=half.size();
    
72.     int v[256];
    
73.     memset(v, 0, sizeof v);
    
74.     string palindrome(n, ' ');
    
75.     generate_palindrome(0, n, half, palindrome, v, mid);
    
76.   }
    
77. }
    

复制代码

houqingniao 发表于 2015-3-2 13:05
第一题Follow up: 给出所有能够组成的palindrome
能想到两头插的做法。感觉还挺烦啊 LZ咋做的? 能上代码不 ...

选出一半数量的字符进行permutation就好了，permutation详见11楼

哦 没仔细看~~~
懂了 哈哈