Google暑期实习电面

bobzhang2004 发表于 2015-12-7 08:41
写了下第一题，不太确定是不是正解，欢迎指教

题目里首先说了不能重复 其次说了 如果中间键已被使用 则可以连接之前不能连接的键，楼主这点没考虑进去？

第一题

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string>
   
4. #include <iostream>
   
5. 
   
6. #define N   (3)
   
7. 
   
8. using namespace std;
   
9. 
   
10. int visited[N*N] = {0};
    
11. 
    
12. bool can_visit(int i, int j) {
    
13. 
    
14.     if (i == j) {
    
15.         return false;
    
16.     } else if (visited[j-1]) {
    
17.         return false;
    
18.     }
    
19. 
    
20.     //start point
    
21.     if (i == 0) {
    
22.         return true;
    
23.     }
    
24. 
    
25.     int rowi = (i-1) / N + 1;
    
26.     int coli = (i-1) % N + 1;
    
27.     int rowj = (j-1) / N + 1;
    
28.     int colj = (j-1) % N + 1;
    
29. 
    
30.     if (rowi == rowj) {
    
31.         int diff = coli - colj;
    
32.         if (diff == 1 || diff == -1) {
    
33.             return true;
    
34.         } else {
    
35.             int k;
    
36.             int min = coli > colj ?colj :coli;
    
37.             int max = coli > colj ?coli :colj;
    
38.             for (k = min+1; k < max; k++) {
    
39.                 if (!visited[(rowi-1) * N + k - 1]) {
    
40.                     return false;
    
41.                 }
    
42.             }
    
43.             return true;
    
44.         }
    
45.     } else if (coli == colj) {
    
46.         int diff = rowi - rowj;
    
47.         if (diff == 1 || diff == -1) {
    
48.             return true;
    
49.         } else {
    
50.             int k;
    
51.             int min = rowi > rowj ?rowj :rowi;
    
52.             int max = rowi > rowj ?rowi :rowj;
    
53.             for (k = min+1; k < max; k++) {
    
54.                 if (!visited[(k-1) * N + coli - 1]) {
    
55.                     return false;
    
56.                 }
    
57.             }
    
58.             return true;
    
59.         }
    
60.     } else {
    
61.         int diffcol = coli - colj;
    
62.         int diffrow = rowi - rowj;
    
63.         if (diffcol == diffrow || diffcol == -diffrow) {//diagnal line
    
64.             if (diffcol == 1 || diffcol == -1) {//ajacent
    
65.                 return true;
    
66.             }
    
67.             int minrow = rowi > rowj ?rowj :rowi;
    
68.             int maxrow;
    
69.             int startcol;
    
70.             int r;
    
71.             if (rowi == minrow) {
    
72.                 startcol = coli;
    
73.                 maxrow = rowj;
    
74.                 if (coli < colj) {
    
75.                     r = 1;
    
76.                 } else {
    
77.                     r = -1;
    
78.                 }
    
79.             } else {
    
80.                 startcol = colj;
    
81.                 maxrow = rowi;
    
82.                 if (coli < colj) {
    
83.                     r = -1;
    
84.                 } else {
    
85.                     r = 1;
    
86.                 }
    
87.             }
    
88.             int k;
    
89.             for (k = minrow+1; k < maxrow; k++) {
    
90.                 if (!visited[(k-1)*N + startcol + r * (k-minrow)]) {
    
91.                     return false;
    
92.                 }
    
93.             }
    
94.             return true;
    
95.         } else {
    
96.             return true;
    
97.         }
    
98.     }
    
99. }
    
100. 
     
101. string int_to_string(int i) {
     
102.     char buf[1024];
     
103.     snprintf(buf, sizeof(buf), "%d", i);
     
104.     return string(buf);
     
105. }
     
106. 
     
107. void back_track_visit(int len, int cur_len, int cur_pos, string path, int &total)
     
108. {
     
109.     if (cur_len == len) {
     
110.         total++;
     
111.         //cout << path << endl;
     
112.         return;
     
113.     }
     
114. 
     
115.     for (int i = 1; i <= N*N; i++) {
     
116.         if (!can_visit(cur_pos, i)) {
     
117.             continue;
     
118.         }
     
119. 
     
120.         visited[i-1] = 1;
     
121.         back_track_visit(len, cur_len+1, i, path + ">" + int_to_string(i), total);
     
122.         visited[i-1] = 0;
     
123.     }
     
124. }
     
125. 
     
126. int main(void)
     
127. {
     
128.     int total = 0;
     
129.     back_track_visit(9, 0, 0, "", total);
     
130.     cout << total << endl;
     
131. }
     

复制代码

请问楼主第二轮第一题“给定一个函数 boolean isWord(string s)，可以判断这个字符串是否是一个合法的英语词汇
然后给一个初始的字符串s，只能对它做删除字母的操作，求问最长的合法的英语词汇”是怎么做的? brute force吗？

singku 发表于 2016-1-5 12:13
题目里首先说了不能重复 其次说了 如果中间键已被使用 则可以连接之前不能连接的键，楼主这点没考虑进去 ...

对啊，如果这样的话，确实还得有个更新map的操作啊

echo33 发表于 2015-12-13 03:14
第一题是分成[1,3,7,9], [2,4,6,8],[5]三种键吗

ls的好像不太对，即使你加上visited

你想出来怎么用backtracking做了吗