Leetcode daily question 2022/1/24-2022/1/30

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

1/24 2045. The second short time to reach the destination

matrix[i] representative i Points that can be reached
Each distance takes equal time We need to know how many steps we have taken between two points
dis[i][0] For from 1 To i The shortest distance dis[i][1] For from 1 To i The second short distance
Because guangsearch The number of steps only increases but not decreases Therefore, when updating the status, the number of steps must not be reduced
Just consider whether it is the first update <float(‘inf’) that will do
For a period of time t If mod=t%(2change)>change explain t Experienced a light change
Need to wait 2change-mod

def secondMinimum(n, edges, time, change):
    """ :type n: int :type edges: List[List[int]] :type time: int :type change: int :rtype: int """
    import collections
    matrix= [[] for _ in range(n+1)]
    for x,y in edges:
        matrix[x].append(y)
        matrix[y].append(x)
    dis = [[float('inf')]*2 for _ in range(n+1)]
    dis[1][0]=0
    l = collections.deque([(1,0)])
    while dis[n][1]==float('inf'):
        loc,step = l.popleft()
        step +=1
        for nxt in matrix[loc]:
            if step<dis[nxt][0]:
                dis[nxt][0]=step
                l.append((nxt,step))
            elif dis[nxt][0]<step<dis[nxt][1]:
                dis[nxt][1] = step
                l.append((nxt,step))
    ans = 0
    for _ in range(dis[n][1]):
        if ans%(2*change)>=change:
            ans +=2*change-ans%(2*change)
        ans+=time
    return ans
                

1/25 1688. The number of matches in the game

1. recursive
2. Eliminate one person at a time Need to be eliminated n-1 personal match n-1 Time

def numberOfMatches(n):
    """ :type n: int :rtype: int """
    def recu(n):
        if n==1:
            return 0
        if n%2==0:
            return n//2
        else:
            return n//2+recu(n//2+1)
    return recu(n)

def numberOfMatches2(n):
    """ :type n: int :rtype: int """
    return n-1

1/26 2013. Detection square

Hash table statistics coordinates
about x,y If y Fixed Find another point tmpx,y
Side length is diff=tmpx-x
seek (x,y) (tmpx,y),(x,y+diff),(tmpx,y+diff)

from collections import defaultdict,Counter
class DetectSquares(object):

    def __init__(self):
        self.m = defaultdict(Counter)


    def add(self, point):
        """ :type point: List[int] :rtype: None """
        x,y = point
        self.m[x][y]+=1


    def count(self, point):
        """ :type point: List[int] :rtype: int """
        ans = 0
        x,y = point
        if x not in self.m:
            return 0
        othery = self.m[x]
        
        for tmpx,cnt in self.m.items():
            if tmpx!=x:
                diff = tmpx-x
                ans += cnt[y]*othery[y+diff]*cnt[y+diff]
                ans += cnt[y]*othery[y-diff]*cnt[y-diff]
        return ans

1/27 2047. Number of valid words in the sentence

Divide into several small segments according to the space s
For each s The characters in are processed in turn
Divided into numbers ;-; punctuation ; English characters

def countValidWords(sentence):
    """ :type sentence: str :rtype: int """
    biao = ["!",".",","]
    def check(s):
        if len(s)==0:
            return False
        word = 0
        line = 0
        has = False
        for i,c in enumerate(s):
            if "0"<=c<="9":
                return False
            elif c=="-":
                if line>0 or word==0:
                    return False
                line+=1
                has = True
            elif c in biao:
                if i<len(s)-1:
                    return False
            else:
                word+=1
                has = False
        if has:
            return False
        return True                
    l = sentence.split(" ")
    ans = 0
    for s in l:
        if check(s):
            print(s)
            ans+=1
    return ans

1/28 1996. The number of weak characters in the game

Will attack a Sort from large to small At the same time, the attack power is the same as the defense b Sort from small to large
Record the maximum defense maxb Can guarantee if the current defense b Less than the maximum defense maxb
Then the attack power a It must also be less than the maximum attack force maxa

def numberOfWeakCharacters(properties):
    """ :type properties: List[List[int]] :rtype: int """
    properties.sort(key = lambda x:(-x[0],x[1]))
    ans = 0
    maxb = 0
    for a,b in properties:
        if maxb==0:
            maxb = b
        else:
            if maxb>b:
                ans+=1
            else:
                maxb = b
    return ans

1/29 1765. The highest point on the map

BFS
The initial water height is 0 The land height is infinite
Expand outward from the water Increase the height in turn The land height takes the smaller value

def highestPeak(isWater):
    """ :type isWater: List[List[int]] :rtype: List[List[int]] """
    n,m = len(isWater),len(isWater[0])
    matrix = [[float('inf')]*m for _ in range(n)]
    l = []
    for i in range(n):
        for j in range(m):
            if isWater[i][j]==1:
                l.append((i,j))
                matrix[i][j]=0
    steps = [(0,-1),(0,1),(1,0),(-1,0)]
    while l:
        tmp = set()
        for i,j in l:
            for x,y in steps:
                newi,newj = i+x,j+y
                if 0<=newi<n and 0<=newj<m:
                    if matrix[i][j]+1<matrix[newi][newj]:
                        matrix[newi][newj] = matrix[i][j]+1
                        tmp.add((newi,newj))
        l = list(tmp)
    return matrix

1/30 884. Unusual words in two sentences

The meaning of the title is known
Count all the words together What appears once is an uncommon word

def uncommonFromSentences(s1, s2):
    """ :type s1: str :type s2: str :rtype: List[str] """
    ans = []
    m = {
    }
    for word in s1.split(" "):
        m[word] = m.get(word,0)+1
    for word in s2.split(" "):
        m[word] = m.get(word,0)+1
    for word in m:
        if m[word]==1:
            ans.append(word)
    return ans