1.在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路（python）： 把二维数组看成是n个有序的一维数组，对一维数组进行二分查找。
class Solution:
# array 二维列表
def Find(self, target, array):
def binsearch(data, x):
left = 0
right = len(data)-1
while left<=right:
middle = (left+right)//2
if data[middle] == x:
return True
elif data[middle] < x:
left = middle+1
else:
right = middle-1
return False
# write code here
for i in array:
if binsearch(i,target):
return True
return False
解题思路二：
从二维数组最左下方开始查找，若比查找的数大，则往上走，反之往右走。（因为数组行从上到下递增，从左到右递增）
def Find(self, target, array):
j =len(array)-1
i =0
while i <=len(array[j])-1 and j >=0:
if array[j][i] ==target:
return True
if array[j][i] > target:
j -=1
elif array[j][i] < target:
i+=1
return False
2.输入一个链表，从尾到头打印链表每个节点的值。
解题思路（用时比较少）：将链表原地反转，然后访问输出。(记录当前节点，前一个节点，将当前节点的下一个节点指向前向节点，这样遍历一遍则最后得到的链表是已经反转过的链表)
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
result = []
if listNode is None:
return result
else:
pre = listNode
current = listNode.next
pre.next = None
while current is not None:
behind = current.next
current.next = pre
pre = current
current = behind
# 输出结果
while pre is not None:
result.append(pre.val)
pre = pre.next
return result
- 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回.
解题思路：根据前序遍历可得到每棵子树的根节点，中序遍历的结果总是{左子树集合}根结点{右子树集合}，然后。先根据前序遍历得到每个根节点，可以将中序遍历序列不断的划分为{左子树集合}根结点{右子树集合}，以此迭代。例如：前序遍历可知：1是根节点，由中序遍历可知{4,7,2}是它的左子树，{4，2，7}在前序遍历中2根节点，然后按此不断划分迭代。
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
else:
node = TreeNode(pre[0]) # 找到根节点
node.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[0:tin.index(pre[0])])
node.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
return node
- 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路：使用两个列表a 和b,push元素时往a中push,pop元素时，先将a中的元素全部pop出来并添加到b中，这样b中的序列刚好与a中相反，先push的元素在顶，后puhs的元素在底。这样队列要pop的元素就是b中最顶的元素，将b中顶部元素pop出来，然后将剩余元素都依次pop出并添加到a中，此时a中的序列刚好跟原来一样，并去掉了最底的元素，此时将从b中pop的元素返回便实现了队列的pop功能。
class Solution:
a = []
b = []
def push(self, node):
# write code here
self.a.append(node)
def pop(self):
# return xx
vaule = None
while self.a:
self.b.append(self.a.pop()) #将a中的元素全部push到b中
if self.b:
vaule = self.b.pop()
while self.b:
self.a.append(self.b.pop())
return vaule
5.给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{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]}。
解题思路：滑动窗口可用固定长度的队列来实现（当固定长度的队列的记录已满，新加入元素时会自动移出最老的元素，刚好就是滑动窗口） 记录滑动窗口的最大值，每当滑动窗口滑动一次，即将数组的下一个元素新加入队时，若改新元素比窗口最大值大，那么新窗口的最大值就是改新元素。若新元素比原滑动窗口的最大值小，那么此时需要依次比较滑动窗口里的元素，重新找出最大值。（因为此时原滑动窗口的最大值可能会被移出）
def maxInWindows(self, num, size):
# write code here
if len(num)==0 or size ==0:
return []
import collections
window = collections.deque(maxlen=size) # 创建最大长度为size的队列为滑动窗口
maxnum = num[0]
result = []
for index,i in enumerate(num):
window.append(i)
if i >=maxnum:
maxnum = i
elif index>=size-1:
maxnum = window[0]
for j in range(len(window)-1):
if window[j]> maxnum:
maxnum = window[j]
if index >= size-1:
result.append(maxnum)
return result
6.给定一个数组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[i]的值可以看作下图的矩阵中每行的乘积。下三角用连乘可以很容求得，上三角，从下向上也是连乘。 因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去
def multiply(self, A):
# write code here
B = []
if A:
n = len(A)
B.append(1)
for i in range(1,n):
B.append(B[i-1]*A[i-1])
temp = 1
j = n-2
while j>=0:
temp*=A[j+1]
B[j]*=temp
j-=1
return B
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent