力扣散题集合

简单

1200、最小绝对差

提示中可以得知数据量在10^5^，如果使用两层for循环判断必定超时，因此本题不能使用双层for循环进行判断

思路：

对arr进行排序
因为要判断最小绝对差，所以只需要对排序后的数字进行判断相邻两数的差值即可，如果小则更新否则不更新

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        min_ = float("inf")
        res = []
        arr.sort() # 排序之后从前往后进行遍历 排序之后找最小差值 只需要在相邻的两个数之间进行寻找判断即可
        for i in range(1,len(arr)):
            if min_ > abs(arr[i]-arr[i-1]):
                min_ = abs(arr[i]-arr[i-1])
                res = [[arr[i-1],arr[i]]]
            elif min_== abs(arr[i]-arr[i-1]):
                res.append([arr[i-1],arr[i]])
        return res

2843、统计对称整数的数目

数字转化为字符串进行判断再求和复杂度较高可以进行优化

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        def judge(num):
            num = str(num)
            a = list(num[:len(num)//2])
            b = list(num[len(num)//2:])
            a = [int(x) for x in a]
            b = [int(x) for x in b]
            return sum(a)==sum(b)
        res = 0
        for i in range(low,high+1):
            if len(str(i))%2!=0:
                continue
            if judge(i):
                res+=1
        return res

中等

2661、找出叠涂元素

题目理解：

注意关键词：arr中在mat的某一行或者某一列都被涂色且下标最小的元素返回其在arr中的下标

首先通过哈希表来对矩阵mat进行遍历，记录所有数字的键和值，其中键为矩阵中的数字，值为(i,j)元组，i和j分别表示该数字在矩阵中的行列下标。

注意题目中的len(mat) 表示矩阵共有多少行，len(mat[0])表示矩阵共有多少列

构建好哈希表之后，还需要一个for循环对arr数组进行遍历，然后需要将其中每一个数字的行列下标

这里是行满了或者列满了，用一个变量来记录当前行列被涂色的数量。

下面的代码中 c1 记录某行有多少个元素被涂色，即一共有多少列，c2记录某列有多少个元素被涂色，即一共有多少行。

判断c1[i]==len(mat[0]) or c2[j]=len(mat) 即可返回最终arr中的下标ii，注意这里i已经被用了，不能再使用i作为循环变量。

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        myhash = defaultdict(tuple)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                # print("mat[{}][{}]={}".format(i,j,mat[i][j]))
                myhash[mat[i][j]] = (i,j)
        # print(myhash)
        c1 = defaultdict(int) # 记录某行有多少个元素被涂色  ==》列
        c2 = defaultdict(int) # 记录某列有多少个元素被涂色  ==》行
        for ii in range(len(arr)):
            i,j = myhash[arr[ii]]
            # print(i,j)
        
            c1[i] += 1
            c2[j] += 1  # c2[j] 表示该列有多少个元素 即 多少行元素
            # len(mat[0])表示有多少行  len(mat) 表示有多少列
            # print(c1[i],c2[j], len(mat),len(mat[0]))
            if c1[i]==len(mat[0]) or c2[j]==len(mat):
                return ii
        return -1

优化代码：

避免重复使用len(mat)这样的变量

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m,n = len(mat), len(mat[0])   # m表示行  n表示列
        myhash = {mat[i][j]:(i,j) for i in range(m) for j in range(n)}

        # print(myhash)
        c1,c2 = [0]*m,[0]*n
        for ii in range(m*n):
            i,j = myhash[arr[ii]]
            c1[i] += 1
            c2[j] += 1
            if c1[i]==n or c2[j]==m:
                return ii
        return -1