剑指offer全集python（3/3）第三大部分

短命女 2022-04-23 15:28 164阅读 0赞

**目录**

45.圆圈后最后剩下额数

46.求1,2.。。n的和

47.不用加减乘除做相加

49.将字符串转换成整数

50.数组中重复的数字

51.构建乘积数组

52.正则表达式匹配

53.表示数值的字符串

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

55.链表中环的入口

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

57.二叉树的下一个结点

58.判断是否是对称二叉树

59.按之字形打印二叉树

60.把二叉树打印成多行

61.序列二叉树

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

63.数据流中的中位数

64.滑动窗口的最大值

65.矩阵中的路径

66.机器人的运动范围

--------------------

![20200423163552793.PNG][]

### 45.圆圈后最后剩下额数 ###

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。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 not n or m < 0:
                return -1 
            data = [i for i in range(n)] #n 为5， m为3 
            index = -1 
            while len(data) > 1:
                index = (index + m) % len(data) #需要进行删除的第几个数
                data.remove(data[index]) #移除特定的数
                index -= 1
            return data[0]

约瑟夫环

class Solution:
        def LastRemaining_Solution(self, n, m):
            # write code here
            #使用模拟游戏的方法进行求解
            if not n or m < 0:
                return -1 
            remainIndex = 0
            for i in range(1, n+1):
                remainIndex = (remainIndex + m) % i 
            return remainIndex

### 46.求1,2.。。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
            #使用递归函数
            
            return n and (n + self.Sum_Solution(n-1))

print(1 and 100) #100
    print(0 and 100) # 0

# -*- coding:utf-8 -*-
    class Solution:
        def Sum_Solution(self, n):
            # write code here
            #使用递归函数
            
            return reduce(lambda x, y: x+y, range(1, n+1))

### 47.不用加减乘除做相加 ###

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

1.  两个数异或：相当于每一位相加，而不考虑进位；
2.  两个数相与，并左移一位：相当于求得进位；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xyczEzNTMyODEwMDQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][20190213172431556.png]

链接：[https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215][https_www.nowcoder.com_questionTerminal_59ac416b4b944300b617d4f7f111b215]  
来源：牛客网

13+11 = ？;

13 的二进制 1 1 0 1 -----a 13

11 的二进制 1 0 1 1 -----b 11

(a&b) <<1 -> 1 0 0 1 **0** \-----d 18

a^b -> 0 1 1 **0** \-----e 6

(d&e) <<1 -> 0 0 1 **0 0** \------f 4

d^e -> 1 0 1 **0 0** \-----g 20

(f&g) <<1 -> 0 1 **0 0 0** \------h 8

f^g -> 1 0 **0 0 0**  \------i 16

(h&i) <<1 -> 0 **0 0 0 0**  \------h 0 ---- --------退出循环

h^i -> 1 1 0 0 0 ------i 24

# -*- coding:utf-8 -*-
    class Solution:
        def Add(self, num1, num2):
            # write code here
            while num2: 
                sum = (num1 ^ num2) & 0xFFFFFFFF #防止为负数的时候溢出
                carry = ((num1 & num2) << 1) & 0xFFFFFFFF
                num1 = sum 
                num2 = carry 
            return num1 if num1<=0x7FFFFFFF else ~(num1^0xFFFFFFFF) ##判断如果为负数的情况下

参考：[https://blog.csdn.net/lrs1353281004/article/details/87192205][https_blog.csdn.net_lrs1353281004_article_details_87192205]

### 49.将字符串转换成整数 ###

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

# -*- coding:utf-8 -*-
    class Solution:
        def StrToInt(self, s):
            # write code here
            if not s or (len(s)==1 and s=='+') or (len(s)==1 and s=='-'):
                return 0
            ret = ''
            num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9' ]
            for st in s:
                if st ==  '+':
                    continue 
                elif st == '-':
                    continue 
                elif st in num:
                    ret += st 
                else:
                    return 0 
                
            if s[0] == '-':
                ret = -int(ret)
            else:
                ret = int(ret)
            return ret

### 50.数组中重复的数字 ###

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

1.使用哈希表

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

### 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\]。不能使用除法。

链接：[https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46][https_www.nowcoder.com_questionTerminal_94a4d381a68b47b7a8bed86f2975db46]  
来源：牛客网

剑指的思路：

**B\[i\]的值可以看作下图的矩阵中每行的乘积。**

下三角用连乘可以很容求得，上三角，从下向上也是连乘。

因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B\[i\]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

![format_png][]

# -*- coding:utf-8 -*-
    class Solution:
        def multiply(self, A):
            # write code here
            if not A:
                return 
            B = [1] * len(A) #创将数组的大小
            #计算出下三角形的乘积
            B[0] = 1
            for i in range(1, len(A)):
                B[i] = B[i-1] * A[i-1]
            
            #计算出右三角的乘积
            temp = 1
            for j in range(len(A)-2, -1, -1):
                temp *= A[j+1] # 多次使用到A 的元素，创将temp
                B[j] *= temp 
            return B

### 52.正则表达式匹配 ###

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

逻辑判断的流程：

> 1. s， pattern都为空
> 
> 2. s不为空，pattern为空
> 
> 3. s为空， pattern不为空
> 
> 3.1 如果pattern\[1\] == '\*'（前提肯定要满足 len(pattern) > 1）
> 
> 4. s不为空，pattern不为空
> 
> 4.1 如果 pattern\[1\] == '\*'（前提肯定要满足 len(pattern) > 1）
> 
> 4.1.1 在pattern\[1\] == '\*'前提下，如果s和pattern第一个字符不相同时
> 
> 4.1.2 在pattern\[1\] == '\*'前提下， 如果s和pattern第一个字符相同时：
> 
> 3 种情况------
> 
> 4.2 否则（如果 pattern\[1\] ！= '\*'）：
> 
> 4.2.1 如果s和pattern第一个字符相同，True
> 
> 4.2.2 否则，False

# -*- coding:utf-8 -*-
    class Solution:
        # s, pattern都是字符串
        def match(self, s, pattern):
            # write code here
            # 分为 4 个大的判断条件
            if not s and not pattern: # 如果 2 者都为空的情况下
                return True
            
            elif s and not pattern:
                return False
            
            elif not s and pattern: # 如果s 为空，但是 pattern 不为空的情况下
                if len(pattern) > 1 and pattern[1] == '*':
                    return self.match(s, pattern[2:])
                else:
                    return False
            else: # 如果两者都不为空的情况下, 在判断第一个字符是否相同的前提下，先判断 *
                
                if len(pattern) > 1 and pattern[1] == '*':
                    # 如果在 pattern[1] == '*'， 但是第一个字符不相同的情况下
                    if  s[0] != pattern[0] and pattern[0] != '.':
                        return self.match(s, pattern[2:])
                    else:
                       #如果在 pattern[1] == '*'， 且第一个字符都相同的情况下 
                    # 有 3 中情况需要考虑
                        m0 = self.match(s, pattern[2:])  # 如： s ='bcd', pattern = 'a*bcd', 相当于 * 为0, 不进行匹配
                        m1 = self.match(s[1:], pattern[2:]) # 如： s = 'abcd'. pattern = 'a*bcd"  匹配成功了 1 位
                        mn = self.match(s[1:], pattern) # 如   s = 'aaaaabcd'. pattern = 'a*bcd" 
                        return m0 or m1 or mn
                else:
                    # 如果第2 个字符不为 *时：
                    if s[0] == pattern[0] or pattern[0] == '.': # 第一个字符相同
                        return self.match(s[1:], pattern[1:])
                    else:
                        return False

### 53.表示数值的字符串 ###

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

需要注意的是，指数E后面必须跟一个整数，不能没有数，也不能为小数。

需要很多逻辑判断呀

# -*- coding:utf-8 -*-
    class Solution:
        # s字符串
        def isNumeric(self, s):
            # write code here
            if not s:
                return False 
            #找出全部不合法的情况：
            hasE, hasSymbol, hasDot = False, False, False
            for i in range(len(s)):
                if s[i] == 'e' or s[i] == 'E':
                    # 如果在首字母出现；重复出现；后面没有元素
                    if i == len(s)-1:
                        return False
                    elif i == 0:
                        return False
                    elif hasE:
                        return False
                    hasE = True 
                elif s[i] == '+' or s[i] == '-':
                    #如果不是出现在第一位,且前面不是e；重复出现，且前面不是e；
                    if hasSymbol and s[i-1] != 'E' and s[i-1] != 'e':
                        return False 
                    elif i != 0 and s[i-1] != 'E' and s[i-1] != 'e':
                        return False
                    hasSymbol = True
                elif s[i] == '.':
                    #如果存在多个 .; 出现在e的后面
                    if hasDot:
                        return False 
                    elif hasE:
                        return False 
                    hasDot = True 
                elif s[i] < '0' or s[i] > '9': # 可能存在不是数字的字符
                    return False 
            return True

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

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

输出描述:

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

# -*- coding:utf-8 -*-
    class Solution:
        # 返回对应char
        def __init__(self):
            self.hashes = {}
            self.st = []
        def FirstAppearingOnce(self):
            # write code here
            if not self.st:
                return 
            for num in self.st:
                if self.hashes[num] == 1:
                    return num 
            return '#'
            
        def Insert(self, char):
            # write code here
            if char not in self.hashes.keys():
                self.hashes[char] = 1
                self.st.append(char)
            else:
                self.hashes[char] += 1

### 55.链表中环的入口 ###

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

使用数组：

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        def EntryNodeOfLoop(self, pHead):
            # write code here
            num = [] #使用一个数组保存遍历的值
            while pHead:
                
                if pHead.val in num:
                    return pHead 
                num.append(pHead.val)
                pHead = pHead.next 
            return None

链接：[https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4][https_www.nowcoder.com_questionTerminal_253d2c59ec3e4bc68da16833f79a38e4]  
来源：牛客网

![format_png 1][]

假设x为环前面的路程（黑色路程），a为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c为环的长度（蓝色+橙色路程）

当快慢指针相遇的时候：

此时慢指针走的路程为Sslow = x + m \* c + a  
快指针走的路程为Sfast = x + n \* c + a  
2 Sslow = Sfast  
2 \* ( x + m\*c + a ) = (x + n \*c + a)  
从而可以推导出：  
x = (n - 2 \* m )\*c - a  
= (n - 2 \*m -1 )\*c + c - a  
即环前面的路程 = 数个环的长度（为可能为0） + c - a  
什么是c - a？这是相遇点后，环后面部分的路程。（橙色路程）

所以，我们可以让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走，  
2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x）  
从相遇点开始走的那个指针也一定刚好到达环入口点。  
所以2者会相遇，且恰好相遇在环的入口点。

最后，判断是否有环，且找环的算法复杂度为：

时间复杂度：O(n)

空间复杂度：O(1)

> 步骤1：找到相遇点，没有则是无环
> 
> 步骤2：找到环入口，让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        def EntryNodeOfLoop(self, pHead):
            # write code here
            #步骤1 ，找到相遇点
            if not pHead or not pHead.next or not pHead.next.next:
                return 
            low = pHead.next 
            fast = pHead.next.next 
            while(low != fast):
                if not low or not fast:
                    return 
                low = low.next 
                fast = fast.next.next
            #环的入口
            head = pHead 
            while(head != low):
                head = head.next 
                low = low.next 
            return low

### 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
            if not pHead:
                return 
            first = ListNode(-1)
            first.next = pHead 
            last = first 
            #需要增加一个last 结点，用来使链表连续
            while pHead and pHead.next:
                if pHead.val == pHead.next.val:
                    val = pHead.val 
                    while pHead and val == pHead.val: #可能存在多个相同元素的结点
                        pHead = pHead.next 
                    last.next = pHead 
                else:
                    last = pHead 
                    pHead = pHead.next #更新结点
            return first.next

### 57.二叉树的下一个结点 ###

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

链接：[https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e][https_www.nowcoder.com_questionTerminal_9023a0c988684a53960365b889ceaf5e]  
来源：牛客网

思路：首先知道中序遍历的规则是：左根右，然后作图

![format_png 2][]

结合图，我们可发现分成两大类：**1、有右子树的**，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） **2、没有右子树的，也可以分成两类**，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。

**1、有右子树的**，那么下个结点就是右子树最左边的点

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

**其中next结点是指向父亲结点**

# -*- 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 
            #如果有右子树的话，找到最左的结点
            if pNode.right:
                pNode = pNode.right  
                while pNode.left: 
                    pNode = pNode.left 
                return pNode #其中包含了如果没有左结点，则返回根结点的情况
            # 如果没有右子树,1.如果此结点左结点，则返回其根节点；2.如果是右叶子结点，则一直往上寻找父节点，然后继续判断其是否有左结点
            while pNode.next:
                pRoot = pNode.next 
                if pRoot.left == pNode:
                    return pRoot 
                pNode = pNode.next 
            return

### 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 
            return self.helper(pRoot.left, pRoot.right)
            
        def helper(self, left, right):
            if not left and not right: #如果左右子树都为空的话，则为真
                return True 
            if not left or not right: #如果只有一边是空的，则不是对称树
                return False
            return left.val == right.val and self.helper(left.left, right.right) and self.helper(left.right, right.left) #判断左右结点的值是否相同；左子树的左结点和右子树的右结点是否相同；---

### 59.按之字形打印二叉树 ###

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

**即使用层次遍历得到每一层分开的多重数组，然后按单双次打印，单次按顺序，双次反向打印。**

# -*- 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 []
            #使用队列存储各个结点信息
            queue = [pRoot]
            values = []
            while queue: #将每层的信息存储起来
                temp = [] #需要重复使用该数组
                for i in range(len(queue)):
                    node = queue.pop(0)
                    temp.append(node.val)
                
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                values.append(temp)
             #分单双层输出
            res = []
            for i, j in enumerate(values):
                if i % 2 == 0:
                    res.append(j)
                else:
                    res.append(j[::-1])
            return res

### 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
            if not pRoot:
                return []
            result = []
            queue = [pRoot] #将所有的结点存储在队列中
            while queue:
                temp = []
                for i in range(len(queue)):
                    node = queue.pop(0)
                    temp.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                result.append(temp)
            return result

### 61.序列二叉树 ###

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

二叉树的序列化就是采用前序遍历二叉树输出节点，再碰到左子节点或者右子节点为None的时候输出一个特殊字符”\#”。

![70][]

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def __init__(self):
            self.flag = -1
        def Serialize(self, root): #3递归进行序列化,需要使用前序遍历,根，左，右
            # write code here
            if not root:
                return '#'
            return str(root.val) +',' + self.Serialize(root.left) +',' + self.Serialize(root.right)
        def Deserialize(self, s):
            # write code here
            self.flag += 1
            li = s.split(',')
            if self.flag >= len(li): #递归的终止条件
                return 
            
            root = None
            if li[self.flag] != '#':
                root = TreeNode(int(li[self.flag]))
                root.left = self.Deserialize(s)
                root.right = self.Deserialize(s)
            return root

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

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

\#中序输出保存到列表中，输出第k-1 个值

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回对应节点TreeNode
        def __init__(self):
            self.li = []
        
        def KthNode(self, pRoot, k):
            # write code here
            #先中序遍历，然后获取第k个结点
            if not pRoot or k <= 0:
                return None
            
            self.inOrder(pRoot)
            if len(self.li) < k: #还需要判断k值是否是大于数的大小
                return None
            return self.li[k-1]
            
        def inOrder(self, pRoot): #中序遍历并将遍历结果爆出到数组中
            if pRoot is None:
                return 
            self.inOrder(pRoot.left)
            self.li.append(pRoot)
            self.inOrder(pRoot.right)

### 63.数据流中的中位数 ###

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

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.res = []
            
        def Insert(self, num):
            # write code here
            self.res.append(num)
            self.res.sort() #对数组进行排序
            
        def GetMedian(self, n=None):
            # write code here
            
            if not self.res:
                return 
            length = len(self.res) 
            if length % 2 == 1: #判断数组的长度是否是奇数
                index = length // 2
                return self.res[index]
            else:
                index = length // 2 
                return (self.res[index] + self.res[index-1]) / 2.0 # 除数必须是小数

\#使用最大堆和最小堆的方法：

最大堆和最小堆：[https://blog.csdn.net/qq\_40587575/article/details/89290135][https_blog.csdn.net_qq_40587575_article_details_89290135]

# -*- coding:utf-8 -*-
    import heapq 
    class Solution:
        def __init__(self):
            self.nums = []
            
        def Insert(self, num):
            heapq.heappush(self.nums, num) #在堆中增加元素
    
        def GetMedian(self, n=None):
            # write code here
            
            if not self.nums:
                return 
            length = len(self.nums)
    
            if length % 2 == 1: #如果数组是奇数情况， 
                index = (length + 1) // 2
            else:
                index = length // 2 
            result = (heapq.nlargest(index, self.nums)[-1] + heapq.nsmallest(index, self.nums)[-1])
            return result / 2.0

### 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\]\}。

使用大顶堆的复杂度是nlogn

# -*- coding:utf-8 -*-
    import heapq 
    class Solution:
        def maxInWindows(self, num, size):
            # write code here
            
            length = len(num)
            if length < size or size <= 0 or length == 0:
                return []
            n = length - size + 1 #总共可以获得多少个值
            result = [None] * n
            for i in range(n):
                li = num[i : i+size]
                result[i] = heapq.nlargest(1, li)[-1]
            return result

使用双端队列，复杂度为O(n)

# -*- coding:utf-8 -*-
     
    class Solution:
        def maxInWindows(self, num, size):
            # write code here
            
            length = len(num)
            if length < size or size <= 0 or length == 0:
                return []
            
            index = []
            maxNums = []
            for i in range(length):
                if index and i - size >= index[0]:  #如果index[0]一直比size个数的值都大，从前面删除元素
                    index.pop(0) 
                while index and num[i] > num[index[-1]]: #如果当前元素比前一个元素都大，则删除前一个元素，保存最大的元素
                    index.pop()
                    
                index.append(i)
                print(index)
                if i+1 - size >= 0:
                    maxNums.append(num[index[0]])
            return maxNums

### 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
            if not matrix or not path or len(matrix) != rows * cols:
                return False
            visited = [False] * len(matrix)
            pathLength = 0 #存储path的长度
            for i in range(rows):
                for j in range(cols):
                    if self.search(matrix, rows, cols, path, j, i, visited, pathLength):
                        return True 
            return False
        
        def search(self, matrix, rows, cols, path, x, y, visited, pathLength):
            if len(path) == pathLength:
                return True
            # 其中 x代表了列数，y代表了行数
            result = False 
            index = y * cols + x
            #判断是否满足递归条件
    #需要满足倒数第2个条件是 其个字符是要相同的
            if 0 <= x < cols and 0 <= y < rows and path[pathLength] == matrix[index] and not visited[index]:
                pathLength += 1
                visited[index] = True 
                x1 = self.search(matrix, rows, cols, path, x-1, y, visited, pathLength)
                x2 = self.search(matrix, rows, cols, path, x, y-1, visited, pathLength)
                x3 = self.search(matrix, rows, cols, path, x+1, y, visited, pathLength)
                x4 = self.search(matrix, rows, cols, path, x, y+1, visited, pathLength)
                result = x1 or x2 or x3 or x4
                if not result:
                    pathLength -= 1
                    visited[index] = False
            return result

### 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 Solution5:
        def movingCount(self, threshold, rows, cols):
            # write code here
            #创建一个全是空的矩阵
            matrix = [[0 for i in range(cols)] for j in range(rows)]
            count = self.countHelper(matrix, rows, cols, threshold, 0, 0)
            return count 
             
        #判断是否满足阈值条件
        def judge(self, threshold, i, j):
            if sum([int(k) for k in (str(i)+ str(j))]) <= threshold:
                return True 
            else:
                return False
        
        #递归计算走的次数
        def countHelper(self, matrix, rows, cols, threshold, i, j):
            count = 0
            if 0 <=i<rows and 0<=j<cols and self.judge(threshold, i, j) and matrix[i][j]==0:
                matrix[i][j] = 1
                count1 = self.countHelper(matrix, rows, cols, threshold, i-1, j)
                count2 = self.countHelper(matrix, rows, cols, threshold, i, j-1)
                count3 = self.countHelper(matrix, rows, cols, threshold, i+1, j)
                count4 = self.countHelper(matrix, rows, cols, threshold, i, j+1)
                count = 1 + count1 + count2 + count3 +count4 
            return count 
            
    s5 = Solution5()        
    print(s5.movingCount(3, 3, 3))

# [剑指offer（1/3）第一大部分][offer_1_3] #

# [剑指offer（2/3）第二大部分][offer_2_3] #

### 完结，撒花。。。。。。。。。。。。。。 ###

[20200423163552793.PNG]: /images/20220226/e998ce3b2e6742a2a564ce087c6b0337.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xyczEzNTMyODEwMDQ_size_16_color_FFFFFF_t_70]: /images/20220226/b0d1843704ba4fe18e907d6f06b8eb43.png
[20190213172431556.png]: /images/20220226/9ec04e69de6a4c389e656aec4fae64cc.png
[https_www.nowcoder.com_questionTerminal_59ac416b4b944300b617d4f7f111b215]: https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215
[https_blog.csdn.net_lrs1353281004_article_details_87192205]: https://blog.csdn.net/lrs1353281004/article/details/87192205
[https_www.nowcoder.com_questionTerminal_94a4d381a68b47b7a8bed86f2975db46]: https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46
[format_png]: /images/20220226/9ee75bf256834f3a968f00ed19048435.png
[https_www.nowcoder.com_questionTerminal_253d2c59ec3e4bc68da16833f79a38e4]: https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
[format_png 1]: /images/20220226/f3109dc19f624478afcbf44b98dcc0c8.png
[https_www.nowcoder.com_questionTerminal_9023a0c988684a53960365b889ceaf5e]: https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e
[format_png 2]: /images/20220226/490b832a19d24b1889f1490ec7d8199b.png
[70]: /images/20220226/23a1c68ef2c142979c83c3353a6a5b6c.png
[https_blog.csdn.net_qq_40587575_article_details_89290135]: https://blog.csdn.net/qq_40587575/article/details/89290135
[offer_1_3]: https://blog.csdn.net/qq_40587575/article/details/88675889
[offer_2_3]: https://blog.csdn.net/qq_40587575/article/details/88767488