剑指offer（1-5）

JZ1

问题描述：

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

思路：

边界条件判断，如果数组为空直接false
从二维数组左下角的元素开始遍历
如果当前数等于目标值，返回true
如果当前值大于目标值，行索引自减
如果当前值小于目标值，列索引自增
如果行索引或者列索引越界，返回false

代码：

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null || array.length == 0 || array[0].length == 0) return false;
        int m = array.length, n = array[0].length;
        int r = m - 1, c = 0;
        while(r >= 0 && c < n){
            if(array[r][c] == target) return true;
            if(array[r][c] > target) r--;
            else if(array[r][c] < target) c++;
        }
        return false;
    }
}

JZ2

问题描述：

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

思路：

直接遍历字符串，使用StringBuilder接收遍历结果
如果当前为空格，加入指定字符串

代码：

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer res = new StringBuffer();
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) == ' '){
                res.append("%20");
            }else{
                res.append(str.charAt(i));
            }
        }
        return res.toString();
    }
}

JZ3

问题描述：

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思路一：

遍历链表，每次在0索引的位置插入元素

思路二：

将链表反转，之后遍历

思路三：

正向遍历，然后使用Collections工具类反转

代码：

public class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    
    // 思路一：
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null) return res;
        ListNode t = listNode;
        while(t != null) {
            res.add(0, t.val);
            t = t.next;
        }
        return res;
    }
    
    // 思路二：
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null) return res;
        ListNode pre = null, next = null;
        while(listNode != null) {
            next = listNode.next;
            listNode.next = pre;
            pre = listNode;
            listNode = next;
        }
        while(pre != null) {
            res.add(pre.val);
            pre = pre.next;
        }
        return res;
    }
    
    // 思路三：
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null) return res;
        while(listNode != null) {
            res.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(res);
        return res;
    }
}

JZ4

问题描述：

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

思路一：

前序遍历顺序：根节点 —— 根节点左子树 —— 根节点右子树
中序遍历顺序：根节点左子树 —— 根节点 —— 根节点右子树
首先确定根节点，前序遍历序列第一个值就是根节点的值
在中序遍历序列中找到上一步根节点所在位置
然后递归进行左子树和右子树的计算

代码：

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        int n = pre.length;
        return create(pre, 0, n - 1, in, 0, n - 1);
    }

    private TreeNode create(int[] pre, int pl, int pr, int[] in, int il, int ir) {
        if (pl > pr) return null;
        if (pl == pr) return new TreeNode(pre[pl]);
        // 首先确定头节点的值
        int cur = pre[pl];
        TreeNode root = new TreeNode(cur);
        int ii = 0;
        for (int i = il; i <= ir; i++) {
            if (in[i] == cur) {
                ii = i;
                break;
            }
        }
        int len = ii - il;
        root.left = create(pre, pl + 1, pl + len, in, il, ii - 1);
        root.right = create(pre, pl + len + 1, pr, in, ii + 1, ir);
        return root;
    }
}

JZ5

问题描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

思路一：

队列的特点：先进先出
入队列的时候，直接加入指定的数据栈中（data）
出队列的时候，在专用的操作栈（opt）中取数据
如果操作栈为空，将数据栈中的元素全部弹过来
如果操作栈不为空，直接弹出元素即可

代码：

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(stack1.isEmpty() && stack2.isEmpty()) throw new RuntimeException("队列为空");
        if(stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }    
        }
        return stack2.pop();
    }
}