剑指offer(python)-记录题解思路

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array)    # 行数
        cols = len(array[0])    # 列数
        for i in range(rows):
            for j in range(cols):
                if(array[i][j] == target):
                    return True
        return False

方法二

考虑题目本身的的特性，每行每列都是有序的数组

每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array)    # 行数
        cols = len(array[0])    # 列数
        i = 0
        j = cols-1
        while i<rows and j>=0:
            if(array[i][j] == target):
                return True
            elif(array[i][j] > target):
                j -= 1
            elif(array[i][j] < target):
                i += 1
        return False

第二题 (字符串) 替换空格

题目描述

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

看到题目的第一反应是找到空格直接替换就行了。简单粗暴。

python的replece方法一句话

str.replace(old, new[, max])

返回字符串中的 old（旧字符串）替换成 new(新字符串)后生成的新字符串，如果指定第三个参数max，则替换不超过 max 次。

方法一

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s = s.replace(' ','%20')
        return s

# s = Solution()
# print(s.replaceSpace('We Are Happy'))

方法二

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        temp = ""
        for i in range(len(s)):
            if s[i] == ' ':
                temp += '%20'
            else:
                temp += s[i]
        return temp

第三题 (链表) 从尾到头打印链表

题目描述

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

借用一个列表来存放值

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        alist = []
        if listNode is None:
            return alist
        p = listNode
        while p.next:
            alist.append(p.val)
            p = p.next
        alist.append(p.val)
        alist.reverse()
        return alist

第四题 (树) 重建二叉树

题目描述

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

前序确定根节点，中序根据根节点确定左右节点

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre and not tin:
            return None
        root = TreeNode(pre[0])
        rootid = tin.index(root.val)
        root.left = self.reConstructBinaryTree(pre[1: rootid+1], tin[:rootid])
        root.right = self.reConstructBinaryTree(pre[rootid+1:], tin[rootid+1:])
        return root

第五题 (栈和队列) 用两个栈实现队列

题目描述

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

class Solution:
    def __init__(self):
        self.s1 = []
        self.s2 = []
    def push(self, node):
        # write code here
        self.s1.append(node)
    def pop(self):
        # return xx
        if self.s2:
            return self.s2.pop()
        else:
            while self.s1:
                self.s2.append(self.s1.pop())
            return self.s2.pop()

python自带的append和pop可以模拟实现栈和队列

# 对于一个列表stack
stack = [3, 4, 5]
# 进栈
stack.append(n)
# 出栈
stack.pop()

# 对于一个队列queue
queue = [1, 2, 3]
# 进队列
queue.append(n)
# 出队列
queue.pop(0)

第六题 (查找和排序) 旋转数组的最小数字

题目描述

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

就是求出数组里面最小的那个

方法一

最简单的使用python的内置函数，不过这样这道题就失去意义了。

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        m = min(rotateArray)
        return m

方法二

先排序再取第一个值

排序也有内置函数sort()可以使用。

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        else:
            rotateArray.sort()
            return rotateArray[0]

自己写一个快排提交出现了错误。

快排在已排序或者数值全部相等情况下最差，复杂度为O(n^2)，退化成冒泡排序。

方法三

根据数组本身具有的特性

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        length = len(rotateArray)
        if length == 0:
            return 0
        elif length == 1:
            return rotateArray[0]
        else:
            for i in range(length - 1):
                if rotateArray[i] > rotateArray[i + 1]:
                    return rotateArray[i + 1]
            return rotateArray[length - 1]

方法四

二分查找，参考牛客‘XD’的答案

根据题意说明是一个递增数组的旋转，所以如题所示【3,4,5】，【1,2】还是局部递增的，在这种的数组中查找，一般选择二分的方法；基本模型有了，下面试着分析：

1.先取出中间的数值，和最后一个比较5>2 说明mid之前的某些部分旋转到了后面，所以下次寻找 low = mid+1 开始；

2.取出的中间值要是小于high，说明mid-high之间都应为被旋转的部分，所以最小应该在mid的前面，但是也有可能当前的mid 就是最小的值所以下次需找的应该从mid开始，也即high = mid 开始

3.当*mid == *high的时候，说明数组中存在着相等的数值，可能是这样的形式【2,2,2,2,1,2】所以应该选择的high 应该递减1 作为下次寻找的上界。

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return 0
        l = 0
        r = len(rotateArray)-1
        mid = -1
        if rotateArray[l] == rotateArray[r]:
            for i in range(len(rotateArray)-1):
                if rotateArray[i] > rotateArray[i+1]:
                    return rotateArray[i+1]
        while rotateArray[l] >= rotateArray[r]:
            if l+1 == r:
                mid = r
                break
            mid = (l+r)//2
            if rotateArray[mid] <= rotateArray[r]:
                r = mid
            elif rotateArray[mid] >= rotateArray[l]:
                l = mid
        return rotateArray[mid]

第七题 (递归和循环) 斐波那契数列

题目描述

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

n<=39

采用递归做的时候运行超时了，所以采用非递归方式。

class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0 or n == 1:
            return n
        a = 0
        b = 1
        for i in range(2, n+1):
            t = a + b
            a = b
            b = t
        return t

第八题 (递归和循环) 跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

实际上也是斐波那契数列

class Solution:
    def jumpFloor(self, number):
        # write code here
        a, b = 1, 1
        for i in range(number):
            a, b = b, a+b
        return a

第九题 (递归和循环) 变态跳台阶

题目描述

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

分析：

n级台阶，第一步有n种跳法：跳1级、跳2级、到跳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(1)

所以f(n)=f(n-1)*2

class Solution:
    def jumpFloorII(self, number):
        # write code here
        return 2**(number-1)

如果不是很理解，可以直接列举几个找规律

number=1 '1' 1种

number=2 '1+1;2' 2种

number=3 '1+1+1;1+2;2+1;3' 4种

number=4 '1+1+1+1;1+1+2;1+2+1;2+1+1;2+2;1+3;3+1;4' 8种

以此类推……

第十题 (递归和循环) 矩形覆盖

题目描述

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

还是斐波那契数列，2*n的大矩形，和n个2*1的小矩形

class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 1:
            return number
        a, b = 1, 2
        for i in range(2,number+1):
            a, b = b, a+b
        return a

可以直接列举几个找规律

n = 1 '|' 1

n=2 '||、=' 2

n=3 ’|||、|=、=|‘ 3

n=4 '||||、||=、|=|、=||、==’ 5

以此类推……

N第十一题 (位运算) 二进制中1的个数

题目描述

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

看题目第一眼想到取余做，但是提交出错了

整理一下思路，首先要判断数是否为正数，如果是负数要用补码表示，所以n & 0xffffffff，把负数变成正数。

方法一

class Solution:
    def NumberOf1(self, n):
        # write code here
        if n<0:
            n = n & 0xffffffff
        return bin(n).count('1')

方法二

使用n & (n - 1)消去n最后一位的1，消了几次就是n中有几个1

class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        if n<0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = (n-1)&n
        return count

第十二题 (代码的完整性) 数值的整数次方

题目描述

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

方法一

python只要一句话哎

class Solution:
    def Power(self, base, exponent):
        return base**exponent

方法二

class Solution:
    def Power(self, base, exponent):
        r = 1.0
        if exponent == 0:
            return 1
        temp = abs(exponent)
        for i in range(temp):
            r = r * base
        if exponent > 0:
            return r
        else:
            return 1/r

第十三题 (代码的完整性) 调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

一开始想用快排的思想，但是快排是不稳定的，不能满***换位置后奇数偶数的相对位置不变。

方法一

首先想到把偶数挑出来，再接到奇数后面。这里就产生了空间复杂度，如果要求原地就不满足了。

class Solution:
    def reOrderArray(self, array):
        l = []
        i = 0
        while i < len(array):
            if array[i] % 2 == 0:
                l.append(array[i])
                array.remove(array[i])
            else:
                i += 1
        array.extend(l)
        return array

方法二

考虑不额外开辟空间

class Solution:
    def reOrderArray(self, array):
        # write code here
        i = 0    # 记录偶数
        while i < len(array):
            while i < len(array) and array[i]%2 == 1:
                i += 1
            j = i + 1    # 记录奇数
            while j < len(array) and array[j]%2 == 0:
                j += 1
            if j < len(array):
                array.insert(i, array.pop(j))
            else:
                break
        return array

代码的鲁棒性：程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。

所以各种情况要考虑完全

第十四题 (代码的鲁棒性) 链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

方法一

head和k的条件判断很重要，因为这两个条件提交了3次才成功。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        if head is None:
            return head
        l = []
        while head.next:
            l.append(head)
            head = head.next
        l.append(head)
        if k > len(l) or k <= 0:
            return None
        return l[-k]

方法二

还是要注意边界条件，很重要！因为两个判断又提交了3次才成功！

class Solution:
    def FindKthToTail(self, head, k):
        if head is None or k <= 0:
            return None
        slow, quick = head, head
        for i in range(k-1):
            if quick is None or quick.next is None:
                return None
            quick = quick.next
        while quick.next:
            slow = slow.next
            quick = quick.next
        return slow

第十五题 (代码的鲁棒性) 反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

不带头节点的单链表反转问题

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None or pHead.next is None:
            return pHead
        p = pHead
        q = pHead.next
        p.next = None
        while q:
            t = q.next
            q.next = p
            p = q
            q = t
        return p

第十六题 (代码的鲁棒性) 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

方法一

开辟一个新的链表，不使用递归

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        temp = ListNode(0)
        t = temp
        while pHead1 and pHead2:
            if pHead1.val > pHead2.val:
                t.next = pHead2
                pHead2 = pHead2.next
            else:
                t.next = pHead1
                pHead1 = pHead1.next
            t = t.next  # 加这句话很重要！？
        if pHead1:
            t.next = pHead1
        if pHead2:
            t.next = pHead2
        return temp.next

方法二

使用递归

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val < pHead2.val:
            t = pHead1
            t.next = self.Merge(pHead1.next, pHead2)
        else:
            t = pHead2
            t.next = self.Merge(pHead1, pHead2.next)
        return t

(N)第十七题 (代码的鲁棒性) 树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

没做出来，参考一下别人的答案

思路：递归。增加辅助函数判断树A树B是否相同。

1）首先在树A中找到和树B根节点值相同的结点R；

2）判断树A中以R为根结点的子树是不是包含和树B一样的结构。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        result = False
        if pRoot1 and pRoot2:
            if pRoot1.val == pRoot2.val:
                result = self.similar(pRoot1, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
    def similar(self, p, q):
        if q is None:   # 如果Tree2已经遍历完了都能对应的上，返回true
            return True
        if p is None:   # 如果Tree2还没有遍历完，Tree1却遍历完了。返回false
            return False
        if p.val != q.val:
            return False
        return self.similar(p.left, q.left) and self.similar(p.right, q.right)

第十八题 (面试思路) 二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if not root:
            return None
        root.right, root.left = root.left, root.right
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root

(N)第十九题 (画图让抽象形象化) 顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

来自牛客讨论的方法

对原矩阵

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

每次打印第一行1，2，3，4后，进行逆时针旋转，变成

8 12 16

7 11 15

6 10 14

5 9 13

继续打印第一行8，12，16后逆时针旋转……

class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        n = len(matrix)
        m = len(matrix[0])
        out = []
        while matrix:
            out += matrix.pop(0)
            if not matrix or not matrix[0]:
                break
            matrix = self.turn(matrix)
        return out
    def turn(self, matrix):
        m = len(matrix)     # 行数
        n = len(matrix[0])  # 列数
        new = []
        for i in range(n-1, -1, -1):
            newh = []
            for j in range(m):
                newh.append(matrix[j][i])
            new.append(newh)
        return new

第二十题 (举例让抽象具体化) 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

python一句话搞定

class Solution:
    def __init__(self):
        self.stack = []
    def push(self, node):
        # write code here
        self.stack.append(node)
    def pop(self):
        # write code here
        return self.stack.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return min(self.stack)

不用python自带的min实现

class Solution:
    def __init__(self):
        self.stack = []
        self.mins = []
    def push(self, node):
        # write code here
        if not self.mins:
            self.mins.append(node)
        else:
            self.mins.append(min(self.mins[-1], node))
        self.stack.append(node)
    def pop(self):
        # write code here
        if not self.stack:
            return None
        self.mins.pop()
        return self.stack.pop()
    def top(self):
        # write code here
        if not self.stack:
            return None
        return self.stack[-1]
    def min(self):
        # write code here
        if not self.mins:
            return None
        return self.mins[-1]

第二十一题(N) (举例让抽象具体化) 栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

来自牛客讨论的思路

方法一

添加辅助的栈，遍历pushV和popV，

遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，此时栈顶1≠4，继续入栈2

此时栈顶2≠4，继续入栈3

此时栈顶3≠4，继续入栈4

此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3

此时栈顶3≠5，继续入栈5

此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3

class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if len(pushV)==0 or len(popV)==0 or len(pushV) != len(popV):
            return False
        stack = []
        j = 0
        for i in range(len(pushV)):
            stack.append(pushV[i])
            while stack and stack[-1] == popV[j]:
                stack.pop()
                j += 1
        if not stack:
            return True
        else:
            return False

方法二

辅助栈stack中存入pushV中取出的数据

如果pushV和popV第一个元素相等，直接都弹出，根本不用压入stack

如果stack的最后一个元素与popV中第一个元素相等，将两个元素都弹出

如果pushV中有数据，压入stack

class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        while popV:
            if pushV and pushV[0] == popV[0]:
                pushV.pop(0)
                popV.pop(0)
            elif stack and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
            elif pushV:
                stack.append(pushV.pop(0))
            else:
                return False
        return True

第二十二题 (举例让抽象具体化)从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

层次遍历输出

借用一个辅助队列

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        t = []
        queue = []
        if not root:
            return t
        queue.append(root)
        t.append(root.val)
        while queue:
            fu = queue.pop(0)
            if fu.left:
                t.append(fu.left.val)
                queue.append(fu.left)
            if fu.right:
                t.append(fu.right.val)
                queue.append(fu.right)
        return t

第二十三题 (N)(举例让抽象具体化) 二叉搜索树的后序遍历序列

题目描述

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

每次碰到树相关的问题都很困惑！

假设序列为 sequence[0, 1, 2, ..., n-1]
(1) 序列的最后一个节点为根节点root = sequence[n -1]；
(2) 从序列第一个元素开始查找第一个值大于root的值的元素 sequence[i]；
(3) 如果从sequence[i]到root前一个节点sequence[n-2]的值都大于root的值，则进行下一步，否则直接返回false；
(4) 如果i>0,则说明二叉查找树含有左子树，那么重复步骤(1)(2)(3)判断序列sequence[0, 1, ..., i-1]是否为二叉查找树的后序遍历结果；
(5) 如果i<n-1,则说明二叉查找树含有右子树，那么重复步骤(1)(2)(3)判断序列sequence[i, i+1, ..., n-2]是否为二叉查找树的后序遍历结果；
(6) 如果步骤(4)、(5)的结果都为true，那么这个序列就是二叉查找树的后序遍历结果；否则不是。

class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 0:
            return False
        root = sequence[-1]
        for i in range(len(sequence)):
            if sequence[i] > root:
                break
        print(sequence[i])
        for j in range(i, len(sequence)-1):
            if sequence[j] < root:
                return False
        l = r = True
        if i > 0:
            l = self.VerifySquenceOfBST(sequence[:i])
        if i < len(sequence)-1:
            r = self.VerifySquenceOfBST(sequence[i:-1])
        return l and r

第二十四题 (举例让抽象具体化) 二叉树中和为某一值的路径

题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的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
        out = []
        s = []
        if root:
            self.DFS(root, expectNumber, out, s)
        return out

    def DFS(self, r, n, out, s):
        s.append(r.val)
        if not r.left and not r.right and sum(s) == n:
            out.append(s[:])    # 注意一下这句话
        if r.left:
            self.DFS(r.left, n, out, s)
        if r.right:
            self.DFS(r.right, n, out, s)
        s.pop()

思路本身还好不是很难，但运行的时候，原来out.append(s[:])写的是out.append(s)，输出的总是空列表，但输出中间值是有的。查了很多博客，提到Python的可变对象、不可变对象等机制。

参考博文：剑指offer：二叉树中和为某一值的路径

第二十五题 (N)(分解让复杂问题简单) 复杂链的复制

题目描述

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

分析一下

链表的复杂在于有一个特殊指针指向任意一个结点，如果去掉这个特殊指针，那么完成链表的复制就很简单了。

第一步复制原来的链表，顺次连接形成新链表

第二步，利用原节点的random指向，来用复制的相应节点的random

最后一步，将复制好的链表拆分出来，或者说将偶数位的节点重新拆分合成新的链表，得到的就是复制的链表

# -*- 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):
        if not pHead:
            return pHead
        # 第一步 复制原来的链表，顺次连接形成新链表
        cloNode = pHead    # 指向被复制的点
        while cloNode:
            node = RandomListNode(cloNode.label)    # 新建复制的点
            node.next = cloNode.next
            cloNode.next = node
            cloNode = node.next
        # 第二步，利用原节点的random指向，来用复制的相应节点的random
        cloNode = pHead    # 指向被复制的点，即原链表的结点A
        while cloNode:
            node = cloNode.next    # 新建复制的点，即复制原链表结点的新节点B
            if cloNode.random:
                node.random = cloNode.random.next
            cloNode = node.next
        # 最后一步，将复制好的链表拆分出来
        cloNode = pHead
        pHead = pHead.next
        while cloNode.next:
            node = cloNode.next
            cloNode.next = node.next
            cloNode = node
        return pHead

参考：剑指Offer-复杂链表的复制 -python

第二十六题 (N)(分解让复杂问题简单) 二叉搜索树与双向链表

题目描述

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

老实说连题目都没读懂，

看解题思路的时候看到这张图，才大概明白了题目的意思

这样子的话就是中序遍历的思想，剩下的还是不怎么会，吐血

参考剑指offer：二叉搜索树与双向链表（Python）

看了3遍终于看明白了。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.pHead = None    
        # pHead指向链表头节点，这里就是指向中序遍历的第一个数字，也即根节点左孩子的最左节点
        self.pTail = None
        # pTail刚开始指向当前操作节点的前一个节点，完成指针指向变化后，指向当前操作节点
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        self.Convert(pRootOfTree.left)
        if not self.pHead:    # 初始化pHead节点和Tail节点
            self.pHead = pRootOfTree
            self.pTail = pRootOfTree
        else:    # pRootOfTree为当前操作节点，变换它的左边的链接
            self.pTail.right = pRootOfTree
            pRootOfTree.left = self.pTail
            self.pTail = pRootOfTree
        self.Convert(pRootOfTree.right)
        return self.pHead

附：前/中/后序/层次遍历(递归/非递归)

class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def initTree(self):    # 构造树
        m = TreeNode(0)
        m1 = TreeNode(1)
        m2 = TreeNode(2)
        m.left = m1
        m.right = m2
        m3 = TreeNode(3)
        m4 = TreeNode(4)
        m1.left = m3
        m1.right = m4
        m5 = TreeNode(5)
        m6 = TreeNode(6)
        m2.left = m5
        m2.right = m6
        m7 = TreeNode(7)
        m8 = TreeNode(8)
        m3.left = m7
        m3.right = m8
        m9 = TreeNode(9)
        m4.left = m9
        return m

    def layer(self, root):    # 层次遍历
        if not root:
            return None
        queue = [root]
        while queue:
            t = queue.pop(0)
            print(t.val, end=" ")
            if t.left:
                queue.append(t.left)
            if t.right:
                queue.append(t.right)

    def preOrder(self, root):    # 先序遍历-递归
        if not root:
            return None
        print(root.val, end=" ")
        self.preOrder(root.left)
        self.preOrder(root.right)

    def preOederNo(self, root):    # 先序遍历-非递归
        if not root:
            return None
        # out = []
        stack = []
        while root or stack:
            while root:
                # out.append(root.val)
                print(root.val, end=" ")
                stack.append(root)
                root = root.left
            if stack:
                t = stack.pop()
                root = t.right
        # return out

    def midOrder(self, root):    # 中序遍历-递归
        if not root:
            return None
        self.midOrder(root.left)
        print(root.val, end=" ")
        self.midOrder(root.right)

    def midOederNo(self, root):    # 中序遍历-非递归
        if not root:
            return None
        # out = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            if stack:
                t = stack.pop()
                # out.append(root.val)
                print(t.val, end=" ")
                root = t.right
        # return out

    def postOrder(self, root):    # 后序遍历-递归
        if not root:
            return None
        self.postOrder(root.left)
        self.postOrder(root.right)
        print(root.val, end=" ")

    def postOederNo(self, root):    # 后序遍历-非递归
        if not root:
            return None
        out = []
        stack = []
        while root or stack:
            while root:
                out.append(root.val)
                stack.append(root)
                root = root.right
            if stack:
                t = stack.pop()
                root = t.left
        for i in out[::-1]:
            print(i, end=" ")

if __name__ == '__main__':
    t = Solution()
    # 构造树
    m = t.initTree()
    print("层次遍历：", end=" ")
    t.layer(m)
    print("")
    print("先序遍历(递归)：", end=" ")
    t.preOrder(m)
    print("")
    print("先序遍历(非递归)：", end=" ")
    t.preOederNo(m)
    print("")
    print("中序遍历(递归)：", end=" ")
    t.midOrder(m)
    print("")
    print("中序遍历(非递归)：", end=" ")
    t.midOederNo(m)
    print("")
    print("后序遍历(递归)：", end=" ")
    t.postOrder(m)
    print("")
    print("后序遍历(非递归)：", end=" ")
    t.postOederNo(m)

运行结果

第二十七题(N) (分解让复杂问题简单) 字符串的排列

题目描述

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

输入描述:

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

python有自带的库可以求全排列

import itertools
class Solution:
    def Permutation(self, ss):
        res = []
        if not ss:
            return res
        else:
            for i in itertools.permutations(ss):
                res.append(''.join(i))
        return sorted(list(set(res)))

不考虑自带库，涉及到全排列

一是使用递归

class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        if len(ss) == 1:
            return [ss]
        res = []
        # 固定第一个元素，然后递归求解
        for i in range(len(ss)):
            for j in self.Permutation(ss[:i]+ss[i+1:]):
                res.append(ss[i]+j)
        return sorted(list(set(res)))

二是使用深度优先算法

其他语言有看到使用字典排序算法

mark一下

前面3题：25、26、27对我来说有点难，没有思路，空着好久，参考了一些的博文和牛客的讨论。

第二十八题 (时间效率)数组中出现次数超过一半的数字

题目描述

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

方法一

使用字典

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        dic = {}
        for i in numbers:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        for i in dic:
            if dic[i]>len(numbers)//2:
                return i 
        return 0

方法二

使用python自带的库

import collections
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        l = collections.Counter(numbers)
        for x in l.most_common(1):
            if x[1] > len(numbers)//2:
                return x[0]
        return 0

简化一下

import collections
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        l = collections.Counter(numbers)
        x = l.most_common(1)    # 得到的x是[( )]形式
        if x[0][1] > len(numbers)//2:
            return x[0][0]
        return 0

第二十九题 (时间效率)最小的K个数

题目描述

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

用python的话方法很多

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        tinput.sort()
        if k > len(tinput):
            return []
        return tinput[:k]

import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k > len(tinput):
            return []
        return heapq.nsmallest(k,tinput)

写一个冒泡排序

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        self.sort(tinput)
        return tinput[:k]
    def sort(self, n):
        for i in range(len(n)):
            for j in range(1,len(n)-i):
                if n[j] < n[j-1]:
                    n[j], n[j-1] = n[j-1], n[j]
        return n

第三十题 (时间效率)连续子数组的最大和

题目描述

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

方法一

比较笨的方法，就是把所有可能算一下，边算边选最大的

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        maxt = array[0]
        for i in range(len(array)):
            temp = 0
            for j in range(i, len(array)):
                temp += array[j]
                if temp > maxt:
                    maxt = temp
        return maxt

方法二

最大序列和的第一个数和最后一个数一定是正数

对当前的数i：

如果前面的累加值为负数或者等于0，那对累加值清0重新累加，把当前的第i个数的值赋给累加值。

如果前面的累加值为整数，那么继续累加，即之前的累加值加上当前第i个数的值作为新的累加值。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        maxt = array[0]
        temp = 0
        for i in array:
            if temp < 0:
                temp = i
            else:
                temp += i
            if temp > maxt:
                maxt = temp
        return maxt

第三十一题 (时间效率)整数中1出现的次数（从1到n整数中1出现的次数）

题目描述

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

方法一

直接用python将每个数转化为字符串看里面有几个1比较简单

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for i in range(1, n+1):
            for i in str(i):
                if i == '1':
                    count += 1
        return count

方法二

遍历每一个数字，然后一个个算，时间复杂度有点高

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        count = 0
        for i in range(1, n+1):
            temp = i
            while temp:
                if temp % 10 == 1:
                    count += 1
                temp //= 10
        return count

方法三

参考牛客‘咩咩jiang’的解析

主要思路：设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析

根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i

1、当i表示百位，且百位对应的数>=2：

如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a/10+1)*100个点的百位为1

2、当i表示百位，且百位对应的数为1：

如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a/10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a/10*100）+(b+1)，这些点百位对应为1

3、当i表示百位，且百位对应的数为0：

如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）

综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1

之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)

换句话说，补8是为了合并第一种和第三种的情况。

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        count = 0
        i = 1
        while i <= n:
            a = n // i
            b = n % i
            count += (a+8)//10*i+(a%10==1)*(b+1)
            i *= 10
        return count

扩展到计算1至n中数字X出现的次数

第三十二题 (时间效率)把数组排成最小的数

题目描述

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

转化为str进行比较

虽然牛客上是使用python2.7，但自己平时使用的都是3.5、3.6版本，所以python3里没有了cmp参数，只有key参数

比较函数（comparison function）转化为了关键字函数（key function）

functools.cmp_to_key(func)函数主要用来将程序转成 Python3 格式的，因为 Python3 中不支持比较函数

from functools import cmp_to_key
class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers:
            return ""
        n = list(map(str, numbers))
        n.sort(key=cmp_to_key(self.cmp))
        return "".join(n)
    def cmp(self, x, y):
        if x+y > y+x:
            return 1
        if x+y < y+x:
            return -1
        else:
            return 0

如果对python2则有

class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers:
            return ""
        n = list(map(str, numbers))
        n.sort(cmp=lambda x, y: int(x + y) - int(y + x))
        return "".join(n)

第三十三题 (时间空间效率的平衡)丑数

题目描述

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

错误的尝试：最开始想用蛮力法，一个数一个数看满不满足，直到得到第N个丑数

class Solution:
    def GetUglyNumber_Solution(self, index):
        l = [1]
        t = 2
        while len(l) < index:
            if self.ischou(t):
                l.append(t)
            t += 1
        return l[-1]
    def ischou(self,i):
        while i >1:
            if i % 2 == 0:
                i = i//2
            elif i % 3 == 0:
                i =i//3
            elif i % 5 == 0:
                i = i//5
            else:
                return False
        return True

代码没问题，但是时间复杂度太高，超出时间限制

考虑其他方法

class Solution:
    def GetUglyNumber_Solution(self, index):
        if index < 7:
            return index
        out = [1]
        t2=t3=t5 = 0
        while len(out) < index:
            m = min(out[t2]*2, out[t3]*3, out[t5]*5)
            out.append(m)
            print(out)
            if out[t2] * 2 == m:
                t2 += 1
            if out[t3] * 3 == m:
                t3 += 1
            if out[t5] * 5 == m:
                t5 += 1
        return out[-1]

第三十四题 (时间空间效率的平衡)第一个只出现一次的字符

题目描述

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

方法一

想到的第一个方法就是扫描字符串，将每一个字符与整个字符串进行比较，找到第一个只出现一次的字符串。

时间复杂度为O(n^2)，算法复杂度过大

考虑用空间换时间

由于字典是无序的所以，使用字典很难找到第一个只出现一次的字符串，所以再遍历一次

class Solution:
    def FirstNotRepeatingChar(self, s):
        if not s:
            return  -1
        dic = {}
        for i in s:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        for i in s:
            if dic[i]==1:
                return s.index(i)

也可以分三个列表，分别存储所有的字符、出现多次的字符；根据前两个可以得到只出现一次的字符。

class Solution:
    def FirstNotRepeatingChar(self, s):
        if not s:
            return  -1
        s1 = []
        s2 = []
        out = []
        for ss in s:
            if ss not in s1:
                s1.append(ss)
            else:
                s2.append(ss)
        for ii in s1:
            if ii not in s2:
                out.append(ii)
        c = out[0]
        return s.index(c)

方法二

体现了python的简便之处

class Solution:
    def FirstNotRepeatingChar(self, s):
        for i in s:
            if s.count(i) == 1:
                return s.index(i)
        return -1

方法三

使用collections下的Counter，字典子类，为可以进行哈希的对象计数

同时还涉及到enumerate，将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标

from collections import Counter
class Solution:
    def FirstNotRepeatingChar(self, s):
        if not s:
            return  -1
        count = Counter(s)
        for i,c in enumerate(s):
            if count[c] == 1:
                return i

第三十五题(N) (时间空间效率的平衡)数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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

输出：7

一上来还是想到两个循环，算法复杂度过大

看讨论区说用Python解决的代码很难在1秒内完成，所以答案过不了

参考Python：数组中的逆序对，提供两种思路

一个如下

计算数组中的最小值在数组中出现的位置，统计数组中最小值前面的个数(即其index)，之后在原始数组中去掉最小值。重复上述步骤。

不过这个做法还是时间复杂度超了

class Solution:
    def InversePairs(self, data):
        if not data:
            return 0
        c = 0
        while len(data) > 1:
            c += data.index(min(data))
            data.pop(data.index(min(data)))
        return c%1000000007

作为只会c和python的渣渣，这个题真的很为难我。先空着吧。

一个是归并排序

参考牛客‘rs勿忘初心’的讨论

(a) 把长度为4的数组分解成两个长度为2的子数组；

(b) 把长度为2的数组分解成两个成都为1的子数组；

在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。

(c) 把长度为1的子数组 合并、排序并统计逆序对 ；

一边合并相邻的子数组，一边统计逆序对的数目。

在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。

由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组排序如上图（c）所示， 以免在以后的统计过程中再重复统计。

(d) 把长度为2的子数组合并、排序，并统计逆序对；

接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。

先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。

如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。

如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。

每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。

思路搞明白就好了，编程语言大同小异。

C++版：

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()==0)
            return 0;
        vector<int> copy(data);    // 辅助数组，每次递归后有序
        return InversePairsCore(data, copy, 0, data.size()-1);
    }
    int InversePairsCore(vector<int>& data, vector<int>& copy, int begin, int end) {
        if(begin == end)
            return 0;
        int mid = begin + (end-begin)/2;
        int left = InversePairsCore(copy, data, begin, mid);
        int right = InversePairsCore(copy, data, mid+1, end);
        
        int last_in_left = mid;		// 比较从尾端开始
        int last_in_right = end;	// 比较从尾端开始
        int index_copy = end; 		// 比较结果存入辅助数组尾端
        long res = 0;
        
        // 归并排序：相当于两个有序数组合成一个有序表（从尾端开始是为了计数）
        while(last_in_left>=begin && last_in_right>=mid+1) {
            if(data[last_in_left] > data[last_in_right]) {
                copy[index_copy--] = data[last_in_left--];
                res += last_in_right - mid;
            }
            else 
                copy[index_copy--] = data[last_in_right--];
        }
        
        while(last_in_left >= begin)
            copy[index_copy--] = data[last_in_left--];
        while(last_in_right >= mid+1)
            copy[index_copy--] = data[last_in_right--];
        
        return (left+right+res) % 1000000007;
    }
};

Java版

public class Solution {
    public int InversePairs(int [] array) {
        if(array==null||array.length==0)
        {
            return 0;
        }
        int[] copy = new int[array.length];
        for(int i=0;i<array.length;i++)
        {
            copy[i] = array[i];
        }
        int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余
        return count;
    }
    private int InversePairsCore(int[] array,int[] copy,int low,int high)
    {
        if(low==high)
        {
            return 0;
        }
        int mid = (low+high)>>1;
        int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
        int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
        int count = 0;
        int i=mid;
        int j=high;
        int locCopy = high;
        while(i>=low&&j>mid)
        {
            if(array[i]>array[j])
            {
                count += j-mid;
                copy[locCopy--] = array[i--];
                if(count>=1000000007)//数值过大求余
                {
                    count%=1000000007;
                }
            }
            else
            {
                copy[locCopy--] = array[j--];
            }
        }
        for(;i>=low;i--)
        {
            copy[locCopy--]=array[i];
        }
        for(;j>mid;j--)
        {
            copy[locCopy--]=array[j];
        }
        for(int s=low;s<=high;s++)
        {
            array[s] = copy[s];
        }
        return (leftCount+rightCount+count)%1000000007;
    }
}

第三十六题 (时间空间效率的平衡)两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。

每次拿到这种题目第一反应就是双重循环，推翻再来。

方法一

参考牛客‘Yannyezixin’的答案

两条相交的链表呈Y型。可以从两条链表尾部同时出发，最后一个相同的结点就是链表的第一个相同的结点。可以利用栈来实现。时间复杂度有O(m + n), 空间复杂度为O(m + n)

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        if not pHead1 or not pHead2:
            return None
        p = []
        q = []
        while pHead1:
            p.append(pHead1)
            pHead1 = pHead1.next
        while pHead2:
            q.append(pHead2)
            pHead2 = pHead2.next
        out = None
        while p and q:
            out1 = p.pop()
            out2 = q.pop()
            if out1 is out2:
                out = out1
            else:
                break
        return out

方法二

之所以不能用两个指针分贝对两个链表进行遍历找相同节点，是因为两者的长度不一样。那么将两个链表合并，pHead1+pHead2和pHead2+pHead1，得到的两个长度就相同了，再依次遍历就能找到相同节点了。

比如

1 2 3 5 6和4 7 5 6

分别合并得到

1 2 3 5 6 4 7 5 6以及

4 7 5 6 1 2 3 5 6

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        p1,p2=pHead1,pHead2
        while p1!=p2:
            if p1:
                p1 = p1.next 
            else:
                p1 = pHead2
            if p2:
                p2 = p2.next  
            else: 
                p2 = pHead1
        return p1

第三十七题 (知识迁移能力)数字在排序数组中出现的次数

题目描述

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

方法一

用python自带的count，很简单一句话

面试的时候大概是不能这么写的，汗颜

class Solution:
    def GetNumberOfK(self, data, k):
        return data.count(k)

方法二

考虑不使用自带函数

class Solution:
    def GetNumberOfK(self, data, k):
        if k not in data:
            return 0
        c = 0
        for i in data:
            if i == k:
                c += 1
        return c

但是这个方法没考虑到有序这个条件

方法三

使用二分查找算法找到第一个k的位置和最后一个k的位置

class Solution:
    def GetNumberOfK(self, data, k):
        if k not in data:
            return 0
        l = self.getleft(data, k, 0, len(data)-1)
        r = self.getright(data, k, 0, len(data)-1)
        return r-l+1
    def getleft(self, data, k, l, r):
        while l <= r:    # !
            mid = (l+r)//2
            if data[mid] < k:    # !
                l = mid+1
            else:
                r = mid-1
        return l    # !
    def getright(self, data, k, l, r):
        while l <= r:    # !
            mid = (l+r)//2
            if data[mid] <= k:    # !
                l = mid+1
            else:
                r = mid-1
        return r    # !

备注感叹号的都是我觉得需要注意的地方

第三十八题 (知识迁移能力)二叉树的深度

题目描述

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

# 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
        return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1


# 考虑层次遍历非递归
class Solution:
    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        t = [pRoot]
        h = 0
        while t:
            for i in range(len(t)):
                temp = t.pop(0)
                if temp.left:
                    t.append(temp.left)
                if temp.right:
                    t.append(temp.right)
            h += 1
        return h

第三十九题 (知识迁移能力)平衡二叉树

题目描述

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

之前碰到过一次，没做出来。第二次做了还是有点小错误

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        if not pRoot:
            return True
        while pRoot:
            if abs(self.depth(pRoot.left) - self.depth(pRoot.right)) > 1:
                return False
            else:
                return self.IsBalanced_Solution(pRoot.left) and  self.IsBalanced_Solution(pRoot.right)
    def depth(self, r):
        if not r:
            return 0
        return max(self.depth(r.left), self.depth(r.right))+1

第四十题 (知识迁移能力)数组中只出现一次的数字

题目描述

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

这道题方法很多

方法一

比较简单能想到的是字典的方法，还有python自带的Counter方法

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        dic = {}
        for i in array:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        t = []
        for v in dic:
            if dic[v] == 1:
                t.append(v)
        return t

方法二

难一点的就是使用异或，如果是只有一个数唯一用异或还是很简单的

参考了一下牛客讨论区的答案

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        t = 0
        # 两个数相异为1相同为0
        for i in array:
            t ^= i
        # 得到的t是两个不同数的异或
        id = 1
        a = b = 0
        # 找到从右起第一个1的位置
        while t & id == 0:
            id <<= 1
        for i in array:
            if i & id == 0:     # 找到标志位为0的那些数
                a ^= i  # 标志位为0的只有一个数是单独的，找到那个数
            else:   # 找到标志位为1的那些数
                b ^= i  # 标志位为1的只有一个数是单独的，找到那个数
        return [a, b]

第四十一题 (知识迁移能力)和为S的连续正数序列

题目描述

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

输出描述:

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

方法一

想了一个比较笨的方法

class Solution:
    def FindContinuousSequence(self, tsum):
        i = 1
        out = []
        while i <= tsum//2+1:
            sum = 0
            t = []
            j = i
            while sum < tsum:
                sum += j
                t.append(j)
                j += 1
            if sum == tsum and len(t)>1:
                out.append(t)
            i += 1
        return out

原以为会因为复杂度高提交失败，没想到过了。

在牛客的讨论区发现两个比较好的方法

方法二

首先是双指针法

class Solution:
    def FindContinuousSequence(self, tsum):
        out = []
        i = 1
        j = 2
        while i < j:
            t = []
            s = (i+j)*(j-i+1)//2
            if s == tsum:
                for k in range(i, j+1):
                    t.append(k)
                out.append(t)
            if s < tsum:
                j += 1
            else:
                i += 1
        return out

方法三

参考‘丁满历险记’解析

1）由于我们要找的是和为S的连续正数序列，因此这个序列是个公差为1的等差数列，而这个序列的中间值代表了平均值的大小。假设序列长度为n，那么这个序列的中间值可以通过（S / n）得到，知道序列的中间值和长度，也就不难求出这段序列了。

2）满足条件的n分两种情况：

n为奇数时，序列中间的数正好是序列的平均值，所以条件为：(n & 1) == 1 && sum % n == 0；

n为偶数时，序列中间两个数的平均值是序列的平均值，而这个平均值的小数部分为0.5，所以条件为：(sum % n) * 2 == n.

3）由题可知n >= 2，那么n的最大值是多少呢？我们完全可以将n从2到S全部遍历一次，但是大部分遍历是不必要的。为了让n尽可能大，我们让序列从1开始，

根据等差数列的求和公式：S = (1 + n) * n / 2，得到.

class Solution:
    def FindContinuousSequence(self, tsum):
        out = []
        n = int((2*tsum)**0.5)
        for i in range(n, 1,-1):
            if (i & 1 == 1 and tsum % i == 0) or ((tsum % i) * 2 == i):
                # 求出满足条件的i
                temp = []
                k = int((tsum / i) - (i - 1) / 2)
                for j in range(i):
                    temp.append(k)
                    k += 1
                out.append(temp)
        return out

这个方法还是要好好理解一下的

第四十二题 (知识迁移能力)和为S的两个数字

题目描述

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

输出描述:

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

双指针法

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        out =[]
        if not array:
            return out
        i = 0
        j = len(array)-1
        mins = array[j]*array[j]
        while i < j:
            if array[i]+array[j] == tsum:
                temp = array[i]*array[j]
                if temp < mins:
                    mins = temp
                    out.append(array[i])
                    out.append(array[j])
                i += 1
                j -= 1
            elif array[i]+array[j] < tsum: 
                i += 1
            elif array[i]+array[j] > tsum: 
                j -= 1
        return out

根据‘马客(Mark)’说的：找到的第一组（相差最大的）就是乘积最小的。

证明：考虑x+y=C（C是常数），x*y的大小。不妨设y>=x，y-x=d>=0，即y=x+d, 2x+d=C, x=(C-d)/2, x*y=x(x+d)=(C-d)(C+d)/4=(C^2-d^2)/4，也就是x*y是一个关于变量d的二次函数，对称轴是y轴，开口向下。d是>=0的，d越大, x*y也就越小。

所以其实代码中设置的mins并没有什么用，去掉也不会影响最后的结果。

第四十三题 (知识迁移能力)左旋转字符串

题目描述

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

使用切片

class Solution:
    def LeftRotateString(self, s, n):
        if not s:
            return ""
        n = n %(len(s))
        return s[n:]+s[:n]

也可以使用三次反转

class Solution:
    def LeftRotateString(self, s, n):
        if not s: return s
        s = list(s)
        self.reverse(s, 0, n - 1)
        self.reverse(s, n, len(s) - 1)
        self.reverse(s, 0, len(s) - 1)
        return ''.join(s)

    def reverse(self, s, start, end):
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

第四十四题 (知识迁移能力)翻转单词顺序列

题目描述

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

class Solution:
    def ReverseSentence(self, s):
        s = list(map(str,s.split(" ")))
        s.reverse()
        return " ".join(s)

附：推荐工程师死绝的世界

插一句：2019.1.22

今天参加了牛客网的寒假算法训练营(一），做到自闭，我怕是对自己有什么误解。

另外呢，日本IT求职学习服务平台PAIZA推出了一个编程游戏《工程师死绝的世界》

玩了几局感觉可以，推荐一下，看懂全靠Google翻译。

第四十五题 (抽象建模能力)扑克牌顺子

题目描述

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。

思路：数字0可以代表任意数

有以下几个条件必须满足

1、除0以外，不能有其他重复数字，注意0最多只有4个。

2、满足顺子的话，排序后前一个数比后一个数小1。同时需要考虑有0的情况，如果后面一个数比前面一个数大于1以上，那么就用0来补。

class Solution:
    def IsContinuous(self, numbers):
        if not numbers:
            return None
        zero = numbers.count(0)
        if zero == 5:
            return False
        numbers.sort()
        for i in range(0, len(numbers)-1):
            if numbers[i] != 0:
                if numbers[i] == numbers[i+1]:
                    return False
                zero -= numbers[i+1] - numbers[i] - 1
        if zero < 0:
            return False
        return True

第四十六题 (N)(抽象建模能力)孩子们的游戏(圆圈中最后剩下的数)

题目描述

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

看着挺简单的，但是不知道怎么用算法表示出来

class Solution:
    def LastRemaining_Solution(self, n, m):
        if n < 1:
            return -1
        if n == 1:
            return 0 
        l = []
        for i in range(n):
            l.append(i)
        i = -1
        j = 0
        while l:
            k = (j+m-1)%n
            i = l.pop(k)
            n -= 1
            j = k
        return i

参考：约瑟夫环问题

时间复杂度为O(n)，空间复杂度为O(1)

在这n个数字中，第一个被删除的数字是(m-1)%n，为简单起见记为k。那么删除k之后的剩下n-1的数字为0,1,…,k-1,k+1,…,n-1，并且下一个开始计数的数字是k+1。相当于在剩下的序列中，k+1排到最前面，从而形成序列k+1,…,n-1,0,…k-1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样（最初的序列是从0开始的连续序列），因此该函数不同于前面函数，记为f’(n-1,m)。最初序列最后剩下的数字f(n,m)一定是剩下序列的最后剩下数字f’(n-1,m)，所以f(n,m)=f’(n-1,m)。

接下来我们把剩下的的这n-1个数字的序列k+1,…,n-1,0,…k-1作一个映射，映射的结果是形成一个从0到n-2的序列：

k+1    ->    0
k+2    ->    1
…
n-1    ->    n-k-2
0   ->    n-k-1
…
k-1   ->   n-2

把映射定义为p，则p(x)= (x-k-1)%n，即如果映射前的数字是x，则映射后的数字是(x-k-1)%n。对应的逆映射是p-1(x)=(x+k+1)%n。

由于映射之后的序列和最初的序列有同样的形式，都是从0开始的连续序列，因此仍然可以用函数f来表示，记为f(n-1,m)。根据我们的映射规则，映射之前的序列最后剩下的数字f’(n-1,m)= p-1 [f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=(m-1)%n代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。

经过上面复杂的分析，我们终于找到一个递归的公式：f(n,m)= [f(n-1,m)+m]%n

19.1.23 说实话没怎么看明白，先这样，等明天脑子清醒了再说。

第四十七题 (发散思维能力)求1+2+3+...+n

题目描述

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

class Solution:
    def Sum_Solution(self, n):
        return (1+n)*n/2

第四十八题(N) (发散思维能力)不用加减乘除做加法

题目描述

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

参考牛客‘咩咩jiang’的讨论

两个数异或：相当于每一位相加，而不考虑进位；

两个数相与，并左移一位：相当于求得进位；

python版

因为python没有无符号又移操作，所以需要越界检查一波

class Solution:
    def Add(self, num1, num2):
        while num2:
            n = num1 ^ num2    # 异或查看两个数哪些二进制位只有一个为1，这些是非进位位
            num2 = (num1 & num2)<<1    # 找出进位项
            num1 = n & 0xFFFFFFFF
        return num1 if num1 <= 0x7FFFFFFF else ~(num1 ^ 0xFFFFFFFF)

C++版

class Solution {
public:
    int Add(int num1, int num2)
    {
        while(num2)
        {
            int temp = num1 ^ num2;
            num2 = (num1 & num2)<<1;
            num1 = temp;
        }
        return num1;
    }
}

C++的另一个版本

1:按位与是查看两个数哪些二进制位都为1，这些都是进位位，结果需左移一位，表示进位后的结果

2:异或是查看两个数哪些二进制位只有一个为1，这些是非进位位，可以直接加、减，结果表示非进位位进行加操作后的结果

3:n1&n2是查看有没有进位位了，如果有，需要重复step1、step2；如果没有，保留n1、n2上二进制为1的部分，

两数相或即为最后结果

class Solution {
public:
    int Add(int num1, int num2)
    {       
         int n1,n2;
        n1 = (num1 & num2)<<1;
        n2 = num1 ^ num2;
        while(n1 & n2)
        {
            num1 = n1;
            num2 = n2;
            n1 = (num1 & num2)<<1;
            n2 = num1 ^ num2;
        }
        return n1 | n2;
    }
}

两个版本其实是一个意思。

吐槽一句，用惯了python回头用c/c++写程序的时候，一直忘记定义变量以及每一句后面加‘；’

插一句：2019.1.24

今天参加了牛客网的寒假算法训练营(二），还是两道题告终，做完回家过年了！

第四十九题(N) (综合)把字符串转换成整数

题目描述

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

输入描述: 输入一个字符串,包括数字字母符号,可以为空

输出描述: 如果是合法的数值表达则返回该数字，否则返回0

示例1

输入

+2147483647 

1a33

输出

2147483647

0

又一次没看懂题目，忧伤啊我的理解能力，再把题目多读两遍

class Solution:
    def StrToInt(self, s):
        numlist = ['0','1','2','3','4','5','6','7','8','9','+','-']
        if not s:
            return 0
        flag = 0
        i = 0
        t = 0
        if s[0] == '-':
            flag = -1
            i = 1
        elif s[0] == '+':
            flag = 0
            i = 1
        while i < len(s):
            print(i,t)
            if s[i] not in numlist:
                return 0
            t = t*10+numlist.index(s[i])
            i += 1
        if flag == 0:
            return t
        else:
            return -t

感觉写的有点复杂了，但是思路都是差不多的。

总结一下数字字符之间的转化

str(x )	将对象 x 转换为字符串
int(x [,base ])	将x转换为一个整数 base=2将二进制变成十进制；base=8将八进制变成十进制；base=16将十六进制变成十进制；不加就是自动变成十进制
ord(x )	将单个字符转换为它的整数值 'a'对应97
oct(x )	将一个整数转换为一个八进制字符串比如将一个整数10变成0o12，所以只取后面几位oct(x)[2:]
hex(x )	将一个整数转换为一个十六进制字符串比如将一个整数10变成0xa，所以只取后面几位hex(x)[2:]

第五十题(N) (数组)数组中重复的数字

题目描述

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

class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        dic = {}
        for i in numbers:
            if i not in dic:
                dic[i] = 1
            else:
                duplication[0] = i
                return True
        return False

第五十一题(N) (数组)构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

解析：盗用一下牛客讨论里面的图，看了图，基本上思路就顺了

可以用两个列表分别存储

一个存储从1开始，依次存储A0、A0*A1、A0*A1*A2、……、A0*A1*A2*……*An-2

一个存储从1开始，依次存储An-1、An-1*An-2、……、An-1*An-2*……*A2*A1

对应想乘

我这里只用一个列表存储，所以注意最后取的是B[:len(A)-2:-1]

不太理解可以举特殊的例子看一会下就知道了。

class Solution:
    def multiply(self, A):
        B = [1]
        if len(A) == 0:
            return None
        for i in range(1,len(A)):
            B.append(B[i-1]*A[i-1])
        temp = 1
        for j in range(len(A)-2, -1, -1):
            temp *= A[j+1]
            B.append(B[j] * temp)
        return B[:len(A)-2:-1]

插一句：2019.1.26

今天参加了牛客网的寒假算法训练营(三），还是两道题告终。惨兮兮，怀疑人生……

第五十二题(N) (字符串)正则表达式匹配

题目描述

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

首先对s和patter本身存在与否进行讨论：

s和pattern都不存在，返回True

s存在但是pattern不存在，返回False

s不存在，pattern存在，只有任意字符+*的组合情况才成立，否则都返回False

其次主要是判断有'.'和'*'的不同情况

仅'.'的情况，比较简单，直接当作相同字符，s和pattern的指针都往下指一个，接着往下就好了；

'*'的情况就比较复杂了：

如果*之前的字符与s中指针指向的字符不匹配，那么*之前的字符出现0次，pattern往后进两个字符，跳到*的后一个字符

如果匹配，就要考虑*之前的字符出现几次，所以用or连接

class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        if not s and not pattern:
            return True
        if s and not pattern:
            return False
        if not s and pattern:
            if len(pattern) > 1 and pattern[1] == '*':
                return self.match(s, pattern[2:])
            else:
                return False
        if len(pattern) > 1 and pattern[1] == '*':
            if s[0] != pattern[0] and pattern[0]!='.':
                return self.match(s, pattern[2:])
            else:
                return self.match(s[1:],pattern) or self.match(s[1:],pattern[2:]) or self.match(s,pattern[2:])
        else:
            if s[0] == pattern[0] or pattern[0] == '.':
                return self.match(s[1:], pattern[1:])
            else:
                return False

第五十三题(N)(字符串)表示数值的字符串

题目描述

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

主要是对‘+’、‘-’、小数点、’e'或者‘E’的讨论

‘+’、‘-’只能出现在字符串的第一位，或者紧跟e/E。如果没有e/E，只能最多出现一次；如果有可以出现最多两次

小数点只能出现最多一次，且不能出现在e/E的后面

e/E只能最多出现一次，且不能不出现在最后一位

除此以外，还要判断一下其他位必须是0-9的字符

class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        if not s:
            return  False
        a = False   # '+'\'-'
        p = False   # '.'
        e = False   # 'e'\'E'
        for i in range(len(s)):
            if s[i] == 'e' or s[i] == 'E':
                if e:
                    return False
                else:
                    e = True
                    if i == len(s)-1:
                        return False
            elif s[i] == '.':
                if p:
                    return False
                else:
                    p = True
                    if e:
                        return False
            elif s[i] == '+' or s[i] == '-':
                if a:
                    if s[i-1] != 'e' and s[i-1] != 'E':
                        return False
                else:
                    a = True
                    if i > 0 and s[i-1] != 'e' and s[i-1] != 'E':
                        return False
            else:
                if s[i] < '0' or s[i] > '9':
                    return False
        return True

第五十四题(字符串)字符流中第一个不重复的字符

题目描述

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

输出描述:

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

没有看更多的方法

class Solution:
    # 返回对应char
    def __init__(self):
        self.s = []
        self.t = []
    def FirstAppearingOnce(self):
        if not self.t:
            return '#'
        else:
            return self.t[0]
    def Insert(self, char):
        self.s.append(char)
        if char not in self.t:
            self.t.append(char)
        else:
            self.t.remove(char)

第五十五题(链表)链表中环的入口结点

题目描述

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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        t = []
        while pHead:
            if pHead not in t:
                t.append(pHead)
            else:
                return pHead
            pHead = pHead.next
        return None

第五十六题(链表)删除链表中重复的结点

题目描述

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

非递归：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        new = ListNode(-1)
        new.next = pHead
        p = pHead
        t = new
        while p and p.next:
            if p.val != p.next.val:
                t = t.next
                p = p.next
            else:
                val = p.val
                while p and p.val == val:
                    p = p.next
                t.next = p
        return new.next

if __name__ == '__main__':
    t = Solution()
    s = ListNode(1)
    s2 = ListNode(2)
    s.next = s2
    s3 = ListNode(3)
    s2.next = s3
    s4 = ListNode(3)
    s3.next = s4
    s5 = ListNode(4)
    s4.next = s5
    s6 = ListNode(4)
    s5.next = s6
    s7 = ListNode(5)
    s6.next = s7
    q = s
    # while q:
    #     print(q.val)
    #     q = q.next
    p = t.deleteDuplication(s)
    while p:
        print(p.val)
        p = p.next

讨论区看到的另一种做法，打问号那一句我一直以为写的是t.next = p，有点疑惑

class Solution:
    def deleteDuplication(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        new = ListNode(-1)
        new.next = pHead
        p = pHead
        t = new
        q = None
        while p and p.next:
            q = p.next
            if p.val == q.val:
                while q and p.val == q.val:
                    q = q.next
                p = q
                t.next = p
            else:
                t = p    # ? 
                p = p.next
        return new.next

递归法：

class Solution:
    def deleteDuplication(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        if pHead.val == pHead.next.val:
            p = pHead.next
            while p and p.val == pHead.val:
                p = p.next
            return self.deleteDuplication(p)
        else:
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead

第五十七题(树)二叉树的下一个结点

题目描述

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

以下情况：

1.二叉树为空，则返回空；

2.如果该节点的右孩子存在，则找到该节点右孩子的最左孩子，如果其右孩子没有左孩子就是右孩子本身；

3.节点不是根节点。

如果该节点是其父节点的左孩子，则返回父节点；

否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。

# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        if not pNode:
            return None
        if pNode.right:
            p = pNode.right
            while p.left:
                p = p.left
            return p
        else:    # !
            if pNode.next: 
                p = pNode.next
                while p.val < pNode.val and p.next:
                    p = p.next
                if p.val < pNode.val:
                    return None
                else:
                    return p
            else:
                return None

!下面的if判断完全是几遍提交，提醒我错误用例之后改出来的。要注意。

之前有一道二叉排序树和双向链表之前的转换，如果先将树变成中序下的链表，再找结点也不是不可以。

第五十八题(树)对称的二叉树

题目描述

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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        else:
            return self.panduan(pRoot.left, pRoot.right)
    def panduan(self, left, right):
        if not left and not right:
            return True
        elif left and right and left.val == right.val:
            l = self.panduan(left.left, right.right)
            r = self.panduan(right.left, left.right)
            return l and r
        else:
            return False

第五十九题(树)按之字形顺序打印二叉树

题目描述

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

借用了层次遍历的思想

用t1和t2分别一层隔一层的存储每层的结点，帮助实现层次遍历

然后用一个temp来存储节点的值，一层正一层反地添加到最终输出的out里

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        out = []
        t1 = [pRoot]
        t2 = []
        while t1 or t2:
            if t1:
                temp = []
                while t1:
                    p = t1.pop(0)
                    temp.append(p.val)
                    if p.left:
                        t2.append(p.left)
                    if p.right:
                        t2.append(p.right)
                out.append(temp)
            if t2:
                temp = []
                while t2:
                    p = t2.pop(0)
                    temp.append(p.val)
                    if p.left:
                        t1.append(p.left)
                    if p.right:
                        t1.append(p.right)
                temp.reverse()
                out.append(temp)
        return out

第六十题(树)把二叉树打印成多行

题目描述

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

还是层次遍历的思想，借用队列先进先出的来实现

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        if not pRoot:
            return []
        out = []
        queue = [pRoot]
        while queue:
            temp = []
            for i in range(len(queue)):
                p = queue.pop(0)
                temp.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            out.append(temp)
        return out

第六十一题(树)序列化二叉树

题目描述

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

特地查了一下定义

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、按层的二叉树遍历方式来进行修改。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

class Solution:
    def Serialize(self, root):
        out = []
        def pre(root):
            if not root:
                out.append('#')
            else:
                out.append(str(root.val))
                pre(root.left)
                pre(root.right)
        pre(root)
        return ' '.join(out)
    def Deserialize(self, s):
        tr = s.split(' ')
        def build():
            if tr:
                t = tr.pop(0)
                if t == '#':
                    return None
                root = TreeNode(int(t))
                root.left = build()
                root.right = build()
            return root
        return build()

第六十二题(树)二叉搜索树的第k个结点

题目描述

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

二叉排序树中序遍历后可以得到顺序排列的数组，所以直接中序遍历

记得讨论特殊情况 k <=0 或者k > len(t)

另外注意题干的输出"结点"，不用val

class Solution:
    # 返回对应节点TreeNode
    def build(self, pRoot, t):
        if not pRoot:
            return None
        self.build(pRoot.left, t)
        t.append(pRoot)
        self.build(pRoot.right, t)
    def KthNode(self, pRoot, k):
        t = []
        self.build(pRoot, t)
        if k <=0 or k > len(t):
            return None
        return t[k-1]

第六十三题(树)数据流中的中位数

题目描述

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

思路很简单，但是python2和python3有区别，练习模式下只能用python2。用3的代码提交了好多遍不通过，吐血

# python2
class Solution:
    def __init__(self):
        self.out = []
        self.count = 0
    def Insert(self, num):
        self.out.append(num)
        self.out.sort()
        self.count += 1
    def GetMedian(self, out):
        if self.count % 2 == 1:
            l = len(self.out)//2
            return self.out[l]
        elif self.count % 2 == 0:
            l = len(self.out)//2
            return (self.out[l]+self.out[l-1])/2.0

# python3
class Solution:
    def __init__(self):
        self.out = []
        self.count = 0
    def Insert(self, num):
        self.out.append(num)
        self.out.sort()
        self.count += 1
    def GetMedian(self):
        if self.count % 2 == 1:
            l = len(self.out)//2
            return self.out[l]
        elif self.count % 2 == 0:
            l = len(self.out)//2
            return (self.out[l]+self.out[l-1])/2
if __name__ == '__main__':
    t = Solution()
    t.Insert(5)
    print(t.GetMedian())
    t.Insert(2)
    print(t.GetMedian())
    t.Insert(3)
    print(t.GetMedian())
    t.Insert(4)
    print(t.GetMedian())

第六十四题(栈和队列)滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

还是要注意边界情况！很重要。

class Solution:
    def maxInWindows(self, num, size):
        out = []
        if not num or size <= 0 or size > len(num):
            return out
        elif size == 1:
            return num
        else:
            for i in range(len(num)-size+1):
                temp = []
                temp = num[i:i+size]
                out.append(max(temp))
            return out

2019.1.31连同之前剩下的两道还有4道题，都是对我而言比较难的题。要好好看一下了。

第六十五题(N)(回溯法)矩阵中的路径

题目描述

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

        m = [[0 for i in range(cols)]for j in range(rows)]
        for i in range(rows):
            for j in range(cols):
                m[i][j] = matrix[i*cols+j]

原思路是转换成双层list形式做，下面的思路没问题。

可是一直不通过，很疑惑！

class Solution:
    def hasPath(self, matrix, rows, cols, path):
        for i in range(rows):
            for j in range(cols):
                if matrix[i*cols + j] == path[0]:
                    if self.find_path(list(matrix), rows, cols, path[1:], i, j):
                        return True

    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 > 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 >= 0 and matrix[(i-1)*cols+j] == path[0]:
            return self.find_path(matrix, rows, cols, path[1:], i-1, j)
        else:
            return False

第六十六题(N)(回溯法)机器人的运动范围

题目描述

地上有一个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 movingCount(self, threshold, rows, cols):
        matrix = [[0 for i in range(cols)]for j in range(rows)]
        count = self.find(threshold, rows, cols, 0, 0, matrix)
        return count
    def find(self, threshold, rows, cols, i, j, m):
        count = 0
        if i<rows and j<cols and i>=0 and j>=0 and m[i][j] == 0 and self.judge(i, j, threshold):
            m[i][j] = 1
            count += 1+self.find(threshold,rows,cols,i+1,j,m)+self.find(threshold,rows,cols,i-1,j,m)+self.find(threshold,rows,cols,i,j+1,m)+self.find(threshold,rows,cols,i,j-1,m)
        return count
    def judge(self, i, j, k):
        # temp = sum(map(int, str(i)+str(j)))
        temp = 0
        while i:
            t = i%10
            i = i//10
            temp += t
        while j:
            t = j%10
            j = j//10
            temp += t
        if temp <= k:
            return True
        else:
            return False

希望能到心仪的城市找到心仪的工作，从提高自己的渣渣编程能力开始！

给自己立个flag：

不求多，但求每题都能认真去做！