狗家高频面经求解

Falldawn 发表于 2021-6-17 06:13
这上面有人说了，感觉就应该是这样做，我改成了Java代码三个数组应该是分别代表从最上面entry行到当前位 ...

这应该是optimal solution, 可以节省空间到O(n)

贴个我的cpp代码, O(2n)时间空间;

1. int max_len(vector<vector<int>> &m) {
   
2.   int rows = m.size();
   
3.   int cols = m.front().size();
   
4. 
   
5.   vector<vector<int>> left(rows, vector<int>(cols, INT_MIN));
   
6.   auto right = left;
   
7. 
   
8.   if (m[0][0] == 0) left[0][0] = 1;
   
9.   if (m[0][cols - 1] == 0) right[0][cols - 1] = 1;
   
10. 
    
11.   for (int i = 1; i < cols; i++) {
    
12.     if (m[0][i]) continue;
    
13.     left[0][i] = m[0][i - 1] ? 1 : left[0][i - 1] + 1;
    
14.   }
    
15. 
    
16.   for (int i = cols - 2; i >= 0; i--) {
    
17.     if (m[0][i]) continue;
    
18.     right[0][i] = m[0][i + 1] ? 1 : right[0][i + 1] + 1;
    
19.   }
    
20. 
    
21.   for (int r = 1; r < rows; r++) {
    
22.     if (m[r - 1][0] == 0 && m[r][0] == 0) left[r][0] = max(left[r - 1][0], right[r - 1][0]) + 1;
    
23.     for (int c = 1; c < cols; c++) {
    
24.       if (m[r][c]) continue;
    
25.       if (m[r][c - 1] == 0) left[r][c] = max(left[r][c], left[r][c - 1] + 1);
    
26.       if (m[r - 1][c] == 0) left[r][c] = max(left[r][c], max(left[r - 1][c], right[r - 1][c]) + 1);
    
27.     }
    
28. 
    
29.     if (m[r - 1][cols - 1] == 0 && m[r][cols - 1] == 0) right[r][cols - 1] = max(left[r - 1][cols - 1], right[r - 1][cols - 1]) + 1;
    
30.     for (int c = cols - 2; c >= 0; c--) {
    
31.       if (m[r][c]) continue;
    
32.       if (m[r][c + 1] == 0) right[r][c] = max(right[r][c], right[r][c + 1] + 1);
    
33.       if (m[r - 1][c] == 0) right[r][c] = max(right[r][c], max(right[r - 1][c], left[r - 1][c]) + 1);
    
34.     }
    
35.   }
    
36. 
    
37.   return max(*max_element(left[rows - 1].begin(), left[rows - 1].end()),
    
38.              *max_element(right[rows - 1].begin(), right[rows - 1].end()));
    
39. }
    

复制代码