1.替换空格

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

思路：字符串元素的替换，只需要找到元素为空格的索引，然后用%20替换即可。

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

2.二维数组中的查找

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

思路一：由于数组中的元素是按规律存放的，对于

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        data = array[0]
        f = 'false'
        for i in range(1, len(array)):
            data.extend(array[i])
        if target in data:
            f = 'true'
        return f
while True:
    try:
        S=Solution()
        # 字符串转为list
        L=list(eval(raw_input()))
        array=L[1]
        target=L[0]
        print(S.Find(target, array))
    except:
        break

思路二：由于存在某种规律，所以我们可以从最小的元素所在的位置或是最大的元素所在的位置，即二维数组的左下角或是右上角开始查找。若当前位置的元素小于查找的数时，行数加1；否则列数加1.

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if array == None:
            return None
        # 行数和列数
        rows, cols = len(array), len(array[0])
        # 下三角寻找
        row = rows - 1
        col = 0
        while row >= 0 and col <= cols - 1:
            if array[row][col] == target:
                return True
            elif array[row][col] > target:
                row -= 1
            else:
                col += 1
        return False

3.从尾到头打印链表

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

思路：从尾到头返回列表中的元素，可以从头到尾遍历链表，将得到的元素不断的插入list的起始位置，然后返回list将相当于返回从尾到头遍历的元素。

e.g.

# -*- coding:utf-8 -*-
# 定义列表节点类型
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        l = []
        head = listNode
        while head:
            l.insert(0,head.val) # 不断的在list的起始位置插入
            head = head.next
        return l

单链表

单链表节点实现：

class SingleNode(object):
    def __init__(self, item):
        self.item = item
        self.next = None

单链表的常用操作：

• is_empty()：链表是否为空
• length()：链表长度
• travel()：遍历链表
• add(item)：链表头部添加元素
• append(item)：链表尾部添加元素
• insert(pos, item)：在指定位置添加元素
• remove(pos, item)：删除节点
• search(item)：查找结点是否存在

```python class SingleLinkList(object): “””单链表””” def init(self): self._head = None

def is_empty(self): “””判断链表是否为空””” return self._head is None

def length(self): “””链表长度”””

 # cur初始时指向头节点
 cur = self._head
 count = 0
 # 尾节点指向None，当未到达尾部时
 while cur is not None:
     count += 1
     # 将cur后移一个节点
     cur = cur.next
 return count

def travel(self): “””遍历链表””” cur = self._head while cur is not None: print(cur.item, end=” “) cur = cur.next print()

def add(self, item): “””头部添加元素”””

 # 先创建一个保存item节点的值
 node = SingleNode(item)
 # 将新节点的链接域next指向头节点，即_head指向的位置
 # 先连接在设置头节点指针 
 node.next = self._head
 # 将链表的头_head指向新节点
 self._head = node

def append(self, item): “””尾部添加元素””” node = SingleNode(item)

 # 先判断链表是否为空，若是空链表，则将_head指向新节点
 if self.is_empty():
     self._head = node
 # 若不为空，则找到尾部，将尾节点的next指向新节点
 else:
     cur = self._head
     while cur.next is not None:
         cur = cur.next
     cur.next = node

def insert(self, index, item): “””指定位置添加元素”””

 # 若指定位置pos为第一个元素之前，则执行头部插入
 if index <= 0:
     self.add(item)
 # 若指定位置超过链表尾部，则执行尾部插入
 elif index > (self.length() - 1):
     self.append(item)
 # 找到指定位置
 else:
     node = SingleNode(item)
     count = 0
     # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
     pre = self._head
     while count < (index - 1):
         count += 1
         pre = pre.next
     # 先将新节点node的next指向插入位置的节点
     node.next = pre.next
     # 将插入位置的前一个节点的next指向新节点
     pre.next = node

def remove(self, item): “””删除节点””” cur = self._head pre = None while cur is not None:

     # 找到了指定元素
     if cur.item == item:
         # 如果第一个就是删除的节点
         if not pre:
             # 将头指针指向头节点的后一个节点
             self._head = cur.next
         else:
             # 将删除位置前一个节点的next指向删除位置的后一个节点
             pre.next = cur.next
         break
     else:
         # 继续按链表后移节点
         pre = cur
         cur = cur.next

def search(self, item): “””链表查找节点是否存在，并返回True或者False””” cur = self._head while cur is not None: if cur.item == item: return True cur = cur.next return False

> > <a name="4a67b223"></a>
##### 双链表
> ```python
class Node(object):
    """双向链表节点"""
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None
class DLinkList(object):
    """双向链表"""
    def __init__(self):
        self._head = None
    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None
    def length(self):
        """返回链表的长度"""
        cur = self._head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        """遍历链表"""
        cur = self._head
        while cur is not None:
            print(cur.item, end=" ")
            cur = cur.next
        print("")
    def add(self, item):
        """头部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 将node的next指向_head的头节点
            node.next = self._head
            # 将_head的头节点的prev指向node
            self._head.prev = node
            # 将_head 指向node
            self._head = node
    def append(self, item):
        """尾部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 移动到链表尾部
            cur = self._head
            while cur.next is not None:
                cur = cur.next
            # 将尾节点cur的next指向node
            cur.next = node
            # 将node的prev指向cur
            node.prev = cur
    def search(self, item):
        """查找元素是否存在"""
        cur = self._head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False
    def insert(self, pos, item):
        """在指定位置添加节点"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos - 1):
                count += 1
                cur = cur.next
            # 将node的prev指向cur
            node.prev = cur
            # 将node的next指向cur的下一个节点
            node.next = cur.next
            # 将cur的下一个节点的prev指向node
            cur.next.prev = node
            # 将cur的next指向node
            cur.next = node
     def remove(self, item):
        """删除元素"""
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                # 如果首节点的元素即是要删除的元素
                if cur.next == None:
                    # 如果链表只有这一个节点
                    self._head = None
                else:
                    # 将第二个节点的prev设置为None
                    cur.next.prev = None
                    # 将_head指向第二个节点
                    self._head = cur.next
                return
            while cur != None:
                if cur.item == item:
                    # 将cur的前一个节点的next指向cur的后一个节点
                    cur.prev.next = cur.next
                    # 将cur的后一个节点的prev指向cur的前一个节点
                    cur.next.prev = cur.prev
                    break
                cur = cur.next

栈

```python class Stack(object): “””栈””” def init(self): self.items = []

def is_empty(self):
    """判断是否为空"""
    return self.items == []
def push(self, item):
    """加入元素"""
    self.items.append(item)
def pop(self):
    """弹出元素"""
    return self.items.pop()
def peek(self):
    """返回栈顶元素"""
    return self.items[len(self.items) - 1]
def size(self):
    """返回栈的大小"""
    return len(self.items)

if name == “main“: stack = Stack() stack.push(“hello”) stack.push(“world”) stack.push(“itcast”) print(stack.size()) print(stack.peek()) print(stack.pop()) print(stack.pop()) print(stack.pop()) print(stack.size())

> > <a name="0796f7f8"></a>
##### 队列
> ```python
class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def enqueue(self, item):
        """进队列"""
        self.items.insert(0, item)
    def dequeue(self):
        """出队列"""
        return self.items.pop()
    def size(self):
        """返回大小"""
        return len(self.items)
if __name__ == "__main__":
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    print(q.size())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

双端队列

```python class Deque(object): “””双端队列”””

def __init__(self):
    self.items = []
def is_empty(self):
    """判断队列是否为空"""
    return self.items == []
def add_front(self, item):
    """在队头添加元素"""
    self.items.insert(0, item)
def add_rear(self, item):
    """在队尾添加元素"""
    self.items.append(item)
def remove_front(self):
    """从队头删除元素"""
    return self.items.pop(0)
def remove_rear(self):
    """从队尾删除元素"""
    return self.items.pop()
def size(self):
    """返回队列大小"""
    return len(self.items)

if name == “main“: deque = Deque() deque.add_front(1) deque.add_front(2) deque.add_rear(3) deque.add_rear(4) print(deque.size()) print(deque.remove_front()) print(deque.remove_front()) print(deque.remove_rear()) print(deque.remove_rear())

---
<a name="19fd154f"></a>
#### 4.用两个栈实现队列
**题目描述：**用两个栈实现队列，分别实现入队和出队操作 思路：一个栈负责入队，另一个负责出队，出栈为空则从入栈中导入到出栈中。
**思路**：队列是一种先进先出的数据结构，而栈是一种后见先出的数据结构。因此需用一个栈A做入队，另一个B做出队。如果B不为空则直接弹出，否则需将A中的全部元素先压入B在从B中出栈。
```python
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.stack2 = []
    def push(self, val):
        self.stack.append(val)
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        while self.stack:
            self.stack2.append(self.stack.pop())
        return self.stack2.pop()

5.重建二叉树

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

思路：根节点preorder[0]在中序遍历数列中的位置index，index左边的部分为左子树的中序遍历序列，index右边的为右子树的中序遍历序列。相应的在前序遍历中，从索引1开始后的部分为对应的左子树和右子树的前序遍历序列，它们的元素个数和中序遍历中划分后的个数相同。 然后将左子树和右子树分别当作一棵新的二叉树，递归调用函数进行重建。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)==0:
            return None
        if len(pre)==1:
            return TreeNode(pre[0])
        else:
            res = TreeNode(pre[0])
            res.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
            res.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
        return res

背景知识：

二叉树：

```python from collection import deque

二叉树结点

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

二叉树

class Tree(object): def init(self): self.root = None

层序遍历

def bfs(self): ret = [] queue = deque([self.root]) while queue: node = queue.popleft() if node: ret.append(node.val) queue.append(node.left) queu.append(node.right) return ret

前序遍历:根-左-右

def pre_traversal(self): ret = [] def traversal(head)： if not head: return ret.append(head.val) traversal(head.left) traversal(head.right) traversal(self.root)

   return ret

中序遍历：左-根-右

def in_traversal(self): ret = []

   def traversal(head):
       if not head:
           return
       traversal(head.left)
       ret.append(head.val)
       traversal(head.right)
   traversal(self.root)
   return ret

后序遍历：左-右-根

def post_traversal(self): ret = []

   def traversal(head):
       if not head:
           return
       traversal(head.left)
       traversal(head.right)
       ret.append(head.val)
   traversal(self.root)
   return ret

根据前序遍历和中序遍历重建二叉树

def construct_tree(preorder=None, inorder=None): “”” 构建二叉树 “”” if not preorder or not inorder: return None

index = inorder.index(preorder[0])

左子树的中序遍历序列

left = inorder[0:index]

右子树的中序遍历序列

right = inorder[index+1:]

返回根节点

root = TreeNode(preorder[0])

递归调用重建二叉树

root.left = construct_tree(preorder[1:1+len(left)], left) root.right = construct_tree(preorder[-len(right):], right) return root

if name == ‘main‘: t = Tree() root = construct_tree([1, 2, 4, 7, 3, 5, 6, 8], [4, 7, 2, 1, 5, 3, 8, 6]) t.root = root print t.bfs() print t.pre_traversal() print t.in_traversal() print t.post_traversal()

---
<a name="6cd32322"></a>
#### 6.数组中重复的数字
**题目描述：**在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
**思路**：1. 题目只需要找出第一个重复的数字即可，因此可以从头开始遍历，然后查看列表剩下的元素中是否含有当前的元素，如有则结束；否则继续往后。
            2. 同样是从头开始遍历，但使用额外的list存放遍历的元素，在每次遍历前先查看list中是否包含该元素，若有则结束；否则将其添加到list后继续遍历。
```python
# 法1 运行时间：24ms 占用内存：5852k
# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        lists = []
        for i in numbers:
            if i not in lists:
                lists.append(i)
            else:
                duplication[0] = i
                return True
        return False
from collections import Counter
# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if not numbers: 
            duplication[0] = -1
            return False
        d = Counter(numbers)
        for i in d.keys():
            if d[i] > 1:
                duplication[0] = i
                return True
        return False
# 法3
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if not numbers: 
            duplication[0] = -1
            return False
        d = {}
        for i in numbers:
            if i not in d:
                d[i] = 1
            else:
                duplication[0] = i 
                return True
        return False

7.构建乘积数组

题目描述：给定一个数组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]。不能使用除法。（注意：规定B[0] = A[1] A[2] … A[n-1]，B[n-1] = A[0] A[1] … _ A[n-2];）

思路：根据题目对于B中元素的要求，B的每个位置的元素为A除去当前位置的所有位置元素的乘积，因此只需要构建一个索引列表，然后每次求B的元素时就从索引列表中除去当前索引，然后将其他位置对应元素相乘添加到B中。

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        l = len(A)
        B = []
        for idx in range(l):
            num = 1
            t = [ _ for _ in range(l)]
            t.remove(idx)
            for i in t:
                num *= A[i]
            B.append(num)
        return B
#
class Solution:
    def multiply(self, A):
        # write code here
        if not A: return None
        B = []
        for i in range(len(A)):
            num = 1
            for n in A[:i] + A[i + 1:]:
                num *= n
            B.append(num)
        return B

8.数值的整数次方

题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0

思路：题目考查代码的完整性，所以只需要考虑好所有可能的情况即可。如果base = 0，则0的任何次方均是0；如果base不为0，当时exponent = 0，则结果都是1；如果两者皆不为0，则正常返回base的exponent次方即可。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        if base == 0:
            return 0
        elif base != 0 and exponent == 0:
            return 1
        else:
            return base ** exponent

9.调整数组顺序使奇数位于偶数前面

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

思路：构建一个新的list，遍历数组中的元素，如果当前元素为奇数，则使用list.insert(index, object)函数将其插入到list开始处；若是偶数，则添加到list末尾即可

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        B = []
        t = []
        for i in array:
            if i % 2 != 0:
                B.append(i)
            else:
                t.append(i)
        B.extend(t)
        return B
# python3
# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        B = []
        for i in array:
            if i % 2 != 0:
                B.insert(0, i)
            else:
                B.append(i)
        return B

10.链表中倒数第K个节点

题目描述：输入一个链表，输出该链表中倒数第k个结点

思路：1. 先完整的遍历一遍列表，如果链表的长度大于k，在返回链表第l-k+1个节点也就是倒数第k个节点，但这样的方法需要遍历两次链表。

1. 设置两个指针p和q，首先q保持不动，p往前走k-1步；然后p和q同时往后，当p到达尾节点时，p所在的位置刚好就是倒数第k个节点，因为p和q之间的距离就是k。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindKthToTail(self, head, k):
        if head == None or k <= 0:
            return None
        p = head
        for i in range(k-1):
            if p.next:
                p = p.next
            else:
                return None
        q = head
        while p.next:
            p = p.next
            q = q.next
        return q
# 法2
class Solution:
    def FindKthToTail(self, head, k):
        if head == None or k <= 0:
            return None
        p = head
        l = 1
        while p.next:
            l += 1
            p = p.next
        if l < k:
            return None
        q =
        head
        tar = l - k + 1
        while tar -1 > 0:
            q = q.next
            tar -= 1
        return q
if __name__ == '__main__':    
    node1 = ListNode(10)
    node2 = ListNode(11)
    node3 = ListNode(13)
    node1.next = node2
    node2.next = node3
    S = Solution()
    print (S.FindKthToTail(node1, 1).val)

11.反转链表

题目描述：输入一个链表，反转链表后，输出新链表的表头。

思路：反转列表相当于在一个新链表的头部不断的插入元素，因此可以遍历链表并将遍历到的元素作为新节点插入到新链表的头部，最后再将尾节点插入到头部即可。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None or pHead.next == None:
            return pHead
        number = []
        while pHead:
            number.append(pHead.val)
            pHead = pHead.next
        number.reverse()
        newHead = ListNode(-1)
        cur = newHead
        for n in number:
            node = ListNode(n)
            cur.next = node
            cur = cur.next
        return newHead.next
# 法2
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead:
            return None
        new = None
        cur = pHead
        while cur.next:
            node = ListNode(cur.val)
            node.next = new
            new = node
            cur = cur.next
        node = ListNode(cur.val)
        node.next = new
        new = node 
        return new

12.合并两个排序列表

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

思路：双指针法

# -*- 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
        p=cur=ListNode(0)
        while pHead1 and pHead2:
            if pHead1.val >= pHead2.val:
                cur.next = pHead2
                pHead2 = pHead2.next
            else:
                cur.next = pHead1
                pHead1 = pHead1.next
            cur=cur.next
        if pHead1:
            cur.next = pHead1
        elif pHead2:
            cur.next = pHead2
        return p.next
# -*- 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
        new = ListNode(0)
        cur = new
        p = pHead1
        q = pHead2
        while p and q:
            if p.val >= q.val:
                cur.next = q
                q = q.next
            else:
                cur.next = p
                p = p.next
            cur = cur.next
        if p:
            cur.next = p
        if q:
            cur.next = q
        return new.next

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

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

思路：首先将list转换为set查看数组中包含哪些数，然后依次从set中取数在数组中查找看个数是否超过一半，若是则输出当前元素，否则继续遍历。若数组中为空或者数组中没有任何元素符合要求则输出0.

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code 
        l = len(numbers)
        if l == 0:
            return 0
        num_set = set(numbers)
        for n in num_set:
            count = 0
            for i in numbers:
                if i == n:
                    count += 1
            if count > l //2:
                return n
        return 0
# 法2
from collections import Counter
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code 
        if not numbers: return None
        n = len(numbers)
        d = Counter(numbers)
        for i in d.keys():
            if d[i] > n // 2:
                return i
        return 0

14.最小的K个数

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

思路：首先看数组的长度时候大于K，若小于K直接返回空数组；否则先将数组排序再返回前K个元素即可。

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k > len(tinput):
            return []
        else:
            tinput.sort()
            return tinput[:k]

15.连续子数组的最大和

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

思路：最大和连续子数组一定有如下几个特点：

• 第一个不为负数
• 如果前面数的累加值加上当前数后的值会比当前数小，说明累计值对整体和是有害的；如果前面数的累加值加上当前数后的值比当前数大或者等于，则说明累计值对整体和是有益的。

解题步骤：

• 定义两个变量，一个用来存储之前的累加值，一个用来存储当前的最大和。遍历数组中的每个元素，假设遍历到第i个数时：
  　　①如果前面的累加值为负数或者等于0，那对累加值清0重新累加，把当前的第i个数的值赋给累加值。
  　　②如果前面的累加值为整数，那么继续累加，即之前的累加值加上当前第i个数的值作为新的累加值。
• 判断累加值是否大于最大值：如果大于最大值，则最大和更新；否则，继续保留之前的最大和。

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        sum = array[0]
        presum = 0
        for i in array:
            if presum < 0:
                presum = i
            else:
                presum += i
            sum = max(presum,sum)
        return sum

16.整数中1出现的次数（从1到n整数中1出现的次数）

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

思路：依次取[1, n] 中的数字，利用 % 取余数判断是否等于1，若成立计数加1，否则利用 // 去掉末位数字继续判断，直到当前数字为0

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        for i in range(n + 1):
            while i > 0:
                # 余数
                if i % 10 == 1:
                    count += 1
                i = i // 10
        return count

18.丑数

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

思路： 动态规划：2，3，5，假设我们已经有n个丑数，按照顺序排列，且第n的丑数为M。那么第n+1个丑数一定是由这n个丑数分别乘以2，3，5，得到的所有大于M的结果中，最小的那个数。

事实上我们不需要每次都计算前面所有丑数乘以2，3，5的结果，然后再比较大小。因为在已存在的丑数中，一定存在某个数m2（在代码中用res[t2]表示，t2表示需要乘以2的丑数的位置），在它之前的所有数乘以2都小于已有丑数，而m2×2的结果一定大于最大的丑数，同理，也存在这样的数m3，m5，我们只需要标记这三个数即可。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index <= 1:
            return index
        # Create an index size list
        nums = [1] * index
         # i2,i3,i5用于记录nums中第i个丑数是乘以2/乘以3/乘以5得到下一个丑数
        i2, i3, i5 = 0, 0, 0
        for i in range(1, index):
            # num = 2^(a)*3^(b)*5^(c)
            nums[i] = min(nums[i2]*2, nums[i3]*3, nums[i5]*5)
            if nums[i] == nums[i2]*2:
                i2 = i2 + 1
            if nums[i] == nums[i3]*3:
                i3 = i3 + 1
            if nums[i] == nums[i5]*5:
                i5 = i5 + 1
        return nums[-1]

19.旋转数组中最小数字

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

思路1（线性搜索）：根据题目要求分别考虑数组为空、数组只有一个元素和数组包含多个元素考虑，当数组为空返回0；当数组只有一个元素则直接返回该元素；若数组包含多个元素，则依次遍历数组找到最小元素即可。

思路2（二分查找）：例如A = {3,4,5,1,2}类的旋转数组可以分为左右两个子数组，因此可以采用二分查找的方法。

• 如果A[mid - 1] < A[mid] < A[mid + 1]，说明当前元素并不是最小的，设置right = mid - 1，left不变
• 如果 A[mid - 1] > A[mid] < A[mid + 1]，说明当前元素就是查找的元素
• 因为数组保持递增，因此不存在A[mid - 1] > A[mid] > A[mid + 1]的情况

思路3（寻找突变点）：题目给定的原数组本身就是递增，因此旋转后的数组存在一个突变点，而这个突变点就是数组中的最小元素。因此，题目求解就转换为了寻找突变点的过程。从索引0开始

• 如果，说明下一个元素就是数组中的最小值
• 如果遍历到头还没有满足条件的元素，那么说明第一个元素就是最小

# 直接将数组排序后输出首部元素
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        l = len(rotateArray)
        if l == 0:
            return 0
        rotateArray = sorted(rotateArray)
        return rotateArray[0]
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        l = len(rotateArray)
        if l == 0:
            return 0
        if l == 1:
            return rotateArray[-1]
        t = rotateArray[0]
        for i in range(1,l):
            n = rotateArray[i]
            if n < t :
                t = n
       return t
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray) - 1 
        if rotateArray[left] < rotateArray[right]:
            return rotateArray[left]
        while left < right: 
            mid = (left + right) // 2
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            elif rotateArray[mid] < rotateArray[right]:
                right = right - 1
            else:
                right = mid
        return rotateArray[left]
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        l = len(rotateArray)
        left = 0
        right = l - 1 
        if rotateArray[left] < rotateArray[right]:
            return rotateArray[left]
        for i in range(l):
            if rotateArray[i] > rotateArray[i + 1]:
                return rotateArray[i + 1]

20. 跳台阶

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

思路：f(1) = 1;f(2) = 2;f(3) = 3;f(4) = 5 ——> f(n) = f(n-1)+f(n-2)，典型的斐波那契数列问题

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

21.矩形覆盖

题目描述：我们可以用

思路：依然是斐波那契数列问题

class Solution:
    def rectCover(self, number):
        res = [0,1,2]
        while len(res) <= number:
            res.append(res[-1] + res[-2])
        return res[number]

22. 二进制中1的个数

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

思路：位运算

class Solution:
    def NumberOf1(self, n):
        # write code here
        # return sum([(n >>i & 1) for i in range(0,32)])
        count = 0
        for i in range(32):
            if n & 1 == 1:
                count += 1
            n = n >> 1
        return count

23.变态跳台阶

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

思路：每个台阶可以看作一块木板，让青蛙跳上去，n个台阶就有n块木板，最后一块木板是青蛙到达的位子， 必须存在，其他$ (n-1)

其实我们所要求的序列为：0,1,2,4,8,16,……所以除了第一位外，其他位的数都是前一位的数去乘以2所得到的积。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 0: return 0
        else:
            return 2**(number - 1)

24.斐波那契数列

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

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0:
            return 0
        if n == 1 or n == 2:
            return 1
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a+b
        return a

25.包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路：使用stack来构建栈，使用min_num来存放曾经出现过的最小的元素。

• 入栈时将元素添加到stack中，如果入栈的元素小于min_num[-1]，即当前最小的元素，则将其添加到min_num中
• 出栈时如果当前栈顶的元素等于当前最小元素，则需要从min_num中进行移除，然后再进行出栈
• 栈中最小的元素即min_num[-1]

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.min_num = [9999]
    def push(self, node):
        # write code here
        self.stack.append(node)
        if node < self.min_num[-1]:
            self.min_num.append(node)
    def pop(self):
        # write code here
        if self.stack == []:
            return None
        if self.top() == self.min_num[-1]:
            self.min_num.remove(self.top())
        return self.stack.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        if self.stack == []:
            return 0 
        else:
            return self.min_num[-1]

26. 顺时针打印矩阵

题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.

思路：先取矩阵的第一行，接着将剩下作为新矩阵进行一个逆时针90度的翻转，接着获取第一行，直到矩阵为空。需要注意的点pop() 越界，翻转矩阵的时候相当于将列数据变成行数据，可以一列一列获取最后注意顺序。

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        result=[]
        while(matrix):
            result+=matrix.pop(0)
            if not matrix or not matrix[0]:
                break            #if防止越界
            matrix=self.turn(matrix)
        return result
    def turn(self,matrix):
        nrow=len(matrix)
        ncol=len(matrix[0])
        newMatrix=[]
        for i in range(ncol):
            sb=[]
            for j in range(nrow):
                sb.append(matrix[j][i]) #取矩阵的每列第i列
            newMatrix.append(sb)
        newMatrix.reverse()#翻转
        return newMatrix

27.字符串的排列

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

思路：回溯法

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        # 所有的不重复字符
        if ss == '': return []
        res = []
        l = len(ss)
        def find(ss, path, index = 0):
            if index == l:
                res.append(''.join(path))
                return
            for i in range(len(ss)):
                # 字符串中可能存在重复字符
                if i > 0 and ss[i] == ss[i - 1]:
                    continue
                path.append(ss[i])
                find(ss[:i] + ss[i + 1:], path, index + 1)
                path.pop()
        ss = list(ss)
        find(ss, [], 0)
        return res

28.第一个只出现一次的字符位置

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

思路：首先找到字符串中出现过的字符，然后依次在字符串中进行查找直到找到第一个只出现一次的字符，返回它在字符串中的索引。

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        set_s = list(set(s))
        set_s.sort(key = s.index)
        for i in set_s:
            count = 0
            for id in range(len(s)):
                if i == s[id]:
                    count += 1
            if count > 1:continue
            else:return s.index(i)
        return -1

29. 数组中的逆序对

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

思路：

# 暴力索引法, 可以得到正确答案，算法复杂度高会超出时间
class Solution:
    def InversePairs(self, data):
        count = 0
        a = data.copy()
        a.sort()
        for i in range(len(a)):
            numbers = a[i:]
            for n in numbers:
                if data.index(n) < data.index(a[i]):
                    count += 1
        return count % 1000000007
# 归并排序辅助解决
# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        # 找逆序对的过程可以在归并排序加以判断解决
        count, result = self.merge_sort(data)
        return count % 1000000007
    def merge_sort(self, a_list):
        n = len(a_list)
        count = 0
        if n <= 1:
            return count, a_list
        # 拆分
        count_l, left = self.merge_sort(a_list[:n // 2])
        count_r, right = self.merge_sort(a_list[n // 2:])
        # 合并排序
        count_merge, merge = self.merge(left, right)
        count = count_l + count_r + count_merge
        return count, merge
    def merge(self, left, right):
        count = 0
        l = r = 0
        result = []
        while l < len(left) and r < len(right):
            if left[l] <= right[r]:
                result.append(left[l])
                l += 1
            else:
                result.append(right[r])
                r += 1
                # 当右边的元素被插入时，证明这个元素比左边的剩下的所有元素都小
                # 可以组成len(left)-l个逆序对
                count += len(left) - l
        result += left[l:] + right[r:]
        return count, result

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

题目描述：统计一个数字在排序数组中出现的次数

思路：首先看给定的数字是否在数组中存在，若不存在直接返回0；若存在则先找到它在数组中第一次出现的位置，因此数组是有序的，然后只需要看它后面有多少数字和它相等即可。

# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if k not in data:
            return 0

        d =Counter(data)
        return d[k]


# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if k not in data:
            return 0

        index = data.index(k)
        count = 0
        for i in range(index, len(data)):
            if k == data[i]:
                count += 1

        return count

# 更详细的考虑，即考虑数组是升序排列、降序排列还是元素都相等
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if k not in data:
            return 0
        elif data[0] == data[-1] == k:
            return len(data)

        index = data.index(k)
        count = 0
        if data[0] < data[-1]:
            for i in range(index, len(data)):
                if k == data[i]:
                    count += 1
            return count
        else:
            for i in range(0, index):
                if k == data[i]:
                    count += 1
            return count

31.数组中只出现过一次的数字

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

思路：首先看数组中有哪些数字，然后依次查找它们在数组中的个数，如果个数为1则保存，最后返回保存的结果即可。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        a = list(set(array))
        a.sort(key = array.index)

        r = []
        for i in a:
            count = 0
            for n in array:
                if i == n:
                    count += 1
            if count == 1:r.append(i)
            else:continue

        return r

# 法2：排序后依次取当前元素和周围元素进行比较
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if array == []:
            return None
        if len(array) == 1:
            return array

        array.sort()
        r = []
        for i in range(len(array)):
            if i == 0 and array[i] != array[i+1] or i == len(array)-1 and array[i] != array[i-1]:
                r.append(array[i])
            elif array[i - 1] != array[i] and array[i] != array[i + 1]:
                r.append(array[i])

        return r

32.和为S的连续正数序列

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

思路：设置start和end两个区间索引，start从0开始，end不断加1，如果当前区间元素和等于S则保存区间，更新start和end；如果区间和大于S则终止end自增，更新start和end；如果区间和小于S，end自增。

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        nums = [ _ for _ in range(1, tsum + 1 // 2 )]
        start = 0
        end = 1
        res = []

        while start <= len(nums) and end <= len(nums):
            if sum(nums[start:end]) == tsum:
                res.append(nums[start:end])
                start += 1
                end = start + 1
            elif sum(nums[start:end]) > tsum:
                start += 1
                end = start + 1
            else:
                end += 1

        return res

33. 求1+2+3+…+n

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

思路：递归调用

# -*- coding:utf-8 -*-
class Solution:
    def Sum_Solution(self, n):
        if n == 1:
            return 1
        return n + self.Sum_Solution(n-1)

34. 滑动窗口的最大值

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

思路：设置两个索引start和end表示滑动窗口，然后利用max取窗口内的最大值，不断滑动直到end到达结束位置为止。

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        start = 0
        end = size
        r = []
        if size == 0:
            return []

        while end <= len(num):
            r.append(max(num[start:end]))
            start += 1
            end = start + size
        return r

# 法2
# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        r = []
        if size == 0:
            return []

        while len(num) >= size:
            r.append(max(num[0:size]))
            num = num[1:]
        return r

35. 把数组排成最小的数

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

思路：将数组中的排列成一个最小（大）的数的基本思路是：首先将数组中的元素转换为字符串，然后看字符串拼接后的结果的大小关系。如3和32，转换成字符拼接后有两种结果：

• 1. 创建数组r存放排列后的结果，首先将原数组首元素放入，然后遍历数组中剩下的元素与中元素进行比较

     • 如果 ，将其插入到前面，更新；否则继续往后比较
     • 如果必到最后没有在中找到满足的要求的元素，则将其添加到后面
• 1. 利用python中内置list的排序函数，它需要定义比较规则，然后利用sort函数对字符串进行排序。

# 法1
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if numbers == []:
            return ""

        r = [numbers[0]]
        for i in numbers[1:]: 
            for id in range(len(r)):
                if int(str(i) + str(r[id])) < int(str(r[id]) + str(i)):
                    r.insert(r.index(r[id]), i)
                    break
                elif id == len(r) - 1:
                    r.append(i)

        return (int(''.join(str(x) for x in r)))


# 回溯法
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers: return ''
        res = []
        l = len(numbers)
        def find(numbers, path, index = 0):
            if index == l:
                t = path[:]
                res.append(''.join(t))
                return

            for i in range(len(numbers)):
                path.append(str(numbers[i]))
                find(numbers[:i] + numbers[i + 1:], path, index + 1)
                path.pop()

        find(numbers, [], 0)
        res = [''.join(i) for i in res]
        res.sort()
        return res[0]

36. 两个链表的第一个公共节点

题目描述：输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路：具有公共节点的链表如下所示：

因此，链表从后往前第一个不同的节点前的那个就是第一个公共节点。但链表从后往前无法遍历，因此可以将链表放入栈中，然后依次出栈并记录当前相同的节点。

• 如果下个节点不同，则输出当前节点为第一个公共节点
• 否则，继续出栈直到碰到第一个彼此不同的节点，输出第一个公共节点

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        def list2stack(L):
            r = []
            while L:
                r.append(L)
                L = L.next
            return r 

        # write code here
        if not pHead1 or not pHead2:
            return None
        stack1, stack2 = list2stack(pHead1), list2stack(pHead2)
        res = None
        while stack1 and stack2:
            p1, p2= stack1.pop(), stack2.pop()
            if p1 == p2:
                res = p1
            else:
                break

        return res

# 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        def list2stack(L):
            r = []
            while L:
                r.append(L)
                L = L.next
            return r 

        # write code here
        if not pHead1 or not pHead2:
            return None
        stack1, stack2 = list2stack(pHead1), list2stack(pHead2)
        res = None
        stack1.reverse()
        stack2.reverse()

        if len(stack1) < len(stack2):
            for i in range(len(stack1)):
                if stack1[i] == stack2[i]:
                    res = stack1[i]
                else:
                    break
        else:
            for i in range(len(stack2)):
                if stack1[i] == stack2[i]:
                    res = stack2[i]
                else: break

        return res

37. 左旋转字符串

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

思路：取前K位然后和第K位以后的元素，然后后者加前者做list的拼接即可。

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

38. 把字符串转换为整数

题目描述：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

• 输入一个字符串,包括数字字母符号,可以为空
• 如果是合法的数值表达则返回该数字，否则返回0

思路：按照题目的描述，合法的字符串只能包含数字和正负号。因此，如果字符串合法则需要考虑多种合法情况：

• 看字符串的长度，如果长度为1：

  • 如果为 + 或 - ，返回0
  • 如果为0，返回0

• 如果字符串长度大于1，首先须看字符串中是否包含正负号来决定整数的正负，然后依次取出数字，最后计算结果

• 另外需看结果是否溢出，32位最大的正数整数0x7FFFFFFF,最小的负数整数0x80000000

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        if s == '': return 0

        numbers = []
        flag = 1
        dict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
        for i in s:
            if i in dict.keys():
                numbers.append(dict[i])
            elif i == '+':
                continue
            elif i == '-':
                flag = -1
            else:
                return 0  # 不合法数字都置0

        if numbers == []:
            return 0

        n = 0
        boundry = (1<<31) - 1 if flag > 0 else 1<<31
        for i in numbers:
            n = n * 10 + i
            if n > boundry:
                return 0
            else:
                continue
        return flag * n

# 使用reduce函数
# -*- coding:utf-8 -*-
from functools import reduce
class Solution:
    def StrToInt(self, s):
        def fun(x, y):return x * 10 + y
        if s == None or len(s) < 1:
            return 0
        numStack = []
        sign = 1
        dict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
        for i in s:
            if i in dict.keys():
                numStack.append(dict[i])
            elif i == '+':
                continue
            elif i == '-':
                sign = -1
            else:
                return 0  # 不合法数字都置0

        ans = 0
        if len(numStack) == 0 or len(numStack) == 1 and numStack[0] == 0:
            return 0
        ans = reduce(fun, numStack)
        # 判断取值范围是否合法（牛客网测试必加）
        if sign == 1 and ans > 0x7FFFFFFF or sign == -1 and ans > 0x80000000:
            return 0
        else:
            return sign * ans

39. 表示数值的字符串

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

思路：不合法的情况：

• 小数点重复出现
• e或E后面不是-或数字
• E或E和小数点重复出现
• +和-相邻
• e或E有多个或只有一个但是最后一个字符

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        if s is None or len(s) == 0:
            return False

        # 是否有e
        hasE = False
        # 是否有小数
        isDecimal = False
        # 是否有+-符号
        hasSign = False

        for i in range(len(s)):
            # 如果有e,只能有一个e且不能是最后一个
            if s[i] == "e" or s[i] == "E":
                if hasE or i == len(s) - 1:
                    return False
                hasE = True
            # 小数点不能重复出现或和e共线
            elif s[i] == ".":
                if hasE or isDecimal:
                    return False
                isDecimal = True
            elif s[i] == "-" or s[i] == "+":
                # 重复出现符号时，必须跟在e后面
                if hasSign and s[i - 1] != "e" and s[i - 1] != "E":
                    return False
                # 重复出现符号时，必须跟在e后面
                if not hasSign and i > 0 and s[i - 1] != "e" and s[i - 1] != "E":
                    return False
                hasSign = True
            elif s[i] < "0" or s[i] > "9":
                return False
        return True

# 使用unicodedata.numeric()进行判断
# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        def is_number(s):
            try:
                float(s)
                return True
            except ValueError:
                pass

            try:
                import unicodedata
                unicodedata.numeric(s)
                return True
            except (TypeError, ValueError):
                pass

            return False

        return is_number(s)

40. 字符流中第一个不重复的字符

题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。如果当前字符流没有存在出现一次的字符，返回#字符。

思路：

• 用字典来存放字符流中字符和对应出现的次数，最后返回第一个值为1的键，否则返回 ‘#’。
• 利用list接收字符流的输入，然后使用set去重后依次查找set中元素在list的个数

# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.s=''
        self.dict1={}
    def FirstAppearingOnce(self):
        # write code here
        for i in self.s:
            if self.dict1[i]==1:
                return i
        return '#'

    def Insert(self, char):
        # write code here
        self.s = self.s + char
        # 更新字典
        if char in self.dict1:
            self.dict1[char] = self.dict1[char] + 1
        else:
            self.dict1[char] = 1

# 法2
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.str = []

    def FirstAppearingOnce(self):
        # write code here
        ss = list(set(self.str))
        ss.sort(key = self.str.index)

        for i in ss:
            if self.str.count(i) == 1:
                return i

        return '#'

    def Insert(self, char):
        # write code here
        self.str.append(char)

41. 树的子结构

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

思路1：对于给定的两棵二叉树来判断B是否是A的子结构，要充分考虑以下几种情形：

• 若A和B中有一棵为空则两者之间必不存在结构，返回False
• 若A和B均不为空，则要先在A中找到和B根节点相同的节点，然后判断它们的子节点是否相同，直到到达A或B的叶子节点

思路2： 首先通过先序遍历法获取A和B的序列，然后判断A的序列中是否包含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
        def hasEqual(root1, root2):
            #　若小树只有相同的根节点，则返回True
            if root2 == None:
                return True
            #　如果大树只有根节点，而小树还有子节点，返回False
            if root1 == None:
                return False

            # 若根节点相同
            if root1.val ==root2.val:
                # 如果小树不存在左子树，表示已判断部分相同，子结构成立，返回True
                if root2.left == None:
                    leftEqual = True
                else:
                    # 往下递归判断
                    leftEqual = hasEqual(root1.left, root2.left)
                # 如果小树右节点为空，判断终止，已判断部分相同，子结构成立，返回True
                if root2.right == None:
                    rightEqual = True
                else:
                    # 往下递归判断
                    rightEqual = hasEqual(root1.right, root2.right)

                # 如果都为True说明子结构成立
                return leftEqual and rightEqual

            # 如果当前节点为根节点都不同，直接返回False
            return False

        # 如果有一棵为空直接返回False     
        if pRoot1 == None or pRoot2 == None:
            return False

        # 如果A和Ｂ的根节点就相同，递归判断子节点
        if pRoot1.val == pRoot2.val:
            ret = hasEqual(pRoot1, pRoot2)
            if ret:
                return True
        # 在A的左子树找和B的根节点相同的子节点再进行判断  
        ret = self.HasSubtree(pRoot1.left, pRoot2)
        if ret:
            return True

        # 在A的右子树找和B的根节点相同的子节点再进行判断
        ret = self.HasSubtree(pRoot1.right, pRoot2)
        return ret

### 先序遍历法
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.res1 = []
        self.res2 = []

    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        def preOrder(flag, root):
            if root == None:
                return None
            if flag == 1:
                self.res1.append(root.val)
            else:
                self.res2.append(root.val)
            preOrder(flag, root.left)
            preOrder(flag, root.right)

        if pRoot1 == None or pRoot2 == None:
            return False

        preOrder(1, pRoot1)
        preOrder(2, pRoot2)

        for i in range(len(self.res1)):
            if self.res1[i] == self.res2[0] and self.res1[i:i + len(self.res2)] == self.res2:
                return True

        return False

42. 二叉树的镜像

题目描述：操作给定的二叉树，将其变换为原二叉树的镜像。

思路：所谓镜像结构，即二叉树的左右子树进行互换，直到到达叶节点为止。因为不断的已左孩子节点和右孩子节点当作“根节点”进行子树互换，所以可采用递归。

# -*- coding:utf-8 -*-
# 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 root == None:
            return None

        # 互换子树，直到子树为空
        root.left, root.right = root.right, root.left
        self.Mirror(root.left)
        self.Mirror(root.right)

43. 从上往下打印二叉树

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

思路：即二叉树的层序遍历，利用队列先进先出的性质依次取层中从左往右的元素。

# -*- 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 root == None:
            return []
        queue = [root]
        ret = []
        while queue:
            node = queue[0]
            ret.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            del queue[0]
        return ret

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

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

思路：递归判断当前的树是否存在路径使得累加值 + number == expectNumber，如果存在加入到路径集中。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        if not root: return []
        if root.val > expectNumber: return []
        # 保存所有可能的路径
        res = []
        def find(path, root, target):
            path.append(root)
            target += root.val

            # 判断是否到达叶子节点
            isLeaf = None
            if not root.left and not root.right:
                isLeaf = True

            if target == expectNumber and isLeaf:
                res.append([i.val for i in path])

            if target < expectNumber:
                if root.left:
                    find(path, root.left, target)
                if root.right:
                    find(path, root.right, target)

            path.pop()

        find([], root, 0)

        return res

45. 二叉树的深度

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

思路：从根节点开始深度优先遍历所有可能的路经，使用全局变量maxdepth来保存最大深度。

class Solution:
    def TreeDepth(self, pRoot):
    # write code here
        global maxdepth
        maxdepth=0

        def DfsTree(root,depth = 0):
            global maxdepth

            if root:
                depth+=1

            isLeaf = None
            if root.left == None and root.right == None:
                isLeaf = True

            if root.left:
                DfsTree(root.left, depth)
            if root.right:
                DfsTree(root.right, depth)

            if isLeaf and depth >  maxdepth:
                maxdepth = depth

        if pRoot == None:
            return 0
        else:
            DfsTree(pRoot)

        return maxdepth

# 法2
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot == None:
            return 0

        lDepth = self.TreeDepth(pRoot.left)
        rDepth = self.TreeDepth(pRoot.right)

        return max(lDepth, rDepth) + 1

46. 平衡二叉树

题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：平衡二叉树指二叉树的每个节点的左右子树的高度差的绝对值不超过1。那么我们从根节点开始依次判断节点的左右子树的深度，然后看差值是否超过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
        def depth(root):
            if root is None:
                return 0
            return max(depth(root.left), depth(root.right)) + 1

        def isBalanced(root):
            if root is None:
                return True

            return isBalanced(root.left) and isBalanced(root.right) and abs(depth(root.left) - depth(root.right)) <= 1

        if pRoot is None:
            return True

        return isBalanced(pRoot)

# 法2
# -*- 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
        def TreeDepth( pRoot):
        # write code here
            global maxdepth
            maxdepth=0

            def DfsTree(root,depth = 0):
                global maxdepth

                if root:
                    depth+=1

                isLeaf = None
                if root.left == None and root.right == None:
                    isLeaf = True

                if root.left:
                    DfsTree(root.left, depth)
                if root.right:
                    DfsTree(root.right, depth)

                if isLeaf and depth >  maxdepth:
                    maxdepth = depth

            if pRoot == None:
                return 0
            else:
                DfsTree(pRoot)

            return maxdepth

        def isBalanced(root):
            if root is None:
                return True

            return isBalanced(root.left) and isBalanced(root.right) and abs(TreeDepth(root.left) - TreeDepth(root.right)) <= 1

        if pRoot is None:
            return True

        return isBalanced(pRoot)

47. 栈的压入、弹出序列

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

思路：按pushV的顺序将元素压入stack中，然后判断此时入栈的元素是否和popV的栈顶元素相同：

• 如果相同，则将stack中元素弹出再接着比较，直到stack为空
• 如果不同，则继续入栈

class Solution:
    def IsPopOrder(self, pushV, popV):

        if pushV == [] or len(pushV ) != len(popV):
            return None

        stack = []
        index = 0
        for item in pushV:
            stack.append(item)
            while stack and stack[-1] == popV[index]:
                stack.pop()
                index += 1

        return True if stack == [] else False

48. 删除链表中重复的节点

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

思路：构建一个新节点连接到给定链表，设置指针head值向新节点，那么p->next == pHead，即给定链表的表头，用于返回结果。设置指针p指向可能重复节点的前一个节点，指针cur寻找可能重复的节点。从头结点开始往后走，当遇到cur和cur->指向的节点值相同时，执行 p = cut->next，cur = cur->next来删除 已存在的重复节点，直到cur- >next = None表示走到尾了终止算法。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        head = ListNode(-1)
        p = head
        p.next = pHead
        cur = pHead
        while cur and cur.next:
            if cur.val != cur.next.val:
                p = p.next
                cur = cur.next
            else:
                val = cur.val
                while cur and cur.val == val:
                    cur = cur.next
                p.next = cur
        return head.next

49. 二叉树的下一个节点

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

思路：二叉树的中序遍历顺序为左 - 根 - 右，那么需要首先判断它是哪一种：

• 如果它存在右子树，说明它是子树的夫结点，下一个节点在其右子树中。如果右子树存在左孩子结点，那么下一个就是左孩子结点，否则说明它就是叶子结点，直接返回

• 如果它不存在右子树，说明当前结点为叶子节点：

  • 如果当前结点为右叶子，那么下一个就是它的父结点，即它next域指向的结点
  • 如果它的父节点有左叶子，说明下一个节点就是父节点

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        if not pNode: return None
        # 如果右子树存在，说明当前节点为子树根结点，下一个结点在右子树
        if pNode.right:
            # 更新结点
            pNode = pNode.right
            # 中序遍历：左-根-右
            # 如果左孩子结点存在则返回左孩子结点
            while pNode.left:
                pNode = pNode.left
            # 否则说明当前结点即叶节点，直接返回
            return pNode
        # 如果右子树不存在，那么当前结点为叶节点
        else:
            # 如果next域有值，不管它是左孩子还是右孩子，先找它的父节点
            while pNode.next:
                # 如果父节点的左孩子存在，那么说明它是右孩子结点，下一个节点即父节点
                if pNode == pNode.next.left:
                    return pNode.next
                # 否则说明它是左孩子结点，下一个结点即父节点
                pNode = pNode.next
        return None

50. 对称的二叉树

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

思路：从根节点往下依次进行判断，如果到达子树的叶子节点，则判断左叶子和右叶子是否相同；否则将继续判断左孩子节点的左子树和右孩子节点的右子树是否相同，以及左孩子节点的右子树和右孩子节点的左子树是否相同。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    #判断对称二叉树
    def isSymmetrical(self, pRoot):
        # write code here
        def travel(root1, root2):
            if root1 == root2:
                return True
            elif root1 and root2 and root1.val == root2.val:
                return travel(root1.left, root2.right) and travel(root1.right, root2.left)
            else:
                return False

        if not pRoot:
            return True

        return travel(pRoot.left, pRoot.right)

51. 把二叉树打印多行

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

思路：层序遍历

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot: return []

        queue = [pRoot]
        res = []
        while queue:
            r = []
            nextLayers = []
            for node in queue:
                r.append(node.val)
                if node.left:
                    nextLayers.append(node.left)
                if node.right:
                    nextLayers.append(node.right)
            res.append(r)
            del queue[0]
            queue = nextLayers

        return res

52. 正则表达式的匹配

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

class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        if len(s) == 0 and len(pattern) == 0:
            return True
        if len(s) > 0 and len(pattern) == 0:
            return False

        # 如果模式第二个字符是*
        if len(pattern) > 1 and pattern[1] == '*':
            if len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.'):
                # 如果第一个字符匹配，三种可能1、字符串移1位；2、字符串移1位，模式移2位；3、模式后移两位(这里将2、3合并书写)
                return self.match(s, pattern[2:]) or self.match(s[1:], pattern)
            else:
                # 如果第一个字符不匹配，模式往后移2位，相当于忽略x*
                return self.match(s, pattern[2:])
        # 如果模式第二个字符不是*
        if len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.'):
            return self.match(s[1:], pattern[1:])
        else:
            return False

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

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

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

思路：后序遍历：左-右-根，后序遍历序列的最后一个是根节点，前面的分别是左子树节点序列和右子树节点序列，从头依次判断前半部分元素是否都小于突变后部分的元素，突变后部分的元素是否都大于根节点。

# 后序遍历：左-右-根
# 后序遍历序列的最后一个是根节点，前面的分别是左子树节点序列和右子树节点序列
# 从头依次判断前半部分元素是否都小于突变后部分的元素，突变后部分的元素是否都大于根节点
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if sequence is None or len(sequence) == 0:
            return True

        # 首先找到根节点
        root = sequence[-1]
        n = len(sequence)
        # 左子树结点值都小于根节点
        i = 0
        for i in range(n):
            if sequence[i] > root:
                break
        # 右子树节点值都大于根节点
        for j in range(i, n - 1):
            if sequence[j] < root:
                return False
        # 判断左子树是不是二叉搜索树
        left = True
        if i > 0:
            left = self.VerifySquenceOfBST(sequence[:i])
        right = True
        if i < n - 1:
            right = self.VerifySquenceOfBST(sequence[i:-1])

        return left and right

54. 复杂链表的复制

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

思路：单纯单链表的复制容易，根据题目描述主要需要考虑每个节点的随机指针。

• 暴力求解：先遍历列表同时记录val和random域的值，分别存放在val_list和random_list中，然后首先使用val_list中的元素依次新建结点并设置next构成基本链。然后构建两个指针p和r，其中p指向当前结点，r用于搜索random指向的结点。接着从新链第一个节点开始，看它在random_list中是否有值，如果有，从头遍历链表，直到找到val为指定值的结点，将当前结点的random指向它，同时将p指向下一个位置，r回到头结点。不断遍历，直到为止。但这样的算法复杂度为#card=math&code=O%28n%5E2%29)，在OJ平台上会发生时间超出的错误
  

• 聪明的求法：先复制节点构成新链然后再断链得到原始链表的复制，具体的过程如下所示：
  

    假设初始链表如（1）所示，链表中包含1、2、3、4四个结点，结点的random指向为：

1 .random = 3
2 .random = 2 
3 .random = 4 
4 .random = 2

    首先在复制每个结点将其链接在它后面构成如（2）所示的新链：

cur = pHead
# 始终保证cur指向原始链表中的结点
while cur:
    node = RandomListNode(cur.label)
    # 在原始链中插入
    node.next = cur.next
    cur.next = node
    cur = node.next

    得到插入复制结点后的新链表后，我们还需要设置新节点的random，使其和它和原始结点一致：

cur = pHead
while cur:
    # 可能某些结点的random为None，因此先进行判断
    if cur.random:
        cur.next.random = cur.random.next

     # # 始终保证cur指向原始链表中的结点
     cur = cur.next.next

    经过上述步骤，新链表的中每个结点的next和random都指向了正确的结点，但这样的链表不是我们想要的。由于不能直接返回给定链表的头结点，我们需要从新链表中将复制的节点抽出来，同时保证抽出的结点的next和random指向和最开始的链表一致。

cur = pHead
# 指向复制结点中的第一个结点,只用于输出
newHead = pHead.next
# 指向复制结点中的第一个结点,用于断链
new_cur = pHead.next

while cur:
    # 断开原链表中的结点和复制结点的next指向，将next指向原链表中的对应结点，即next.next
    cur.next = cur.next.next
    # 看是否遍历完了所有的结点
    if new_cur.next:
        # 类似上一步
        new_cur.next = new_cur.next.next
        # 由于此时new_cur指向的节点的next已经发生了改变，因此只需要将next后移即可
        new_cur = new_cur.next

    # 类似new_cur的上一步操作
    cur = cur.next

    最终newHead作为头结点的链表就是复制后的链表，即我们想要的结果。由于在复制完结点后所做的只是结点的next和random指向的操作，因此时间复杂度为

#card=math&code=O%28n%29)

# 复杂度O(n^2)，时间超过
# -*- 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 pHead == None:
            return None

        cur = pHead.next
        list_ele = []
        random_ele = []
        while cur:
            list_ele.append(cur.label)
            if cur.random:
                random_ele.append(cur.random.label)
            else:
                random_ele.append(None)
            cur = cur.next

        newHead = RandomListNode(-1)
        p = newHead
        for i in list_ele:
            node = RandomListNode(i)
            p.next = node
            p = p.next

        pp = newHead.next
        r = newHead.next
        index = 0
        while pp:
            randomEle = random_ele[index]
            index += 1
            if randomEle != None:
                while r:
                    if r.label == randomEle:
                        pp.random = r
                        r = newHead.next
                    else:
                        r = r.next

            pp = pp.next
        return newHead 

# 正确做法
# -*- 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 pHead == None:
            return None

        cur = pHead
        while cur:
            node = RandomListNode(cur.label)
            node.next = cur.next
            cur.next = node
            cur = node.next

        cur = pHead
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        cur = pHead
        newHead = pHead.next
        new_cur = pHead.next

        while cur:
            cur.next = cur.next.next
            if new_cur.next:
                new_cur.next = new_cur.next.next
                new_cur = new_cur.next

            cur = cur.next

        return newHead

## 投机做法
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
import copy
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        ret = copy.deepcopy(pHead)

        return ret

55. 二叉搜索树与双向链表

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

思路：二叉搜索树可分为根节点、左子树和右子树，在把左、右子树转换成排序的双向链表后再和根节点链接起来，整棵搜索二叉树就转换成了排序的双向链表。因此这个过程可以分为两个阶段：

• 将左、右子树转换为双向排序链表
• 将左、右子树的转换链表和其对应的根节点链接

整个过程通过可以递归进行。

• 法2：从上图转换后得到得双向链表可以看出，链表中元素得排列就是二叉树中序遍历后得结果。因此，当得到中序遍历后的结果，我们只需要做的是从第一个节点（）开始，将第个结点作为第个结点的left，将第i个结点作为第个结点的right，不断操作直到最后。
  

• 剑指offer 二叉搜索树与双向链表 python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        def find_right(node):
            while node.right:
                node = node.right
            return node
        # write code here
        if pRootOfTree == None:
            return None

        # 左、右子树
        leftNode = self.Convert(pRootOfTree.left)
        rightNode = self.Convert(pRootOfTree.right)

        # 记录最终输出链表的头结点，只为输出
        retNode = leftNode

        # 处理左子树
        if leftNode:
            # 找到左子树的双向链表的最后一个结点
            leftNode = find_right(leftNode)
        else:
            retNode = pRootOfTree

        # 将根节点指向左子树链表的最后一个结点和右子树链表的第一个结点
        pRootOfTree.left = leftNode
        pRootOfTree.right = rightNode

        # 另一个方向的链接，将左子树链表的最后一个节点指向根节点，将右子树链表的第一个节点指向根节点
        if leftNode != None:
            leftNode.right = pRootOfTree
        if rightNode != None:
            rightNode.left = pRootOfTree

        return retNode

# 法2
class Solution:
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return
        self.mid = []
        self.middle(pRootOfTree)
        for i in range(len(self.mid)-1):
            self.mid[i].right = self.mid[i+1]
            self.mid[i+1].left = self.mid[i]

        return self.mid[0]

    def middle(self, root):
        if not root:
            return
        self.middle(root.left)
        self.mid.append(root)
        self.middle(root.right)

56. 按之字形顺序打印二叉树

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

思路：做法和第52题差不多，不同之处在于不同的层打印顺序不同：

• 偶数层，从左往后打印
• 奇数层，从右往左打印

因此，在保存每层结果时，设置index来判断当前层是偶数层还是奇数层，如果是偶数层直接保存；否则使用list.reverse()反转结果后再保存即可。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot == None:
            return []

        res = []
        cur = [pRoot]
        index = 0
        while cur:
            curList = []
            nextLayer = []
            for node in cur:
                curList.append(node.val)
                if node.left:
                    nextLayer.append(node.left)
                if node.right:
                    nextLayer.append(node.right)
            # 保存该层的结果
            if index % 2 == 0:
                res.append(curList)  
            else:
                curList.reverse()
                res.append(curList)
            # 打印下面的层
            index += 1
            cur = nextLayer

        return res

57. 链表中环的入口结点

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

思路：所谓链表环是指在链表中存在节点的next指向它前面的节点。使用快慢指针，如果相遇了，那么把一个指针调整到头部，重新开始再相遇即可。

# 逐个寻找，时间复杂度高
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead == None:
            return None

        p = pHead.next
        cur = p
        flag = None
        while p:
            while cur:
                if cur.next == p:
                    flag = True
                    break
                else:
                    cur = cur.next

            if flag:
                return p
            else:
                p = p.next
                cur = p

        return None

# 快慢指针
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        slow, fast = pHead, pHead

        # 判断是否存在环
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break

        if not fast or not fast.next:
            return None

        fast = pHead
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast
# 空间换时间
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        if pHead == None:
            return None

        r = []
        cur = pHead
        while cur:
            if cur.next in r:
                return cur.next
            else:
                r.append(cur)
                cur = cur.next

        return None

58. 反转单词顺序列

题目描述：牛客最近来了一个新员工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 == None or len(s) == 0:
            return s

        ss = s.split(' ')
        ss.reverse()
        return " ".join(ss)

59. 扑克牌顺子

题目描述：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有几个，因为0小于任何整数，所以可以先排序，然后看除0之外的数字。依次比较当前数字和下一个数字，：

• 如果相等，必然构不成顺子，直接返回False
• 如果下一个数字比当前数字大1，则继续往后

• 如果下一个数字比当前数字大的超过1，则继续两者的差值，表示需要多少个0来填补

  • 如果差值减1大于当前0的个数，则直接返回False
  • 如果差值减1小于当前0的个数，则更新0的个数继续往后

# 先统计后判断
# -*- coding:utf-8 -*-
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if numbers == []:
            return False

        zeroNum = numbers.count(0)
        numbers.sort()
        numLack = 0
        for i in range(zeroNum, len(numbers) -1):
            if numbers[i] == numbers[i + 1]:
                return False
            if numbers[i] + 1 == numbers[i + 1]:
                continue
            else:
                numLack += (numbers[i + 1] - numbers[i] - 1)
        if numLack <= zeroNum:
            return True
        else:
            return False

# 法2：实时判断
# -*- coding:utf-8 -*-
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if numbers == []:
            return False

        zeroNum = numbers.count(0)
        numbers.sort()

        for i in range(zeroNum, len(numbers) -1):
            if numbers[i] == numbers[i + 1]:
                return False

            if numbers[i] + 1 == numbers[i + 1]:
                continue
            elif numbers[i + 1] - numbers[i]  - 1 > zeroNum:
                return False
            else:
                zeroNum = zeroNum - (numbers[i + 1] - numbers[i] - 1)

        return True

60. 序列化二叉树

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

• 二叉树的序列化：指把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

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

思路：

• 序列化：先序遍历，字符串之间用’,’间隔

• 反序列前序遍历“根左右”的顺序，根节点位于其左右子节点的前面，即非空（#）的第一个节点是某子树的根节点，左右子节点在该根节点后，以空节点#为分隔符。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 先序遍历，字符串之间用','间隔
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        return str(root.val) +',' + self.Serialize(root.left) +','+ self.Serialize(root.right)

    def Deserialize(self, s):
        list = s.split(',')
        return self.deserializeTree(list)

    def deserializeTree(self, list):
        if len(list)<=0:
            return None
        val = list.pop(0)
        root = None
        if val != '#':
            root = TreeNode(int(val))
            root.left = self.deserializeTree(list)
            root.right = self.deserializeTree(list)
        return root

61. 二叉搜索树的第K个节点

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

思路：二叉树的中序遍历结果自然就是升序序列，因此只需要先做中序遍历并存储遍历结果，然后输出第K个结果即可。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        def inOrder(root):
            if root == None:
                return None
            inOrder(root.left)
            res.append(root)
            inOrder(root.right)

        if pRoot == None or k <= 0:
            return None

        global res
        res = []
        inOrder(pRoot)

        if len(res) < k:
            return None
        else:
            return res[k - 1]

62. 矩阵中的路径

题目描述：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 $\begin{bmatrix} a & b & c &e \ s & f & c & s \ a & d & e& e\ \end{bmatrix}\quad $矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

思路：回溯法，

class Solution:
    """ 在矩阵中寻找是否存在路径等于给定的字符串

    Returns:
        matrix -- 寻找路径的字符矩阵
        rows   -- 矩阵的行数
        cols   -- 矩阵的列数
        path   -- 待寻找的路径

    """
    def hasPath(self, matrix, rows, cols, path):
        # 为了保证当前路径上已经被访问过的结点不再重复访问
        # 设置 vis 来标记某个元素是否被访问过，容量和 matrix 相同
        vis = [True] * rows * cols

        for i in range(rows):
            for j in range(cols):
                # 从 matrix[i][j] 开始寻找是否存在路径
                if self.hasPathAtAStartPoint(matrix, rows, cols, i, j, path, vis):
                    # 如果存在则返回True
                    return True
        # 如果从所有位置出发都不能找到，则返回False
        return False

    # 从某个点(x, y)出发寻找路径
    def hasPathAtAStartPoint(self, matrix, rows, cols, i, j, path, vis):
        # index 表示当前访问元素的位置
        index = i * cols + j

        # 递归的终止条件
        # 如果路径存在则返回True
        if not path:
            return True

        # 如果访问越出边界、当前位置元素不是path的起始元素或者当前位置已被访问过，直接返回False
        if i < 0 or i >= rows or j < 0 or j >= cols or matrix[index]!=path[0] or vis[index]== False:
            return False

        # 如果没有找到则将当前位置重新置为False
        vis[index] = False
        # 递归条件,如果以(0, 0)作为原点
        # 向上走: i - 1
        # 向下走: i + 1
        # 向前走: j + 1
        # 向后走: j _ 1
        if(self.hasPathAtAStartPoint(matrix,rows,cols,i+1,j,path[1:],vis) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i-1,j,path[1:],vis) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i,j-1,path[1:],vis) or
               self.hasPathAtAStartPoint(matrix,rows,cols,i,j+1,path[1:],vis)):
            return True
        vis[index] = True

        return False

63. 机器人的运动范围

题目描述：地上有一个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 judge(self, threshold, i, j):
        # sum(map(int, str(i) + str(j)))这一句简直精髓! 直接得到坐标位置的 位和! i,j是超过1位的数也可以完美解决!
        if sum(map(int, str(i) + str(j))) <= threshold:
            return True
        else:
            return False

    def findgrid(self, threshold, rows, cols, matrix, i, j):
        count = 0
        if i<rows and j<cols and i>=0 and j>=0 and self.judge(threshold, i, j) and matrix[i][j] == 0: # matrix[i][j]==0表示没走过这一格
            matrix[i][j] = 1  # 表示已经走过了
            count = 1 + self.findgrid(threshold, rows, cols, matrix, i, j+1) \
            + self.findgrid(threshold, rows, cols, matrix, i, j-1) \
            + self.findgrid(threshold, rows, cols, matrix, i+1, j) \
            + self.findgrid(threshold, rows, cols, matrix, i-1, j)
        return count

    def movingCount(self, threshold, rows, cols):
        matrix = [[0 for i in range(cols)] for j in range(rows)]
        count = self.findgrid(threshold, rows, cols, matrix, 0, 0)
        print(matrix)
        return count

# test
s = Solution()
count = s.movingCount(9, 12, 12)
print count

64. 剪绳子

题目描述：给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路：按照从下而上的顺序计算，先得到f(2),f(3)，再计算f(4),f(5), %3Dmax(f(i)%20%5Ctimes%20f(n-i))%2C0%3Ci%3Cn#card=math&code=f%28n%29%3Dmax%28f%28i%29%20%5Ctimes%20f%28n-i%29%29%2C0%3Ci%3Cn)

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number == 1:return 1
        if number == 2:return 1
        if number == 3:return 2
        dp = [1]
        for i in range(2,number+1):
            maxs = i
            for j in range(1,i-1):
                tmp = dp[i-j-1]*j
                if tmp>maxs:
                    maxs = tmp
            dp.append(maxs)
        return dp[-1]

65.和为S的两个数字

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

思路：先找到和为S的两个数，然后依次遍历和为S的列表中中的元素，并设置flag标记当前乘积最小的两个数，最后返回flag。

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        res = []
        for i in range(len(array)):
            for n in array[i + 1:]:
                if array[i] + n == tsum:
                    res.append([array[i], n])

        t = 9999999
        flag = []
        for i in res:
            number = i[0] * i[1]
            if number < t:
                t = number
                flag = i 

        return flag

# 指针夹逼法
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if not array :
            return []
        first = 0
        lenth = len(array) - 1
        last = lenth
        while last > first:
            if array[first] + array[last] > tsum:
                last -= 1
            elif array[first] + array[last] < tsum:
                first += 1
            elif array[first] + array[last] == tsum:
                return [array[first],array[last]]
        return []

66.不用加减乘除做加法

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

思路：

• 相加各位的值，不算进位，二进制每位相加就相当于各位做异或操作，即 a ^ b ；
• 计算进位值，相当于各位做与操作，再向左移一位,，即 (a & b) >> 1。
• 重复上述两步， 各位相加 ，计算进位值。进位值为0，跳出循环

# -*- coding:utf-8 -*-
class Solution: 
    def Add(self, num1, num2):
        # write code here
        while num2 != 0:
            sums = num1 ^ num2
            num2 = (num1&num2)<<1 # 进位
            num1 = sums & 0xFFFFFFFF # 考虑负数

        return num1 if num1<=0x7FFFFFFF else ~(num1^0xFFFFFFFF)

67. 孩子们的游戏

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

如果没有小朋友，请返回-1

思路：

# -*- coding:utf-8 -*-
class Solution:

    def LastRemaining_Solution(self, n, m):
        # write code here
        if n == 0:
            return -1
        s = 0
        for i in range(2, n+1):
            s = (s+m) % i
        return s