lc marathon 7.16

138. Copy list with random pointer

The key is establish Old node -> New node Mapping

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        dic={
    }
        p=head # p Point to the currently replicated node 
        dumphead=Node(-1)
        q=dumphead# q Point to the last node of the replication chain , You need to connect the nodes of this round of replication 
        while(p!=None):
            node_c=Node(p.val)# replicate 
            q.next=node_c #  Connect the replication node 
            dic[p]=node_c #  Add mapping 
            q=q.next # q The node continues to point to the last 
            p=p.next # p Node forward 
        #  Copy random The direction of 
        p=head 
        q=dumphead.next # p,q  Nodes start synchronously 
        while(p!=None):
            if p.random!=None:
                q.random=dic[p.random]
            p=p.next
            q=q.next
        return dumphead.next

The finger of the sword Offer II 092. Flip the character

    #  Traverse every bit  , And suppose   This one   For the first 1( Or the last one 0)（ Front all 0, The back is full of 1）  Number of flips 
    #  In order to reduce the time complexity to O(N)
    #  We traverse each hour , It needs to be preceded by 1 The number of , And the back 0 The number of 
    #  There is a string 0 The total number of cases , Need to be behind each position 0 The number of 

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        num_s=list(s)
        count_0=s.count('0') # 0 Total number of 
        num_0=[0 for i in range(len(s))] # Store behind each location 0 The number of 
        if len(s)==1 or len(s)==0:
            return 0
        if s[0]=='1':  #  If the first one is 1, Then the following is all 0
            num_0[0]=count_0
        elif s[0]=='0':
            num_0[0]=count_0-1 #  If the first one is 1, Then the following is all 0 Minus one 
        for i in range(1,len(num_s)):
            if num_s[i]=='1':
                num_0[i]=num_0[i-1]
            else:
                num_0[i]=num_0[i-1]-1
        mini=9999 #  Used to store the minimum number of flips 
        dic={
    '0':1,'1':0}
        for i in range(len(num_s)):
            #i  Current number   The number of the previous number 
            pre0=count_0-dic[num_s[i]]-num_0[i]# Current number   front 0 The number of 
            pre1=i-pre0# Current number   front 1 The number of 
            mini=min(mini,pre1+num_0[i])
        return mini

Interview questions 08.09. Brackets

Memory storage + to flash back It's really easy to use

def generateParenthesis( n: int) :

    return gen(n)

@cache
def gen(n):
    if n==0:
        return [""]
    if n==1:
        return ["()"]
    rs=set()
    for i in range(n-1):
        for pre in gen(i):
            for las in gen(n-i-1):
                rs.add(pre+'('+las+')')
                rs.add(pre+'()'+las)
                rs.add('('+pre+')'+las)
    return list(rs)


if __name__ == '__main__':
    print(generateParenthesis(3))

Interview questions 05.03. Flip digit

Ask for a complement （ For compatibility with negative numbers ）bin(num & 0xfffffffff

class Solution:
    def reverseBits(self, num: int) -> int:
        if num==-1:
            return 32
        numbin=str(bin(num & 0xffffffff))[2:]# Turn it into 2 Base number 
        #  Traverse each number , We need to get to 0 when , Record continuous before it 1 The number of , And get it after continuous 1 The number of 
        pre=0 # Recorded in the 0 Before continuous 1 The number of  
        las=0 # Recorded in the 0 After that... In succession 1 The number of 
        i=0
        #0000
        maxo=0#  Record after conversion   The longest continuous 1 The number of 
        while(i<len(numbin)):
            if numbin[i]=='1': #  Record 1 The number of 
                pre+=1
                i=i+1
            elif numbin[i]=='0':
                ori=i #  Store the current i The location of 
                i=i+1 #  Jump to the next  
                while(i<len(numbin) and numbin[i]=='1'):
                    i+=1
                #  Final i Skip to the next 0 The location of   perhaps  len(numbin)
                las=i-ori-1 #  On behalf of the 0 After that... In succession 1 The number of 
                maxo=max(maxo,pre+las+1)
                pre=las # 
                las=0
        maxo=max(pre+1,maxo)
        return maxo