头像

Paml_Jam

HNU




离线:1个月前


新鲜事 原文

Paml_Jam
5个月前
滑动窗口 Python 版本 原题链接:https://www.acwing.com/problem/content/156/ 报 Time Limit Exceeded 有大佬可以帮看看或者给个可以过的代码吗? ``` import sys n,k=map(int,input().split()) nums=list(map(int,sys.stdin.readline().strip().split())) que=[] for i in range(n): if que and que[0]+k<=i: que.pop(0) while que and nums[que[-1]]>=nums[i]: que.pop() que.append(i) if i>=k-1: print(nums[que[0]],end=' ') print() que=[] for i in range(n): if que and que[0]<=i-k: que.pop(0) while que and nums[que[-1]]<=nums[i]: que.pop() que.append(i) if i>=k-1: print(nums[que[0]],end=' ')
```


新鲜事 原文

Paml_Jam
5个月前
用Python 写的差分矩阵,通过7/10的样例 报 Time Limit Exceeded 大佬可以帮忙看看怎么优化吗 代码如下: n,m,q=map(int,input().split()) arrays=[] for _ in range(n): arrays.append(list(map(int,input().split()))) def Insert(x1,y1,x2,y2,c): matrix[x1][y1]+=c if x2+1<n: matrix[x2+1][y1]-=c if y2+1<m: matrix[x1][y2+1]-=c if x2+1<n and y2+1<m: matrix[x2+1][y2+1]+=c matrix=[[0 for _ in range(m)] for _ in range(n)] for i1 in range(n): for i2 in range(m): Insert(i1,i2,i1,i2,arrays[i1][i2]) for _ in range(q): x1,y1,x2,y2,c=map(int,input().split()) Insert(x1-1,y1-1,x2-1,y2-1,c) for i1 in range(n): for i2 in range(m): if i2>0:matrix[i1][i2]+=matrix[i1][i2-1] for i2 in range(m): if i1>0:matrix[i1][i2]+=matrix[i1-1][i2] for i2 in range(m): print(matrix[i1][i2],end=' ') print()



Paml_Jam
6个月前

图片无法上传

详细解析请移步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))




Paml_Jam
6个月前

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




Paml_Jam
6个月前

干就完了

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
6个月前

为啥一定要写内容呢




Paml_Jam
6个月前

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

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
6个月前
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
6个月前
 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
6个月前
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