2. 面经
  3. 【Amazon面经】

【Amazon面经】 Amazon OA 数据岗

兔精精 2020-6-22 2012

Given a matrix with r rows and c columns, find the maximum score of a path starting at [0, 0] and ending at [r-1, c-1]. The score of a path is the minimum value in that path. For example, the score of the path 8 → 4 → 5 → 9 is 4.

Don't include the first or final entry. You can only move either down or right at any point in time.

Example 1:

Input: [[5, 1], [4, 5]]

Output: 4

Explanation:

Possible paths:

5 → 1 → 5 => min value is 1

5 → 4 → 5 => min value is 4

Return the max value among minimum values => max(4, 1) = 4.

Example 2:

Input: [[1, 2, 3] [4, 5, 1]]

Output: 4

Explanation:

Possible paths:

1-> 2 -> 3 -> 1

1-> 2 -> 5 -> 1

1-> 4 -> 5 -> 1

So min of all the paths = [2, 2, 4]. Note that we don't include the first and final entry.

Return the max of that, so 4.

收藏的用户（0） X
正在加载信息~
最新回复 (1)
  • Crusader 2021-3-6
    0 引用 2楼 
    
"""
Time: O(r+c)
Space: O(1)
"""

def maximum_score_path(matrix):

   r = len(matrix)

   if r < 1:
       return 0

   c = len(matrix[0])

   if c < 1:
       return 0

   curr_min = float('inf')
   i = r - 1
   j = c - 1

   while not ((i - 1 == 0 and j == 0) or (j - 1 == 0 and i == 0)):
       if min(curr_min, matrix[i-1][j]) > min(curr_min, matrix[i][j-1]):
           curr_min = min(curr_min, matrix[i-1][j])
           i -= 1
       else:
           curr_min = min(curr_min, matrix[i][j-1])
           j -= 1

   return curr_min

if __name__ == "__main__":

   input = []

   print maximum_score_path(input) == 0

   input = [[]]

   print maximum_score_path(input) == 0

   input = [
       [5, 1],
       [4, 5]
   ]

   print maximum_score_path(input) == 4

   input = [
       [1, 2, 3],
       [4, 5, 1]
   ]

   print maximum_score_path(input) == 4

   input = [
       [1, 2, 13, 22],
       [9, 5, 14, 17],
       [7, 8, 11, 3 ],
       [18, 35, 10, 1]
   ]

   print maximum_score_path(input) == 7
返回
创作新主题