lc marathon 7.16

138. 复制带随机指针的链表

关键是 建立 旧节点->新节点 的映射

"""
# 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指向当前被复制的节点
        dumphead=Node(-1)
        q=dumphead# q指向复制链的最后一个节点，需要连接本轮复制的节点
        while(p!=None):
            node_c=Node(p.val)#进行复制
            q.next=node_c # 连接复制节点
            dic[p]=node_c # 加入映射
            q=q.next # q节点继续指向最后一个
            p=p.next # p节点前进
        # 复制random的指向
        p=head 
        q=dumphead.next # p,q 节点同步出发
        while(p!=None):
            if p.random!=None:
                q.random=dic[p.random]
            p=p.next
            q=q.next
        return dumphead.next

剑指 Offer II 092. 翻转字符

    # 遍历每一位 ，并假设 这一位 为第一个开始的1(或者最后一个0)（前面全0，后面全1） 的翻转次数
    # 为了将时间复杂度降到O(N)
    # 我们遍历每位时，需要该数前面1的个数，和后面0的个数
    # 在有字符串0的总数的情况下，需要每个位置后面0的个数

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        num_s=list(s)
        count_0=s.count('0') # 0的总个数
        num_0=[0 for i in range(len(s))] #存储每个位置后面0的个数
        if len(s)==1 or len(s)==0:
            return 0
        if s[0]=='1':  # 如果第一位是1，则后面为全部0
            num_0[0]=count_0
        elif s[0]=='0':
            num_0[0]=count_0-1 # 如果第一位是1，则后面为全部0的个数减一
        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 # 用于存储最少翻转次数
        dic={
    '0':1,'1':0}
        for i in range(len(num_s)):
            #i 当前数 前面的数的个数
            pre0=count_0-dic[num_s[i]]-num_0[i]#当前数 前面0的个数
            pre1=i-pre0#当前数 前面1的个数
            mini=min(mini,pre1+num_0[i])
        return mini

面试题 08.09. 括号

记忆化存储+回溯 是真滴好用啊

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))

面试题 05.03. 翻转数位

求补码（为了兼容负数）bin(num & 0xfffffffff

class Solution:
    def reverseBits(self, num: int) -> int:
        if num==-1:
            return 32
        numbin=str(bin(num & 0xffffffff))[2:]#转化成2进制
        # 遍历每个数，我们需要到0时，记录在它之前连续的1的个数，并获得它之后连续1的个数
        pre=0 #记录在0之前连续1的个数 
        las=0 #记录在0之后连续1的个数
        i=0
        #0000
        maxo=0# 记录转换后 最长连续1的个数
        while(i<len(numbin)):
            if numbin[i]=='1': # 记录1的个数
                pre+=1
                i=i+1
            elif numbin[i]=='0':
                ori=i # 存储当前i的位置
                i=i+1 # 跳到下一位 
                while(i<len(numbin) and numbin[i]=='1'):
                    i+=1
                # 最终i跳到下一个0的位置 或者 len(numbin)
                las=i-ori-1 # 代表在0之后连续1的个数
                maxo=max(maxo,pre+las+1)
                pre=las # 
                las=0
        maxo=max(pre+1,maxo)
        return maxo