LeetCode day28

6 minutes read
LeetCode
#LeetCode
views 1146 words

Diffculty: Medium

279. Perfect Squares

Topic: BFS, Math, DP

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Approach1

Approach2

285. Inorder Successor in BST 二叉搜索树中的中序后继节点

Topic:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node p is the node with the smallest key greater than p.val.

Example 1:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

Note:

  1. If the given node has no in-order successor in the tree, return null.
  2. It’s guaranteed that the values of the tree are unique.

Approach1

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """

        if p.right:
            ret = p.right
            while ret.left:
                ret = ret.left
        else:
            ret = None
            node = root
            while node != p:
                if node.val > p.val:
                    ret = node
                    node = node.left
                else:
                    node = node.right

        return ret

287. Find the Duplicate Number

Topic: Array, Two pointer, Binary Search

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

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

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(^2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

Approach1

def findDuplicate(nums: List[int]) -> int:
    if not nums: return 0
    dic  = defaultdict(int)
    for i in nums:
        dic[i] += 1
        if dic[i] > 1:
            return i

违反了O(1) extra space

Approach2

预备知识：

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果

使用二分查找法定位在一个区间里的整数:

先猜一个数（有效范围 [left, right]里的中间数 mid），然后统计原始数组中小于等于这个中间数的元素的个数 cnt，如果 cnt 严格大于 mid. 根据抽屉原理，重复元素就在区间 [left, mid] 里

以 [2, 4, 5, 2, 3, 1, 6, 7] 为例，一共 8 个数，n + 1 = 8，n = 7，根据题目意思，每个数都在 1 和 7 之间。

例如：区间 [1, 7] 的中位数是 4，遍历整个数组，统计小于等于 4 的整数的个数，如果不存在重复元素，最多为 4 个。等于 4 的时候区间 [1, 4] 内也可能有重复元素。但是，如果整个数组里小于等于 4 的整数的个数严格大于 4 的时候，就可以说明重复的数存在于区间 [1, 4]

def findDuplicate(nums: List[int]) -> int:
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = left + (right-left)//2
        cnt = 0
        for i in nums:
            if i <= mid:
                cnt += 1
        # 根据抽屉原理，小于等于 4 的数的个数如果严格大于 4 个，
        # 此时重复元素一定出现在 [1, 4] 区间里

        if cnt > mid:
            # 重复的元素一定出现在 [left, mid] 区间里
            right = mid
        else:
            # if 分析正确了以后，else 搜索的区间就是 if 的反面
            # [mid + 1, right]
            left = mid + 1
    return left

时间复杂度：O(NlogN)，二分法的时间复杂度为 O(logN)，在二分法的内部，执行了一次 for 循环，时间复杂度为 O(N)，故时间复杂度为 O(NlogN)

空间复杂度：O(1)，使用了一个 cnt 变量，因此空间复杂度为 O(1)

Approach3

快慢指针, 把本题中的特殊数组抽象成一个链表，进而用快慢指针来求解.

n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n), nums[nums[index]]不会出界

def findDuplicate(nums: List[int]) -> int:
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[slow]]
    root = 0
    while root != slow:
        root = nums[root]
        slow = nums[slow]
    return slow

289. Game of Life

Topic: Array

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

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

Follow up:

  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Approach1

def gameOfLife(board: List[List[int]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    direction = [(0,-1),(0,1),(1,0),(-1,0),(1,1),(-1,-1),(-1,1),(1,-1)]
    row = len(board)
    col = len(board[0])
    # new_board = [[2 for j in range(col)] for i in range(row)]

    for i in range(row):
        for j in range(col):
            cnt = 0
            for z in direction:
                new_i = i+z[0]
                new_j = j+z[1]
                if 0 <= new_i <row and 0 <= new_j < col:
                    cnt += board[new_i][new_j] & 1
                # if new_i < 0 or new_j < 0 or new_i == row or new_j == col:
                #     continue
                # cnt += board[new_i][new_j] & 1

            if board[i][j] and cnt in [2, 3]:
                board[i][j] = 3
            if not board[i][j] and cnt == 3:
                board[i][j] = 2
    
    for i in range(row):
        for j in range(col):
            board[i][j] >>= 1  # 3 = 0011, 右移一位变成0001 & 2 = 0010, 右移一位变成0001

Approach2

Use CV, CNN kernel and padding

def gameOfLife(board: List[List[int]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    import numpy as np
    r, c = len(board), len(board[0])
    # 下面两行做 zero padding
    board_exp = np.array([[0 for _ in range(c + 2)] for _ in range(r + 2)])
    board_exp[1:1 + r, 1:1 + c] = np.array(board)
    # 设置卷积核
    kernel = np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]])
    # 开始卷积
    for i in range(1, r + 1):
        for j in range(1, c + 1):
            # 统计细胞周围 8 个位置的状态
            temp_sum = np.sum(kernel * board_exp[i - 1:i + 2, j - 1:j + 2])
            # 按照题目规则进行判断
            if board_exp[i, j] == 1:
                if temp_sum < 2 or temp_sum > 3:
                    board[i - 1][j - 1] = 0
            else:
                if temp_sum == 3:
                    board[i - 1][j - 1] = 1