LeetCode 每日一题 2022/2/7-2022/2/13

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

2/7 1405. 最长快乐字符串

每次选取都选最多的字符
判断前两个是否相同 如果相同则选次多的字符

def longestDiverseString(a, b, c):
    """ :type a: int :type b: int :type c: int :rtype: str """
    ans = []
    nums = [[a,'a'],[b,'b'],[c,'c']]
    while True:
        nums.sort(key=lambda x:-x[0])
        nxt = False
        for i,(num,c) in enumerate(nums):
            if num<=0:
                break
            if len(ans)>=2 and ans[-1]==ans[-2]==c:
                continue
            nxt = True
            ans.append(c)
            nums[i][0]-=1
            break
        if not nxt:
            return ''.join(ans)           

2/8 1001. 网格照明

n <= 10**9无法进行matrix模拟
记录行,列,正斜,反斜四个不同情况的哈希表
将每一个灯能照亮的区域在四个不同情况的哈希表中体现
便利关灯的九个区域 如果有灯则将这个灯影响的哈希表更新

def gridIllumination(n, lamps, queries):
    """ :type n: int :type lamps: List[List[int]] :type queries: List[List[int]] :rtype: List[int] """
    from collections import defaultdict
    slamp = set()
    row,col,sla,bsla=defaultdict(int),defaultdict(int),defaultdict(int),defaultdict(int)
    for i,j in lamps:
        if (i,j) in slamp:
            continue
        row[i]+=1
        col[j]+=1
        sla[i-j]+=1
        bsla[i+j]+=1
        slamp.add((i,j))
        
    def query(i,j):
        if row[i]>0 or col[j]>0 or sla[i-j]>0 or bsla[i+j]>0:
            return True
        return False
    
    ans = []
    for i,j in queries:
        if query(i,j):
            ans.append(1)
        else:
            ans.append(0)
            
        for x in [-1,0,1]:
            for y in [-1,0,1]:
                newi,newj = i+x,j+y
                if 0<=newi<n and 0<=newj<n:
                    if (newi,newj) in slamp:
                        slamp.remove((newi,newj))
                        row[newi]-=1
                        col[newj]-=1
                        sla[newi-newj]-=1
                        bsla[newi+newj]-=1
    return ans
        
                

2/9 2006. 差的绝对值为 K 的数对数目

统计每个数值个数 对于i有n个 查询i+k有m个 则可以组成n*m个数对

def countKDifference(nums, k):
    """ :type nums: List[int] :type k: int :rtype: int """
    from collections import defaultdict
    m = defaultdict(int)
    for num in nums:
        m[num]+=1
    
    ans = 0
    for num in m.keys():
        ans += m[num]*m[num+k]
    return ans
                

2/10 1447. 最简分数

从小到大遍历分子
保存每一个分数的值
如果这个分数不是最简
则这个分数的数值必定出现过
例如2/4 不是最简 可以简化为1/2 因为从小到大遍历
所以0.5这个数值已经存在过 可以判断出2/4不是最简

def simplifiedFractions(n):
    """ :type n: int :rtype: List[str] """
    ans = []
    s = set()
    for i in range(1,n):
        for j in range (i+1,n+1):
            v = i*1.0/j
            if v not in s:
                ans.append("%d/%d"%(i,j))
                s.add(v)
    return ans           

2/11 1984. 学生分数的最小差值

排序后 滑动窗口长度为k 最左边为最小值 最右边为最大值

def minimumDifference(nums, k):
    """ :type nums: List[int] :type k: int :rtype: int """
    if k==1:
        return 0
    nums.sort()
    l,r = 0,k-1
    ans = float("inf")
    while r<len(nums):
        ans = min(ans,nums[r]-nums[l])
        if ans ==0:
            return ans
        r+=1
        l+=1
    return ans
                

2/12 1020. 飞地的数量

先统计所有陆地数
从四边去除可以走出边界的陆地数 广搜连通的陆地

def numEnclaves(grid):
    """ :type grid: List[List[int]] :rtype: int """
    ans = 0
    m,n = len(grid),len(grid[0])
    for i in range(m):
        ans += sum(grid[i])
    l = []
    for i in range(m):
        if grid[i][0]==1:
            l.append((i,0))
        if grid[i][n-1]==1:
            l.append((i,n-1))
    for j in range(1,n-1):
        if grid[0][j]==1:
            l.append((0,j))
        if grid[m-1][j]==1:
            l.append((m-1,j))
    
    while l:
        tmp = set()
        for i,j in l:
            if grid[i][j]==1:
                ans-=1
                grid[i][j]=0
                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if 0<=x<m and 0<=y<n:
                        tmp.add((x,y))
        l = list(tmp)
    return ans
                

2/13 1189. “气球” 的最大数量

分别统计b a l o n 这几字母的个数
一个balloon中需要两个l和o 所以将其个数除以2
五个字母的最小值 即为组成单词的最大个数

def maxNumberOfBalloons(text):
    """ :type text: str :rtype: int """
    a,b,l,o,n = 0,0,0,0,0
    for c in text:
        if c=="a":
            a+=1
        elif c=="b":
            b+=1
        elif c=="l":
            l+=1
        elif c=="o":
            o+=1
        elif c=="n":
            n+=1
    o = o//2
    l = l//2
    return min(a,b,l,o,n)