Google New Grad Phone Interview

legendava 发表于 2015-1-6 13:44
为什么那个zigzag a 之后是d，应该是b比较合理感觉

有两种走法，可以先走b. 这种的话，应该是abdgecfhi

第四题，zigzag 打印

1. public class ZigzagPrintMatrix {
   
2. 
   
3.     public static List<Integer> zigzagPrint(int[][] board) {
   
4.         List<Integer> result = new ArrayList<Integer>();
   
5.         int m = board.length;
   
6.         if (m == 0 || board[0].length == 0) return result;
   
7.         int n = board[0].length;
   
8.         int i = 0, j = 0;
   
9.         while (i < m && j < n) {
   
10.             result.add(board[i][j]);
    
11.             if (i + 1 < m) i++;
    
12.             else if (j + 1 < n) j++;
    
13.             else break;
    
14.             while (i > 0 && j + 1 < n) {
    
15.                 result.add(board[i][j]);
    
16.                 i--;
    
17.                 j++;
    
18.             }
    
19.             result.add(board[i][j]);
    
20.             if (i == 0) j++;
    
21.             else i++;
    
22.             while (i + 1 < m && j > 0) {
    
23.                 result.add(board[i][j]);
    
24.                 i++;
    
25.                 j--;
    
26.             }
    
27.         }
    
28.         return result;
    
29.     }
    
30.    
    
31.     public static void main(String[] args) {
    
32.      //  int[][] board = {{1,2,3,4,5}, {6,7,8,9,1}, {2,3,4,5,6}};
    
33.         int[][] board = {{1,2,3}, {4,5,6}, {7,8,9}};
    
34.         List<Integer> result = zigzagPrint(board);
    
35.         for (int d : result){
    
36.             System.out.print(d + " ");
    
37.         }
    
38.         System.out.println();
    
39.     }
    
40. }

复制代码

除了第四题 都是Leetcode原题啊～

void zigzagPrint(vector<vector<char> > matrix) {
  int n =  matrix.size();
  for(int i = 0; i < 2*n-1; i++) {
    for(int j = 0; j <= min(i,n-1); j++) {
      if (i-j<0 || i-j>=n) {
        continue;
      }
      if (i%2) {
        cout<<matrix[j][i-j];
      } else {
        cout<<matrix[i-j][j];
      }
    }
  }
  cout<<endl;
}

int main() {
  vector<vector<char>> matrix({{'a','b','c'},{'d','e','f'},{'g','h','i'}});
  zigzagPrint(matrix);
}

写了下代码，应该最浅node应该用bfs会好些

1. public class TreeQuestions {
   
2.        
   
3.         class Node {
   
4.                 int val;
   
5.                 Node left;
   
6.                 Node right;
   
7.         }
   
8.        
   
9.         public int getTreeHeight(Node root) {
   
10.                 if (root == null) {
    
11.                         return 0;
    
12.                 }
    
13.                
    
14.                 return Math.max(getTreeHeight(root.left), getTreeHeight(root.right)) + 1;
    
15.         }
    
16.        
    
17.        
    
18.         private Node res = null;
    
19.         private int level = 0;
    
20.         public Node getDeepestLeafNode(Node root) {
    
21.                 if (root == null) {
    
22.                         return null;
    
23.                 }
    
24.                 helper(root, 1);
    
25.                 return res;
    
26.         }
    
27.        
    
28.         public void helper(Node root, int n) {
    
29.                 if (root == null) {
    
30.                         return;
    
31.                 }
    
32.                 if (root.left == null && root.right == null && n > level) {
    
33.                         level = n;
    
34.                         res = root;
    
35.                 }
    
36.                 helper(root.left, n + 1);
    
37.                 helper(root.right, n + 1);
    
38.         }
    
39.        
    
40.         private Node res2 = null;
    
41.         private int level2 = Integer.MAX_VALUE;
    
42.         public Node getShallowestLeafNode2(Node root) {
    
43.                 if (root == null) {
    
44.                         return null;
    
45.                 }
    
46.                 helper2(root, 1);
    
47.                 return res2;
    
48.         }
    
49.        
    
50.         public void helper2(Node root, int n) {
    
51.                 if (root == null || n >= level2) {
    
52.                         return;
    
53.                 }
    
54.                 if (root.left == null && root.right == null && n < level2) {
    
55.                         level2 = n;
    
56.                         res2 = root;
    
57.                 }
    
58.                 helper(root.left, n + 1);
    
59.                 helper(root.right, n + 1);
    
60.         }
    
61. }

复制代码