实在不想看JVM了。刷几道剑指Offer的题，今天就水一水吧，脑子迷糊。
1.二维数组中的查找
解题思路：从右上角开始搜索，从上到下为递增，从右到左为递减。根据这个思路来进行搜索，算法复杂度n+m
public class Solution {
public boolean Find(int target, int [][] array) {
int x=0,y=array[0].length-1;
while(x<array.length&&y>-1){
if(array[x][y]>target){
y--;
}else if(array[x][y]<target){
x++;
}else{
return true;
}
}
return false;
}
}
2.替换空格
解题思路：不能一个一个插入，复杂度太高，要用空间来换取时间。一个一个赋值比较好。
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer sb = new StringBuffer();
for(int i=0;i<str.length();i++) {
if(str.charAt(i)==' ') {
sb.append("%20");
}else {
sb.append(str.charAt(i));
}
}
return sb.toString();
}
}
3.从尾到头打印链表
解题思路：这题用C++的话可以直接把指针反转，不过Java传进来的是一个集合类。就算了吧。用傻瓜式解法。
/**
* 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<Integer> al = new ArrayList<Integer>();
while(listNode!=null) {
al.add(0,listNode.val);
listNode = listNode.next;
}
return al;
}
}
4.重建二叉树
解题思路：递归建树。基础题。
/**
* 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.length==0) return null;
TreeNode trn = new TreeNode(pre[0]);
if(pre.length==1) return trn;
else for(int i=0;i<in.length;i++) {
if(in[i]==pre[0]) {
int [] preleft = new int[i];
int [] preright = new int[in.length-i-1];
int [] inleft = new int[i];
int [] inright = new int[in.length-i-1];
System.arraycopy(pre,1,preleft,0,i);
System.arraycopy(pre,i+1,preright,0,in.length-i-1);
System.arraycopy(in,0, inleft, 0, i);
System.arraycopy(in,i+1, inright, 0, in.length-i-1);
trn.left = reConstructBinaryTree(preleft, inleft);
trn.right = reConstructBinaryTree(preright,inright);
return trn;
}
}
return trn;
}
}
5.用两个栈实现队列
解题思路：对先进后出和先进先出的基础理解即可想明白。
import java.util.Stack;
public class Solution {
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.empty()) {
return stack2.pop();
}
else{
while(!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
}