Google Onsite

问下楼主 第二题 如果障碍物只是在最外面一圈的话 只有 终点和起点在同一行或者同一列或者最外围那一圈才可能到达吧？   这样题就很不make sense 啊， 我猜障碍物应该处处存在吧？   这样的话用dfs可以吗？

sophie0815 发表于 2016-11-13 13:57
问下楼主 第二题 如果障碍物只是在最外面一圈的话 只有 终点和起点在同一行或者同一列或者最外围那一圈才可 ...

是的 上面那圖只是解釋
障礙物可以很多
我是用DFS 一旦選擇方向就一直走到底

第三轮：LZ已经写了recusive的，这和DP差不多了：时间O(nk)，空间O(k)

1. double getProb(int k, vector<double>& c) {
   
2.   int n = c.size(); if (k > n) return 0;
   
3.   // prev[kk]: probability of kk heads in first nn-1 coins
   
4.   // cur[kk]:  probability of kk heads in first nn coins
   
5.   vector<double> prev(k+1, 0.0), cur(k+1, 0.0);
   
6.   prev[0] = cur[0] = 1.0;
   
7.   for (int nn = 1; nn <= n; ++nn) {
   
8.     cur[0] = prev[0]*c[nn-1];
   
9.     for (int kk = 1; kk <= min(nn,k); ++kk) {
   
10.       cur[kk] = prev[kk-1]*c[nn-1] + prev[kk]*(1-c[nn-1]);  
    
11.       prev[kk-1] = cur[kk-1];
    
12.     }
    
13.     prev[min(nn,k)] = cur[min(nn,k)];
    
14.   }
    
15.   return cur[k];
    
16. }

复制代码

第三题列了一下状态转移方程不知道对不对... f[n][k]代表在第 n 个硬币有 k个头的概率,那么 f[n][k] = P(n)*f[n-1][k-1] + (1-P(n))*f[n-1][k]

第一轮：将s="12345678910111213..." 看成一个Trie，那么第nDigits 层就有9×10^(nDigits -1)个数，每个数有nDigits 个数字。对于给定的index=i看s[\i]对应的数字在那一层，再看落到哪个数的哪个数字上就好了。

1. char getChar(int i) {
   
2.   if (i < 0) return '\0';
   
3.   int count = 9, nDigits = 0;
   
4.   while (i+1 > (++nDigits)*count) { i -= nDigits*count; count *= 10; }
   
5.   int x = count/9 + i/nDigits, pos = nDigits - i%nDigits;
   
6.   while (--pos > 0) x /= 10;
   
7.   return '0' + x%10;
   
8. }

复制代码

zhenjieruan 发表于 2016-11-14 06:16
第三题列了一下状态转移方程不知道对不对... f[n][k]代表在第 n 个硬币有 k个头的概率,那么 f[n][k] = P(n) ...

嗯，我觉得就是这样对n和k做DP就行了。
对n的DP实际可以只用2个变量，省空间。

hahayufindjob 发表于 2016-11-13 00:41
不是太明白，不用string 算，那么是要统计下stirng中各个char的出现规律吗？

我不是LZ: 这个题是相当于给定一个无穷的stringstream: 123456789101112131415... 问第i个位置的digit是什么？

第二题：用DFS是不是这个意思. 当用DFS迭代时同时要传当前的方向，然后若在同一方向的位置无障碍物时就只沿这个方向搜索；否则沿垂直的2个方向搜索。

1. int m, n; // maze dimensions
   
2. vector<int> start, goal;
   
3. vector<vector<int>> dirs = {{1,0},{0,-1},{-1,0},{0,1}};
   
4. 
   
5. bool dfs(vector<vector<int>>& maze, int i, int j, int d) {
   
6.   if (i < 0 || i >= m || j < 0 || j >= n || maze[i][i]) return false;
   
7.   if (i == goal[0] && j == goal[1]) return true;
   
8.   maze[i][i] = 1; // set as visited
   
9.   // next location in same direction
   
10.   vector<int> next = {i+dirs[d][0], j+dirs[d][1]};
    
11.   // search only same direction if available
    
12.   if (0 <= next[0] && next[0] < m && 0 <= next[1] && next[1] < n && !maze[next[0]][next[1]])
    
13.       return dfs(maze, next[0], next[1], d);
    
14.   // search other directions only if same direction unavailable      
    
15.   else return dfs(maze, i+dirs[(d+1)%4][0], j+dirs[(d+1)%4][1], (d+1)%4) ||
    
16.               dfs(maze, i+dirs[(d-1)%4][0], j+dirs[(d-1)%4][1], (d-1)%4);
    
17. }
    
18. 
    
19. bool canFinish(vector<vector<int>>& maze, vector<int> s, vector<int> e) {
    
20.   if ((m = maze.size()) == 0) return false;
    
21.   if ((n = maze[0].size()) == 0) return false;
    
22.   start = s, goal = e;
    
23.   // search each direction from start
    
24.   return dfs(maze, s[0]+dirs[0][0], s[1]+dirs[0][1], 0) ||
    
25.          dfs(maze, s[0]+dirs[1][0], s[1]+dirs[1][1], 1) ||
    
26.          dfs(maze, s[0]+dirs[2][0], s[1]+dirs[2][1], 2) ||
    
27.          dfs(maze, s[0]+dirs[3][0], s[1]+dirs[3][1], 3);
    
28. }

复制代码

zzgzzm 发表于 2016-11-14 05:20
第三轮：LZ已经写了recusive的，这和DP差不多了：时间O(nk)，空间O(k)

能解释一下概率是怎么计算的吗？
碰见概率就蒙蔽

楼主第四题 带权有向图 最短路径 Djkstra算法吗？