按牛客的顺序来，个人的刷题的一个总结，太水的没有特色的题就跳过了。。

1. 二维数组中的查找

题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：1. O(n2) 最优解 O(n)
水题

---

2. 替换空格

题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

水题

---

3.从尾到头打印链表

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

水题

---

4.重建二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：前序遍历（根左右）和中序遍历(左根右)区别在于，前序的根节点很容易获取pre[0],再找到中序对应的位置，递归就好。

class Solution:
    # 返回构造的TreeNode根节点,pre,tin均为list类型
    def reConstructBinaryTree(self, pre, tin):
        if not pre or not tin:
            return None
        root = TreeNode(pre[0])
        ind = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:ind+1], tin[:ind])
        root.right = self.reConstructBinaryTree(pre[ind+1:], tin[ind+1:])
        return root

---

5.用两个栈实现队列

题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：这道题也很水，算是练习栈的操作把，把栈1的元素全部pop到栈2顺序倒过来就算队列的pop了。

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        self.stack1.append(node) 

    def pop(self):
        if not self.stack1:
            return None
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        result = self.stack2.pop()
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        return result

---

6.旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：这道题目感觉出的不是很好，O(n)很容易搞定，出题者的本意是考二分查找O(log(n)),有没有重复的数难度差异也很大，。

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        start, end = 0, len(rotateArray) - 1
        while start <= end:
            mid = (start + end) /2
            if rotateArray[mid] > rotateArray[0]:
                start = mid +1
            else:
                end = mid - 1
        return rotateArray[start]

有重复情况 变成hard leetcode154
    def minArray(self, numbers: List[int]) -> int:
        low, high = 0, len(numbers) - 1
        while low < high:
            mid = low + (high - low) // 2
            if numbers[mid] > numbers[high]:
                low = mid + 1
            elif numbers[mid] < numbers[high]:
                high = mid
            else:
                high -= 1
        return numbers[low]

7.斐波那契数列、8跳台阶

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

思路：递归水题，8和7做法一致，8为7的应用

9.变态跳台阶

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：跳1级，剩下n-1级，则剩下跳法是f(n-1)，跳2级，剩下n-2级，则剩下跳法是f(n-2)，所以f(n)=f(n-1)+f(n-2)+...+f(1)，因为f(n-1)=f(n-2)+f(n-3)+...+f(1)

        return 2 ** (number-1)

10.矩阵覆盖

题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

思路：f(n)只能由f(n-2)加两个横的长方形和f(n-1)加一个竖的长方形组成，所以f(n) = f(n-1) + f(n-2）依然是斐波那契额数列。

11.二进制中1的个数

题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：水题，这道题python做有坑，python存储方式跟C++，java不太一样，整数不限长度，按位移的操作不方便。

return bin(n&0xffffffff).count('1')

或者用巧妙的方法，每次取最后一位‘1’。

    def NumberOf1(self, n):
        res = 0 
        n = n & 0xffffffff #高位补0
        while n:
            n = n & (n-1)
            res += 1
        return res

12.数值的整数次方

题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

思路：不用作弊的方法了，这道题用快速幂。

    def Power(self, base, exponent):
        if base == 0:
            return 0
        if exponent == 0：
            return 1
        e = abs(exponent)
        mul = base
        res = 1
        while (e > 0):
            if (e & 1) == 1:
                res = res * mul
            e = e >> 1
            mul = mul * mul
        return res if exponent > 0 else 1/res

13.调整顺序使奇数位于偶数前面（排序题）

类似快排的双指针做法

14.链表中倒数第k个节点（常规链表）

两个指针，一个先走k步

15.反转链表

画好图，加一个Listnode先存着

16.合并两个排序的链表

easy O(1) 空间

18.二叉树镜像

左右递归

20.包含min的栈

easy

21.栈的压入、弹出序列

栈模拟走一波就行

22.从上往下，从左往右打印二叉树

层次遍历基础题，借助队列

27.数组中出现超过一半的数

---

17.树的子结构

递归检查每一个节点，或者bfs来一把判断是不是(不推荐)

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not B or not A:
            return False
        return self.isEqual(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
    
    def isEqual(self, A, B):
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        if A.val == B.val:
            return self.isEqual(A.left, B.left) and self.isEqual(A.right, B.right)

19.顺时针打印矩阵

玩转数组边界的好题

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

思路ok 后续 = 前序的方法 反过来 用stack

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

树的题需要二刷

24.复杂链表的复制

第一遍就没做好，这个怪我把

25.二叉搜索树与双向列表

简单就好

26.字符串的排列（回溯）

瞬间想到，可以拿出来练练

28.最小的K个数

堆排序O(nlogk)适合处理海量数据
使用快排的分区函数求出第k小的元素 o(n) o(1) 是

30. 整数中1出现的次数

数学题 需要多看看

31.把数组排成最小的数

考sort

32.丑数

what‘s the fuck？还做错，可怕

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

hash

34. 数组中的逆序对

归并排序

39 数组中出现一次的数字

1. hash
2. 异或后找1 再异或 巧妙

这道题必须写出几种方法

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

思路：O(n*log(n))

    def GetLeastNumbers_Solution(self, tinput, k):
        import heapq
        if k > len(tinput):
            return []
        return heapq.nsmallest(k,tinput)

需要再做的题 T9

12. 矩阵中的路径

DFS 注意保存中间值即可

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board:
            return False
        if not word:
            return True
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, i, j, word):
                    return True
        return False
    
    def dfs(self, board, i, j, word):
        if word == '':
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]:
            return False
        tmp = board[i][j]
        board[i][j] = '#'
        res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i ,j+1, word[1:]) or self.dfs(board, i-1, j,word[1:]) \
        or self.dfs(board, i, j-1, word[1:])
        board[i][j] = tmp
        return res