LeetCode day17

2020-05-11 4 minutes read

LeetCode

#LeetCode

views 740 words

Diffculty: Medium

50. Pow(x, n)

Topic: Math, Binary Search

Implement pow(x, n), which calculates x raised to the power n (x^n).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range $[−2^{31}, 2^{31} − 1]$

Approach1

快速幂 + 递归, 本质是分治算法.

加入计算 $x^{64}$ , 可以从x开始, 每次直接把上一次的结果进行平方, 6次就可以得到值 ==> $x \rightarrow x^{2} \rightarrow x^{4} \rightarrow x^{8} \rightarrow x^{16} \rightarrow x^{32} \rightarrow x^{64} $

如果从右往左看:

当计算 x^n时，可以先递归地计算出 $y = x^{\lfloor n/2 \rfloor}$ ，其中 $\lfloor a \rfloor$ 表示对 a 进行下取整；
根据递归计算的结果，如果 n 为偶数，那么 $x^n = y^2$ ；如果 n 为奇数，那么 $x^n = y^2 * x$
递归的边界为 n = 0，任意数的 0 次方均为 1

由于每次递归都会使得指数减少一半，因此递归的层数为 O(logn)，算法可以在很快的时间内得到结果

def myPow(x: float, n: int) -> float:
    def quickMul(N):
        if N == 0:
            return 1.0
        y = quickMul(N // 2)
        return y * y if N % 2 == 0 else y * y * x
    
    return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

时间复杂度：O(logn)，即为递归的层数

空间复杂度：O(logn)，即为递归的层数. 这是由于递归的函数调用会使用栈空间.

Approach2

快速幂 + 迭代

def myPow(x: float, n: int) -> float:
    def quickMul(N):
        ans = 1.0
        # 贡献的初始值为 x
        x_contribute = x
        # 在对 N 进行二进制拆分的同时计算答案
        while N > 0:
            if N % 2 == 1:
                # 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute
            # 将贡献不断地平方
            x_contribute *= x_contribute
            # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N //= 2
        return ans
    
    return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

时间复杂度：O(logn)，即为对 nn 进行二进制拆分的时间复杂度

空间复杂度：O(1)O(1)

54. Spiral Matrix

Topic: Array

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Approach1

First row, last column, last row, first column and then move inwards by 1 and then repeat.

def spiralOrder(matrix: List[List[int]]) -> List[int]:
   if not matrix:return []

    x=y=0                                     # 矩阵元素位置初始化
    res = []                                  # 初始化，存储遍历后的矩阵元素
    dx = [ 0, 1, 0,-1]                        # 方向：右，下，左，上
    dy = [ 1, 0,-1, 0]                        # 注：与通常平面坐标系 记号 不同
    di = 0                                    # 初始化方向变量
    visited = set()                           # 初始化集合，存储已走过的坐标
    m,n = len(matrix),len(matrix[0])          # 矩阵的行列 
            
    for i in range(m*n):                                     # 
        res.append(matrix[x][y])                             # 存储遍历矩阵过的元素
        visited.add((x,y))                                   # 存储遍历过的坐标
        tx,ty = x+dx[di],y+dy[di]                            # 先记录下一步坐标，用于判断下一步怎么走
        if 0<=tx<m and 0<=ty<n and (tx,ty) not in visited:   # 判断坐标是否需变向，且没有遍历过
            x,y = tx,ty                                       
        else:                                                
            di = (di+1)%4                                    # 改变方向，右下左上为一圈，防止方向坐标越界
            x,y = x + dx[di],y+dy[di]                        # 下一步坐标
    return res

Approach2

逆时针旋转矩阵：先转置，再上下翻转。顺时针旋转矩阵：先上下翻转，再转置

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    res = []
    while matrix:
        res += matrix.pop(0)
        print(matrix)
        matrix = list(zip(*matrix))[::-1]
        print(matrix)
        print('===')
    '''
[[4, 5, 6], [7, 8, 9]]
[(6, 9), (5, 8), (4, 7)]
===
[(5, 8), (4, 7)]
[(8, 7), (5, 4)]
===
[(5, 4)]
[(4,), (5,)]
===
[(5,)]
[(5,)]
===
[]
[]
===
    '''
    return res

55. Jump Game

Topic: Array, Greedy

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.(数组中的每个元素代表你在该位置可以跳跃的最大长度)

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 3 * 10^4
0 <= nums[i][j] <= 10^5

Approach1

def canJump(nums: List[int]) -> bool:
    # last_index = len(nums) -1
    if len(nums)==1: return True
    max_step = 0  #初始化当前能到达最远的位置
    for i,num in enumerate(nums):
        if max_step>=i and i + num > max_step: #如果当前位置能到达，并且当前位置+跳数>最远位置
            max_step = i + num
    # print(max_step,'??')
    return max_step >= i

56. Merge Intervals

Topic: Array, Sort

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Approach1

def merge(intervals: List[List[int]]) -> List[List[int]]:
    if len(intervals) == 0:
        return []
    res = []
    intervals.sort(key=lambda x: x[0])  # 先按区间左边界值由小到大排序
    for i in intervals:
        if len(res) == 0 or res[-1][1] < i[0]: # 如果res是空 或者 res最新一个的右区间小于当前的左区间, 直接添加
            res.append(i)
        else: # 否则(有重合), 直接更新res最新一个的右区间
            res[-1][1] = max(i[1], res[-1][1])
    return res