剑指Offer 45-66题(Python版)

小一

发布于 2019-08-14 15:48:40

8160

发布于 2019-08-14 15:48:40

文章被收录于专栏：谓之小一

45.扑克牌顺序

题目：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何，如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

# -*- coding:utf-8 -*-
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if numbers==[]:
            return False
        numbers.sort()
        zero=0
        for i in range(0,len(numbers)):
            if numbers[i]==0:
                zero=zero+1
        for i in range(zero+1,len(numbers)):
            if numbers[i]==numbers[i-1]:
                return False
            if numbers[i]-numbers[i-1]==1:
                continue
            else:
                diff=numbers[i]-numbers[i-1]-1
                zero=zero-diff

        if zero<0:
            return False
        return True

if __name__=='__main__':
    numbers=[1,0,0,1,0]
    solution=Solution()
    ans=solution.IsContinuous(numbers)
    print(ans)

46.孩子们的圈圈(圈圈中最后剩下的数)

题目：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)。

思路：约瑟夫环问题。

# 题目
# 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。
# 其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。
# 每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,
# 从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,
# 并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

# 思路
# 约瑟夫环问题

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n<1 or m<1:
            return -1
        last=0
        for i in range(2,n+1):
            last=(last+m)%i
        return last

if __name__=='__main__':
    n,m=8,4
    solution=Solution()
    ans=solution.LastRemaining_Solution(n,m)
    print(ans)

47.求1+2+3+...+n

题目：求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：利用递归当作计算结果。

# -*- coding:utf-8 -*-
class Solution:
    def Sum_Solution(self, n):
        # write code here
        if n==0:
            return 0
        return self.Sum_Solution(n-1)+n

if __name__=='__main__':
    n=6
    solution=Solution()
    ans=solution.Sum_Solution(n)
    print(ans)

48.不用加减乘除做加法

题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

思路：二进制异或进位。

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        while num2!=0:
            sum=num1^num2
            carry=(num1&num2)<<1
            num1=sum
            num2=carry
        return num1

if __name__=='__main__':
    num1,num2=10,500000
    solution=Solution()
    ans=solution.Add(num1,num2)
    print(ans)

49.把字符串转换成整数

题目：将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。

输入描述：输入一个字符串,包括数字字母符号,可以为空输出描述:如果是合法的数值表达则返回该数字，否则返回0。

示例
+2147483647
    1a33
2147483647
    0

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here
        if len(s) == 0:
            return 0
        else:
            if s[0] > '9' or s[0] < '0':
                a = 0
            else:
                a = int(s[0]) * 10 ** (len(s) - 1)
            if len(s) > 1:
                for i in range(1, len(s)):
                    if s[i] >= '0' and s[i] <= '9':
                        a = a + int(s[i]) * 10 ** (len(s) - 1 - i)
                    else:
                        return 0
        if s[0] == '+':
            return a
        if s[0] == '-':
            return -a
        return a

if __name__=='__main__':
    s='115'
    solution=Solution()
    ans=solution.StrToInt(s)
    print(ans)

50.数组中重复的数字

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：利用dict计算重复数字。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        numset=set(numbers)
        dict={}
        duplication.append(0)
        for val in numbers:
            dict[val]=0
        for i in range(0,len(numbers)):
            dict[numbers[i]]=dict[numbers[i]]+1
        for val in numset:
            if dict[val]>1:
                duplication[0]=val
                return True
        return False

if __name__=='__main__':
    numbers=[2,1,3,1,4]
    solution=Solution()
    duplication=[]
    ans=solution.duplicate(numbers,duplication)
    print(ans)

51.构建乘积数组

# 题目
# 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
# 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

# 思路
# 审题仔细 没有A[i]

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B=[]
        for i in range(0,len(A)):
            temp=1
            for j in range(0,len(A)):
                if j==i:
                    continue
                temp=temp*A[j]
            B.append(temp)
        return B

if __name__=='__main__':
    solution=Solution()
    A=[1,2,3,4,5]
    ans=solution.multiply(A)
    print(ans)

52.正则表达式匹配

题目：请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

思路：

当模式中的第二个字符不是 *时：

如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

当模式中的第二个字符是 *时：

如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式。
模式后移2字符，相当于 x*被忽略。即模式串中*与他前面的字符和字符串匹配0次。
字符串后移1字符，模式后移2字符。即模式串中*与他前面的字符和字符串匹配1次。
字符串后移1字符，模式不变，即继续匹配字符下一位，因为 *可以匹配多位。即模式串中*与他前面的字符和字符串匹配多次。

# -*- coding:utf-8 -*-
class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        if s == pattern:
            return True
        if not pattern:
            return False
        if len(pattern) > 1 and pattern[1] == '*':
            if (s and s[0] == pattern[0]) or (s and pattern[0] == '.'):
                return self.match(s, pattern[2:]) \
                       or self.match(s[1:], pattern) \
                       or self.match(s[1:], pattern[2:])
            else:
                return self.match(s, pattern[2:])
        elif s and (s[0] == pattern[0] or pattern[0] == '.'):
            return self.match(s[1:], pattern[1:])
        return False

if __name__=='__main__':
    solution=Solution()
    s='aaa'
    pattern='a*a.a'
    ans=solution.match(s,pattern)
    print(ans)

53.表示数值的字符串

题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        # 标记符号、小数点、e是否出现过
        sign,decimal,hasE=False,False,False
        for i in range(0,len(s)):
            if s[i]=='e' or s[i]=='E':
                if i==len(s)-1:# e后面一定要接数字
                    return False
                if hasE==True:# 不能出现两次e
                    return False
                hasE=True
            elif s[i]=='+' or s[i]=='-':
                #第二次出现+或-一定要在e之后
                if sign and s[i-1]!='e' and s[i-1]!='E':
                    return False
                # 第一次出现+或-，如果不是出现在字符最前面，那么就要出现在e或者E后面
                if sign==False and i>0 and s[i-1]!='e' and s[i-1]!='E':
                    return False
                sign=True
            elif s[i]=='.':
                # e后面不能出现小数点，小数点不能出现两次
                if decimal or hasE:
                    return False
                decimal=True
            elif s[i]>'9' or s[i]<'0':
                return False
        return True

if __name__=='__main__':
    solution=Solution()
    s='123e.1416'
    ans=solution.isNumeric(s)
    print(ans)

54.字符流中第一个不重复的字符

题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

输出描述：如果当前字符流没有存在出现一次的字符，返回#字符。

# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.all={}
        self.ch=[]
    def FirstAppearingOnce(self):
        # write code here
        if self.all is None:
            return '#'
        for c in self.ch:
            if self.all[c]==1:
                return c
        return '#'

    def Insert(self, char):
        # write code here
        self.ch.append(char)
        if char in self.all:
            self.all[char]=self.all[char]+1
        else:
            self.all[char]=1

if __name__=='__main__':
    solution=Solution()
    solution.Insert('g')
    ans = solution.FirstAppearingOnce()
    print(ans)
    solution.Insert('o')
    ans = solution.FirstAppearingOnce()
    print(ans)
    solution.Insert('o')
    ans = solution.FirstAppearingOnce()
    print(ans)
    solution.Insert('g')
    ans = solution.FirstAppearingOnce()
    print(ans)
    solution.Insert('l')
    ans = solution.FirstAppearingOnce()
    print(ans)
    solution.Insert('e')
    ans = solution.FirstAppearingOnce()
    print(ans)

55.链表中环的入口节点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：把链表中节点值放到dict数组中，并记录出现的次数，如果出现次数超过一次，则为环的入口节点。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead is None:
            return None
        num,dict,flag=[],{},True
        tempans=0
        while pHead and flag==True:
            num.append(pHead.val)
            numset=set(num)
            for c in numset:
                dict[c]=0
            for c in num:
                dict[c]=dict[c]+1
            for c in num:
                if dict[c]>1:
                    flag=False
                    tempans=c
            pHead=pHead.next
        while pHead:
            if pHead.val==tempans:
                return pHead
            pHead=pHead.next
        return None

if __name__=='__main__':
    pHead1 = ListNode(1)
    pHead2 = ListNode(2)
    pHead3 = ListNode(3)
    pHead4 = ListNode(4)
    pHead5 = ListNode(5)

    pHead1.next=pHead2
    pHead2.next=pHead3
    pHead3.next=pHead4
    pHead4.next=pHead5
    pHead5.next=pHead1

    solution=Solution()
    ans=solution.EntryNodeOfLoop(pHead1)
    print(ans.val)

56.删除链表中重复的节点

题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

思路：记录链表中出现的数字，然后构建新链表。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        num=[]
        tempnum1=pHead
        while tempnum1:
            num.append(tempnum1.val)
            tempnum1=tempnum1.next
        dict={}
        for c in num:
            dict[c]=0
        for c in num:
            dict[c]=dict[c]+1
        newnum=[]
        for c in num:
            if dict[c]==1:
                newnum.append(c)
        if newnum==[]:
            return None
        head=ListNode(newnum[0])
        temphead=head
        for i in range(1,len(newnum)):
            tempnode=ListNode(newnum[i])
            temphead.next=tempnode
            temphead=tempnode
        # while head:
        #     print(head.val)
        #     head=head.next
        return head

if __name__=='__main__':
    pHead1 = ListNode(1)
    pHead2 = ListNode(1)
    pHead3 = ListNode(1)
    pHead4 = ListNode(1)
    pHead5 = ListNode(1)
    pHead6 = ListNode(1)
    pHead7 = ListNode(1)

    pHead1.next=pHead2
    pHead2.next=pHead3
    pHead3.next=pHead4
    pHead4.next=pHead5
    pHead5.next=pHead6
    pHead6.next=pHead7

    solution=Solution()
    ans=solution.deleteDuplication(pHead1)
    print(ans)

57. 二叉树中的下一个节点

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：分析二叉树的下一个节点，一共有以下情况：1.二叉树为空，则返回空；2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。

# -*- coding:utf-8 -*-
class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return pNode
        if pNode.right:
            left1=pNode.right
            while left1.left:
                   left1=left1.left
            return left1

        while pNode.next:
            tmp=pNode.next
            if tmp.left==pNode:
                return tmp
            pNode=tmp

if __name__=='__main__':
    solution=Solution()

58.对称的二叉树

题目：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：采用递归的方法来判断两数是否相同。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        result=self.same(pRoot,pRoot)
        return result
    def same(self,root1,root2):
        if not root1 and not root2:
            return True
        if root1 and not root2:
            return False
        if not root1 and root2:
            return False
        if root1.val!= root2.val:
            return False

        left=self.same(root1.left,root2.right)
        if not left:
            return False
        right=self.same(root1.right,root2.left)
        if not right:
            return False
        return True

if __name__=='__main__':

    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(2)
    A4 = TreeNode(3)
    A5 = TreeNode(4)
    A6 = TreeNode(4)
    A7 = TreeNode(3)

    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A3.left=A6
    A3.right=A7


    solution = Solution()
    ans=solution.isSymmetrical(A1)
    print(ans)

59.按之字形顺序打印二叉树

题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路： 把当前列结果存放到list之中，设置翻转变量，依次从左到右打印和从右到左打印。

# -*- 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
        root=pRoot
        if not root:
            return []
        level=[root]
        result=[]
        righttoleft=False
        while level:
            curvalues=[]
            nextlevel=[]
            for i in level:
                curvalues.append(i.val)
                if i.left:
                    nextlevel.append(i.left)
                if i.right:
                    nextlevel.append(i.right)
            if righttoleft:
                    curvalues.reverse()
            if curvalues:
                    result.append(curvalues)
            level = nextlevel
            righttoleft = not righttoleft
        return result

if __name__=='__main__':
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)
    A7 = TreeNode(7)

    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A3.left=A6
    A3.right=A7

    solution = Solution()
    ans=solution.Print(A1)
    print(ans)

60.把二叉树打印成多行

题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        root=pRoot
        if not root:
            return []
        level=[root]
        result=[]
        while level:
            curvalues=[]
            nextlevel=[]
            for i in level:
                curvalues.append(i.val)
                if i.left:
                    nextlevel.append(i.left)
                if i.right:
                    nextlevel.append(i.right)
            if curvalues:
                    result.append(curvalues)
            level = nextlevel
        return result

if __name__=='__main__':
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)
    A7 = TreeNode(7)

    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A3.left=A6
    A3.right=A7

    solution = Solution()
    ans=solution.Print(A1)
    print(ans)

61.序列化二叉树

题目：请实现两个函数，分别用来序列化和反序列化二叉树。

思路：转变成前序遍历，空元素利用"#"代替，然后进行解序列。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

import collections
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return None
        res=[]
        self.pre(root,res)
        return res

    def pre(self,root,res):
        if not root:
            return
        res.append(root.val)
        if root.left:
            self.pre(root.left, res)
        else:
            res.append('#')
        if root.right:
            self.pre(root.right,res)
        else:
            res.append('#')
    def Deserialize(self, s):
        if s=='':
            return None
        vals=[]
        for i in range(0,len(s)):
            vals.append(s[i])
        vals=collections.deque(vals)
        ans=self.build(vals)
        return ans

    def build(self,vals):
        if vals:
            val = vals.popleft()
            if val == '#':
                return None
            root = TreeNode(int(val))
            root.left = self.build(vals)
            root.right = self.build(vals)
            return root
        return self.build(vals)

# [1, ',', 2, ',', 4, ',', ',', ',', 5, ',', ',', ',', 3, ',', 6, ',', ',', ',', 7, ',', ',']
if __name__=="__main__":
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)
    A7 = TreeNode(7)

    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A3.left=A6
    A3.right=A7

    solution = Solution()
    ans=solution.Serialize(A1)
    print(ans)
    root=solution.Deserialize(ans)
    res=solution.Serialize(root)
    print(res)

62.二叉搜索树中的第K个节点

题目：给定一棵二叉搜索树，请找出其中的第k小的结点。例如（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为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
        res=[]
        if not pRoot:
            return None
        self.order(pRoot,res)
        if len(res)<k or k<=0:
            return None
        else:
            return res[k-1]

    def order(self,root,res):
        if not root:
            return
        self.order(root.left,res)
        res.append(root)
        self.order(root.right,res)

if __name__=='__main__':
    A1 = TreeNode(5)
    A2 = TreeNode(3)
    A3 = TreeNode(7)
    A4 = TreeNode(2)
    A5 = TreeNode(4)
    A6 = TreeNode(6)
    A7 = TreeNode(8)

    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A3.left=A6
    A3.right=A7

    k=3
    solution = Solution()
    ans=solution.KthNode(A1,k)
    print(ans)

63.数据流中的中位数

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.data=[]
    def Insert(self, num):
        # write code here
        self.data.append(num)
        self.data.sort()
    def GetMedian(self):
        # write code here
        length=len(self.data)
        if length%2==0:
            return (self.data[length//2]+self.data[length//2-1])/2.0
        else:
            return self.data[int(length//2)]


if __name__=="__main__":
    solution=Solution()
    solution.Insert(5)
    ans = solution.GetMedian()
    print(ans)
    solution.Insert(2)
    ans = solution.GetMedian()
    print(ans)
    solution.Insert(3)
    ans = solution.GetMedian()
    print(ans)
    solution.Insert(4)
    ans = solution.GetMedian()
    print(ans)
    solution.Insert(1)
    ans = solution.GetMedian()
    print(ans)

64.滑动窗口的最大值

题目：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}，{2,3,4,2,6,[2,5,1]}。

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size==0 or num==[]:
            return []
        res=[]
        for i in range(0,len(num)-size+1):
            tempnum=[]
            for j in range(i,i+size):
                tempnum.append(num[j])
            res.append(max(tempnum))
        return res

if __name__=="__main__":
    solution=Solution()
    num=[2,3,4,2,6,2,5,1]
    size=3
    ans=solution.maxInWindows(num,size)
    print(ans)

65.矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

思路：当起点第一个字符相同时，开始进行递归搜索，设计搜索函数。

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        for i in range(0,rows):
            for j in range(0,cols):
                if matrix[i*rows+j]==path[0]:
                    if self.find_path(list(matrix),rows,cols,path[1:],i,j):
                        return True
        return False

    def find_path(self,matrix,rows,cols,path,i,j):
        if not path:
            return True
        matrix[i*cols+j]=0
        if j+1<cols and matrix[i*cols+j+1]==path[0]:
            return self.find_path(matrix,rows,cols,path[1:],i,j+1)
        elif j-1>=0 and matrix[i*cols+j-1]==path[0]:
            return self.find_path(matrix, rows, cols, path[1:], i, j - 1)
        elif i+1<rows and matrix[(i+1)*cols+j]==path[0]:
            return self.find_path(matrix, rows, cols, path[1:], i+1, j)
        elif i-1>=0 and matrix[(i-1)*cols+j]==path[0]:
            return self.find_path(matrix, rows, cols, path[1:], i-1, j)
        else:
            return False

if __name__=='__main__':
    solution=Solution()
    matrix='ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS'
    rows=5
    cols=8
    path='SGGFIECVAASABCEHJIGQEMS'
    ans=solution.hasPath(matrix,rows,cols,path)
    print(ans)

66.机器人的运动范围

题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：对未走过的路径进行遍历，搜索所有的路径值。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.vis = {}

    def movingCount(self, threshold, rows, cols):
        # write code here
        return self.moving(threshold, rows, cols, 0, 0)

    def moving(self, threshold, rows, cols, row, col):
        rowans,colans=0,0
        rowtemp,coltemp=row,col
        while rowtemp>0:
            rowans=rowans+rowtemp%10
            rowtemp=rowtemp//10
        while coltemp>0:
            colans=colans+coltemp%10
            coltemp=coltemp//10

        if rowans+colans>threshold:
            return 0
        if row >= rows or col >= cols or row < 0 or col < 0:
            return 0
        if (row, col) in self.vis:
            return 0
        self.vis[(row, col)] = 1

        return 1 + self.moving(threshold, rows, cols, row - 1, col) +\
               self.moving(threshold, rows, cols, row + 1,col) + \
               self.moving(threshold, rows,cols, row,col - 1) + \
               self.moving(threshold, rows, cols, row, col + 1)


if __name__=='__main__':
    solution=Solution()
    threshold=10
    rows,cols=1,100
    ans=solution.movingCount(threshold,rows,cols)
    print(ans)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-08-16，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自谓之小一微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度