Leetcode daily question 2021/12/20-2021/12/26

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

12/20 475. heater

Put the house The heaters are sorted from small to large
For every house Find the two heaters about their distance The shortest distance is the required distance
Double pointer l,r Represents left and right heaters
find heaters[r] The location is larger than the location of the current house
In order to make r There must be stay heater Add a heater at infinity at the end

def findRadius(houses, heaters):
    """ :type houses: List[int] :type heaters: List[int] :rtype: int """
    heaters.sort()
    houses.sort()
    print(houses)
    print(heaters)
    heaters.append(float('inf'))
    ans = 0
    l,r = 0,1
    for h in houses:
        while heaters[r]<h:
            l+=1
            r+=1
        ans = max(ans,min(abs(h-heaters[l]),abs(heaters[r]-h)))
    return ans

12/21 1154. The day of the year

Get the date of each year Judge whether it is Runnian
Add up the days before the month Plus the number of days in the current month

def dayOfYear(date):
    """ :type date: str :rtype: int """
    monthday = [31,28,31,30,31,30,31,31,30,31,30]
    l = date.split("-")
    year = int(l[0])
    if year%4==0 and (year%100!=0 or year==2000):
            monthday[1]=29
    ans =0
    month = int(l[1])
    if month>1:
        ans += sum(monthday[:month-1])
    day = int(l[2])
    ans +=day
    return ans

12/22 686. Repeat stack string matching

1. Judge b If there a Nonexistent characters If there is, it must not
take n individual a The assembled length is greater than nb String
Compare the existence and... From scratch b Same substring
2. about a,b Do less [b/a] Take the whole a At most [b/a] Round up +1 individual a
Judge whether the new string exists b

def repeatedStringMatch1(a, b):
    """ :type a: str :type b: str :rtype: int """
    m={
    }
    for c in a:
        m[c]=1
    for c in b:
        if c not in c:
            return -1
    na,nb = len(a),len(b)
    n = nb//na+2
    
    newa = "".join([a]*n)
    for i in range(len(newa)-nb+1):
        if newa[i:i+nb]==b:
            left = (nb-(na-i))
            n = left//na+1
            if left%na>0:
                n+=1
            return n
    return -1

def repeatedStringMatch(a, b):
    """ :type a: str :type b: str :rtype: int """
    na,nb = len(a),len(b)
    n = (nb+na-1)//na
    newa = a*n
    if newa.find(b)!=-1:
        return n
    newa = a*(n+1)
    if newa.find(b)!=-1:
        return n+1
    return -1

12/23 1044. Longest repeated substring

1. Violent search Record the longest answer
2. Hash the string
   If the hash value is the same, the two strings are the same
   Rabin-Karp The algorithm calculates the hash value
   A base is prone to hash conflicts Use two to greatly reduce the possibility of conflict
   Bisect the length of the substring

def longestDupSubstring1(s):
    """ :type s: str :rtype: str """
    n = len(s)
    ans = ""
    for i in range(n):
        if i+len(ans)>=n:
            break
        while s[i:i+len(ans)+1] in s[i+1:]:
            ans = s[i:i+len(ans)+1]
    return ans

def longestDupSubstring(s):
    """ :type s: str :rtype: str """
    prime1 = 31
    prime2 = 97
    MOD = 10**9+7
    n = len(s)
    arr = [ord(x)-ord('a') for x in s]
    def check(length):
        h1,h2 = 0,0
        for i in range(length):
            h1 = (h1*prime1+arr[i])%MOD
            h2 = (h2*prime2+arr[i])%MOD
        p1 = pow(prime1,length)%MOD
        p2 = pow(prime2,length)%MOD
        mem = set()
        mem.add((h1,h2))
        for left in range(1,n-length+1):
            h1 = (h1*prime1-arr[left-1]*p1+arr[left+length-1])%MOD
            h2 = (h2*prime2-arr[left-1]*p2+arr[left+length-1])%MOD
            if (h1,h2) in mem:
                return s[left:left+length]
            mem.add((h1,h2))
        return ""
    l,r = 0,n-1
    ans = ""
    while l<=r:
        mid = l+(r-l+1)//2
        cur = check(mid)
        if cur!="":
            ans = cur
            l = mid +1
        else:
            r = mid -1
    return ans

12/24 1705. The maximum number of apples to eat

The smallest pile l Storage ( Decay date , The number of apples )
Traverse the apples every day
Throw away the broken apples first
If there are apples that day take ( Decay date , The number of apples ) Put it in the pile
Choose the one with the closest decay date and take it out first
Update reactor
After traversing the date of growing apples Also take out the rest in turn

def eatenApples(apples, days):
    """ :type apples: List[int] :type days: List[int] :rtype: int """
    import heapq
    l = []
    ans = 0
    heapq.heapify(l)
    for i,apple in enumerate(apples):
        while l and l[0][0]<=i:
            heapq.heappop(l)
        if apple:
            heapq.heappush(l,[i+days[i],apple])
        if l:
            l[0][1]-=1
            if l[0][1]==0:
                heapq.heappop(l)
            ans+=1
    day = len(apples)
    while l:
        while l and l[0][0]<=day:
            heapq.heappop(l)
        if len(l)==0:
            break
        d,n = heapq.heappop(l)
        num = min(d-day,n)
        ans +=num
        day +=num
    return ans

12/25 1609. Even tree

BFS Guang Shu
level Record the current number of layers
Number of each v Need to meet with level It's different in parity
prev Record the size of the previous number in the current position To judge whether the current layer is increasing or decreasing

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def isEvenOddTree(root):
    """ :type root: TreeNode :rtype: bool """
    level = 0
    l = [root]
    while l:
        tmp = []
        prev = 0
        for i,node in enumerate(l):
            v = node.val
            if level%2+v%2!=1:
                return False
            if i>0:
                if level%2==0:
                    if v<=prev:
                        return False
                else:
                    if v>=prev:
                        return False
            prev = v
            if node.left:
                tmp.append(node.left)
            if node.right:
                tmp.append(node.right)
        level+=1
        l = tmp[:]
    return True

12/26 1078. Bigram participle

Record the first word before the current word The state of the second word a,b
If the second word status is True Then add the current word
If the first word status is True Judge whether the current word is the same as the second word
Judge whether the current word is the same as the first word Modify the first word status

def findOcurrences(text, first, second):
    """ :type text: str :type first: str :type second: str :rtype: List[str] """
    a,b = False,False
    l = text.split(" ")
    ans = []
    for word in l:
        if b:
            b = False
            ans.append(word)
        if a and word==second:
            b = True
        if word == first:
            a = True
        else:
            a = False
    return ans