剑指offer牛客网练习20200202

川长思鸟来 2023-07-03 04:49 33阅读 0赞

1.剪绳子

# -*- coding:utf-8 -*-
    class Solution:
        def cutRope(self, number):
            # write code here
            num=number
            if num==2:
                return 1
            if num==3:
                return 2
            if num%3==2:
                return 2*3**((num-2)/3)
            elif num%3==0:
                return 3**(num/3)
            else:
                return 4*3**((num-4)/3)

2.机器人的运动范围

没有特别复杂的思路就是新建相同大小的数组，遍历到了就设为1即可，并且把这个点加入到队列当中

注意k值如果<0，那么（0，0)也无法访问应该返回0

# -*- coding:utf-8 -*-
    class Solution:
        def movingCount(self, threshold, rows, cols):
            # write code here
            arr=[[0]*cols for i in range(rows)]
            if threshold<0:
                return 0
            #print(arr)
            l=[[0,0]]
            arr[0][0]=1
            #print(arr[0][12])
            count=1
            while(l):
                print(l[0][0],l[0][1],cols,rows)
                if l[0][0]+1>=0 and l[0][0]+1<rows and l[0][1]>=0 and l[0][1]<cols and arr[l[0][0]+1][l[0][1]]==0:
                    tempi=list(map(int,list(str(l[0][0]+1))))
                    tempj=list(map(int,list(str(l[0][1]))))
                    if sum(tempi)+sum(tempj)<=threshold:
                        arr[l[0][0]+1][l[0][1]]=1
                        l.append([l[0][0]+1,l[0][1]])
                        count+=1
                if l[0][0]-1>=0 and l[0][0]-1<rows and l[0][1]>=0 and l[0][1]<cols and arr[l[0][0]-1][l[0][1]]==0:
                    tempi=list(map(int,list(str(l[0][0]-1))))
                    tempj=list(map(int,list(str(l[0][1]))))
                    if sum(tempi)+sum(tempj)<=threshold:
                        arr[l[0][0]-1][l[0][1]]=1
                        l.append([l[0][0]-1,l[0][1]])
                        count+=1
                if l[0][0]>=0 and l[0][0]<rows and l[0][1]+1>=0 and l[0][1]+1<cols and arr[l[0][0]][l[0][1]+1]==0:
                    tempi=list(map(int,list(str(l[0][0]))))
                    tempj=list(map(int,list(str(l[0][1]+1))))
                    if sum(tempi)+sum(tempj)<=threshold:
                        arr[l[0][0]][l[0][1]+1]=1
                        l.append([l[0][0],l[0][1]+1])
                        count+=1
                if l[0][0]>=0 and l[0][0]<rows and l[0][1]-1>=0 and l[0][1]-1<cols and arr[l[0][0]][l[0][1]-1]==0:
                    tempi=list(map(int,list(str(l[0][0]))))
                    tempj=list(map(int,list(str(l[0][1]-1))))
                    if sum(tempi)+sum(tempj)<=threshold:
                        arr[l[0][0]][l[0][1]-1]=1
                        l.append([l[0][0],l[0][1]-1])
                        count+=1
                l.pop(0)
                print(l)
            return count

3.滑动窗口的最大值

注意size比num长度大或者为0

主要思路就是利用两个栈吧= =的东西= =0.查看栈里是否存在过期数1.如果滑动窗口新滑动到的那个数比原来的最大值大那么目前比它小的在栈里的都可以pop，2.如果小的话就作为备选，备选的话就把备选里面存在比它小的数都扔掉，然后把它加进去即可

# -*- coding:utf-8 -*-
    class Solution:
        def maxInWindows(self, num, size):
            # write code here
            if size==0 or size>len(num):
                return []
            l=[num[0]]
            result=[]
            if size==1:
                result.append(num[0])
            for i in range(1,len(num)):
                if i>=size:
                    if l and l[0]==num[i-size]:
                        l.pop(0)
                    elif l and l[-1]==num[i-size]:
                        l.pop()
                if not l or (l and num[i]>l[-1]):
                    l=[num[i]]
                else:
                    while num[i]>l[0]:
                        l.pop(0)
                    l=[num[i]]+l
                if i>=size-1:
                    result.append(l[-1])
            return result

4.二叉搜索树的第k个结点

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回对应节点TreeNode
        def KthNode(self, pRoot, k):
            # write code here
            l=[]
            cur=pRoot
            count=0
            while(l or cur):
                if cur:
                    l.append(cur)
                    cur=cur.left
                else:
                    count+=1
                    cur=l.pop()
                    if count==k:
                        return cur
                    else:
                        cur=cur.right
            return None

5.按之字形打印二叉树

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def Print(self, pRoot):
            # write code here
            if not pRoot:
                return []
            l=[pRoot]
            result=[[pRoot.val],[]]
            last=l[0]
            left=False
            flag=True
            while(l):
                if l[0].left:
                    l.append(l[0].left)
                    result[-1]+=[l[0].left.val]
                if l[0].right:
                    l.append(l[0].right)
                    result[-1]+=[l[0].right.val]
                if l[0]==last:
                    last=l[-1]
                    if flag:
                        result[-1]=result[-1][::-1]
                    result.append([])
                    flag=not flag
                l.pop(0)
            result.pop()
            result.pop()
            return result