基础数据结构

本文分析包括数组（字符串）、链表、队列（双端队列）、栈和树的简要分析和解题思路

数组

数据结构分析

数组是一个非常常见且基础的数据结构，且在不同的编程语言中都有着很相似的性质，而围绕着他们的算法面试题也是最多的；很多时候，在分析数组（字符串）相关面试题的时候，我们往往要针对数组（字符串）中的每一个元素（字符）进行处理

在对这种题型的分析中，我们很可能需要把字符串转换成字符数组或字符串数组，通过使用数组的特性，而去操作字符串本身

数组题型多种多样，这里举一个比较典型的例子，Leetcode-344-反转字符串

这个题目规定了，我们需要原地修改数组，使用O(1)的额外空间解决问题，其实意思就是说，我需要使用一个临时变量，而不是一个同等大小的数组，通过循环反向放入构建而成

当读懂了题目，我们很容易能得到思路
既然不能使用另外的数组，那我们就通过交换头尾相对应的元素来完成；
我们可以使用一个指针指向第一个元素，从最前向后移动；
使用第二个指针指向最后一个元素，从最后向前移动；
两个指针的元素分别通过一个临时变量进行交换；
当两个指针指向同一个数，或者第二个指针指向的是第一个指针前边的数，则代表我们完成了本次反转

示例代码如下

public void reverseString(char[] s) {
    /*
     * 必须说明，这个题目给的参数为char[]，如果是String s，则可以通过
     * s.toCharArray() 将字符串转换成字符数组
    */
    int sLen = s.length;

    for(int left=0, right=sLen-1; left<right; left++, right--){
        char temp = s[right];
        s[right] = s[left];
        s[left] = temp;
    }
}

这道题目我们规定了两个指针，而这种解题思路又被称为双指针，Leetcode可以通过"双指针"这个标签实现专项练习，点我查看例题

数据结构总结

至此，我们可以总结一下数组这种数据结构的优点
首先是优点

• 构建一个数组非常简单
• 能让我们在O(1)的时间里根据数组的下标（index）查询某个元素

然后是缺点

• 构建时必须分配一段连续的空间
• 查询某个元素是否存在时需要遍历整个数组，耗费O(n)的时间（其中，n是元素的个数）
• 删除和添加某个元素时，同样需要耗费O(n)的时间

在选择数据结构去辅助你的算法的时候，一定要充分考虑这个数据结构的缺点能不能接受，比如快速查询元素是个非常棒的特性，但是时间复杂度O(n)删除和增加操作很多时候是不能接受的，也就是说，如果你的算法需要你对元素进行随机的删除，增加等，则一定要慎重选择数组作为辅助数据结构，对于其他的数据结构也是一个道理。

例题

最后，让我们看看数组题目中，比较常见难度的题目，LeetCode-242-有效的字母异位词

如果对字符和排序比较敏感，你就能知道，char这个基本数据类型，在ASCII编码中都是各个固定的数值，都是一个整数，即使用’b’-‘a’，就等于1，同理’c’-‘a’=2，所以，看到这个题目可以想到，是否可以把字符串转换成char数组，然后对char数组排序，排序之后的char数组转换成字符串再对比一下就可以了；

这个思路很正确，Java中也提供了相应的sort排序方法，但是我们要考虑，排序方法中，最快的排序时间复杂度是O(nlogn)，这个题目是不是可以冲一冲O(n)的时间复杂度呢

那么这时候我们换一个思路

即我们知道字母只有26个，则我们可以通过一个长度为26的int[]来保存字母出现的次数，数组的下标即代表是第几个字母，如int[0]为a，int[1]为b；

这样我们可以先把第一个字符串按照一个一个的字符，统计各个字符出现的频次，比如第一个字符为"aabbcceezz"，则我们使用int数组是可得int[0]=2,int[1]=2;int[2]=2,int[4]=2,int[25]=2;

扫描完之后我们再按照同样的方法去扫描第二个字符串，和刚刚的思路相反，之前每次统计频次是次数+1，现在我们要-1，比如我们第二个字符串为"ccaabbeezz"，则我扫描第一个之后，c相应的次数就-1，即扫描第一个字符后，int[2]=1，这样如果两个字符串相等，则每个下标相应的元素都应该被减成0；

当如果第二个字符和第一个字符不一样的时候，则必定会出现一个字母，相应下标-1之后小于0，这时候就代表两个字符串不相等，我们也只需要考虑这种不同的情况

示例代码

/**
 * 代码中出现了很多直接通过下标取数据的操作，这时候实际是使用了
 * 数组根据下标查询的时间复杂度为O(1)，这么写单纯是为了代码可读
 * 性，实际上不要这么写
 */
public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();

        int[] nums = new int[26];

        for(int i=0; i<sChars.length; i++){
            nums[sChars[i]-'a'] = nums[sChars[i]-'a']+1;
        }
        for(int j=0; j<tChars.length; j++){
            nums[tChars[j]-'a'] = nums[tChars[j]-'a']-1;
            if(nums[tChars[j]-'a'] < 0){
                return false;
            }
        }

        return true;
    }

链表

在LeetCode中，题库第一个简单题之后就是一个中等难度的链表题目，很多同志连构建方法都没搞懂就卡在了第二道题，很像是背了四年单词，只背到了abandon

数据结构分析

链表分为单链表和双链表；
单链表是指链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起，即每一个元素的引用区域，指向下一个元素；

而双链表是指，双链表的每个结点中都含有两个引用字段，即一个元素的后引用区域指向下一个元素，或者后一个元素的前引用区域指向上一个元素；

而这种引用指向的结构可以想到，它其实是为了解决数组的一个缺点，即需要申请一块连续的空间；但同时，链表也失去了数组通过下标快速查询的能力

数据结构总结

根据这个结构，我们可以总结一下链表的优缺点
首先是优点

• 链表可以灵活的分配内存空间
• 链表能在O(1)的时间复杂度下删除或添加元素（对于单链表，是前一个元素已知；对于双链表，是后一个元素已知的情况下才是O(1)的时间复杂度）

然后是缺点

• 链表查询元素需要O(n)的时间复杂度（即每次查询都要从头开始一个一个的查）

那么根据优缺点，我们就能看出链表和数组的不同，这让他们也有了不同的使用场景，比如当你的算法中，元素的个数不确定，又有很多的删除添加操作，则应该使用链表；如果你的算法中元素个数确定，大部分的操作都是查询，没什么删除添加操作，则选择数组更好。

根据数据结构的特性，可以归为一下几种链表类的题型和解题技巧

• 利用快慢指针（有时候需要用到三个指针）
  • 反转链表
  • 倒数第k个元素
  • 寻找列表中中间位置的元素
  • 判断列表是否有环
  • ···
• 构建一个虚假链表头，常用于返回新的链表时（如果不使用虚假的链表头，则每次构建都要增加一个if-else去判断链表头是否为空，如果有一个虚假链表头，则只需要不断往后增加元素，最后返回的时候去掉这个假的链表头即可）
  • 两个排序链表，进行整合排序
  • 将链表的奇偶数按原定顺序分离，生成前半部分奇数，后半部分偶数的链表

常见题型

• 题型
  • 单链表反转
  • 链表中环的检测
  • 两个有序链表合并
  • 删除链表倒数第n个节点
  • 求链表的中间节点
• 要注意的边界条件
  • 如果链表为空
  • 如果链表只包含一个节点
  • 如果链表只包含两个节点
  • 代码逻辑在处理头结点和尾节点的时候，能否正常工作

使用链表的时候，可以在纸上画出链表结点的相应关系，链表相对来说已经比较抽象，所以画出修改的方法也有助于自己的理解

从链表的题型来看，尤其是像K个一组，或者按顺序合并链表等的操作中，可以明显看出链表的很多操作都是同一种类型的操作，只是将这种操作重复了好多次，所以链表的很多题型，都可以使用递归的思想进行，这篇文章就讲个几个比较常见的链表使用递归思想的题目

例题

接下来我们看一道例题，LeetCode-25-K个一组，翻转链表

示例代码

public ListNode reverseKGroup(ListNode head, int k) {
    int j = k;
    ListNode next = null;
    ListNode prev = null;
    ListNode curr = head;

    int l = k;
    ListNode test = head;

    while(test != null && l>0){
        test = test.next;
        l--;
    }

    if(test == null && l != 0){
        return head;
    }

    while(curr != null && j>0){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        j--;
    }

    if(curr == null && j != 0){
        return prev;
    }

    head.next = reverseKGroup(curr, k);

    return prev;
}

在这个题目中，最重要的部分就是

while(curr != null && j>0){
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
    j--;
}

这段代码是所有翻转链表都会用到的，只要记住这段代码，翻转链表类的题目就不是问题

栈

数据结构分析

栈是LeetCode题目中中等难度偏上时经常会使用到的数据结构。

栈的最大特点就是后进先出（LIFO），对于栈来说，所有的操作都是在栈的顶部完成的，所以实际上对栈的数据操作只有三个

1. 查看栈顶部的元素
2. 向栈顶部压入元素
3. 从栈顶部弹出元素

这里其实可以看一下Java容器Stack的源代码，也是只有这么几个操作

public class Stack<E> extends Vector<E> {
    //构造方法
    public Stack() {
    }

    /**
     * 将元素从栈的顶部压入，并将压入的元素作为值返回
     */
    public E push(E item) {
        addElement(item);

        return item;
    }

    /**
     * 弹出栈顶部的元素，并将弹出的元素作为值返回
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * 查看栈顶部的元素，注意和pop区分，peek方法并不会移除顶部元素
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * 判断堆栈是否为空
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * 返回对象在堆栈中的位置，以 1 为基数
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

看完这段代码有的同志们可能就发现了，虽然方法就只有这么几个，但是想peek，pop这种操作，实际上使用的方法是继承自Vector的方法，这里就要牵扯出接下来的概念：

即构建一个栈，应该是使用数组还是链表，大概思考一下就知道，这两种方法实现栈这种数据结构并不难，具体的实现方法可以看这里。
用数组实现的栈，称为顺序栈；用链表实现的栈，称为链式栈；
因为Java的Stack实现自Vector，而Vector是一个动态数组，所以我们可以认为Java自带的Stack是一个顺序栈，可能这时候你已经想到了，数组实现的栈有一个很大的问题；
就是当数组容量已经用完，但是又需要入栈的时候，按照数组动态扩容，是需要申请一个更大的内存做一个容量更大的数组，然后将现有的元素全部放进新的数组，这个扩容的过程岂不是又用了O(n)的时间复杂度？

但是如果用均摊分析法来考虑，有很多很多很多元素需要入栈的时候，如果我们按照每次增加两倍的方法去扩容数组，那个O(1)时间复杂度的入栈操作比O(n)时间复杂度的扩容操作要多得多，所以平均下来，时间复杂度还是O(1)，即不论如何，栈的入栈操作，时间复杂度都是O(1)

数据结构总结

那么我们什么时候需要用到栈呢？

很明显，当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

非常典型的用法

这里可以讲个题外话，就是浏览器左上角的前进后退按钮，这种前进后退的操作，其实就可以用栈来操作；

我可以构建两个栈，当新页面产生的时候就push进去，点了后退就pop栈顶url，然后把这个pop的值push进另一个栈，这样点击前进的时候就可以把第二个栈的栈顶元素pop出来到第一个栈，完美实现前进后退功能；

例题

LeetCode-20-有效的括号

示例代码

/**
 * 这里先用hash表存一下({[代码就不会显得这么蠢
 * 这样写比较容易懂，将就一下吧
 */
public boolean isValid(String s) {
    if(s.length()%2 != 0){
        return false;
    }
    Stack<String> stringStack = new Stack<String>();
    String[] strings = s.split("");

    if("}".equals(strings[0]) || "]".equals(strings[0]) || ")".equals(strings[0])){
        return false;
    }

    for(String l : strings){
        if(stringStack.isEmpty()){
            stringStack.push(l);
        }else{
            if(("}".equals(l) && "{".equals(stringStack.peek()))
               || ("]".equals(l) && "[".equals(stringStack.peek()))
               || (")".equals(l) && "(".equals(stringStack.peek()))){

                stringStack.pop();
            }else{
                stringStack.push(l);
            }
        }
    }

    return stringStack.isEmpty();
}