LeetCode day18

5 minutes read
LeetCode
#LeetCode
views 941 words

Diffculty: Medium

62. Unique Paths

Topic: Array, DP

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Constraints:

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

Approach1

动态规划5大步骤：

  1. 定义状态：即定义数据元素的含义，这里定义dp[i][j]为当前位置的路径数，i表示i列，j表示j行
  2. 建立状态转移方程：因为从题目要求中可以看出，机器人只能向右或向下移动. 所以到达dp[i][j]就可能是经过dp[i-1][j]到达，也可能是经过dp[i][j-1]到达(列减一或者行减一). 所以状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]
  3. 设定初始值：通过状态转移方程可以看出，i和j下表要从1开始，否则会导致数组溢出异常(因为减一). 同时每一个位置点代表到达当前位置的路径条数，所以要设置最初的路径条数即dp[i][0]=1,dp[0][j]=1，即第一行，第一列值为1.
  4. 状态压缩：即优化数组空间，每次状态的更新只依赖于前一次的状态，优化一般作用于多维数组，观察是否可以将多维数组以一维数组来动态表示，即用一维数组来保存上次的状态. 这道题的优化方法是存在的. 具体看下面的代码解释. 状态转移方程：dp[i] = dp[i-1] + dp[i]

  5. 选出结果：根据状态转移方程，求路径的总数，因此dp[-1][-1]表示的是到达最后位置的路径总条数

    def uniquePaths(m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
# 采用二位数组形式的动态规划
# f[i][j]表示当前移动到的总次数，要求f[-1][-1]
# 状态转移公式：f[i][j] = f[i-1][j]+f[i][j-1]
# 初始值：每一步移动的次数可以看做横轴和纵轴的和，因此 f[i][0] = 1,f[0][j]=1
# 运动的轨迹：要么往下，要么往左
# 时间复杂度：O(m*n),空间复杂度：O(m*n)
    
f = [[0 for i in range(n)] for i in range(m)]
for i in range(m):
    f[i][0] = 1
for j in range(n):
    f[0][j] = 1
for i in range(1,m):
    for j in range(1,n):
        f[i][j] = f[i-1][j]+f[i][j-1]
return f[-1][-1]
    

"""优化空间复杂度为O(n)"""
# 对二维矩阵进行压缩成一位数组,将最新生成的值覆盖掉旧的值,逐行求解当前位置的最新路径条数！
# 实质：在于动态计算并替换当前位置下的路径数最新值
# 状态转移公式变成：f[i] = f[i-1]+f[i]
# 初始值： f = [1]*m,取横轴
# f[-1]表示可能路径的总数
# 空间复杂度：O(n),时间复杂度:O(m*n)

f = [1]*m
for j in range(1,n):
    for i in range(1,m):
        f[i] = f[i-1]+f[i]
return f[-1]

73. Set Matrix Zeroes

Topic: Array

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

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

Follow up:

  • A straight forward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?

Approach1

用 O(m+n)额外空间, 两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0

def setZeroes(matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    row = len(matrix)
    col = len(matrix[0])
    row_zero = set()
    col_zero = set()
    for i in range(row):
        for j in range(col):
            if matrix[i][j] == 0:
                row_zero.add(i)
                col_zero.add(j)
    for i in range(row):
        for j in range(col):
            if i in row_zero or j in col_zero:
                matrix[i][j] = 0

Approach2

用O(1)空间, 用matrix第一行和第一列记录该行该列是否有0,作为标志位.

但是对于第一行,和第一列要设置一个标志位,为了防止自己这一行(一列)也有0的情况

def setZeroes(matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    row = len(matrix)
    col = len(matrix[0])
    row0_flag = False
    col0_flag = False
    # 找第一行是否有0
    for j in range(col):
        if matrix[0][j] == 0:
            row0_flag = True
            break
    # 第一列是否有0
    for i in range(row):
        if matrix[i][0] == 0:
            col0_flag = True
            break

    # 把第一行或者第一列作为 标志位
    for i in range(1, row):
        for j in range(1, col):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    #print(matrix)
    # 置0
    for i in range(1, row):
        for j in range(1, col):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if row0_flag:
        for j in range(col):
            matrix[0][j] = 0
    if col0_flag:
        for i in range(row):
            matrix[i][0] = 0
    
    # 简化版===========================================
    """
    Do not return anything, modify matrix in-place instead.
    """
    flag_col = False
    row = len(matrix)
    col = len(matrix[0])
    for i in range(row):  # 用matrix第一行和第一列记录该行该列是否有0,作为标志位
        if matrix[i][0] == 0: flag_col = True
        for j in range(1,col):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    
    # 如果标志位为0, 则该行(列)设为0
    for i in range(row - 1, -1, -1):  # from row-1 to 0
        for j in range(col - 1, 0, -1):  # from col-1 to 1
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

        if flag_col == True: matrix[i][0] = 0

75. Sort Colors

Topic: Array, Sort, Two pointer

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
  • First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

这道题目就是要给只有 0, 1, 2 三种数字的数组排序.

使用快速排序

python的builtin function - sort(), 是in-place的

Approach1

一次遍历，三指针.

l 指向 0 的右边，r 指向 2 的最左边，cur 则是当前查看的数字。

如果当前的数字是 0，就交换给 l，如果是 2 则交换给 r。如果是 1 就不用动了。

但是这里和 l 交换与和 r 交换不同的是，与 l 交换后 cur 加一以跳过刚从前面换过来的数组，但是与 r 交换不行，这是因为与 l 交换来的数，都是前面过来的，一定是 1,所以不用再看.

def sortColors(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    l = cur = 0
    r = len(nums) - 1
    while cur <= r:
        if nums[cur] == 0:
            if cur != l:
                nums[cur], nums[l] = nums[l], nums[cur]
            cur += 1
            l += 1
        elif nums[cur] == 2:
            nums[cur], nums[r] = nums[r], nums[cur]
            r -= 1
        else:
            cur += 1

时间复杂度：O(log(n))

空间复杂度：O(1)

Approach2

两次遍历，统计个数 + 生成新数字

两次遍历的方法比较简单，第一次遍历先统计出每个数字出现的次数，下一次遍历直接按照次数生成新数字就可以了，完全不用交换数字

def sortColors(nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    cnt = [0] * 3
    for n in nums: 
        cnt[n] += 1
    i = 0
    for cur in range(3):
        for j in range(cnt[cur]):
            nums[i] = cur
            i += 1