剑指Offer习题全解

Kill Offer Solution

Posted by Jerry on May 4, 2017

动手写代码前先好好思考,多考虑各种边界极限条件,这样下手写代码一定会写出鲁棒性(Robust)的代码。

剑指Offer习题全解

二维数组中的查找

/*两种思路
一种是:
把每一行看成有序递增的数组,
利用二分查找,
通过遍历每一行得到答案,
时间复杂度是nlogn*/
public class Solution {
    public boolean Find(int [][] array,int target) {
        for(int i=0;i<array.length;i++){
            int low=0;
            int high=array[i].length-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(target>array[i][mid])
                    low=mid+1;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    return true;
            }
        }
        return false;
 
    }
}
 
/*另外一种思路是:
利用二维数组由上到下,由左到右递增的规律,
那么选取右上角或者左下角的元素a[row][col]与target进行比较,
当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,
即col--;
当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,
即row++;
时间复杂度O(n+m)*/
public class Solution {
    public boolean Find(int [][] array,int target) {
        int row=0;
        int col=array[0].length-1;
        while(row<=array.length-1&&col>=0){
            if(target==array[row][col])
                return true;
            else if(target>array[row][col])
                row++;
            else
                col--;
        }
        return false;
 
    }
}

替换空格

/*方法一
* 时间复杂度O(n)
* 空间复杂度O(n)
*/
public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<str.length();i++){
            if(str.charAt(i)==' '){
                sb.append("%20");
            }else{
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }

}

/*方法二
在当前字符串替换,怎么替换才更有效率(不考虑java里现有的replace方法)。
从前往后替换,后面的字符要不断往后移动,要多次移动,所以效率低下
从后往前,先计算需要多少空间,然后从后往前移动,则每个字符只为移动一次,这样效率更高一点。
*/
public class Solution {
    public String replaceSpace(StringBuffer str) {
        int spacenum = 0;//spacenum为计算空格数
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' ')
                spacenum++;
        }
        int indexold = str.length()-1; //indexold为为替换前的str下标
        int newlength = str.length() + spacenum*2;//计算空格转换成%20之后的str长度
        int indexnew = newlength-1;//indexold为为把空格替换为%20后的str下标
        str.setLength(newlength);//使str的长度扩大到转换成%20之后的长度,防止下标越界
        for(;indexold>=0 && indexold<newlength;--indexold){  
                if(str.charAt(indexold) == ' '){  //
                str.setCharAt(indexnew--, '0');
                str.setCharAt(indexnew--, '2');
                str.setCharAt(indexnew--, '%');
                }else{
                    str.setCharAt(indexnew--, str.charAt(indexold));
                }
        }
        return str.toString();
    }
}

/*
* 方法三,用正则表达式
*/
public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll("\\s", "%20");
    }
}

从头到尾打印链表

/*
* 方法一, 调用Collections工具类
*/
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
         
        while(listNode != null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
         
        Collections.reverse(list);//使用Collections的reverse方法,直接将list反转
        return list;
    }
}
/*
* 方法二, 调用Collections工具类
*/
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode!=null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> ret = new ArrayList<>();
        while(!stack.isEmpty()){
            ret.add(stack.pop());
        }
        return ret;
    }
}

重建二叉树

/*
* 方法一
*/
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return constructBT(pre, 0,pre.length,in,0,in.length);
    }

    public TreeNode constructBT(int[] pre, int s1, int len1, int[] in, int s2, int len2){
        if(len1==0||len2==0||len1!=len2)return null;
        TreeNode root = new TreeNode(pre[s1]);
        int pivot = search(in, s2, s2+len2-1, pre[s1]);
        int leftLen = pivot - s2;
        root.left = constructBT(pre, s1+1, leftLen, in, s2, leftLen);
        root.right = constructBT(pre, s1+leftLen+1, len1-leftLen -1, in, pivot+1, len2-leftLen-1);
        return root;
    }

    public int search(int[] a, int low ,int high, int target){
        while(low<=high&&a[low]!=target){
            low++;
        }
        return low;
    }

}
/*
* 方法二,本质上和方法一相同
*/

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
       if(pre.length == 0||in.length == 0){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for(int i = 0; i < in.length; i++){
            if(pre[0] == in[i]){
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
            }
        }
        return node;
    }
}

用两个栈实现队列

/*
* 方法一
*/
import java.util.Stack;

public class Solution {
    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();
    
    public void push(int node) {
        s1.push(node);
    }
    
    public int pop() {
    	if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            } 
        }
        if(s2.isEmpty())throw new RuntimeException("Empty");
        return s2.pop();
    }
}

###

/*
* 方法一 时间复杂度O(logn)
*/
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    	if(array==null||array.length==0)return 0;
        int i = 0;
        int j = array.length-1;
        while(array[i]>=array[j]){
            if(i+1==j)return array[j];
            int mid = (i+j)/2;
            if(array[i]==array[j]&&array[i]==array[mid])return find(array, i, j);
            if(array[i]<=array[mid])i=mid;
            else j = mid;
        }
        return array[i+1];
    }
    private int find(int[] a, int i, int j){
        int min = Integer.MAX_VALUE;
        for(int k = i;k<=j;k++){
            min = Math.min(a[k],min);
        }
        return min;
    }
}
/*
* 方法二
*/
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    	if(array==null||array.length==0)return 0;
        return find(array, 0, array.length-1);
    }
    private int find(int[] a, int i, int j){
        int min = Integer.MAX_VALUE;
        for(int k = i;k<=j;k++){
            min = Math.min(a[k],min);
        }
        return min;
    }
}

跳台阶

/*
* 方法一
*/
public class Solution {
    public int JumpFloor(int t) {
        if(t<=0)return 0;
        if(t==1)return 1;
        int f1 = 1, f2 = 2;
        int i = 2;
        while(i<t){
            int tmp = f2 + f1;
            f1 = f2;
            f2 = tmp;
            i++;
        }
        return f2;
    }
}

变态跳台阶

/*
* 方法一
*/
public class Solution {
    public int JumpFloorII(int target) {
        if(target<=0)throw new RuntimeException("Error");
        return (int)Math.pow(2,target-1);
    }
}

矩形覆盖

/*
* 方法一
*/
public class Solution {
    public int RectCover(int t) {
		if(t<=0)return 0;
        if(t==1)return 1;
        int f1 = 1, f2 = 2;
        int i = 2;
        while(i<t){
            int tmp = f2 + f1;
            f1 = f2;
            f2 = tmp;
            i++;
        }
        return f2;
    }
}

二进制中1的数

/*
* 方法一
*/
public class Solution {
    public int NumberOf1(int n) {
        int cnt = 0;
		while(n!=0){
            n=n&(n-1);
            cnt++;
        }
        return cnt;
    }
}
/*
* 方法二
*/
public class Solution {
    public int NumberOf1(int n) {
        int cnt = 0;
		while(n!=0){
            if((n&1)==1)cnt++;
            //无符号右移,即高位补0
            n = n >>> 1;
        }
        return cnt;
    }
}

求两个整数二进制数中,有几个不同的数字

/*
* 方法一
*/
public class Solution {
    public int findD(int n1, int n2){
        //异或
        int n = n1^n2;
        return(NumberOf1(n));
    }
    public int NumberOf1(int n) {
        int cnt = 0;
		while(n!=0){
            n=n&(n-1);
            cnt++;
        }
        return cnt;
    }
}

数值的整数次方

/*
* 方法一
*/
public class Solution {
    public double Power(double base, int exponent) {
        if(base==0.0&&exponent==0)throw new RuntimeException("Illeag");
        int flag = 1;
        if(exponent<0)flag=-1;
        double ret = unsignPower(base, exponent*flag);
        if(flag<0)ret = 1.0/ret;
        return ret;
  }
    private double unsignPower(double base, int exponent){
        if(exponent==0)return 1;
        double ret = 1.0;
        for(int i = 1;i<=exponent;i++){
            ret *= base;
        }
        return ret;
    }
}
/*
* 方法二
*/
public class Solution {
    public double Power(double base, int exponent) {
        if(base==0.0&&exponent==0)throw new RuntimeException("Illeag");
        int flag = 1;
        if(exponent<0)flag=-1;
        double ret = unsignPower(base, exponent*flag);
        if(flag<0)ret = 1.0/ret;
        return ret;
  }
    private double unsignPower(double base, int exponent){
        if(exponent==0)return 1;
        if(exponent == 1)return base;
        double ret = unsignPower(base, exponent >>> 1);
        ret *= ret;
        if((exponent&1)==1)ret *= base;
        return ret;
    }
}

调整数组顺序使奇数位于偶数前面

/*
* 方法一 //还可以用其他稳定的排序算法(如插入排序),下面这算法是用冒泡排序的变种
*/
public class Solution {
    public void reOrderArray(int [] a) {
        if(a==null||a.length<2)return;
        int n = a.length;
        for(int i = 0;i<n;i++){
            for(int j = n-1;j>i;j--){
                if((a[j]&1)==1&&(a[j-1]&1)==0){
                    swap(a,j-1,j);
                }
            }
        }
    }
    private void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

链表中倒数第k个结点

/*
* 方法一 双指针
*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
		if(head==null||k<=0)return null;
        int i = 1;
        ListNode p = head, q = head;
        while(i<k&&p.next!=null){
            p=p.next;
            i++;
        }
        if(i<k)return null;
        while(p.next!=null){
            p = p.next;
            q = q.next;
        }
        
        return q;
    }
}
/*
* 方法二 遍历两遍
*/

反转链表

/*
* 方法一,头插法,直接进行反转
*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
		if(head==null)return null;
        ListNode p = head, r = null, q = null;
        while(p!=null){
            r = p.next;
            if(q==null){
                q = p;
                q.next = null;
            }else{
              	p.next = q;
                q = p;
            }
            p = r;
        }
        return q;
    }
}
/*
* 方法二 递归
*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
		if(head==null||head.next==null)return head;
        ListNode pReverseNode = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return pReverseNode;
    }
}
/*
* 方法三 简单点的
*/
public ListNode ReverseList(ListNode head) {
    ListNode pre = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

合并两个排序链表

/*
* 方法一
*/
public class Solution {
    public ListNode Merge(ListNode l1,ListNode l2) {
        if(l1==null||l2==null)return l1==null?l2:l1;
		ListNode p = l1, q = l2, head = null, r,t=null;
        while(p!=null&&q!=null){
            if(p.val<q.val){
                r = p;
                p = p.next;
            }else{
                r = q;
                q = q.next;
            }
            if(head==null){
                head = r;
                head.next = null;
                t = head;
            }else{
                t.next = r;
                r.next = null;
                t = t.next;
            }
        }
        ListNode l = (p!=null)?p:q;
        while(l!=null){
            t.next = l;
            l = l.next;
            t = t.next;
            t.next = null;
        }
        return head;
    }
}
/*
* 方法二 递归方法
*/
public class Solution {
    public ListNode Merge(ListNode l1,ListNode l2) {
        if(l1==null||l2==null)return l1==null?l2:l1;
		if(l1.val<l2.val){
            l1.next = Merge(l1.next, l2);
            return l1;
        }else{
            l2.next = Merge(l1, l2.next);
            return l2;
        }
    }
}

树的子结构

/*
* 方法一
*/
public class Solution {
    public boolean HasSubtree(TreeNode r1,TreeNode r2) {
        if(r1==null||r2==null)return false;
        return isSub(r1,r2)||HasSubtree(r1.left,r2)||HasSubtree(r1.right,r2);
    }
    
    private boolean isSub(TreeNode r1, TreeNode r2){
        if(r2==null)return true;
        if(r1==null)return false;
        if(r1.val!=r2.val){
            return false;
        }
        return isSub(r1.left,r2.left)&&isSub(r1.right,r2.right);
    }
}

二叉树的镜像

/*
* 方法一 递归
*/
public class Solution {
    public void Mirror(TreeNode root) {
        postOrder_m(root);
    }
    private TreeNode postOrder_m(TreeNode root){
        if(root!=null){
            TreeNode l = postOrder_m(root.left);
            TreeNode r = postOrder_m(root.right);
            root.left = r;
            root.right = l;
            return root;
        }
        return null;
    }
}
/*
* 方法二
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root ==null)return;
        Mirror(root.left);
        Mirror(root.right);
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
    }
}
/*
* 方法三 队列
*/
import java.util.*;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root ==null)return;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode t = q.remove();
        	TreeNode l = t.left;
            TreeNode r = t.right;
            t.left = r;
            t.right = l;
            if(l!=null)q.add(l);
            if(r!=null)q.add(r);
        }
    }
}