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

数组

数据结构分析

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

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

数组题型多种多样,这里举一个比较典型的例子,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();
}