Leetcode daily question 2021/12/6-2021/12/12

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

12/6 1816. Truncate a sentence

1. Follow the space split
Take before k individual Merge
2. Traversal string
Space encountered +1 Until the end of the traversal or encounter the k A space

def truncateSentence1(s, k):
    """ :type s: str :type k: int :rtype: str """
    l = s.split(" ")
    l = l[:k]
    return " ".join(l)

def truncateSentence(s, k):
    """ :type s: str :type k: int :rtype: str """
    loc = 0
    n = len(s)
    while k>0:
        if s[loc]==" ":
            k-=1
        loc+=1
        if loc==n:
            return s
    return s[:loc-1]

12/7 1034. Boundary coloring

BFS
Search around from the top
mem Record the connected components that have been reached
If the top, bottom, left and right are connected Then this point is not at the boundary

def colorBorder(grid, row, col, color):
    """ :type grid: List[List[int]] :type row: int :type col: int :type color: int :rtype: List[List[int]] """
    m,n = len(grid),len(grid[0])
    oricolor = grid[row][col]
    step = [(1,0),(0,1),(-1,0),(0,-1)]
    l = [(row,col)]
    change = []
    mem={
    }
    while l:
        tmp = []
        for x,y in l:
            mem[(x,y)]=1
            num = 0
            for i,j in step:
                nx,ny = x+i,y+j
                if 0<=nx<m and 0<=ny<n and grid[nx][ny]==oricolor:
                    if (nx,ny) not in mem:
                        tmp.append((nx,ny))
                    num +=1
            if num!=4:
                change.append((x,y))
        l = tmp[:]
    for x,y in change:
        grid[x][y] = color
    return grid

12/8 689. The maximum sum of three non overlapping subarrays

Three sliding windows from left to right
sum1,sum2,sum3 Respectively record the respective sum of the current three sliding windows
maxs1 Is the maximum value of the first sliding window
maxs2 Is the maximum value of the first two sliding windows
maxs3 Is the maximum of three sliding windows
maxs1loc Is the starting position of the maximum value of the first sliding window
maxs2loc Is the starting position of the maximum value of the first two sliding windows
maxs3loc And the answers we need ans

def maxSumOfThreeSubarrays(nums, k):
    """ :type nums: List[int] :type k: int :rtype: List[int] """
    ans = []
    sum1,maxs1,maxs1loc = 0,0,0
    sum2,maxs2,maxs2loc = 0,0,()
    sum3,maxs3 = 0,0
    n = len(nums)
    for i in range(k*2,n):
        sum1+=nums[i-k*2]
        sum2+=nums[i-k]
        sum3+=nums[i]
        if i>=k*3-1:
            if sum1>maxs1:
                maxs1=sum1
                maxs1loc = i-k*3+1
            if maxs1+sum2>maxs2:
                maxs2=maxs1+sum2
                maxs2loc = (maxs1loc,i-k*2+1)
            if maxs2+sum3>maxs3:
                maxs3 = maxs2+sum3
                ans = [maxs2loc[0],maxs2loc[1],i-k+1]
            print(sum1,sum2,sum3)
            print(maxs1,maxs2,maxs3)
            print(maxs1loc,maxs2loc,ans)
            sum1-=nums[i-k*3+1]
            sum2-=nums[i-k*2+1]
            sum3-=nums[i-k+1]
    return ans
    

12/9 794. Effective tic tac toe game

Classification of discussion
O The number of must <=X The number of also |X-O|<=1
Calculate the horizontal , vertical , oblique Three cases, three identical numbers
Vertically and horizontally, each situation can only have one group in common Diagonals can satisfy three same requirements for both groups
Meeting the conditions must be the last step X Go ahead
If X Meet the three string that X The number must be >O Number
If O Meet the three string that O The number must be ==X Number

def validTicTacToe(board):
    """ :type board: List[str] :rtype: bool """
    numO,numX = 0,0
    for s in board:
        for c in s:
            if c=="O":
                numO+=1
            elif c=="X":
                numX+=1
    if numO>numX:
        return False
    if numX-numO>1:
        return False
    
    finish0,finish1,finish2 = 0,0,0
    finishType = set()
    
    for s in board:
        if s=="XXX":
            finish0+=1
            finishType.add("X")
        elif s=="OOO":
            finish0+=1
            finishType.add("O")
        if finish0>1:
            return False
    for i in range(3):
        s = board[0][i]+board[1][i]+board[2][i]
        if s=="XXX":
            finish1+=1
            finishType.add("X")
        elif s=="OOO":
            finish1+=1
            finishType.add("O")
        if finish1>1:
            return False
    if board[0][0]==board[1][1]==board[2][2] and board[0][0]!=" ":
        finish2+=1
        finishType.add(board[1][1])
    if board[0][2]==board[1][1]==board[2][0] and board[0][2]!=" ":
        finish2+=1
        finishType.add(board[1][1])
    if len(finishType)>1:
        return False
    if finish0+finish1+finish2==0:
        return True
    if ("X"in finishType and numO==numX) or("O"in finishType and numO==numX-1):
        return False
    return True

12/10 748. The shortest complement

check Used for statistical word The number of occurrences of all characters in
take words Sort by word length
From short to long and license Compare the number of characters in If it is satisfied, it will return to the first one

def shortestCompletingWord(licensePlate, words):
    """ :type licensePlate: str :type words: List[str] :rtype: str """
    from collections import defaultdict
    licensePlate = licensePlate.lower()
    words.sort(key=lambda x:len(x))
    def check(word):
        m = defaultdict(int)
        for c in word:
            m[c] +=1
        return m
    
    w = ""
    for c in licensePlate:
        if "a"<=c<="z":
            w+=c
    orim = check(w)
    n = len(w)
    
    for word in words:
        if len(word)<n:
            continue
        curm = check(word)
        ck = True
        for k,v in orim.items():
            if curm[k]<v:
                ck=False
                break
        if ck:
            return word

12/11 911. Online elections

Preprocessing find times Election results at each point in time
Binary search is not greater than t Maximum point in time result

from collections import defaultdict
class TopVotedCandidate(object):

    def __init__(self, persons, times):
        """ :type persons: List[int] :type times: List[int] """
        n = len(times)
        self.times = times
        self.person = [-1]*n 
        m = defaultdict(int)
        curp,curv = -1,0
        for i in range(n):
            m[persons[i]]+=1
            if curv<=m[persons[i]]:
                curv = m[persons[i]]
                curp = persons[i]
            self.person[i] = curp
        
    def q(self, t):
        """ :type t: int :rtype: int """
        if t<=self.times[0]:
            return self.person[0]
        if t>=self.times[-1]:
            return self.person[-1]
        l,r=0,len(self.times)
        while l<=r:
            mid = (l+r)//2
            if self.times[mid]==t:
                return self.person[mid]
            elif t<self.times[mid]:
                r = mid-1
            else:
                l = mid+1
        return self.person[r]

12/12 709. Convert to lowercase

You can directly use the provided lower
You can also capitalize ASCALL+32 Change to lowercase

def toLowerCase(self, s):
       """ :type s: str :rtype: str """
       return str.lower(str(s))