1. 二维数组中查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
思路：
选择该二维数组的最右上角的那个数开始扫描，当target小于该值时，可以清除一列，当target大于该值时，可以清除一行
public class Solution {
public boolean Find(int target, int [][] array) {
if (null == array) {
return false;
}
int i = 0;//表示第一行
int j = array[0].length;//表示该二维数组的列数
int start;
while (i < array.length && j > 0) {
start = array[i][j-1];//每次清除一行或一列后的最右上角的元素
if (target < start) {
j--;
} else if (target > start) {
i++;
} else {
return true;
}
}
return false;
}
}
2. 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：
- 将每个空格替换成“%20”，则相当于每一个空格都需要新加两个字符的位置；如果考虑输入的是一个数组，为了能够让每个字符只移动一次，则可以预先预留出来足够的正合适的空间，
- 同时用两个指针从分别从旧的末尾和新的末尾开始向前遍历，可做到每个字符只移动一次
public class Solution {
public String replaceSpace(StringBuffer str) {
if (null == str || str.length() == 0) {
return "";
}
int strOldLength = str.length();//最开始的字符串长度
int blankNumber = 0;//记录空白字符的个数
for (int i = 0; i < strOldLength; i++) {
if (' ' == str.charAt(i)) {
++blankNumber;
// 每遇到一个空格，StringBuffer都在末尾新增两个空的位置
str.append(' ').append(' ');
}
}
// 如果扫描完字符串的数组没有发现空格，则直接返回
if (0 == blankNumber) {
return str.toString();
}
int strNewLength = str.length();
int firstPoint = strOldLength-1; // 旧的末尾索引
int lastPoint = strNewLength-1; // 新的末尾索引
// 当所有的空格都替换后，两个节点会相遇
while (firstPoint >= 0 && lastPoint > firstPoint) {
if (' ' == str.charAt(firstPoint)) {
str.setCharAt(lastPoint--, '0'); // 设置当前索引位置的值为0，通过指针
str.setCharAt(lastPoint--, '2');
str.setCharAt(lastPoint--, '%');
} else {
str.setCharAt(lastPoint--, str.charAt(firstPoint));
}
firstPoint--;
}
return str.toString();
}
}
3. 从尾到头打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：
有多种解答方案：1，递归(本博客列出的代码实例) 2，栈 3，倒转链表指针，再从头到尾打印
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {//该思路是采用递归，从尾到头依次打印链表节点
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList arrayList = new ArrayList();
if (listNode == null) {
return arrayList;
}
printListFromTailToHead(arrayList, listNode);
return arrayList;
}
public void printListFromTailToHead(ArrayList array, ListNode listNode) {
if (listNode.next == null) {//当到达链表尾部时，将值添加到ArrayList
array.add(listNode.val);
}else {
printListFromTailToHead(array, listNode.next);//进入下一个节点
array.add(listNode.val);//自己的下一个节点执行完，回退到本节点时再将值添加进ArrayList
}
}
4. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
二叉树的前序序列中第一个节点永远是根节点root，中序序列中root所在的位置的左边序列，都是当前root节点的左子树，右边都是root节点的右子树，
因此，前序序列的root节点的下一位又是它的左子树的根节点，同样的规则适用于它的左右子树，所以这里我们可以用递归来实现
/**
* 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 || pre.length != in.length) {
System.out.println("数组不能为空或者两个数组长度不一致");
return null;
}
// 之所以需要四个位置变量，是因为需要记录前序序列的开始和结束位置，也要记录
return reConstructBinaryTree(pre, in, 0, pre.length-1, 0, in.length-1);
// 中序序列的开始和结束位置
}
// fStart表示前序序列开始节点， fStop表示前序序列结束节点，mStart表示中序序列开始节点，mStop表示中序序列结束节点
public TreeNode reConstructBinaryTree(int [] pre, int [] in, int fStart, int fStop, int mStart, int mStop) {
int rootValue = pre[fStart];
TreeNode root = new TreeNode(rootValue);//先创建根节点
root.left = null;
root.right = null;
//判断是否是只有一个节点
if (fStart == fStop) {
if (mStart == mStop) {
return root;
}else { //其实上面做了判断，这里就不会走到else子句中来
System.out.println("两个数组输入有误");
return null;
}
}
int mm = mStart; //用一个变量记录二叉树的root节点在中序序列中的位置
//直到在中序序列中找到root，或者遍历完中序序列数组
while (in[mm] != rootValue && mm <= mStop) {
++mm;
}
//此时还不相等的话，说明中序序列中没有此时的root
if (in[mm] != rootValue) {
System.out.println("中序序列中没有与前序序列中确定的root节点相等的节点值");
return null;
}
//这里一定要这样写，记录移动的位置
int mLengh = mm - mStart;
//前序序列当前的树开始的节点位置+移动的位置就等于当前树的子树的结束位置
int fLeftSubTreeStop = fStart + mLengh;
if (mm > mStart) {
root.left = reConstructBinaryTree(pre, in, fStart+1, fLeftSubTreeStop, mStart, mm-1);
//(前序序列数组，中序序列数组，前序序列当前树开始节点的后一位，
//前序序列当前树的子树结束的位置，中序序列当前树开始的位置，中序序列root位置的前一位)
}
if (mm < mStop) {
root.right = reConstructBinaryTree(pre, in, fLeftSubTreeStop+1, fStop, mm+1, mStop);
//(前序序列数组，中序序列数组，前序序列当前树的子树结束的位置的前一位，
//前序序列中当前树结束的位置，中序序列root位置的后一位，中序序列中当前树结束的位置
}
return root;
}
}
5. 用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：
- 将stack1当做入队列，将stack2当做出队列，当队列需要push入队列一个元素的时候，直接push到stack1就可以了；当队列需要pop出队列时
- 首先判断stack2是否为空，如果为空，则将stack1中的元素全部pop出来并依次push到stack2中，再让stack2来pop一下就可以了；如果不为空，stack2直接pop一下就行。
import java.util.Stack;
public class Solution {//思路：将stack1当做入队列，将stack2当做出队列，当队列需要push入队列一个元素的时候，直接push到stack1就可以了；当队列需要pop出队列时
//，首先判断stack2是否为空，如果为空，则将stack1中的元素全部pop出来并依次push到stack2中，再让stack2来pop一下就可以了；如果不为空，stack2直接pop一下就行。
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.size() == 0) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
if (stack2.size() == 0) {//当stack1和stack2都长度为0的时候，运行到这里还是会出现stack2的长度为0，所以要做异常处理
System.out.println("stack1和stack2的长度都为0，不能进行pop操作，抛出异常");
return -1;
}
return stack2.pop();
}
}
6. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：对一个n长度的非减排序数组进行旋转有两种情况：
- 第一：旋转了1～n-1个数字，会形成两个非减排序的子数组，如： 4 5 和 1 2 3；它的最小值是在第二个子数组的开头，同时，第一个子数组的所有元素都大于或者等于第二个子数组，可以利用二分查找法来处理；
- 第二：旋转了0个数字，得到的旋转数组仍然是原数组：1 2 3 4 5，最小值就是第一个元素
注意：第二种情况里面：当数组头节点=尾节点=中间节点的时候，无法用二分查找来缩小查找范围，如：0 1 1 1 1 1 ，旋转 0 1 1 1 1变成：1 0 1 1 1 1,，只能用顺序查找
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (null == array || array.length == 0) {
return 0;
}
int n = array.length - 1;
int first = 0;//二分查找的开头元素位置索引
int min = first;//用一个新的元素记录最小值，是为了方便如果是第二种情况，就不需要循环直接返回首节点
int last = n-1;//二分查找的末尾元素位置索引
int middle = 0;//中间节点位置索引
while (array[first] >= array[last]) {//当数组的开头节点大于等于数组的末尾节点时，需要进行循环判断
if (last - first == 1) {//当二分查找的结束索引与开始索引之间相邻的时候，说明就找到了最小元素，
//而且最小元素是结束索引上的元素(因为first指针总会指向第一个子数组，而第二个子数组总会指向第二个子数组)
min = last;
break;
}
middle = first + (last-first)/2;
if (array[first] == array[middle] && array[middle] == array[last]) {//此时无法用二分查找
// return 。。。
//此处省略顺序查找的方法
}
if (array[middle] >= array[first]) {//当中间元素大于等于二分查找数组的开头元素时，说明中间元素落在了第一个子数组中，最小元素要去后面找
first = middle;
}else if (array[middle] <= array[last]) {//否则当中间元素小于等于二分查找数组的末尾元素时，说明中间元素落在了第二个子数组中，最小元素去前面找
last = middle;
}
}
//如果数组的第一个元素小于最后一个元素，说明：非减排序的数组的旋转数组是它本身：1 2 3 4 5，这时第一个元素就是最小元素
return array[min];
}
}
