算法工程师进化-算法编程

1 引言

　　对于每一个毕业生而言，只要面试互联网公司，手撕代码算是一个必备节目了。为了能够应对这种面试题，我们需要平时多刷题多积累。一般情况下，如果能够把剑指Offer的算法题搞懂，并且能够举一反三，就足以应对大多数的面试。

　　下面我们针对剑指Offer的题目逐一进行总结学习。

2 剑指Offer

2.1 二维数组中的查找

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

　　思路：

• 这属于数组类型的题目，考察的是查找；
• 该题的关键在于把握数组的特点，基于数组排序的特点，当我们选择不同的起始点开始查找时，对下一步的查找会有不同的影响；
• 我们以右上角作为起始点，这样当遍历值大于或者小于target时，遍历的方向只有一种；

　　代码：

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

　　总结：

• 数组查找类型的题目，一方面要结合数组的特点，另一方面可以考虑二分查找的方法，这也是经常考察的点。

2.2 替换空格

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

　　思路：

• 该题属于字符串类型的题目，考察的是字符串替换；
• 既然是字符串替换，那么就需要有查找，然后才有替换，但是问题的难点在于字符串长度的扩展和字符的顺移。
• 关键点：一次遍历扩展字符串长度，另一次遍历替换字符（从后往前）

 　　代码：

    public String replaceSpace(StringBuffer str) {
        int len=str.length();
        for(int i=0;i<len;i++) {
            if(str.charAt(i)==' ') {
                str=str.append("  ");
            }
        }
        int j=str.length()-1;
        for(int i=len-1;i>=0;i--) {
            if(str.charAt(i)!=' ') {
                str.setCharAt(j--, str.charAt(i));
            }
            else {
                str.setCharAt(j--, '0');
                str.setCharAt(j--, '2');
                str.setCharAt(j--, '%');
            }
        }
        return str.toString();
    }

 　　总结：

• 对于字符串类型的题目，需要注意StringBuffer和String，String不可变，StringBuffer可扩展；
• 另外修改字符串中字符的方法：setCharAt(int,char)；
• 对于字符串的替换问题，需要有逆向思维（逆向遍历）；

3.3 从尾到头打印链表

　　题目描述：输入一个链表，从尾到头打印链表每个节点的值；

　　思路：

• 这是一道链表类型的题目，考察的是遍历；
• 链表的特性只能从头到尾进行遍历，但是题目要求从尾到头打印链表，那么我们可以考虑递归和非递归的思路进行解决；
• 非递归的思路，需要利用空间（栈），递归的思路往往在面试的过程中会是一个加分项。因为递归本身就比较抽象，可以说是装X利器了。

　　代码：

　　非递归思路：

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res=new ArrayList<Integer>();
        Stack<ListNode> s=new Stack<ListNode>();
        while(listNode!=null) {
            s.push(listNode);
            listNode=listNode.next;
        }
        while(!s.isEmpty()) {
            res.add(s.pop().val);
        }
        return res;
    }

　　递归思路：

　　递归思路需要把握递归出口，递归之前的操作，递归之后的操作以及递归的限制条件，当然有时不一定都有；

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res=new ArrayList<Integer>();
        print(listNode,res);
        return res;
    }
    public void print(ListNode listNode,ArrayList<Integer> res) {
        if(listNode==null) {
            return ;
        }
        print(listNode.next,res);
        res.add(listNode.val);
    }

　　总结：

• 对于递归思路，需要理清打印操作是在递归之后还是在递归之前，很明显，对于当前函数，递归是以下一节点开始的子问题，而打印操作是打印当前节点，因此打印操作在递归之后；
• 该题可扩展到链表逆置，同样也有递归和非递归两种解法；

2.4 重建二叉树

　　题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

　　思路：

• 这是一道二叉树类型的题目，基本会考虑递归的解法；
• 举例说明二叉树的重建，子问题为：以前序遍历的第一个节点为子树的根，然后从中序遍历中寻找该节点，这样中序遍历下该节点的左边所有节点为左子树，右边所有节点为右子树；
• 递归函数的参数：除了前序遍历和中序遍历的数组，还需要序列的preStart,preEnd,inStart和inEnd；

　　代码：

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0) {
            return null;
        }
        return helper(pre,in,0,pre.length-1,0,in.length-1);
    }
    public TreeNode helper(int[] pre,int[] in,int preStart,int preEnd,int inStart,int inEnd) {
        if(preStart>preEnd) {
            return null;
        }
        TreeNode node=new TreeNode(pre[preStart]);
        for(int i=inStart;i<=inEnd;i++) {
            if(in[i]==pre[preStart]) {
                int len=i-inStart;
                node.left=helper(pre,in,preStart+1,preStart+len,inStart,i-1);
                node.right=helper(pre,in,preStart+len+1,preEnd,i+1,inEnd);
                break;
            }
        }
        return node;
    }

　　总结：

• 该题的关键在于发掘子问题，明确递归子问题的参数，然后递归出口，递归之前的操作（构建根节点），递归之后的操作（返回根节点），递归的限制条件；

2.5 用两个栈实现队列

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

　　思路：

• 该题属于数据结构的理解，包括栈和队列；
• 栈的特点为先进后出，队列的特点为先进先出；那么如何利用两个栈达到先进先出的效果？
• 方法1：push操作始终push到栈1中，pop操作首先判断栈2有没有元素，如果没有，就将栈1的元素全部依次push到栈2中，然后再pop，这样就实现了先进先出的特点；如果栈2有元素，直接pop即可；注意，只要栈2中有元素，就不要再将栈1中的元素依次push到栈2中，否则违反先进先出的原则。

　　代码：

    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.isEmpty()) {
            return stack2.pop();
        }
        else {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

• 方法2：该方法专门用一个栈来push和pop，另一个栈专门用于过渡；我们以子问题的思路来进行思考，假设栈1的元素已经处理为先进先出，即假设我们按顺序1,2,3push元素到栈1中，但是栈1显示为1,2,3（从栈顶到栈底的顺序）；现在如果要push一个元素4到栈1中（4,1,2,3），那么必须把栈1调整为1,2,3,4；那么调整就可以利用到栈2，在push之前，先将栈1中元素全部依次push到栈2，然后push元素到栈1底部，最后再把栈2中的元素又依次push到栈1中；

　　代码：

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        stack1.push(node);
        while(!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
    }
    
    public int pop() {
        return stack1.pop();
    }

　　总结：

• 两个栈实现队列的两种方法：一种是以一个栈push，另一个栈pop；另一种，专门用一个栈push和pop，另一个栈专门用于过渡；
• 拓展：如果是两个队列实现栈：方法1好像不适用，按照方法2，以子问题的思路思考，假设按顺序1,2,3push元素到队列1中，那么队列1中应该显示为3,2,1（从队头到队尾），这样就实现了先进后出；现在如果push一个元素4到队列1中（3,2,1,4），如何调整为4,3,2,1；这样就考虑使用队列2，首先在push之前，先将队列1中元素依次push到队列2中，然后push新元素到队列1，最后再将队列2中元素依次push到队列1中。