数据结构是程序员必须掌握的基础知识，也一直是技术面试的重点。数组和链表是内存中两种基本的数据结构，而字符串、树、栈和队列等是在前者基础上实现的抽象数据类型。本次就对这些常用的数据结构进行梳理。

在剑指系列中，由于篇幅限制给出的代码中仅聚焦于核心算法而没有作防御型编程（第三章除外），许多数据结构真正操作时需要作防御型编程以避免空指针、数组越界等异常。

数组

数组是一种使用连续内容空间按照顺序存储数据的数据结构，创建数组时要声明数组容量的大小，在不确定要使用的大小时可能出现浪费或需要扩容的问题因而空间效率不佳，但存取的时间效率为O(1)。Java中数组是一种特殊的对象，不由某个类实例化而来，而是由JVM直接创建。其中可以存储基本类型或引用类型。

关于动态数组：在Java的集合框架中实现List接口的类从逻辑上都可以理解为一种动态数组，其中LinkedList底层为双向链表扩容很方便，而ArrayList和Vector底层都为数组，在扩容时需要开辟新的数组空间并将原来的数组内容复制过去，是较为耗时的操作。两者都采用了重复倍增的方式，ArrayList默认每次增长为之前大小的1.5倍并且不可设置，Vector默认倍数为2倍并且提供了设置增长倍数的方法。Vector提供的方法在线程间是同步的，但效率低，ArrayList反之。

面试题3：数组中的重复数字

题目描述

在一个长度为n的数组numbers[]里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

示例

输入:
长度为7的数组{2,3,1,0,2,5,3}
输出:
任意一个重复的数字，如2

解题思路

1. 排序后再找出重复的数

排序后的数组中重复的数字是相邻的，所以遍历数组比较相邻的数就不难找到。这种方法时间复杂度为O(nlogn)+O(n)=O(nlogn)，需要O(1)的额外的辅助空间。

public int getDuplicate(int[] numbers){
    //这边不再直接写快排算法了，2.4节中再写
    java.util.Arrays.sort(numbers);
    int left=numbers[0],right;
    for(int i=1;i<numbers.length;i++){
        right=numbers[i];
        if(left==right){
            return right;
        }else{
            left=right;
        }
    }
}

2. 使用哈希解决问题

依次向哈希集中插入数组中的数字，如果哈希集中已经有相同的数字则插入失败，返回该数字。这种方法只遍历一次数组时间复杂度为O(n)，但需要平均大小为O(n)的额外的HashSet辅助空间。

//import java.util.HashSet;
public int getDuplicate(int[] numbers){
    HashSet<Integer> set=new HashSet<>();
    for(int i:numbers){
        //如果插入失败则已存在同样的数字，返回
        if(!set.add(i)){
            return i;
        }
    }
}

也可以不使用类库自己构造简单哈希数组boolean[] hash=new boolean[numbers.length];读取到一个数字i就检查hash[i]是否为false，是则设为true并继续循环，否则说明已有相同的数字，返回该数。使用boolean而不是int是因为本题中存储的数字可以直接和数组下标相关联，而哈希数组本身不用再存储数字，使用boolean理论上能节省空间。但是否真的能节省空间需要看虚拟机的实现，这里不展开了。

3. 找寻规律重写排序

长度为n的数组中所有的数都在0~n-1范围内，那么如果数字i不在numbers[i]处就把它和numbers[i]处的数交换，如果发现该数已经和i相等了，则说明重复。在内部的while循环中，每个数字最多只要交换两次就能找到自己的位置（或找到相同的数），所以时间复杂度还是O(n)，空间复杂度为O(1)。

public int getDuplicate(int[] numbers){
    for(int i=0;i<nuumbers.length;i++){
        /*如数组中没有i这个值，则内部一次while循环结束时，
        一定会在[i+1,length-1]这个范围中通过不断两两比较和交换找到相同的数；
        有i这个值则下一次for会继续往后比较，并且后面的一部分数字已经在对应位置上*/
        while(numbers[i]!=i){
            if（numbers[i]==numbers[numbers[i]]）{
                return numbers[i];
            }else{
                //交换，若numbers[i]=t,保证numbers[t]=t
                int temp=numbers[i];
                numbers[i]=numbers[temp];
                numbers[temp]=temp;
            }
        }
    }
}

拓展：限制不能改动数组、不能使用额外O(n)的空间

加上这样的限制的话就需要用时间换空间，给出一种基于二分的思路：对于长度为n的数组，每次遍历数组，统计[0,(n-1)/2]范围内数字出现的次数，若出现次数超过n/2，则该范围内必有重复数字，否则在[(n-1)/2+1,n-1]范围内必然有重复的数。这样就可以逐步将遍历时统计的范围缩小，直至范围缩小为两个差为1的值。每次遍历统计需要O(n)时间，而外部需要调用O(logn)次，总时间复杂度为O(nlogn)。

面试题4：二维数组中的查找

题目描述

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

示例

输入：
目标数10和数组
1   2   8   9
2   4   9   12
4   7   10  13
6   8   11  15
输出：
true

解题思路

既然n行m列都是递增排序的，那么显然不宜使用逐行逐列的暴力搜索，没有利用顺序信息，时间复杂度为O(n*m)。

1. 逐行并对每行进行二分查找

该方法也仅利用了部分顺序信息，时间复杂度为O(nlogm)。

public boolean Find(int target, int [][] array) {
    boolean hasTarget=false;
    for(int i=0;i<array.length;i++){
        if(Arrays.binarySearch(array[i],target)>=0){
            hasTarget=true;
        }
    }
    return hasTarget;
}

2. 按照规律缩小查找范围

从行的角度看，如果行首数字大于目标数，则该行后面不可能存在目标数，否则行首上面的同列元素中也不可能存在目标数； 从列的角度看，如果列首数字大于目标数，则该列后面不可能存在目标数，否则列首左面的同行元素中也不可能存在目标数； 通过该方法不断缩小查找范围，那么自然应当从最大的行首或者列首开始找起，即数组左下角或右上角，时间复杂度为O(m+n)。下面给出从左下角搜索的实现。

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

字符串

在Java中，字符串不是基本类型而是引用类型，其底层也是字符数组。由于字符串在编程时使用的频率很高，且字符串操作需要注意很多细节，所以会经常考查到。

面试题5：替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。

示例

输入：
"We Are Happy"
输出：
"We%20Are%20Happy"

解题思路

1. 使用JDK提供的方法

由于在Java中字符串也是一个对象，提供了丰富的操作方法，可以使用String类自带的方法进行替换。当然这使用了O(n)的额外空间。

public String replaceSpace(StringBuffer str) {
    String a=str.toString();
    String s=a.replace(" ","%20");
    return s;
}

2. 手动处理字符数组

题目的本意是考查对底层字符数组扩容的处理，那么可以遍历数组统计出空格个数，进而计算出要额外申请的空间。再从后往前逐个移动。

public String replaceSpace(StringBuffer str){
    //每遇到一个空格追加两个字符长度
    //也可以统计空格个数再使用str.setlength(int newLength);
    //不能用str.ensureCapacity();
    int initialLength=str.length();
    for(int i=0;i<initialLength;i++){
        if(str.charAt(i)==' ')
            str.append("  ");
    }

    //从后往前移动
    int pointer=str.length()-1;
    System.out.println(pointer);
    for(int i=initialLength-1;i>=0;i--){
        if(str.charAt(i)!=' '){
            str.setCharAt(pointer,str.charAt(i));
            pointer--;
        }else{
            str.setCharAt(pointer,'0');
            str.setCharAt(pointer-1,'2');
            str.setCharAt(pointer-2,'%');
            pointer-=3;
        }
    }
    return str.toString();
}

链表

链表是一种动态数据结构，能在O(1)的时间内完成插入和删除，但访问效率不如数组。链表是一些更复杂的数据结构的构造基础。

面试题6：从尾到头打印链表

题目描述

输入一个链表，按链表从尾到头的顺序打印出来每个节点的值。

解题思路

由于链表只能单向访问，所以需要用一种数据结构暂存访问过的节点，再逆向打印。这一题背后考查的是栈，使用递归调用栈或者迭代存入自己的栈都可以。（当然你也可以使用ArrayList存储遍历到的节点，然后用get(int index)来实现逆序输出）

//import java.util.Stack;
public void printListFromTailToHead(ListNode listNode) {
    Stack<Integer> stack =new Stack<>();
    while(listNode!=null){
        stack.push(listNode.value);
        listNode=listNode.next;
    }
    while(!stack.empty()){
        System.out.println(stack.pop());
    }
}

//递归写法，有StackOverflow风险
public void printListFromTailToHead(ListNode listNode) {
    int val=listNode.value;
    if(listNode.next!=null)
        printListFromTailToHead(listNode.next);
    System.out.println(val);
}

树

树的逻辑很简单：除根节点外每个节点有且仅有1个父节点，根节点没有父节点；除叶子节点外每个节点有1个或多个子节点，叶子节点没有子节点。我们通常在内存中处理数据使用二叉树，在外存中为了提升单次I/O效率使用多叉树（B-树、B+树等）。二叉树的前序、中序、后序以及层次遍历的特性需要我们熟练掌握。

面试题7：重建二叉树

题目描述

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

示例

输入:
前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
输出：
重建后二叉树的根节点

解题思路

二叉树的前序遍历的结果为【根节点】【左子树的前序遍历】【右子树的前序遍历】，而中序遍历的结果为【左子树的前序遍历】【根节点】【右子树的前序遍历】，则可以从前序遍历序列中确定并构造根节点，进而从中序遍历结果中分别确定左右子树，通过递归调用可以得到根节点的左右子节点。

//import java.util.Arrays;
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if (pre.length==0||in.length==0){
        return null;
    }
    TreeNode root=new TreeNode(pre[0]);
    for (int i=0;i<in.length;i++){
        if (in[i]==pre[0]){
            int[] leftPre= Arrays.copyOfRange(pre,1,i+1);
            int[] leftIn=Arrays.copyOfRange(in,0,i);
            int[] rightPre=Arrays.copyOfRange(pre,i+1,pre.length);
            int[] rightIn=Arrays.copyOfRange(in,i+1,in.length);
            root.left=reConstructBinaryTree(leftPre,leftIn);
            root.right=reConstructBinaryTree(rightPre,rightIn);
            break;
        }
    }
    return root;
}

面试题8：二叉树的下一个节点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路

若该节点右子树非空则中序遍历的下一节点为右子树的最左节点，右子树为空则向上寻找直至某一父节点是其父节点的左子树，如果找到最后父节点都不是其父节点的左子树，则没有中序遍历下一节点。

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //该节点右子树非空则中序遍历的下一节点为右子树的最左节点
        if (pNode.right!=null){
            TreeLinkNode cur=pNode.right;
            while (cur.left!=null){
                cur=cur.left;
            }
            return cur;
        }
        //右子树为空则向上寻找直至某一父节点是其父节点的左子树
        while (pNode.next!=null){
            if (pNode.next.left==pNode)
                return pNode.next;
            pNode=pNode.next;
        }
        //如果找到最后父节点都不是其父节点的左子树，则没有中序遍历下一节点
        return null;
    }

栈和队列

两者分别是先进后出和先进先出结构，树的非递归前中后序遍历可以用到栈，层次遍历可以用到队列。

面试题9：用两个栈实现队列

题目描述

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

解题思路

执行队列的Push操作时，只需要压入stack1中即可，不用考虑stack2的状态；而执行队列的Pop操作时，如果stack2为空则需要依次弹出stack1中的内容并压入stack2之后再从stack2弹出，如果stack2不为空则直接弹出即可。这样保证了stack2栈顶永远是最早进入的元素，而stack1栈顶永远是最晚进入的元素。

public class Stack2Queue {
    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.empty())
            return stack2.pop();
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

拓展：用两个队列实现一个栈

解题思路

使用一个队列作为缓冲，根据一个布尔值标记当前使用的缓冲队列。每次入栈时，直接插入到该缓冲队列尾即可；每次出栈时，将当前使用的缓冲队列中的值（除了队尾的最后一次插入的）转移到另一条队列中，这时就能弹出最后一次插入的值，最后将另一条队列标记为当前使用的缓冲队列。

public class Queue2Stack {
    Queue<Integer> queue1=new LinkedList<>();
    Queue<Integer> queue2=new LinkedList<>();
    boolean useQ1AsTemp=true;

    public void push(int node) {
        if (useQ1AsTemp) {
            queue1.offer(node);
        } else {
            queue2.offer(node);
        } 
    }
    
    public int pop() {
        if (useQ1AsTemp) {
            while (queue1.size() > 1) {
                queue2.offer(queue1.poll());
            }
            useQ1AsTemp=false;
            return queue1.poll();
        } else {
            while (queue2.size() > 1) {
                queue1.offer(queue2.poll());
            }
            useQ1AsTemp=true;
            return queue2.poll();
        } 
    }
}