Paml_Jam

HNU

3569

D.devil

Paml_Jam
2020-06-19 16:27



Paml_Jam
2020-06-18 12:29

Paml_Jam
2020-05-29 14:19

class Solution(object):
def strStr_0(self,haystack,needle):
# 暴力搜素
n=len(haystack)
m=len(needle)
if n==0:return 0
if n<m:return -1
for i1 in range(n):
if haystack[i1]!=needle[0]:continue
for i2 in range(m):
if i1+i2==n:return -1
if haystack[i1+i2]!=needle[i2]:break
else:return i1
return -1

def strStr_1(self,haystack,needle):
# KMP 算法
n=len(haystack)
m=len(needle)

if n<m:return -1
if not n:return n
if not m:return m

def getTable(string):
s=len(string)
memory=[0]*s
i=1
l=0
while i<s:
if string[i]==string[l]:
l+=1
memory[i]=l
i+=1
else:
if l==0:
i+=1
else:
l=memory[l-1]
result=[None]+memory[:-1]
return result

prefixTable=getTable(needle)
i1=i2=0
while i1<n:
if i2==m-1 and haystack[i1]==needle[i2]:
return i1-m+1
if haystack[i1]==needle[i2]:
i1+=1
i2+=1
else:
i2=prefixTable[i2]
if i2==None:
i1+=1
i2=0
return -1

if __name__=='__main__':

haystack="ccaaaaabaaabaaac"

needle  ="aaaaabaaab"

haystack="aabaaabaaac"

needle="aabaaac"

sl=Solution()

print(sl.strStr_0(haystack,needle))

print(sl.strStr_1(haystack,needle))



Paml_Jam
2020-05-23 13:47

## @yxc 按照y总的思路写的 是代码出问题了 还是审查机制的问题呢

class ListNode(object):
def __init__(self,x):
self.val=x
self.next=None
self.random=None

class Solution(object):
while p:
new=ListNode(p.val)
#新建节点
new.next=p.next
p.next=new
p=p.next.next
while p:
if p.random:
p.next.random=p.random.next
#更新属性
p=p.next.next
dummy=ListNode(None)
cur=dummy
while p:
#拆分
Next=p.next.next
cur.next=p.next
cur=cur.next
p.next=Next
p=p.next
return dummy.next



Paml_Jam
2020-05-23 10:12

class Solution:
def verifySequenceOfBST(self,sequence):
n=len(sequence)
if n<=1:
return True

root=sequence[-1]
idx1=None
idx2=None

for i in range(n):
if sequence[i]<root:
idx1=i
for i in range(n):
if sequence[i]>root:
idx2=i
break

if idx1==None and idx2!=None:
return self.verifySequenceOfBST(sequence[:-1])
if idx2==None and idx1!=None:
return self.verifySequenceOfBST(sequence[:-1])

if idx1>idx2:
return False
else:
l=self.verifySequenceOfBST(sequence[:idx1+1])

r=self.verifySequenceOfBST(sequence[idx1+1:-1])

return l and r


Paml_Jam
2020-05-22 14:35

Paml_Jam
2020-05-21 17:26

class Solution(object):
def isNumber(self,s):
s=s.strip()
#去除空格
if not s:
return False
if s[0]=='+' or s[0]=='-':
s=s[1:]
if not s or s[0]=='+' or s[0]=='-' or s[0]=='.' and len(s)==1:
return False
dot=0
Ee=0
num=0
for i in range(len(s)):
char=s[i]
if '0'<=char<='9':
num+=1
elif char=='+' or char=='-':
if not (s[i-1]=='e' or s[i-1]=='E'):
return False
elif char=='.':
dot+=1
if dot>1:
return False
if Ee:
return False
elif char=='e' or char=='E':
Ee+=1
if num==0:
return False
if i==0:
# E e 开头
return False
if i+1==len(s):
# E e 结尾
return False
if Ee>1:
return False
if s[i+1]=='+' or s[i+1]=='-':
if i+2==len(s):return False
else:
return False
return True


Paml_Jam
2020-05-21 13:51
class Solution(object):
def isMatch(self,s,p):
n=len(p)
m=len(s)
memory=[[False]*(m+1) for _ in range(n+1)]
memory[n][m]=True

if m==0 and n==2 and p[-1]=='*':
# 边界存疑
return True

for i1 in range(n-1,-1,-1):

for i2 in range(m-1,-1,-1):

cur=memory[i1][i2]

if p[i1]=='.' or p[i1]==s[i2]:

cur=memory[i1+1][i2+1]

if i1+1<n and p[i1+1]=='*':

cur=cur or memory[i1+2][i2]
#零次
if p[i1]=='.' or p[i1]==s[i2]:

cur=cur or memory[i1+2][i2+1] or memory[i1][i2+1]

memory[i1][i2]=cur

return memory[0][0]


Paml_Jam
2020-05-21 08:27
 class ListNode(object):
def __init__(self,x):
self.val=x
self.next=None

class Solution(object):
dummy=ListNode(None)
#快指针
pt1=dummy
#慢指针
pre=None

while pt0:
if pt0.next==None:
if pt0.val==pre:
pt1.next=None
else:
pt1.next=pt0
break
if pt0.val!=pre and pt0.val!=pt0.next.val:
#延伸
pt1.next=pt0

pt1=pt1.next

pre=pt0.val

pt0=pt0.next

return dummy.next


Paml_Jam
2020-05-18 16:24
class TreeNode(object):
def __init__(self,x):
self.val=x
self.left=None
self.right=None

class Solution(object):
def buildTree(self,preorder,inorder):
if not preorder:return None
idx=inorder.index(preorder[0])

root=TreeNode(preorder[0])
l=self.buildTree(preorder[1:idx+1],inorder[:idx])

r=self.buildTree(preorder[idx+1:],inorder[idx+1:])

root.left=l

root.right=r

return root