思路：遍历下一个链表节点，递归输出后即为逆序

day4_根据前序和中序重建二叉树

思路：
i = tin.index(pre[0]) # 根节点索引
root = TreeNode(pre[0])
root.left = reConstructBinaryTree(pre[1:i+1], tin[:i])
root.right = reConstructBinaryTree(pre[i+1:], tin[i+1:])

day5_用两个栈实现队列

思路：由于栈是先进后出的数据结构，队列是先进先出的数据结构，
对于队列的Pop（删除)操作：假设我们有两个栈分别是stack1和stack2，我们有三个元素a,b,c依次进入栈stack1中，接下来要进行删除元素的话，根据队列的数据结构应该是删除最先进入的a元素，但是不能直接对stack1进行pop操作，于是我们需要借助栈stack2，先将元素压入stack2中再进行pop操作即可实现，但是需要注意的是，如果stack2中本身有元素的话直接进行pop操作即可。
对于队列Push操作：我们直接将元素压入stack1即可，无论stack2中是否还有元素存在均不影响。

day11_二进制中1的个数

思路：把一个整数减去1，再和原整数做与运算，会把该整数的最右边一个1变成0.
那么一个整数的二进制表示中有多少个1，就可以进行多少次这种操作。

day13_调整数组顺序使得奇数位于偶数前

思路：从头开始遍历找到第一个偶数后，然后将其后面的遇到的奇数依次插入到该偶数的前面。

day14_链表中倒数第k个节点

思路：利用快慢指针，快指针为p1,慢指针为p2，快指针p1先指向头结点然后向后遍历，
遍历k-1个位置后，然后同时慢p2指针也开始向后遍历，直至快指针遍历结束的时候，
慢指针即指向我们的倒数第k个位置。

day15_反转链表

思路1：为了反转链表，同时我们要保证我们需要在转换的过程中我们需要三个指针：即不仅要记住当前节点，也需要记住前一个节点和后一个节点。
思路2：头插法

day16_合并两个排序的链表

思路：首先考虑两个链表的头结点的大小后，将较小值作为我们新链表的头节点，然后依次合并两个链表剩余节点

day17_树的子结构demo

思路：基于根节点与目标结构的根节点的值是否相同，如果相同在去判断子节点的值是否相同(递归)，如果跟节点值不同，在去判断左子树、右子树与目标结构的左子树、右子树的值是否相同。

1
2
3
4
5
6
7
if pRoot1 and pRoot2:
    if pRoot1.val == pRoot2.val:
        result = self.JudgeSubTree(pRoot1.left, pRoot2.left) and self.JudgeSubTree(pRoot1.right, pRoot2.right)
    if not result:
        result = self.HasSubtree(pRoot1.left, pRoot2)
    if not result:
        result = self.HasSubtree(pRoot1.right, pRoot2)

day18_二叉树的镜像

思路：从根节点遍历到左、右节点：核心代码如下

root.left, root.right = root.right, root.left

day19_顺时针打印矩阵

PrintCircleNumber(matrix,row,col,start,ret)

day20_包含min函数的栈

思路：参考剑指offer，利用一个辅助栈来保存当前栈中的最小值。

day21_栈的压入与弹出序列

思路：本道题的关键是压入顺序下一个弹出的数字刚好是弹出顺序的栈顶数字，那么直接弹出；否则继续压入数字，直到与下一个弹出的数字相等为止

day22_从上到下打印二叉树

思路：该数据容器应该是一个队列

day23_二叉搜索树的后序遍历demo

1
2
3
# 解题思路：在二叉搜索树的后序遍历（左-右-根）得到的序列中，最后一个数字是树的根结点的值。
# 输入数组的数字可以分为两部分：第一部分是左子树的结点的值，它们都比根结点的值小；
# 第二部分是右子树结点，它们都比根结点的值大。

day24_二叉树中和为某一值得路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_path(self, root, expectNumber, path, currentNumber):
    currentNumber += root.val
    path.append(root)

    # 满足条件
    isLeaf = root.left == None and root.right == None
    if currentNumber == expectNumber and isLeaf:
        self.result.append([p.val for p in path])
        # for i in path:
        #     print(i.val,end=' ')

    if root.left:
        self.find_path(root.left, expectNumber, path, currentNumber)
    if root.right:
        self.find_path(root.right, expectNumber, path, currentNumber)
    path.pop()

day25_复杂链表的复制

1
2
3
4
5
6
解题思路：
要求：链表中除了指向后一个结点的指针之外，还有一个指针指向任意结点
分为三步完成：
一:复制每个结点，并把新结点放在老结点后面，如1->2,复制为1->1'->2->2'
二:为每个新结点设置random指针
三:把复制后的结点链表拆开

day26 二叉搜索树转为双向链表

解题思路：前序遍历即可，但是需要注意原先指向左子节点的指针调整为链表中指向前一个节点的指针, 原先指向右子节点的指针调整为链表中指向后一个节点的指针

1
2
3
4
5
6
7
8
9
# 处理左子树(处理右子树类似)
self.Convert(pRootOfTree.left)
left = pRootOfTree.left
# 连接根与左子树最大结点
if left:
    while left.right:
        left = left.right
    pRootOfTree.left = left
    left.right = pRootOfTree

day27 字符串的排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def helper(self, array, solution):
        if len(array) == 0:
            print(solution)
            return
        for i in range(len(array)):
            new_solution = solution + [array[i]]        # 新建排序列表
            new_array = array[:i] + array[i+1:]         # 新建待选择列表
            self.helper(new_array, new_solution)        # 回溯
     # 组合
     def helper(self, array, solution, n):
        if len(solution) == n:
            print(solution)
            return
        for i in range(len(array)):
            new_solution = solution + [array[i]]        # 新建组合列表
            new_array = array[i+1:]                     # 新建待选择列表表
            self.helper(new_array, new_solution, n)     # 回溯

day29_最小的K个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
解法3：创建一个大小为k的数据容器来存储最小的k个数字，接下来每次从输入的n个整数中读入一个数。如果容器中
已有的数字少于k个数，则直接把这次读入的整数放入容器中，如果容器中已有k个数字，即容器已满，此时我们不能再
插入新的数字而只能替换已有的数字。而是找出这已有的k个数中的最大值，然后拿这次待插入的整数和最大值进行比较。
如果待插入的值比当前已有的最大值还要大，则替换掉当前的最大值。
def GetLeastNumbers_Solution2(self, tinput,  k):
    vec = tinput[:k]
    max_index = self.find_max(vec)
    for x in tinput[k:]:
        if x < vec[max_index]:
            vec[max_index] = x
            max_index = self.find_max(vec)
    return vec

def find_max(self,  array):
    return array.index(max(array))

day30_连续子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 思路：分析数组的规律
def FindGreatestSumOfSubArray(self, array):
    if not array or not isinstance(array, list):
        return 0
    cur_sum = 0
    cur_great = -float('inf')
    for num in array:
        if cur_sum <= 0:
            cur_sum = num
        else:
            cur_sum += num
        if cur_sum > cur_great:
            cur_great = cur_sum
    return cur_great

day31整数中1出现的次数

1
2
3
解题思路：
最简单的思路就是累加1至n中每个整数1出现的次数。我们可以通过对10求余数判断整数的个位数字是不是1.
如果这个数字大于10，整除以10之后再判断个位数字是不是1.

day33丑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
把只包含质因子2、3和5的数称作丑数（Ugly Number）习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
# 解题思路：创建数组保存已经找到的丑数，用空间换时间的解法：第一种方式之所以低效很大程度上是因为不管一个数是不
丑数，我们都要对它做计算。根据丑数的定义，丑数应该是另一个丑数乘以2,3或5的结果。因此我们可以创建一个
数组，里面是排好序的丑数，每一个丑数都是前面的丑数乘以2,3,或5得到的。
def GetUglyNumber_Solution(self, index):
    if index <= 0:
        return 0
    ret = [1]
    count = 1
    multiple2, multiple3, multiple5 = 0, 0, 0
    while count < index:
        minval = min(ret[multiple2]*2, ret[multiple3]*3, ret[multiple5]*5)
        ret.append(minval)
        while ret[multiple2] * 2 <= ret[-1]:
            multiple2 += 1
        while ret[multiple3] * 3 <= ret[-1]:
            multiple3 += 1
        while ret[multiple5] * 5 <= ret[-1]:
            multiple5 += 1
        count += 1
    return ret

day34第一次只出现一次的字符

1
2
3
解题思路：
如果需要判断多个字符是不是在某个字符串里出现过或者统计多个字符在字符串中出现的次数，我们可以考虑
给予数组创建一个简单的哈希表，这样可以用很小的空间消耗换来时间效率的提升。

*day35数组中的逆序对

1
2
3
4
5
6
7
8
9
解题思路：
1.最直接的解法就是顺利扫描整个数组，每扫描到一个数字，逐个比较该数字与其后面的数字的大小。
如果后面的数字比它小，则这两个数字构成逆序对。此算法的时间复杂度大致为O(n^2).

2.另一种思路就是基于归并排序。我们首先将数组分解为两个长度为其原始长度一半的子数组，接着在对其子数组
进行拆分（递归实现），直至拆分成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。
以{7,5,6,4}为例，在一开始的一对长度为1的子数组{7}，{5}中7>5，因此构成一个逆序对（7,5）。同样在第二对
子数组中{6}，{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对逆序
对排序，以免重复统计。

day36 两个链表的第一个公共结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 解题思路
3.结合长度的方法：首先遍历两个链表得到它们的长度，就能知道哪个链表更长以及长的链表比短的链表多几个结点。在第
二次遍历的时候，让较长的链表先走若干步，使其走到与短链表同样长度的位置然后同时在两个链表上同时遍历，找到的第
一个相同的结点就是它们的公共结点。

4.上一种方法的改进：这种方法不需要计算链表的长度，是上一种方法的改进，当两链表一样长的时候，它们的公共节点的
数目是一样，所以此时大家一起前进，会有p1==p2的情况，当两链表不等长的时候，当短的链表走完的时候，它会重新指向
长的链表，然后当长的链表走完的时候，会指向短的链表。此时，两链表到公共节点的距离就相等了。因为当短链表走完时，
两指针之间的差值就相当于上面的nLengthDiffer。

def FindFirstCommonNode4(self,pHead1,pHead2):
    p1 = pHead1
    p2 = pHead2
    while p1 != p2:
        p1 = p1.next if p1 != None else pHead2
        p2 = p2.next if p2 != None else pHead1
    return p1

day37_数字在有序数组中出现的次数

1
2
3
4
5
6
7
8
9
解题思路：
1.直观的解法：由于是排序数组，我们自然而然的会想到用二分查找算法。在上面的例子中，我们先用
二分查找找到一个3，但3可能出现多次，因此我们找到的3的左右两边可能都有3，于是我们在3的左右两
边顺序扫描，分别找到第一个3和最后一个3.因为要查找的数字在长度为n的数组中有可能出现0(n)次，
所以顺序扫描时间复杂度是0(n).

2.更好地利用二分查找：我们利用二分其实是可以直接找到第一个k值的，当我们找到k值后，我们可以在判断一下
这个数字是不是第一个k。即如果位于该数字前面的一个数字不是k，则此时二分查找的中间数字就是第一个k；如果
中间数字的前一个数字也是k则说明第一个k值在前半段，下一轮仍在数组的前半段查找就好。

day38二叉树的深度

1
2
3
4
解题思路：
如果一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么树的深度应该是
其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度就是其右子树的深度加1。
如果既有左子树又有右子树，那么树的深度就是其左右深度较大的值再加1.

39 判断该二叉树是否是平衡二叉树

1
2
3
4
5
6
7
8
9
解题思路：
1.因为有了二叉树深度的经验之后在解决这个问题，我们很容易就能想到一个思路：在
遍历树的每个结点的时候，我们利用函数直接求出其左右子树深度之后。如果每个结点
的左右子树深度差都不差过1，按照定义它就是一棵平衡树的二叉树。

2.第一种思路的代码很简洁，但是每个结点可能会重复遍历很多遍，我们考虑一个更加
高效的办法，如果我们用后续遍历的方式遍历二叉树的每个一结点，在遍历结点之前我们
就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度，我们就可以一边
遍历一边判断每个结点是不是平衡的。

*day40_数组中只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
解题思路：
利用异或运算的性质：任何一个数字异或它自己都等于0.也就是说，如果我们从头到尾依次异或数组中的每一个数字，
那么最终的结果刚好是那个只出现一次的数字，因为那些成对出现的偶数次的数字全部在异或中抵消了。
于是我们可以依次异或数组中的每一个数字，那么最终的结果就是两个只出现一次的数字的异或结果。

由于这两个数肯定字不一样，那么异或的结果肯定不为0，也就是说在这个结果数字的二进制中至少就有一位为1。
我们在结果数字中找到第一个为1的位置，记为第n位。

现在我们以第n位是不是1为标准把原数组中的数字分成两个子数组，第一个子
数组中的每个数字的第n位都是1，而第二个子数组中的每个数字的第n位都是0.由于我们分配的标准是数字中的某一位
是1还是0，那么出现了两次的数字肯定被分配到同一个数组（因为两个相同的数字的任意一位都是相同的）。我们不
可能把两个相同的数字分配到不同的子数组中去，于是我们已经把原数组分配成了两个子数组，每个子数组都只包含
一个只出现一次的数字，而其他数字出现了两次。

day41和为S的连续正数序列

1
2
3
4
5
解题思路：
我们考虑用两个数small和big分别表示序列的最小值和最大值。首先初始化small为1，big为2.
如果从small到big的序列的和大于s，我们可以从序列中去掉较小的值，也就是增大small的值。
如果从small到big的值小于s，我们可以增大big，让这个序列包含更多的数字。因为这个序列
至少要有两个数字，我们一直增加small到(1+s)/2位置即可。

day42和为S的两个数字

1
2
3
4
5
6
解题思路：
1.这个题最直接的思路就是先在数组中固定一个数，再依次判断数组中的其余的n-1个数字与它的和是不是等于S.

2.为了寻找更好的算法，我们先在数组中选择两个数字，如果它们的和等于输入的S，我们就找到了要找的两个数字，
如果和小于S，我们希望两个数字的和再大一点。由于数组已经排好序，我们可以考虑选择较小数字后面的数字。
同样的，如果两个数字的和大于输入的S，我们可以选择较大数字前面的数字。

day43左旋转字符串

1
2
3
4
5
解题思路：
1.以'abcdefg'为例，我们可以把它分为两部分。第一部分将前n个字符翻转，接着翻转从n+1到末尾的，
最后翻转一下整个字符串就可以了。
2.python还可以利用切片操作，直接对字符串进行切片，同样也是对第n个字符那切片，然后将前后两部分
字符调换一下位置就好了。

day44翻转单词顺序

1
2
3
解题思路：
首先翻转句子中的所有字符，但是此时我们会将句子中的单词也会翻转。于是第二步我们需要
再翻转每个单词中的顺序。

day45 扑克牌顺子

1
2
3
4
5
6
7
8
解题思路：
    我们可以把5张牌看成由5个数字组成的数组。大小王是特殊的数字，我们不妨把它定义成0，这样
就能和其他的扑克牌区分出来。
    接下来我们分析怎么判断5个数字是不是连续的，最直观的方法就是把数组排序。值得注意的是，
由于0可以当成任意数字，即相邻的两个数字相隔若干个数字，但我们若有足够的0可以补满这两个数字
的空缺，这个数组实际上还是连续的。
    于是我们需要做3件事情：首先把数组排序，再统计数组中0的个数，最后统计排序之后的数组中相邻
数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的，反之不是连续的。

*day46孩子们的游戏（圆圈中最后剩下的数—约瑟夫环）

1
2
3
解题思路：本题就是有名的约瑟夫环问题：
1.利用环形链表模拟圆圈的经典解法。
2.分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字。

day47求1+2+…+n

1
2
3
4
5
6
7
8
9
10
11
12
"""题目描述
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
"""
"""解题思路：
1.利用内置函数sum和range即可快速实现。
2.利用逻辑与的短路特性实现递归终止：	# “and”运算符表示“与”，前一项为假则整个表达式为假，因此可以利用这个性质进行递归运算
class Solution:
    def Sum_Solution(self, n):
        result = n
        temp = n > 0 and self.Sum_Solution(n-1)
        result += temp
        return result

day54链表中环的入口结点

1
2
3
解题思路：
 思路是这样的：设定两个指针，一个慢指针，一个快指针，快指针的速度是慢指针的两倍，
 然后呢，如果有环，他们一定会在环中相遇。

day55删除链表中的重复节点

1
2
3
解题方法
要删除有序链表中所有的重复节点，而头结点有可能就是重复节点。这样的比较好的解决方式就是新建头结点，
然后往后遍历，同样的值就全部略过

day56二叉树的下一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
解题思路：
           a
          /  \
         b    c
        / \  / \
       d  e f   g
         / \
        h   i
        
上图中这棵二叉树的中序遍历(左根右)是d,b,h,e,i,a,f,c,g,我们以此为例进行分析。
1)如果一个结点有右子树，那么它的下一个结点就是它的右子树中的最左子结点。也就是说从
右结点出发一直沿着指向左指针的结点就能找到它的下一个结点。
2)如果一个结点没有右子树，且它是它父结点的左子树，那么它的下一个结点就是它的父结点。
3）如果一个结点既没有右子树，并且它还是它父结点的右子结点，这种情况相对复杂，我们可以
沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结
点存在，那么这个节点的父结点就是我们要找的下一个结点。