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

谁践踏了优雅 2022-02-28 00:58 250阅读 0赞

**目录**

23.从上往下打印二叉树

24.二叉搜索树的后序遍历序列

25.二叉树中和为某一值的路径

26.复杂链表的复制

27.二叉搜索树和双向链表

28.字符串的排列

29.数组中出现次数超过一半的数字

30.最小的k个数

31.连续数组的最大和

32.整数1出现的个数

33.把数组排成最小数

34.丑数

35.第一次只出现一次的字符

36.数组的逆序对

37.两个链表的第一个公共结点

38.数字在排序数组中出现的次数

39.二叉树的深度

40.平衡二叉树

40.数组中只出现一次的数字

41.和为s 的两个数字

41.和为s 的连续正序数列

42.左旋转字符串

43.翻转单词序列

44.扑克牌的顺子

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

![20200423163621880.PNG][]

### 23.从上往下打印二叉树 ###

从上往下打印出二叉树的每个节点，同层节点从左至右打印。（依次打印出每层的结点值）

需要一个队列和一个存储数据的数组

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回从上到下每个节点值列表，例：[1,2,3]
        def PrintFromTopToBottom(self, root):
            # write code here
            if not root:
                return []
            
            result = [] #存储结果
            queue = [] #实现队列
            queue.append(root)
            while queue:
                curNode = queue.pop(0)
                result.append(curNode.val)
                if curNode.left:
                    queue.append(curNode.left)
                if curNode.right:
                    queue.append(curNode.right)
    
            return result

### 24.二叉搜索树的后序遍历序列 ###

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。（二叉搜索树的中序遍历是有序的）

根据后续遍历的性质，尾元素必定是树的根，同时小于尾元素的值是左子树，大于尾元素的值为右子树，且序列前半部分均小于尾元素，后半部分均大于尾元素（如果同时存在左右子树的话），可以将序列划分左子树序列和右子树序列，然后递归比较是否每一段均满足此性质。减少递归深度的办法：某段的元素个数如果<=3，则返回True；某整段的最小元素不小于尾元素或者整段的最大元素不大于尾元素，说明仅有左子树或者右子树，返回True。

整数序列的最后一个值是根结点，然后比根结点小的值是左子树，比根节点大的是右子树，递归左右子树

如序列： 1，3，2，5，6，7，4

# -*- coding:utf-8 -*-
    class Solution:
        def VerifySquenceOfBST(self, sequence):
            # write code here
            length = len(sequence)
            if length == 0:
                return False
            else:
                root = sequence[-1] #原始数组中最后一个元素为根节点
                left = 0
                while sequence[left] < root:  #找到最左边的元素索引 加1，因为 ：left是开区间
                    left += 1
                right = left 
                while right < length-1:
                    if sequence[right] < root: #如果存在根节点都比右结点还大的数，则为False
                        return False
                    right += 1
                if left == 0:
                    return True 
                else:
                    left_ret =  self.VerifySquenceOfBST(sequence[:left])
                if left == right: 
                    return True 
                else:
                    right_ret = self.VerifySquenceOfBST(sequence[left: right])
                    
                return left_ret and right_ret

### 25.**二叉树中和为某一值的路径** ###

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

输入一棵二叉树和一个值，求从根结点到叶结点的和等于该值的路径

\#使用深度优先的方法

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        # 返回二维列表，内部每个列表表示找到的路径
        def FindPath(self, root, expectNumber):
            # write code here
            #使用深度优先方法
            if not root:
                return []
            
            res, path, sums = [], [], [] #分别保存结果，结点路径， 每个结点路径和
            path.append(root)
            sums.append(root.val)
            
            def dfs(root):# 深度优先遍历全部结点，
                if root.left:
                    path.append(root.left)
                    sums.append(sums[-1] + root.left.val)
                    dfs(root.left)
                    
                if root.right:
                    path.append(root.right)
                    sums.append(sums[-1] + root.right.val)
                    dfs(root.right)
                    
                if not root.left and not root.right:
                    if sums[-1] == expectNumber:
                        res.append([p.val for p in path])
                print([p.val for p in path])        
                print(sums)
                path.pop() #去除做结点， 使其遍历 右结点
                sums.pop()
                
            dfs(root)
            return res
        
    #     def FindPath(self, root, expectNumber):
    #         # write code here
    #         if not root:
    #             return []
    #         result = []
    #         def FindPathMain(root, path, currentSum):
    #             currentSum += root.val
    #             path.append(root)
    #             isLeaf = root.left == None and root.right == None
    #              
    #             if currentSum == expectNumber and isLeaf:
    #                 onePath = []
    #                 for node in path:
    #                     onePath.append(node.val)
    #                 result.append(onePath)
    #              
    #             if currentSum < expectNumber:
    #                 if root.left:
    #                     FindPathMain(root.left, path, currentSum)
    #                 if root.right:
    #                     FindPathMain(root.right, path, currentSum)
    #             path.pop()
    #             
    #         FindPathMain(root, [], 0)
    #         return result
    
    pNode1 = TreeNode(10)
    pNode2 = TreeNode(5)
    pNode3 = TreeNode(12)
    pNode4 = TreeNode(4)
    pNode5 = TreeNode(7)
    
    
    pNode1.left = pNode2
    pNode1.right = pNode3
    pNode2.left = pNode4
    pNode2.right = pNode5
    
    
    S = Solution()
    print(S.FindPath(pNode1, 22))

### 26.复杂链表的复制 ###

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

![format_png][]

此题有点复杂呀，指针指来指去的（记住每个while循环都要更新结点）

# -*- coding:utf-8 -*-
    # class RandomListNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.next = None
    #         self.random = None
    class Solution:
        # 返回 RandomListNode
        def Clone(self, pHead):
            # write code here
            if not pHead:
                return None 
            self.cloneNodes(pHead)
            self.connectRandomNodes(pHead)
            ret = self.splitNodes(pHead)
            return ret
            
        def cloneNodes(self, pHead):
            #第一步骤:复制结点
            dummy = pHead 
    
            while dummy:
                dummyNext = dummy.next 
                copyNode = RandomListNode(dummy.label) #创建复制的结点
                #dummy.next = copyNode 
                #copyNode.next = dummyNext 搞错方向
                copyNode.next = dummyNext 
                dummy.next = copyNode 
    
                dummy = dummyNext # 更新dummy结点
        
        def connectRandomNodes(self, pHead):
            #第二步骤，复制random结点
            dummy = pHead 
            while dummy:
                dummyRandom = dummy.random 
                copyNode = dummy.next 
                if dummyRandom: #如果random存在的话
                    copyNode.random = dummyRandom.next 
                dummy = copyNode.next  #更新dummy结点
    
        def splitNodes(self, pHead):
            #第三步骤，分裂复制的链表
            dummy = pHead 
            cloneNode = pHead.next  #最后返回的复制结点的头指针
            while dummy:
                copyNode = dummy.next 
                dummyNext = copyNode.next 
                dummy.next = dummyNext #取出原始的结点
                if dummyNext:
                    copyNode.next = dummyNext.next  #1取出复制的结点
                else:
                    copyNode.next = None
                dummy = dummyNext #更新结点
            return cloneNode

### 27.二叉搜索树和双向链表 ###

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

![format_png 1][]

我认为最容易懂的代码：

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def Convert(self, pRootOfTree):
            # write code here
            if not pRootOfTree:
                return None 
            self.li = []
            self.middle(pRootOfTree)
            for i in range(len(self.li) -1):
                self.li[i].right = self.li[i+1]
                self.li[i+1].left = self.li[i]
                
            return self.li[0]#返回首结点
            
        def middle(self, root):
            if not root:
                return 
            self.middle(root.left)
            self.li.append(root)
            self.middle(root.right)

![70][]

参考的图形：[https://blog.csdn.net/u010005281/article/details/79657259][https_blog.csdn.net_u010005281_article_details_79657259]

### 28.字符串的排列 ###

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

依次取一个元素，然后依次和之前递归形成的所有子串组合，形成新的字符串

# -*- coding:utf-8 -*-
    class Solution:
        def Permutation(self, ss):
            # write code here
            if not ss:
                return []
            if len(ss) == 1:
                return ss 
    
            ssList = list(ss)
            ssList.sort() #将 字符串转换成列表并排序
            ret = []
            for i in range(len(ssList)):    #依次取出一个字符，其余字符进行递归操作
                if i > 0 and ssList[i] == ssList[i-1]: #如果存在字符相同的情况
                    continue 
                temp = self.Permutation(''.join(ssList[: i]) + ''.join(ssList[i+1: ]))
                for j in temp:
                    ret.append(ssList[i] + j)
    
            return ret

### 29.数组中出现次数超过一半的数字 ###

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

\#使用哈希表 思路: 使用hash，key是数字，value是出现的次数

# -*- coding:utf-8 -*-
    class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            # write code here
    
            #使用哈希表
            if not numbers:
                return 0
    
            hashes = {}
            length = len(numbers)
            for num in numbers:
                if hashes.get(num): #如果num存在字典中
                    hashes[num] += 1
                else:
                    hashes[num] = 1
                if hashes[num] > (length // 2):
                    return num 
            return 0

### 30.最小的k个数 ###

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

> 两种方法。
> 
> 第一种方法是基于划分的方法，如果是查找第k个数字，第一次划分之后，划分的位置如果大于k，那么就在前面的子数组中进行继续划分，反之则在后面的子数组继续划分，时间复杂度O(n)；
> 
> 第二种方法是可以适用于海量数据的方法，该方法基于二叉树或者堆来实现，首先把数组前k个数字构建一个最大堆，然后从第k+1个数字开始遍历数组，如果遍历到的元素小于堆顶的数字，那么久将换两个数字，重新构造堆，继续遍历，最后剩下的堆就是最小的k个数，时间复杂度O(nlog k)。

当数组较小的时候，直接使用库返回最小的n 个元素

# -*- coding:utf-8 -*-
    class Solution:
        def GetLeastNumbers_Solution(self, tinput, k):
            # write code here
    
            import heapq 
            length = len(tinput)
    
            if k > length:
                return []
            return heapq.nsmallest(k, tinput)

使用最大堆

# -*- coding:utf-8 -*-
    class Solution:
        def GetLeastNumbers_Solution(self, tinput, k):
            # write code here
            import heapq 
            length = len(tinput)
            if not tinput or length < k or k <= 0:
                return []
            if length == k:
                tinput.sort()
                return tinput
            
            output = []
            for num in tinput:
                if len(output) < k:
                    output.append(num)
                else:
                    output = heapq.nlargest(k, output)
                    
                    if output[0] < num:
                        continue 
                    else:
                        output[0] = num 
                    
            return output[::-1]

### 31.连续数组的最大和 ###

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

# -*- coding:utf-8 -*-
    class Solution:
        def FindGreatestSumOfSubArray(self, array):
            # write code here
            if not array:
                return 
            ret = float('-inf')
            cur = 0
            for num in array:
                if cur <= 0: #如果计算得到前面所有值为负的话，舍弃前面数值
                    cur = num 
                else:
                    cur += num 
                ret = max(ret, cur) #保存，并更新最大值
            return ret

动态规划解答：

# -*- coding:utf-8 -*-
    class Solution:
        def FindGreatestSumOfSubArray(self, array):
            # write code here
            if not array:
                return 
            
            # 使用动态规划的方法
            ret = [0] * len(array)
            for i in range(len(array)):
                if i == 0 or ret[i-1] <= 0: 
                    ret[i] = array[i]
                else:
                    ret[i] = ret[i-1] + array[i] #
                    
            return max(ret)

### 32.整数1出现的个数 ###

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

1.将数字转换成字符串

# -*- coding:utf-8 -*-
    class Solution:
        def NumberOf1Between1AndN_Solution(self, n):
            # write code here
            # 将数字转换成字符串
            count = 0
            for i in range(1, n+1):
                for s in str(i):
                    if s == '1':
                        count += 1
            return count

### 33.把数组排成最小数 ###

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。

**这里自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。（核心）**

# -*- coding:utf-8 -*-
    class Solution:
        def PrintMinNumber(self, numbers):
            # write code here
            if not numbers:
                return ''
            strNum = [str(num) for num in numbers]
            
            for i in range(len(numbers)-1):
                for j in range(i+1, len(numbers)):
                    if strNum[i]+strNum[j] > strNum[j]+strNum[i]:
                        strNum[i], strNum[j] = strNum[j], strNum[i]
                        
            return ''.join(strNum)

### 34.丑数 ###

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

首先从丑数的定义我们知道，一个丑数的因子只有2,3,5，那么丑数p = 2 ^ x \* 3 ^ y \* 5 ^ z，换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，那么我们从1开始乘以2,3,5，就得到2,3,5三个丑数，在从这三个丑数出发乘以2,3,5就得到4，6,10,6，9,15,10,15,25九个丑数

# -*- coding:utf-8 -*-
    class Solution:
        def GetUglyNumber_Solution(self, index):
            # write code here
            if not index: #如果index 为0 时，则返回 0
                return 0 
            
            uglyNumbers = [1] * index
            
            index2, index3, index5 = 0, 0, 0
            nextIndex = 1
            while nextIndex < index: 
                minVal = min(uglyNumbers[index2] * 2, uglyNumbers[index3]*3, uglyNumbers[index5]*5)
                uglyNumbers[nextIndex] = minVal 
                
                while uglyNumbers[index2] *2 <= minVal: #如果小于最小值，则向前移动
                    index2 += 1
                while uglyNumbers[index3] * 3 <= minVal:
                    index3 += 1
                while uglyNumbers[index5] * 5 <= minVal:
                    index5 += 1
                    
                nextIndex += 1
            return uglyNumbers[-1]

### 35.第一次只出现一次的字符 ###

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

**\#使用哈希表进行储存**

# -*- coding:utf-8 -*-
    class Solution:
        def FirstNotRepeatingChar(self, s):
            # write code here
            if not s:
                return -1
            hashes = {} #使用哈希表进行存储
            alist = list(s)
            length = len(alist)
            
            for i in range(length):
                if not hashes.get(alist[i]): #如果 i 不存在的话
                    hashes[alist[i]] = 1
                else:
                    hashes[alist[i]] += 1
            
            for i in range(length):
                if hashes[alist[i]] == 1:
                    return i 
            return -1

### 36.数组的逆序对 ###

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

输入描述:

题目保证输入的数组中没有的相同的数字

数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2\*10^5

示例1

输入

1,2,3,4,5,6,7,0

输出

要找到数组中的逆序对，可以看做对数据进行排序，需要交换数组中的元素的次数，但是防止相同大小的元素发生交换，因此需要选择一个稳定的排序方法，记录发生交换的次数。那么，基于比较的稳定的排序方法中，最快的方法就是归并了，所以直接按照归并排序的思路，将数组分解、合并、排序即可。但是需要注意的是，在常规归并排序的时候，如果前一个元素大于后一个元素，直接进行交换即可，只进行了一次操作，但是对于这道题来讲，对于每一次的归并段，我们选择从后向前遍历，前面的归并段的某一个数值left\[i\]如果大于后面的某一个数值right\[j\]，因为在right自己独自排序的过程中，已经保证了right是有序的，所以j位置前面的数字全部小于right\[j\]，所以在这里逆序对的个数就会是 j-start-length，其中start是整个数组的起点，length是left的长度，然后再进行交换。

**暂定，复习下七种排序算法**

**1.使用排序方法：时间复杂度： O（n）**

li = [5, 6, 4, 3, 2, 7, 9] # 3, 3, 2, 1,
    # li = [1, 2, 3, 4, 5, 6, 7, 0]
    def reverseOrderNum(li):
        n = len(li)
        index = 0
        for i in range(n-1):
            for j in range(i+1, n):
                if li[i] > li[j]:
                    index += 1
        return index
    print(reverseOrderNum(li))

**2.使用归并方法：时间复杂度：O(nlogn)**

做排序算法时，归并都是返回一个排序好的数组

class Solution:
    
        def InversePairs(self, data):
            if not data or len(data) == 1:
                return data
            copy = [0] * len(data)
            count = self.InversePairsCore(data, copy, 0, len(data)-1)
            # print(copy)
            return count
    
        def InversePairsCore(self, data, copy, low, high):
            if low == high:
                return 0
            mid = (high + low) // 2
            leftCount = self.InversePairsCore(data, copy, low, mid) % 1000000007
            rightCount = self.InversePairsCore(data, copy, mid+1, high) % 1000000007
            count = 0
            i, j = mid, high
            locCopy = high
            while i >= low and j > mid:
                if data[i] > data[j]:
                    count += j - mid
                    copy[locCopy] = data[i]
                    locCopy -= 1
                    i -= 1
                    if count >= 1000000007:
                        count %= 1000000007
                else:
                    copy[locCopy] = data[j]
                    locCopy -= 1
                    j -= 1
            for ii in range(i, low-1, -1):
                copy[locCopy] = data[ii]
                locCopy -= 1
            for jj in range(j, mid-1, -1):
                copy[locCopy] = data[jj]
                locCopy -= 1
            for s in range(low, high+1):
                data[s] = copy[s]
            return leftCount + rightCount + count

### 37.两个链表的第一个公共结点 ###

输入两个链表，找出它们的第一个公共结点。（感觉牛客网出的题目描述的没有leetcode清楚呀）

**公共结点的意思是两个链表相遇之后后面都是一样的**

思路: 先获取到两个链表的长度，然后长的链表先走多的几步，之后一起遍历

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        def FindFirstCommonNode(self, pHead1, pHead2):
            # write code here
            if not pHead1 or not pHead2:
                return 
            
            move1, move2 = pHead1, pHead2
            length1, length2 = 0, 0
            while move1: #计算链表1 的长度
                length1 += 1
                move1 = move1.next 
                
            while move2: #计算链表2 的长度
                length2 += 1
                move2 = move2.next 
            
            while length1 > length2:
                pHead1 = pHead1.next 
                length1 -= 1
            
            while length2 > length1:
                pHead2 = pHead2.next 
                length2 -= 1
                
            while pHead1: #两个链表一起往前走
                if pHead1 == pHead2:
                    return pHead1
                pHead1, pHead2 = pHead1.next, pHead2.next 
                
            return None

### 38.数字在排序数组中出现的次数 ###

统计一个数字在排序数组中出现的次数。

使用二分法分别找到数组中第一个和最后一个出现的值的坐标，然后相减 + 1

# -*- coding:utf-8 -*-
    class Solution:
        def GetNumberOfK(self, data, k):
            # write code here
            #return data.count(k)
            if not data:
                return 0
            
            left = self.get_first_k(data, k)
            right = self.get_last_k(data, k)
            if left < 0 and right < 0:
                return 0
            if left < 0 or right < 0: # 如果左边有一个不存在，代表另外一个是存在的，所以 返回1 个
                return 1 
            return right -left + 1
            
            
        def get_first_k(self, data, k):
            left, right = 0, len(data)-1
            while left <= right:
                mid = (left + right) // 2
                if data[mid] < k:
                    if mid+1 < len(data) and data[mid+1] == k: #如果后一位数字等于k 的话
                        return mid + 1
                    left = mid + 1
                elif data[mid] == k:
                    if mid-1 < 0 or (mid-1 >= 0 and data[mid-1] < k):#确保是获得左边的第一个索引，如果mid是0的话，如果 前一个值小于k时
                        return mid 
                    right = mid - 1
                else:
                    right = mid - 1
            return -1
                    
        def get_last_k(self, data, k):
            left, right = 0, len(data)-1
            while left <= right:
                mid = (left + right) // 2
                if data[mid] < k:
                    left = mid + 1
                elif data[mid] == k:
                    if mid + 1 == len(data) or (mid+1 < len(data) and data[mid+1] > k):#如果索引是length-1的话，如果后一位大于k的话
                        return mid 
                    left = mid + 1
                else: #如果中间值 大于 k的时候
                    if mid -1 >= 0 and data[mid-1] == k:
                        return mid -1 
                    right = mid - 1
            return -1

### 39.二叉树的深度 ###

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def TreeDepth(self, pRoot):
            # write code here
            if not pRoot:
                return 0
            #if not pRoot.left and not pRoot.right: #可要可不要
               # return 1
            return 1 + max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right))

### 40.平衡二叉树 ###

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

基于二叉树的深度，再次进行递归。以此判断左子树的高度和右子树的高度差是否大于1，若是则不平衡，反之平衡。

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def IsBalanced_Solution(self, pRoot):
            # write code here
            if not pRoot:
                return True 
            left = self.get_depth(pRoot.left)
            right = self.get_depth(pRoot.right) #获取左右子树的深度
            if abs(right - left) > 1:
                return False
            return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
            
        def get_depth(self, pRoot): #获取树的深度
            if not pRoot:
                return 0
            return 1 + max(self.get_depth(pRoot.left), self.get_depth(pRoot.right))

链接：[https://www.nowcoder.com/questionTerminal/8b3b95850edb4115918ecebdf1b4d222][https_www.nowcoder.com_questionTerminal_8b3b95850edb4115918ecebdf1b4d222]  
来源：牛客网  
  
在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def IsBalanced_Solution(self, pRoot):
            # write code here
            return self.helper(pRoot) != -1
            
        
        def helper(self, pRoot):
            if not pRoot:
                return 1 
            left = self.helper(pRoot.left)
            if left == -1:
                return -1
            right = self.helper(pRoot.right)
            if right == -1:
                return -1
            if abs(right - left) > 1: #如果左右结点的相对值大于 1时，则不是平衡树
                return -1
            return 1+ max(self.helper(pRoot.left), self.helper(pRoot.right))

### 40.数组中只出现一次的数字 ###

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

使用哈希表

# -*- coding:utf-8 -*-
    class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here’
            if not array:
                return 
            hashes = {}
            for num in array:
                if num not in hashes.keys():
                    hashes[num] = 1
                else:
                    hashes[num] += 1
            ret = []
            for num in array:
                if hashes[num] == 1:
                    ret.append(num)
                    
            return ret

**使用异或**

任何一个数字异或他自己都等于0，0异或任何一个数都等于那个数。数组中出了两个数字之外，其他数字都出现两次，那么我们从头到尾依次异或数组中的每个数，那么出现两次的数字都在整个过程中被抵消掉，那两个不同的数字异或的值不为0，也就是说这两个数的异或值中至少某一位为1。我们找到结果数字中最右边为1的那一位i，然后一次遍历数组中的数字，如果数字的第i位为1，则数字分到第一组，数字的第i位不为1，则数字分到第二组。这样任何两个相同的数字就分到了一组，而两个不同的数字在第i位必然一个为1一个不为1而分到不同的组，然后再对两个组依次进行异或操作，最后每一组得到的结果对应的就是两个只出现一次的数字。

# -*- coding:utf-8 -*-
    class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here’
            if not array:
                return []
            
            D_value = 0
            for num in array: #获得不同的两个数的  差值
                D_value ^= num 
            #获取bit 位置
            index = 0
            while D_value & 1 == 0 and index < 32: #获取D_value 的 bit 位置
                index += 1
                D_value = D_value >> 1
            a, b = 0, 0
            for j in range(len(array)):
                if self.isBit1(array[j], index): #这里将两个不同的数分成了 两半
                    a ^= array[j]
                else:
                    b ^= array[j]
            return [a, b]
            
        def isBit1(self, num, index): # num主要是为了计算 a， b
            num = num >> index
            return num & 1

### 41.和为s 的两个数字 ###

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

对应每个测试案例，输出两个数，小的先输出。

<table> 
 <tbody> 
  <tr> 
   <td>从左右一起查找</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td># 因为当两个数的和一定的时候, 两个数字的间隔越大, 乘积越小</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td># 所以直接输出查找到的第一对数即可</td> 
  </tr> 
 </tbody> 
</table>

# -*- coding:utf-8 -*-
    class Solution:
        def FindNumbersWithSum(self, array, tsum):
            # write code here
            if not array:
                return []
            low, high = 0, len(array)-1
    
            while high > low:
                curSum = array[low] + array[high]
                if curSum > tsum:
                    high -= 1
                elif curSum < tsum:
                    low += 1
                else:
                    return [array[low], array[high]]
            return []

### 41.和为s 的连续正序数列 ###

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

双指针技术，就是相当于有一个窗口，窗口的左右两边就是两个指针，我们根据窗口内值之和来确定窗口的位置和宽度

# -*- coding:utf-8 -*-
    class Solution:
        def FindContinuousSequence(self, tsum):
            # write code here
            if tsum < 3:
                return []
            low, high = 1, 2
            ret = []
            while low < high:
                cur = (high + low) * (high-low+1) / 2 #求和公式
                if cur == tsum:
                    ret.append(range(low, high+1))
                    low += 1
                elif cur < tsum: #如果当前值比总值小，则前往前走 
                    high += 1
                else:
                    low += 1  
                    
            return ret

### 42.左旋转字符串 ###

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

# -*- coding:utf-8 -*-
    class Solution:
        def LeftRotateString(self, s, n):
            # write code here
            if not s:
                return ''
            if len(s) <= n:
                return s 
            return s[n:] + s[:n]

复制一个s

class Solution:
        def LeftRotateString(self, s, n):
            # write code here
            if not s:
                return ''
            if len(s) <= n:
                return s 
            length = len(s)
            s += s
            return s[n : length+n]

### 43.翻转单词序列 ###

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

# -*- coding:utf-8 -*-
    class Solution:
        def ReverseSentence(self, s):
            # write code here
            if s == ' ':
                return ' '
            if s == None or len(s) <= 0:
                return ''
    
            ts = s.split()
            ret = ''
            for i in range(len(ts)-1, -1, -1):
                if i == 0:
                    ret += ts[i]
                else:
                    ret += ts[i] + ' '
            return ret

### 44.扑克牌的顺子 ###

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。

先置换特殊字符AJQK为数字，排序，然后求出大小王即0的个数，然后求出除去0之外的，数组间的数字间隔(求间隔的时候记得减去1，比如4和5的间隔为5-4-1，表示4和5是连续的数字)，同时求间隔的时候需要鉴别是否出现对。最后比较0的个数和间隔的大小即可。

\# 如果出现相同的数，则必定不是顺子

# -*- coding:utf-8 -*-
    class Solution:
        def IsContinuous(self, numbers):
            # write code here
            if not numbers:
                return 
            my_dict = {'A':1, 'J':11, 'Q':12, 'K':13}
            # 将数组的A，等转换 成 数值, 并计算0 的个数
            zero_num = 0
            for i in range(len(numbers)):
                if numbers[i] in my_dict.keys():
                    numbers[i] = my_dict[numbers[i]]
                if numbers[i] == 0:
                    zero_num += 1
            # 对转换后的数组进行排序
            numbers.sort()
            small = zero_num 
            big = small + 1
            gap_sum = 0
            while big < len(numbers):
                if numbers[small] == numbers[big]: #如果有相同的数的话，肯定不是顺子
                    return False 
                gap_sum += numbers[big] - numbers[small] -1
                small += 1
                big += 1
            if  gap_sum > zero_num:
                return False
            else:
                return True

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

# [剑指offer（3/3）第三大部分][offer_3_3] #

[20200423163621880.PNG]: /images/20220228/405cb46dbfc44dc5a0c0d8133720ff71.png
[format_png]: /images/20220228/4971ad5e914e419bb4d46beb52c04813.png
[format_png 1]: /images/20220228/de3491376ccc41d19b6178398b66b82f.png
[70]: /images/20220228/234fb844381641fba3b4eb2e49af99b1.png
[https_blog.csdn.net_u010005281_article_details_79657259]: https://blog.csdn.net/u010005281/article/details/79657259
[https_www.nowcoder.com_questionTerminal_8b3b95850edb4115918ecebdf1b4d222]: https://www.nowcoder.com/questionTerminal/8b3b95850edb4115918ecebdf1b4d222
[offer_2_3]: https://blog.csdn.net/qq_40587575/article/details/88675889
[offer_3_3]: https://blog.csdn.net/qq_40587575/article/details/88920399