头像

Paml_Jam

HNU


访客:234

离线:7小时前



Paml_Jam
9小时前

图片无法上传

详细解析请移步b站专栏: k m p

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




AttributeError: ‘ListNode’ object has no attribute ‘ID’

我验证之后发现在代码运行前后,head的id并没有变化

目前题解区未发现python 解法 ,求一份python代码

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

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

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




干就完了

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



为啥一定要写内容呢




不必死磕 多次提交,每次修改代码即可

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



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]



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

class Solution(object):
    def deleteDuplication(self,head):
        dummy=ListNode(None)
        dummy.next=head
        pt0=head
        #快指针
        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
11天前
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




Paml_Jam
11天前
[n,v]=map(int, input().split())
groups=[[] for i in range(n)]
cnts=[]
for i in range(n):
    cnt=int(input())
    cnts.append(cnt)
    for _ in range(cnt):
        groups[i].append([int(x) for x in input().split()])

memory=[0]*(1+v)
for i1 in range(n):
    for i2 in range(v,-1,-1):
        tmp=memory[i2]
        for i3 in range(cnts[i1]):
            if i2>=groups[i1][i3][0]:
                tmp=max(tmp,memory[i2-groups[i1][i3][0]]+groups[i1][i3][1])
        memory[i2]=tmp
print(memory[-1])



Paml_Jam
13天前

声明

发现题解区居然没有python解法

又发现讨论区大佬@[roon2300]有很好的python解法

于是稍加注释以及排版,将大佬的题解贴出来,以供大家参考


N=20001
class node:
    def __init__(self, pos, val):
        self.pos=pos
        self.val=val

dp=[0]*N

q=[node(0,0) for i in range(N)]

[n,m]=map(int,input().split())

while n:

    [v,w,s]= map(int,input().split())

    for j in range(v):

        hh=0
        #区间首端
        tt=0
        #区间尾端
        stop=(m-j)//v
        #区间长度
        for k in range(0,stop+1):

            val=dp[k*v+j]-k*w

            while hh<tt and val>=q[tt-1].val:
            #维护单调性
                tt-=1

            q[tt].pos=k

            q[tt].val=val

            tt+=1
            #延长区间

            if q[hh].pos<k-s:
            #数量限制
                hh+=1

            dp[v*k+j]=q[hh].val+k*w
            #还原
    n-=1

print(dp[m])