本文按照牛客网的顺序，牛客网剑指offer刷题网址：https://www.nowcoder.com/ta/coding-interviews
本文涉及的题目：
1、二维数组中的查找
2、从尾到头打印链表
3、重建二叉树
1、二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路
类似于二分查找，根据题目，如果拿数组中任意一个元素与目标数值进行比较，如果该元素小于目标数值，那么目标数值一定是在该元素的下方或右方，如果大于目标数值，那么目标数值一定在该元素的上方或者左方。
对于二分查找来说，每次比较只能移动一个指针，同时，指针的移动方向必须在查找过程中保持一致。在二维数组的查找中，两个指针是一个上下方向移动，一个是左右方向移动的。两个指针可以从同一个角出发，也可以从不同的角出发。这里我们只考虑从同一个角出发的情况。
假设我们从左上角出发，也就是row=0 和 col=0，如果元素小于目标数值，我们会将row往下移或着col往右移，这样，被屏蔽的区域可能会是目标元素所在的区域。比如row+=1，那么第一行除左上角以外的元素就被忽略了，如果col+=1，那么第一列出左上角以外的元素就被忽略了。因此这样是不可行的。
所以本题从右上角出发寻找解题思路，即开始时col=len(array[0])-1,row=0,col往左移动，row往下移动，当某元素小于目标数值时，col-=1，而当某元素大于目标数值时，row+=1。代码如下：
java
public class Solution {
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length-1;
while(row<array.length && col>=0){
if(array[row][col] == target)
return true;
else if(array[row][col] > target)
col -= 1;
else
row += 1;
}
return false;
}
}
python
# -*- coding:utf-8 -*-
class Solution:
def Find(self, target, array):
# write code here
if not array:
return False
row = 0
col = len(array[0])-1
while row < len(array) and col >=0:
if array[row][col] == target:
return True
elif array[row][col] < target:
row = row + 1
else:
col = col - 1
return False
2、从尾到头打印链表
问题描述
输入一个链表，从尾到头打印链表每个节点的值。
思路解析
使用栈从头到尾push链表的元素，然后pop所有的元素到一个list中并返回
代码实现
java
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arr = new ArrayList<Integer>();
ListNode p = listNode;
ArrayList<Integer> stack = new ArrayList<Integer>();
while(p!=null){
stack.add(p.val);
p = p.next;
}
int n = stack.size();
for(int i=n-1;i>=0;i--){
arr.add(stack.get(i));
}
return arr;
}
}
python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def printListFromTailToHead(self, listNode):
# write code here
if not listNode:
return []
p = listNode
stack = []
res = []
while p:
stack.append(p.val)
p = p.next
for i in range(len(stack)-1,-1,-1):
res.append(stack[i])
return res
3、重建二叉树
问题描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路解析
根据前序遍历的结果，对于输入的遍历序列，第一个数一定是根结点，那么我们去中序遍历的结果中找到该根节点，中序遍历结果中根结点左边的是左子树的节点，右边的是右子树的节点，这样很容易使用递归的思路实现二叉树的重建。
代码实现
java
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre == null || in == null || pre.length == 0 || in.length == 0){
return null;
}
return buildTree(pre, in, 0, pre.length - 1, 0, in.length - 1);
}
public TreeNode buildTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
TreeNode root = new TreeNode(pre[preStart]);
int rootIn = 0;
for(; rootIn < in.length; rootIn++){
if(in[rootIn] == root.val){
break;
}
}
int leftLength = rootIn - inStart;
int rightLength = inEnd - rootIn;
if(leftLength > 0){
root.left = buildTree(pre, in, preStart + 1, preStart + leftLength, inStart, rootIn - 1);
}
if(rightLength > 0){
root.right = buildTree(pre, in, preStart + leftLength + 1, preEnd, rootIn + 1, inEnd);
}
return root;
}
}
python
# -*- 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 not pre or not tin:
return None
root = TreeNode(pre[0])
i = 0
while i < len(tin):
if tin[i] == pre[0]:
break
i = i + 1
index = i
root.left = self.reConstructBinaryTree(pre[1:index+1],tin[:index])
root.right = self.reConstructBinaryTree(pre[index+1:],tin[index+1:])
return root
