Leetcode 初级算法 --- 数组篇

"""
思路：列表转为集合，判断集合长度和列表长度是否相等，相等False，否则True
"""
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        if len(set(nums)) == len(nums):
            return False
        return True

"""
思路：`nums.count(i)` 计算出现次数
"""
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in nums:
            if nums.count(i) == 1:
                return i

"""
思路： 先排序，然后根据索引判断对应位置数字是否相等，相等加入到空列表中，不想等数字小的i+1继续比较
"""
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
       
        i = j = 0
        lst = []
       
        while i<len(nums1) and j<len(nums2):
            if nums1[i] == nums2[j]:
                lst.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return lst

"""
思路： 递归。先判断数组是否为空，再判断最后一位是否为9，等于9递归调用到[:-1]，不等于9最后一位+1
"""
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if len(digits) == 0:
            digits = [1]
        elif digits[-1] == 9:
            digits = self.plusOne(digits[:-1])
            digits.extend([0])
        else:
            digits[-1] += 1
        return digits

"""
思路：先计算数组中0的个数，根据个数删除数组中的零，最后再数组最后添加相应个数的0
"""
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = nums.count(0)
        for i in range(count):
            nums.remove(0)
        nums.extend([0]*count)
        return nums

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if nums == None or len(nums) < 2:
            return None
        res_dict = {}
        for i, item in enumerate(nums):
            if (target - item) in res_dict.keys():
                return (res_dict[target - item], i)
            else:
                res_dict[item] = i
        return (-1, -1)

class Solution:
  # 方法一：矩阵转置
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        
        # 矩阵反转
        for i in range(n):
            for j in range(i, n):
                matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]
                
        for i in range(n):
            matrix[i].reverse()
     
     
     # 方法二：zip()函数
     def rotate1(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = zip(*matrix[::-1])

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[] for _ in range(9)]
        col = [[] for _ in range(9)]
        cell = [[] for _ in range(9)]
       
        for i, item in enumerate(board):
            for j, num in enumerate(item):
                if num != '.':
                    k = i//3*3 + j//3
                    if num in row[i] + col[j] + cell[k]:
                        return False
                    row[i].append(num)
                    col[j].append(num)
                    cell[k].append(num)
        return True