LeetCode算法刷题

2022年

5月4号

118题 杨辉三角
思路：
每一行的开头和结尾都是1。其他值都是上一行上一列和上一行当前列的和。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        yanghui = list()

        for i in range(numRows):
            row = list()
            for j in range(0,i+1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    row.append(yanghui[i-1][j-1] + yanghui[i-1][j])
            yanghui.append(row)
        
        return yanghui

36题 有效的数独
思路：
重点在于判断board[i][j]在第i行，和第j列，还有第int(i/3) int(j/3)个小格子里面是否出现过两次以上。

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [[0] * 9 for _ in range(9)]
        cols = [[0] * 9 for _ in range(9)]
        subboxs = [[[0] * 9 for _ in range(3)] for _ in range(3)]
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c != '.':
                    c = int(c) - 1
                    rows[i][c] += 1
                    cols[j][c] += 1
                    subboxs[int(i/3)][int(j/3)][c] += 1
                    if rows[i][c] > 1 or cols[j][c] > 1 or subboxs[int(i/3)][int(j/3)][c] > 1:
                        return False
        return True

5月5号
73 矩阵置零
思路：
将矩阵中值为0的行和列的坐标分别进行标记，存储到两个列表中，然后遍历，进行赋值为0的 *** 作。自己的笨办法

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        hang = []
        lie = []
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 0:
                    hang.append(i)
                    lie.append(j)
        for i in hang:
            for j in range(col):
                matrix[i][j] = 0
        for j in lie:
            for i in range(row):
                matrix[i][j] = 0
        return matrix

144 二叉树前序遍历
自己的写办法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        if root == None:
            return ans 
        
        def bianli(ans,root):
            if root == None:
                return ans
            ans.append(root.val)
            bianli(ans,root.left)
            bianli(ans, root.right)
        bianli(ans, root)
        return ans

94 二叉树的中序遍历
自己的写办法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        if root == None:
            return ans 
        
        def bianli(ans,root):
            if root == None:
                return ans
            bianli(ans,root.left)
            ans.append(root.val)
            bianli(ans, root.right)
        bianli(ans, root)
        return ans

145 二叉树的后续遍历
自己的写办法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        if root == None:
            return ans 
        def bianli(ans,root):
            if root == None:
                return ans
            bianli(ans,root.left)
            bianli(ans, root.right)
            ans.append(root.val)
        bianli(ans, root)
        return ans

5月6日
387 字符串中的第一个唯一字符
思路：
用字典存储每个字符出现的次数，遍历字符串，找出第一个出现一次的字符。

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        frequency = collections.Counter(s)
        for i, ch in enumerate(s):
            if frequency[ch] == 1:
                return i
        return -1

102 二叉树的层序遍历
思路：
使用广度优先搜素（BFS）只能得到一维的输出数组，没办法区分每一层的元素。因此需要把每一层的节点遍历完之后再进入下一层开始遍历数据。引入一个队列专门存放节点，每一次迭代都将队列的长度存入一个变量，即为该层的节点数。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ret = []
        if root == None:
            return ret
        queue = []
        queue.append(root)
        while len(queue) != 0:
            level = []
            size = len(queue)
            for i in range(1, size +1):
                node = queue.pop(0)
                level.append(node.val)
                if node.left != None:
                    queue.append(node.left)
                if node.right != None:
                    queue.append(node.right)
            ret.append(level)
        return ret

5月9日

136 只出现一次的数字
思路：
可以使用哈希表记录每个数字出现的次数。也可以判断第i个数字是否在数组中出现第二次。自己写的方法

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # fre = collections.Counter(nums)
        for i in range(len(nums)):
            if nums[i] not in nums[i+1:] and nums[i] not in nums[:i]:
                return nums[i]

方法二，字典记录数字出现次数

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        fre = collections.Counter(nums)
        for i in nums:
            if fre[i] == 1:
                return i

70 爬楼梯
思路：爬到第i层的方法数是爬到第i-1层与i-2层方法数的和，因此用递归的方法求解

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        p = 1
        q = 2
        for i in range(3, n+1):
           number = q + p
           p = q
           q = number

        return number