剑指Offer-重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

结题思路

在二叉树的前序遍历中,第一个数字总是数的根节点的值。但在中序遍历中,根节点的值在序列的中间,左子树的结点的值位于根节点的左边,而右子树的节点的值位于根节点的值的右边,因此,我们需要扫描中序遍历,才能找到根节点的值。实例如图:
 -c

既然我们已经分别找到了左、右子树的前序遍历和中序遍历序列,我们可以用同样的方法去分别构建左右子树。也就是递归去实现。

代码

/**
 * 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) {
        return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length);
    }
    
    public TreeNode reConstructBinaryTree(int[] pre,int pStart,int pEnd,int[] in,int iStart,int iEnd){
        if(pStart > pEnd || iStart > iEnd ){
            return null;
        }
        
        TreeNode node = new TreeNode(pre[pStart]);
        int k = find(in, pre[pStart], iStart, iEnd) - iStart;
        node.left = reConstructBinaryTree(pre, pStart+1, pStart+k, in, iStart, iStart+k);
        node.right = reConstructBinaryTree(pre, pStart+k+1, pEnd, in, iStart+k+1, iEnd);
        return node;
        
    }
    
    public int find(int[] array,int target,int start,int end){
        for(int i = start;i<=end;i++){
            if(array[i] == target){
                return i;
            }
        }
        return -1;
    }
}
2017/3/9 posted in  算法-数据结构
 

剑指Offer-从尾到头打印链表

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

问题解答

要解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可是输出的要求顺序却是从尾到头。也就是说第一个遍历到的节点,最后一个输出,而最后一个遍历到的节点第一个输出。这就是典型的后进先出,我们可以用栈实现这个顺序。每经过一个节点的时候,把该节点放入到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出节点的值,此时,输出的节点顺序已经反转过来了。
既然可以使用栈实现这个需求,那么我们就可以考虑使用递归,递归本质上就是一个栈结构。这样要实现反过来输出链表,我们每访问到一个结点的时候,先递归输出它后面的节点,在输出该节点自身,这样链表的输出就反过来了。

递归实现

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    private ArrayList<Integer> array = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        search(listNode);
        return array;
    }
    public void  search(ListNode listNode){
        if(listNode != null){
            search(listNode.next);
            array.add(listNode.val);
        }
        
    }
}

本题基于递归实现看起来很简洁,但是有个问题,当链表非常长的时候,就会导致函数调用层级很深,从而有可能导致函数调用栈溢出。

显示栈实现

import java.util.*;

public class Solution {
    
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        while(listNode != null){
            stack.offerFirst(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> array = new ArrayList<>(stack.size());
        while (stack.size()>0) {
            array.add(stack.pollFirst());
        }
        return array;
    }
    
}

翻转链表

如果可以改变原链表的结构,就可以对链表进行翻转。

import java.util.ArrayList;
public class Solution {
    private ArrayList<Integer> array = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array = new ArrayList<>();
        ListNode head = null;
        ListNode next = null;
        while (listNode != null) {
            next = listNode.next;
            listNode.next = head;
            head = listNode;
            listNode = next;
        }
        while (head != null) {
            array.add(head.val);
            head = head.next;
        }
        return array;
    }
    
}
2017/3/9 posted in  算法-数据结构
 

剑指Offer-替换空格

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

结题思路

这个题目Java开发者可能一下就笑了,so easy啊,一个库函数就解决了。但是,我们还是要尝试去造一下轮子,追求原理。
由于要将空格替换为%20,字符串前后的长度肯定不一样,那么就肯定涉及到了重新申请内存地址。

最简单的思路,我们遍历字符串,发现空格,就将空格后面的字符进行移动,然后继续遍历。这样的做法时间复杂度为O(n2),因为每次都移动了大量的字符。

所以我们提出一个简要的方法,重新申请一个字符串(C/C++中准确的成为字符数组),这个新字符串的长度为原字符串长度+空格个数*2(空格的个数,可以通过一次遍历获得),然后用两个指针变量分别指向两个字符串的首位,然后进行复制,当原字符串指针指向空格时,新字符串插入“%20”,直到末尾。

实现代码

库函数解决:

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll(" ", "%20");
    }
}

自己过不去版:

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer newStr = new StringBuffer();
        
        int i = 0;
        
        while(i<str.length()){
            if(str.charAt(i) != ' '){
                newStr.append(str.charAt(i));
            }else{
                newStr.append("%20");
            }
            i++;
        }
        return newStr.toString();
    }
}
2017/3/8 posted in  算法-数据结构
 

剑指Offer-二维数组中的查找

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

解题思路

假设二维数组为N行,M列。则初始下标变量int i=0; int j = M-1;。此时选取a[i][j]作为比较标准:

  • 若target == a[i][j],则表明已找到对应的数字,返回true;
  • 若target > a[i][j],由于数组是从左至右递增的,所以这一行左边的数据都要比a[i][j]小,所以可以排除,此时将i++,作为新的比较标准;
  • 若target < a[i][j],由于数组是从上而下递增的,该列的所有数字都比target大,不需要比较,则将j--,作为新的比较标准;
  • 若遍历到i==n,j==0,依旧没有找到匹配数据,则返回false;

实现代码

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length == 0){
            return false;
        }
        int i = 0;
        int j = array[0].length - 1;
        
        while(i < array.length && j >=0){
            if(array[i][j] == target){
                return true;
            }
            if(target > array[i][j]){
                i++;
                continue;
            }
            if(target < array[i][j]){
                j--;
                continue;
            }
        }
        return false;

    }
}
2017/3/8 posted in  算法-数据结构