Leetcode daily question 2022/2/7-2022/2/13

The preliminary problem-solving ideas are recorded And local implementation code ; Not necessarily optimal I also hope you can discuss Progress together

2/7 1405. The longest happy string

Select the most characters each time
Judge whether the first two are the same If it is the same, select the next more characters

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. Grid lighting

n <= 10**9 Unable to proceed matrix simulation
Record line , Column , Positive skew , Skew the hash table of four different cases
The area that can be illuminated by each lamp is reflected in the hash table of four different situations
Nine areas convenient for turning off lights If there is a light, update the hash table affected by this light

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. The absolute value of the difference is K Number to number

Count the number of each value about i Yes n individual Inquire about i+k Yes m individual Can form n*m Pairs of numbers

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. Simplest fraction

Traversing molecules from small to large
Save the value of each score
If this score is not the simplest
Then the value of this fraction must have appeared
for example 2/4 Not the simplest It can be simplified as 1/2 Because from small to large
therefore 0.5 This value already exists It can be judged 2/4 Not the simplest

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. The minimum difference in student scores

After ordering The length of the sliding window is k The leftmost is the minimum The rightmost is the maximum

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. The number of enclaves

First count all the land
Remove the number of lands that can go out of the boundary from the four sides Search the connected land

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. “ balloon ” Maximum number of

Separate statistics b a l o n The number of these letters
One balloon We need two of them l and o So divide the number by 2
The minimum value of five letters That is, the maximum number of words

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)