剑指 offer -- 刷题记录

      任谁都躲不过找工作的问题，好希望能多准备一些时间，奈何时间不等人，每天刷几道题，并且记录下来吧：

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

def replaceSpace(s):
    # write code here
    num_space = 0
    new_s = ''
    for i in range(len(s)):
        if i == ' ':
            num_space += 1
    for i in range(len(s)):
        if s[i] == ' ':
            new_s = new_s + '%20'
        else:
            new_s = new_s + s[i]
    return new_s

a = ' ii oob  '
replaceSpace(a)

    开辟了另外的空间，空间复杂度有点高，但看起来思路很简单。还有一种做法是首先确定整个字符串的长度，然后不断的插入，并将后边的字符串向后推。

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

class ListNode:
    def __init__(self, val=None):
        self.val = val
        self.next = None
        
def printListFromTailToHead(listNode):
    result = []
    head = listNode
    while head:
        result.insert(0,head.val)
        head = head.next
    return result
e1 = ListNode(1)
e2 = ListNode(2)
e3 = ListNode(3)
e4 = ListNode(5)
e1.next = e2
e2.next = e3
e3.next = e4
print(e1.next)
printListFromTailToHead(e1)

     首先，我们的定义链表节点类，节点内只有两个信息，一个是该节点的值，另外一个是节点的下一个节点。

     开辟一个新空间就一个列表，在这个列表的列表头 index = 0 处，不断的插入链表的值即可

三、 重建二叉树：

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

利用前序遍历和中序遍历之间的关系，使用递归的方式求解：

# 重建二叉树
# 利用 二叉树的前序遍历 中序遍历 重建二叉树
# 前序遍历的顺序为先根节点再左再右  中序遍历的顺序为先左节点再中再右
# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        elif len(pre) == 1:
            return TreeNode(pre[0])
        else:
            root = TreeNode(pre[0])
            position = tin.index(pre[0])
            root.left = self.reConstructBinaryTree(pre[1:position+1], tin[:position])
            root.right = self.reConstructBinaryTree(pre[position+1:], tin[position+1:])
        return root

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

# 用两个栈 实现一个队列
# 栈的特性是先入后出 队列的特性是先入先出
# 所以需要用两个栈 其中一个负责压栈设为栈1 另外一个负责弹栈设为栈2
# 当压栈时,将元素压入栈1, 当弹栈时 如果栈2为空,就将栈1的内容弹入栈2 , 此时队列的头在栈顶, 将其弹出即可
# 当栈2不为空时,则先弹出栈2的内容,直到其为空

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if len(self.stack2) == 0:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

五、 旋转数组

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

     为了降低时间复杂度，这里一定要使用旋转数组的性质，旋转数组有两个分离的数组构成，而且后边的小于、等于前边的。所以这里的方法就是，二分法，不断将数组二分，如果中位点大于左边的点，就将中位点设为左，否则设为右，递归的将问题分解成小问题，边界条件是  right - left ==1。

# 找旋转数组 最小值
# 为了降低时间复杂度 需要利用旋转数组的性质 
def minNumberInRotateArray(rotateArray):
    # write code here
    if len(rotateArray) == 0:
        return 0
    left = 0
    mid = 0
    right = len(rotateArray) - 1
    while rotateArray[left] >= rotateArray[right]:
        if (right-left) == 1:
            mid = right
            break
        if rotateArray[left] == rotateArray[mid] and rotateArray[mid] == rotateArray[right]:
            return minInside(rotateArray,left ,right)
        if rotateArray[left] >= rotateArray[right]:
            mid = (left + right) // 2
            if rotateArray[mid] >= rotateArray[left]:
                left = mid
            else:
                right = mid                
    return rotateArray[mid]

def minInside(array,left,right):
    result = array[left]
    for i in range(left,right+1):
        if array[i] < result:
            result = array[i]
    return result

a = [1,0,1,1,1]
b = minNumberInRotateArray(a)
print(b)