剑指offer编程题-1

2018-06-18 01:37:02来源：未知阅读 ()

1.二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

利用二维数组由上到下，由左到右递增的规律，
那么选取右上角a[row][col]与target进行比较，如果等于就直接找到，
当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,
即col--；
当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,
即row++；

    public class Solution {

　　public boolean Find(int target, int [][] array) {
        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;
 
    }

 }

注意：

对于一个二维数组：

int[][] arr = {  
        {2,3,4},  
        {4,5,6},  
        {7,8,9}  
    };

int rows = i.length;//行数
int columns = i[0].length;//列数

[[]]这样一个数组代表行数是1，列数时0.

2.替换空格

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：构造一个StringBuffer类，逐个添加字符，遇到空间换成%20之后再添加。

public class Solution {
    
     public String replaceSpace(StringBuffer str) {
         StringBuffer strCopy= new StringBuffer();
         
         for(int i=0 ; i<str.length();i++){
             String c = String.valueOf(str.charAt(i));
             if(c.equals(" ")){
             strCopy.append("%20");
         }else {
             strCopy.append(c);
         }
        }

    return strCopy.toString();
 }
}

注意：

Java中字符数组、String类、StringBuffer三者的相互转换

3.从尾到头打印链表

题目描述

输入一个链表，从尾到头打印链表每个节点的值。

思路：遇到先进后出的情况，可以采取两种思路：

1.利用堆栈的思想

2.利用递归的思想

下面是采用堆栈的思想：

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<ListNode> stack = new Stack<ListNode>();
        while(listNode!=null){
            stack.push(listNode);
            listNode = listNode.next;
        }
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(!stack.isEmpty()){
            list.add(stack.pop().val);
        }
        return list;
        
    }
}

下面是采用递归的思想：

import java.util.ArrayList;
public class Solution {
     ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       
          if(listNode!=null){
               this.printListFromTailToHead(listNode.next);
               list.add(listNode.val);
           }
        return list;
    }
}

4.重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

方式1：


import java.util.*;
/**
 * 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||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));
            　　 break;
　　　　　　　　}
        }
        return node;
    }
}

这是形式最为简洁的方法，首先前序的第一个数字肯定是根节点，然后根据这个元素在中序中找到根节点位置i，

那么中序左边0，i是左子树，右边i+1,in.length是右子树。

并且也能在前序中确定左子树是从1，i+1的元素，右子树是i+1,pre.length。（注意这里是左边界包含，右边界不包含）

然后从原数组中分别复制前序和中序的左子树和右子树，递归调用即可。直到pre.length或者in.length（当然这里他俩本来就一样）为0表示递归到叶子节点。

注：Arrays.copyOfRange()方法

要使用这个方法，首先要import java.util.*;

Arrays.copyOfRange(T[ ] original,int from,int to)

将一个原始的数组original，从小标from开始复制，复制到小标to，生成一个新的数组。

注意这里包括下标from，不包括下标to。

这个方法在一些处理数组的编程题里很好用，效率和clone基本一致，都是native method，比利用循环复制数组效率要高得多。

2.方式2

另外一种方法其实跟上面的思路是一样的，就是不需要复制出左子树和右子树的数组，直接在原数组上操作。

在原数组上操作就是要搞清楚每次递归的时候左子树和右子树在原数组上的位置，

对于中序比较好确认，以根节点i为分界线，startIn至i-1为左子树，i+1至endIn为右子树

对于前序，前序的索引需要通过中序左右子树的大小 i-startIn 来计算，前序左子树为startPre+1至startPre+i-startIn,前序右子树为startPre+i-startIn

startPre>endPre||startIn>endIn为表示已经递归完成

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
         
        if(startPre>endPre||startIn>endIn)
            return null;
        TreeNode root=new TreeNode(pre[startPre]);
         
        for(int i=startIn;i<=endIn;i++)
            if(in[i]==pre[startPre]){
                root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                break;
            }
                 
        return root;
    }
}