现在才开始刷题，似乎有点晚了，但是只要做了，永远都不晚！
1、二维数组查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：从左下角元素往上查找，右边元素是比这个元素大，上边是的元素比这个元素小。于是，target比这个元素小就往上找，比这个元素大就往右找。如果出了边界，则说明二维数组中不存在target元素。
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
rows = len(array) - 1
cols= len(array[0]) - 1
i = rows
j = 0
while j<=cols and i>=0:
if target<array[i][j]:
i -= 1
elif target>array[i][j]:
j += 1
else:
return True
return False
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target,array):
if array == [[]]:
return False
nRow = len(array)
nCol = len(array[0])
if target < array[0][0] or target > array[nRow-1][nCol-1]:
return False
else:
for i in range(nRow):
for j in range(nCol):
if target == array[i][j]:
return True
else:
return False
a = Solution()
a.Find(7,[[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]])
2、替换空格
请实现一个函数，将一个字符串中的空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。
思路：从前向后记录‘ ’数目，从后向前替换‘ ’。
class Solution {
public:
void replaceSpace(char *str,int length) {
int count=0;
for(int i=0;i<length;i++){
if(str[i]==' ')
count++;
}
for(int i=length-1;i>=0;i--){
if(str[i]!=' '){
str[i+2*count]=str[i];
}
else{
count--;
str[i+2*count]='%';
str[i+2*count+1]='2';
str[i+2*count+2]='0';
}
}
}
};
其实，replace()一句话就可以搞定啊( return s.replace(' ',' '))，但是这样怎么能体现我们的逆向思维以及对字符串的掌握能力呢？所以，必须要展示我们的分析能力嘛。
3、从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
思路：
可以使用栈或者递归的方式实现。
# -*- 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
out = []
if listNode is None:
return out
while listNode.next is not None:
out.append(listNode.val)
listNode = listNode.next
out.append(listNode.val)
out.reverse()
return out
4、重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：采用递归实现，需要判断前序遍历和中序遍历中左子树和右子树的结点的个数和位置。pre[0]为根节点。
# -*- 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:
flag = TreeNode(pre[0])
flag.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
flag.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:] )
return flag
5、用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：
栈A用来作入队列栈B用来出队列，当栈B为空时，栈A全部出栈到栈B,栈B再出栈（即出队列）
# -*- 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 self.stack2==[]:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
return self.stack2.pop()
6、旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：（
思路不代表代码的实现
）
采用二分法解答这个问题，
mid = low + (high - low)/2
需要考虑三种情况：
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ，
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid
注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid
一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1，就会产生错误， 因此high = mid
但情形(1)中low = mid + 1就不会错误
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
ret = rotateArray[0]
if len(rotateArray) == 1:
return ret
for i in range(1,len(rotateArray)):
now = rotateArray[i]
if now < ret:
ret = now
break
return ret
