关键是 建立 旧节点->新节点 的映射
"""
# 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
# 遍历每一位 ，并假设 这一位 为第一个开始的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
记忆化存储+回溯 是真滴好用啊
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))
求补码（为了兼容负数）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
