Leetcode daily question 2022/3/14-2022/3/20

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

3/14 599. The minimum index sum of two lists

Traverse the index corresponding to all values in the first list record
Traverse the second list if the corresponding value exists in the first list Calculate index and Determine whether the minimum

def findRestaurant(list1, list2):
    """ :type list1: List[str] :type list2: List[str] :rtype: List[str] """
    m = {
    }
    for loc,v in enumerate(list1):
        m[v] = loc
    num  = float("inf")
    ans = []
    for loc,v in enumerate(list2):
        if v in m:
            if num>m[v]+loc:
                ans = [v]
                num = m[v]+loc
            elif num == m[v]+loc:
                ans.append(v)
    return ans        

3/15 2044. Count the number of subsets that can get the maximum value by bit

All numbers are bitwise or must be the largest
n There are... Digits in total 2^n Maybe Use one n Number selected for binary representation
If you get the target value result +1

def countMaxOrSubsets(nums):
    """ :type nums: List[int] :rtype: int """
    target = 0
    for num in nums:
        target |=num
        
    n = len(nums)
    ans = 0
    for i in range(1,2**n):
        v = 0
        for loc in range(n):
            if i&(1<<loc)>0:
                v |=nums[loc]
        if v==target:
            ans +=1
    return ans  

3/16 432. whole O(1) Data structure of

Double linked list node Each node records different times of keys
Rank according to the number of occurrences
nodes[key] Hash table record string key The node
add to key when ：
Judge key Does it already exist
If it doesn't exist ：
Judgment is to key Add to the number of occurrences 1 Of node in
Or create a new one with the number of occurrences 1 Of node
If there is ：
Judge key Number of occurrences cnt+1 Of node Whether there is hold key Join in
Or create a new one cnt+1 Of node
hold key From the original node Remove
If the original node No, key Will node remove
subtract key when :
If nodes[key] key Only once
The remove key
Otherwise, judgment cnt-1 Of node Whether there is take key Enter or create node
The least frequent occurrence is root The first one after that node Medium keys
What appears most is root Before the last one node Medium keys

class Node(object):
    def __init__(self,key="",cnt=0):
        self.prev = None
        self.next = None
        self.keys = set([key])
        self.cnt = cnt
        
    def insert(self,node):
        node.prev = self
        node.next = self.next
        node.prev.next = node
        node.next.prev = node
        return node
    
    def remove(self):
        self.prev.next = self.next
        self.next.prev = self.prev

class AllOne(object):

    def __init__(self):
        self.nodes = {
    }
        self.root = Node()
        self.root.prev = self.root
        self.root.next = self.root

    def inc(self, key):
        """ :type key: str :rtype: None """
        if key not in self.nodes:
            if self.root.next == self.root or self.root.next.cnt>1:
                node = self.root.insert(Node(key,1))
                self.nodes[key] = node
            else:
                self.root.next.keys.add(key)
                self.nodes[key] = self.root.next
        else:
            node = self.nodes[key]
            nxt = node.next
            if nxt == self.root or nxt.cnt>node.cnt+1:
                self.nodes[key] = node.insert(Node(key,node.cnt+1))
            else:
                nxt.keys.add(key)
                self.nodes[key] = nxt
            node.keys.remove(key)
            if len(node.keys)==0:
                node.remove()
        


    def dec(self, key):
        """ :type key: str :rtype: None """
        node = self.nodes[key]
        if node.cnt==1:
            del self.nodes[key]
        else:
            pre = node.prev
            if pre==self.root or pre.cnt<node.cnt-1:
                self.nodes[key] = node.prev.insert(Node(key,node.cnt-1))
            else:
                pre.keys.add(key)
                self.nodes[key] = pre
        node.keys.remove(key)
        if len(node.keys)==0:
            node.remove()


    def getMaxKey(self):
        """ :rtype: str """
        if self.root.prev==self.root:
            return ""
        else:
            v = self.root.prev.keys.pop()
            self.root.prev.keys.add(v)
            return v


    def getMinKey(self):
        """ :rtype: str """
        if self.root.next==self.root:
            return ""
        else:
            v = self.root.next.keys.pop()
            self.root.next.keys.add(v)
            return v
        

3/17 720. The longest word in the dictionary

1. Sort the list from short to long Use the dictionary tree
For words word If you can find word[:-1] Previous string Then you can put word Add to dictionary
Record the longest word
2. Sort the list from short to long
Use set Save the words that meet the conditions

def longestWord(words):
    """ :type words: List[str] :rtype: str """
    words.sort(key=lambda x:len(x))
    from collections import defaultdict
    dic = defaultdict(map)
    ans = ""
    num = 0
    for word in words:
        if len(word)==1:
            dic[word]={
    }
            if num<1 or (num==1 and word<ans):
                num=1
                ans = word
        else:
            tmpdic = dic
            tag = True
            for c in word[:-1]:
                if c in tmpdic:
                    tmpdic = tmpdic[c]
                else:
                    tag = False
                    break
            if tag:
                tmpdic[word[-1]]={
    }
                if num<len(word) or (num==len(word) and word<ans):
                    num = len(word)
                    ans = word
    return ans

def longestWord2(words):
    """ :type words: List[str] :rtype: str """
    value = set([""])
    for word in sorted(words):
        if word[:-1] in value:
            value.add(word)
    return max(sorted(value),key=len)
        

3/18 2043. Simple banking system

simulation

class Bank(object):

    def __init__(self, balance):
        """ :type balance: List[int] """
        self.num = len(balance)
        self.bl = balance


    def transfer(self, account1, account2, money):
        """ :type account1: int :type account2: int :type money: int :rtype: bool """
        if max(account1,account2)>self.num or self.bl[account1-1]<money:
            return False
        self.bl[account1-1]-=money
        self.bl[account2-1]+=money
        return True


    def deposit(self, account, money):
        """ :type account: int :type money: int :rtype: bool """
        if account>self.num:
            return False
        self.bl[account-1]+=money
        return True

    def withdraw(self, account, money):
        """ :type account: int :type money: int :rtype: bool """
        if account>self.num or self.bl[account-1]<money:
            return False
        self.bl[account-1]-=money
        return True
        

3/19 606. Create a string from a binary tree

recursive If the left child node is empty, you need to add empty brackets The right child node is empty, and there is no need to add
Root left and right

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def tree2str(root):
    """ :type root: TreeNode :rtype: str """
    def find(node):
        if not node:
            return ""
        if not node.left and not node.right:
            return str(node.val)
        if not node.right:
            return "%d(%s)"%(node.val,find(node.left))
        return "%d(%s)(%s)"%(node.val,find(node.left),find(node.right))
    return find(root)
                

3/20 2039. When the network is idle

Use wide search to find out each node to 0 The shortest path to the server dist
news x From node to 0 The server returns the required 2dist
Every node p[x] Send a message
If p[x]>=2dist The second message will not be sent
If p[x]<2dist Will send multiple messages
The last message sent is p[x]((2dist-1)//p[x])
Last need 2dist return 1 Idle in seconds

def networkBecomesIdle(edges, patience):
    """ :type edges: List[List[int]] :type patience: List[int] :rtype: int """
    n = len(patience)
    m = [[] for _ in range(n)]
    for x,y in edges:
        m[x].append(y)
        m[y].append(x)
        
    mem = [False]*n
    mem[0] = True
    l = [0]
    ans,dist = 0,1
    while l:
        tmp = []
        for loc in l:
            for node in m[loc]:
                if mem[node]:
                    continue
                mem[node] = True
                tmp.append(node)
                ans = max(ans,(dist*2-1)//patience[node]*patience[node]+2*dist+1)
        l = tmp
        dist +=1
    return ans