Leetcode daily question 2022/7/18-2022/4/24

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

---

7/18 749. Isolate the virus

BFS simulation
Search all areas After encountering virus
Search widely and label the linked viruses with the same label -tag
At the same time, count the number of neighbors that will be affected in the next step in this area

def containVirus(isInfected):
    """ :type isInfected: List[List[int]] :rtype: int """
    ans = 0
    m,n = len(isInfected),len(isInfected[0])
    
    while True:
        neighbors = []
        firewalls = []
        for i in range(m):
            for j in range(n):
                if isInfected[i][j]== 1:
                    l = [(i,j)]
                    tag = len(neighbors)+1
                    neighbor = set()
                    fw = 0
                    isInfected[i][j] = -tag
                    
                    while l:
                        tmp = []
                        for x,y in l:
                            for mx,my in [(0,1),(1,0),(0,-1),(-1,0)]:
                                nx,ny = x+mx,y+my
                                if 0<=nx<m and 0<=ny<n:
                                    if isInfected[nx][ny]==1:
                                        tmp.append((nx,ny))
                                        isInfected[nx][ny] = -tag
                                    elif isInfected[nx][ny]==0:
                                        fw +=1
                                        neighbor.add((nx,ny))
                        l = tmp[:]
                    neighbors.append(neighbor)
                    firewalls.append(fw)
        if not neighbors:
            break
        tag = 0
        for i in range(1,len(neighbors)):
            if len(neighbors[i])>len(neighbors[tag]):  
                tag = i
                
        ans += firewalls[tag]
        
        for i in range(m):
            for j in range(n):
                if isInfected[i][j]<0:
                    if isInfected[i][j]==-tag-1:
                        isInfected[i][j] = 2
                    else:
                        isInfected[i][j] = 1
        for i,nb in enumerate(neighbors):
            if i!=tag:
                for x,y in nb:
                    isInfected[x][y] = 1
        
        if len(neighbors)==1:
            break
    return ans

---

7/19 731. My schedule II

Line segment tree Dynamic opening point
val Record the number of times each node has
lazy Lazy mark Record the number of times that the child nodes in this node have not been distributed

class MyCalendarTwo(object):

    def __init__(self):
        self.val = {
    }
        self.lazy = {
    }
        
    def update(self,start,end,l,r,idx,val):
        if start>r or end<l:
            return
        if start<=l and r<=end:
            self.val[idx] = self.val.get(idx,0)+val
            self.lazy[idx] = self.lazy.get(idx,0)+val
            return
        mid = (l+r)>>1
        self.update(start,end,l,mid,2*idx,val)
        self.update(start,end,mid+1,r,2*idx+1,val)
        v = max(self.val.get(2*idx,0),self.val.get(2*idx+1,0))
        self.val[idx] = self.lazy.get(idx,0)+v

    def book(self, start, end):
        """ :type start: int :type end: int :rtype: bool """
        self.update(start,end-1,0,10**9,1,1)
        if self.val.get(1,0)>2:
            self.update(start,end-1,0,10**9,1,-1)
            return False
        return True

---

7/20 1260. Two dimensional grid migration

mn about grid[i][j] Marked as in+j
Each number moves k Time Find the moved marker bit

def shiftGrid(grid, k):
    """ :type grid: List[List[int]] :type k: int :rtype: List[List[int]] """
    m,n = len(grid),len(grid[0])
    ans = [[0]*n for _ in range(m)]
    total = m*n
    for i in  range(m):
        for j in range(n):
            loc = (i*n+j+k)%total
            x = loc//n
            y = loc%n
            ans[x][y] = grid[i][j]
    return ans

---

7/21 814. Two fork tree pruning

dfs Check two subtrees
If all subtrees are 0 And is itself 0 return true

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pruneTree(root):
    """ :type root: Optional[TreeNode] :rtype: Optional[TreeNode] """
    def check(node):
        if not node:
            return True
        l = check(node.left)
        if l:
            node.left = None
        r = check(node.right)
        if r:
            node.right = None
        if l and r and node.val==0:
            return True
        return False
    if check(root):
        return None
    return root

---

7/22 757. Set the intersection size to at least 2

take intervals Sort Press x[0] Ascending x[1] Descending
Make sure x[0] Phase at the same time Back x[1] Included by the previous
Think back and forth
For the interval behind In order to have more intersection with the previous interval
Take the first two numbers as good
Use last1,last2 Record the current top two numbers
For the current interval x Come on
If last2<=x[1] Explain that the two existing numbers are x Inside No need to add
If last1<=x[1] Explain that a number is x Inside Need to add a Add x First number x[0] The optimal It is most likely to be in the previous interval
otherwise It means that there is no number at present x Inside Two need to be added x[0],x[0]+1

def intersectionSizeTwo(intervals):
    """ :type intervals: List[List[int]] :rtype: int """
    intervals.sort(key=lambda x: (x[0], -x[1]))
    ans, n = 0, len(intervals)
    last1,last2 = intervals[-1][0],intervals[-1][0]+1
    ans = 2

    for i in range(n-2,-1,-1):
        if intervals[i][1]>=last2:
            continue
        elif intervals[i][1]>=last1:
            last1,last2 = intervals[i][0],last1
            
            ans +=1
        else:
            last1,last2 = intervals[i][0],intervals[i][0]+1

            ans +=2
    return ans

---

7/23 The finger of the sword Offer II 115. Reconstruction sequence

Treat two adjacent points in each subsequence as an edge
Set all entries to 0 Join the queue A topological sort
If there is more than one node in the queue It is not unique
If the queue element is 1 individual Take out Point the number to each node in degrees -1

def sequenceReconstruction(nums, sequences):
    """ :type nums: List[int] :type sequences: List[List[int]] :rtype: bool """
    from collections import defaultdict
    n = len(nums)
    inD = [0]*n
    m = defaultdict(list)
    for s in sequences:
        for i in range(len(s)-1):
            x,y = s[i],s[i+1]
            m[x].append(y)
            inD[y-1]+=1
    
    l = [i for i,v in enumerate(inD) if v==0]
    
    while l:
        tmp = []
        if len(l)>1:
            return False
        for x in l:
            for y in m[x+1]:
                inD[y-1]-=1
                if inD[y-1]==0:
                    tmp.append(y)
        l = tmp
    return True

---

7/24

---