谷歌面试原题地址

样例 1

示例 1: 输入: carrot =  [[5, 7, 6, 3], [2,  4, 8, 12], [3, 5, 10, 7], [4, 16, 4, 17]] 输出:  83 解释： 起点坐标是(1, 1), 移动路线是：4 -> 8 -> 12 -> 7 -> 17 -> 4 -> 16 -> 5 -> 10 

样例 2

示例 2: 输入: carrot =  [[5, 3, 7, 1, 7],  [4, 6, 5, 2, 8],  [2, 1, 1, 4, 6]]  输出:   30  解释：  起始点是 (1, 2), 移动路线是：5 -> 7 -> 3 -> 6 -> 4 -> 5 

算法：模拟

解题思路

模拟捡胡萝卜的过程，记录答案。

复杂度分析

时间复杂度：O(n*m)

n 为矩阵长度，m 为矩阵宽度。

空间复杂度：O(n*m)

n 为矩阵长度，m 为矩阵宽度。

代码

public class Solution {     /**      * @param carrot: an integer matrix      * @return: Return the number of steps that can be moved.      */     public int PickCarrots(int[][] carrot) {                  int row = carrot.length, col = carrot[0].length, step = 0;         int x = (row + 1) / 2 - 1, y = (col + 1) / 2 - 1;         int answer = carrot[x][y];          int[] x_dir = new int[]{0, 0, 1, -1};         int[] y_dir = new int[]{1, -1, 0, 0};         int[][] visited = new int[row][col];          for (int i = 0; i < row; i++) {             for (int j = 0; j < col; j++) {                 visited[i][j] = 0;             }         }         visited[x][y] = 1;         while (step <= row * col - 1) {             int move_dir = -1, move_max = -1;              for (int i = 0; i < 4; i++) {                 int temp_x = x + x_dir[i];                 int temp_y = y + y_dir[i];                  if (temp_x >= 0 && temp_x < row && temp_y >= 0 && temp_y < col && visited[temp_x][temp_y] == 0) {                     if (carrot[temp_x][temp_y] > move_max) {                         move_max = carrot[temp_x][temp_y];                         move_dir = i;                     }                 }             }             if (move_dir == -1) {                     break;                 }                  x += x_dir[move_dir];                 y += y_dir[move_dir];                  visited[x][y] = 1;                 answer += carrot[x][y];                 step += 1;         }         return answer;     } }