Leetcode daily question 2021/12/27-2022/1/2

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

12/27 825. Friends of the right age

1. user x Will not be older than their own y Send friend request
Count the number of people at all ages Deposit in m
Rank your age from bottom to top Generate prefixes and arrays
Count the range of friends added by each age Two points
2. Because the age range knows Count sorting The prefix and

def numFriendRequests1(ages):
    """ :type ages: List[int] :rtype: int """
    from collections import defaultdict
    m = defaultdict(int)
    for age in ages:
        m[age]+=1
    ageList = list(m.keys())
    ageList.sort()
    presum = [0,m[ageList[0]]]
    
    for i in range(1,len(ageList)):
        presum.append(presum[i]+m[ageList[i]])
    ans = 0
    for loc,age in enumerate(ageList):
        num = m[age]
        minage = age*1.0/2+7 # Greater than minage
        if minage<age:
            ans += num*(num-1)
        l,r = 0,loc-1
        while l<=r:
            mid = (l+r)//2
            if ageList[mid]>minage:
                r = mid-1
            else:
                l = mid+1
        if l>=0 and loc>=0:
            ans += (presum[loc]-presum[l])*num
    return ans
    
def numFriendRequests(ages):
    """ :type ages: List[int] :rtype: int """
    total = [0]*121
    for age in ages:
        total[age]+=1
    presum = [0]*121
    for i in range(1,121):
        presum[i] = presum[i-1]+total[i]
    ans = 0
    for age in range(15,121):
        if total[age]>0:
            minage = int(age/2+8)-1
            ans += total[age]*(presum[age]-presum[minage]-1)
    return ans

12/28 472. Conjunctions

1. Include compound words Must contain more than three words
The compound word must be a combination of several short words So we can start with short words
Use one set To store what has been considered list Short words in When you need to analyze this word again in the future, you can directly return True
Use set Can reduce the use of in Time consuming when searching
Overtime
2. Dictionary tree
Sort phrases from short to long
Judge whether a word is a conjunction In the dictionary tree DFS

def findAllConcatenatedWordsInADict1(words):
    """ :type words: List[str] :rtype: List[str] """
    ret = []
    if len(words)<3:
        return ret
    words.sort(key=lambda x:len(x))
    exist_dict = set()
    def check(w):
        if w in exist_dict:
            return True
        for i in range(len(w)-1,0,-1):
            if w[:i] in exist_dict and check(w[i:]):
                return True
            
        return False
   
    for w in words:
        if check(w):
            ret.append(w)
        exist_dict.add(w)
    return ret
    
def findAllConcatenatedWordsInADict(words):
    """ :type words: List[str] :rtype: List[str] """
    trie = {
    }
    
    def add(word):
        node = trie
        for c in word:
            if c in node:
                node = node[c]
            else:
                node[c] = {
    }
                node = node[c]
        node['end']=1
    def dfs(word):
        if word=="":
            return True
        node = trie
        for i,c in enumerate(word):
            if c in node:
                tmp = node[c]
                if 'end' in tmp and dfs(word[i+1:]):
                    return True
                node = node[c]                  
            else:
                return False
    ret = []
    if len(words)<3:
        return ret
    words.sort(key=lambda x:len(x))
    for word in words:
        if word =="":
            continue
        if dfs(word):
            ret.append(word)
        else:
            add(word)
    return ret

12/29 1995. Statistics special quads

1. Ordinary quadruple enumeration
2.a+b+c=d
Enumerate from back to front c Location map Storage d Possible number of occurrences

def countQuadruplets1(nums):
    """ :type nums: List[int] :rtype: int """
    n = len(nums)
    ans = 0
    for a in range(n-3):
        for b in range(a+1,n-2):
            for c in range(b+1,n-1):
                for d in range(c+1,n):
                    if nums[a]+nums[b]+nums[c]==nums[d]:
                        ans +=1
    return ans

def countQuadruplets(nums):
    """ :type nums: List[int] :rtype: int """
    from collections import defaultdict
    n = len(nums)
    m = defaultdict(int)
    ans = 0
    for c in range(n-2,1,-1):
        m[nums[c+1]]+=1
        for a in range(c-1):
            for b in range(a+1,c):
                s = nums[a]+nums[b]+nums[c]
                if s in m:
                    ans += m[s]
    return ans

12/30 846. A smooth hand

Each group has groupSize card therefore hand The number of must be divided by it
If it cannot be divided, it must false
map Count the number of cards of each kind
Use the minimum stack to store all the cards that appear
The number of fetches from the minimum heap is not 0 Minimum face
Increase the continuous groupSize Zhang
from map Reduce the number of corresponding cards by one
If there is no card on a card in the middle shows false
Small optimization ：
If the number of faces of a card k The number of each group has been greater than the remaining number
Description cannot form a complete k Group return false
for example The number of each group is 4 Remaining cards 8 Zhang Wei 1,1,1,2,2,3,3,4,
Minimum value 1 here 1 The quantity of is 2 34>8 It must be impossible to form three groups

def isNStraightHand(hand, groupSize):
    """ :type hand: List[int] :type groupSize: int :rtype: bool """
    from collections import defaultdict
    import heapq
    l = []
    heapq.heapify(l)
    n = len(hand)
    if n%groupSize!=0:
        return False
    if groupSize==1:
        return True
    m = defaultdict(int)
    for num in hand:
        m[num]+=1
        if m[num]==1:
            heapq.heappush(l,num)
            
    while n>0:
        start = l[0]
        while m[start]==0:
            heapq.heappop(l)
            start = l[0]     
        for i in range(start,start+groupSize):
            num = m[i]
            if num==0 or groupSize*num>n:
                return False
            m[i]-=1
        n-=groupSize
    return True

12/31 507. Perfect number

Find out Num Of 2 Power root sqrt
from 2 To sqrt Judge whether it is num The factor of Add up different factors

def checkPerfectNumber(num):
    """ :type num: int :rtype: bool """
    if num==1:
        return False
    sqrt = int(num**(1/2))+1
    s = 1
    for i in range(2,sqrt):
        if num%i==0:
            s += i
        if num//i!=i:
            s += num//i
        if s>num:
            return False
    return s==num

1/1 2022. Convert a one-dimensional array into a two-dimensional array

Judge whether the number is equal to m*n individual
common m That's ok Take... In turn n individual

def construct2DArray(original, m, n):
    """ :type original: List[int] :type m: int :type n: int :rtype: List[List[int]] """
    ans = []
    if len(original)!=m*n:
        return ans
    for i in range(m):
        ans.append(original[i*n:i*n+n])
    return ans

1/2 390. Eliminate the game

Remove half each time
If it's No k round interval step = 2^k
k For the even From left to right
At this beginning x The value must change by x+step
k It's odd From right to left
If the number is odd The beginning position changes to x+step
If the number is even The beginning position is reserved

def lastRemaining(n):
    """ :type n: int :rtype: int """
    start = 1
    step = 1
    k = 0
    num = n
    while num>1:
        if k%2==0: 
            start += step
        elif num%2==1:
            start +=step
        
        k+=1
        num >>=1
        step<<=1
    return start