常用数据结构

1 数组、字符串【Array、String】

1.1 字符串转化

数组和字符串是最基本的数据结构，在很多编程语言中都有着十分相似的性质，而围绕着它们的算法面试题也是最多的。

很多时候，在分析字符串相关面试题的过程中，我们往往要针对字符串当中的每一个字符进行分析和处理，甚至有时候我们得先 把给定的字符串转换成字符数组 之后再进行分析和处理。

举例：翻转字符串“algorithm”。

解法：用两个指针，一个指向字符串的第一个字符a，一个指向它的最后一个字符m，然后互相交换。交换之后，两个指针向中央一步步地靠拢并相互交换字符，直到两个指针相遇。这是一种比较快速和直观的方法。...

//翻转字符串“algorithm”
int main()
{
    char temp,a[] = "algorithm";
    int i,j,length = strlen(a);
    temp = NULL;
    i = 0;
    j = length - 1;
    while(i != j)
    {
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
        j--;
    }
    for(i = 0;i < length;i++)
    {
        printf("%c\t",a[i]);
    }
    return 0;
}

1.2数组的优缺点

数组的优点在于：

构建非常简单

能在O(1)的时间里根据数组的下标（index）查询某个元素

而数组的缺点在于：

构建时必须分配一段连续的空间

查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数）

删除和添加某个元素时，同样需要耗费 O(n) 的时间

1.3【242】有效的字母异位词

字母异位词：

也就是两个字符串中的相同字符的数量要对应相等。例如，s等于“anagram”，t等于“nagaram”，s和t就互为字母异位词。因为它们都包含有三个字符a，一个字符g，一个字符 m，一个字符 n，以及一个字符 r。而当 s 为 “rat”，t 为 “car”的时候，s 和 t 不互为字母异位词。

解题思路：

一个重要的前提“假设两个字符串只包含小写字母”，小写字母一共也就26个，因此：

知识点： 哈希映射

可以利用两个长度都为26的字符数组来统计每个字符串中小写字母出现的次数，然后再对比是否相等；

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isAnagram(char * s, char * t)
{
    //判断两个字符串长度是否相等，不相等则直接返回 false
    if(strlen(s) != strlen(t))
        return 0;
    //若相等，则初始化 26 个字母哈希表，遍历字符串 s 和 t
    int A[26] = {0},B[26] = {0};  //哈希映射
    int i;
    while(*s != '\0')
    {
        A[*s - 'a']++;
        B[*t - 'a']++;
        s++;
        t++;
    }
    //判断两个表是否相同
    for(i = 0; i < 26; i++)
    {
        if(A[i] != B[i])
            return 0;
    }
    return 1;
}
int main()
{
    char b[] = "nagaram",a[] = "anagram";
    if(isAnagram(a,b) != 0)
        printf("True");
    else
        printf("False");
    return 0;
}

可以只利用一个长度为 26 的字符数组，将出现在字符串 s 里的字符个数加 1，而出现在字符串 t 里的字符个数减 1，最后判断每个小写字母的个数是否都为 0。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isAnagram(char * s, char * t)
{
    //判断两个字符串长度是否相等，不相等则直接返回 false
    if(strlen(s) != strlen(t))
        return 0;
    //若相等，则初始化 26 个字母哈希表，遍历字符串 s 和 t
    int A[26] = {0};  //哈希映射
    int i;
    while(*s != '\0\)
    {
        //s 负责在对应位置增加，t 负责在对应位置减少
        A[*s - 'a']++;
        A[*t - 'a']--;
        s++;
        t++;
    }
    //如果哈希表的值都为 0，则二者是字母异位词
    for(i = 0; i < 26; i++)
    {
        if(A[i] != 0)
            return 0;
    }
    return 1;
}
int main()
{
    char b[] = "nagaram",a[] = "anagram";
    if(isAnagram(a,b) != 0)
        printf("True");
    else
        printf("False");
    return 0;
}

2 链表（LinkedList）

单链表：链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。

双链表：与单链表不同的是，双链表的每个结点中都含有两个引用字段。

2.1链表的优缺点

链表的优点如下：

链表能灵活地分配内存空间；

能在O(1)时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在 O(1) 时间内删除或者添加该元素。

链表的缺点是：

不像数组能通过下标迅速读取元素，每次都要从链表头开始一个一个读取；

查询第 k 个元素需要 O(k) 时间。

2.2 应用场景

如果要解决的问题里面需要很多快速查询，链表可能并不适合；如果遇到的问题中，数据的元素个数不确定，而且需要经常进行数据的添加和删除，那么链表会比较合适。而如果数据元素大小确定，删除插入的操作并

不多，那么数组可能更适合。

2.3 经典解法

2.3.1 利用快慢指针（有时候需要用到三个指针）

典型题目例如：链表的翻转，寻找倒数第k个元素，寻找链表中间位置的元素，判断链表是否有环等等。

2.3.2 .构建一个虚假的链表头

一般用在要返回新的链表的题目中，比如，给定两个排好序的链表，要求将它们整合在一起并排好序。又比如，将一个链表中的奇数和偶数按照原定的顺序分开后重新组合成一个新的链表，链表的头一半是奇数，后一半是偶数。

在这类问题里，如果不用一个虚假的链表头，那么在创建新链表的第一个元素时，我们都得要判断一下链表的头指针是否为空，也就是要多写一条ifelse语句。比较简洁的写法是创建一个空的链表头，直接往其后面

添加元素即可，最后返回这个空的链表头的下一个节点即可。

建议：在解决链表的题目时，可以在纸上或者白板上画出节点之间的相互关系，然后画出修改的方法

2.4 【25】K个一组翻转链表

解题思路：

参考： https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/kge-yi-zu-fan-zhuan-lian-biao-by-powcai/

这道题考察了两个知识点：

对链表翻转算法是否熟悉

对递归算法的理解是否清晰

在翻转链表的时候，可以借助三个指针：prev、curr、next，分别代表前一个节点、当前节点和下一个节点，实现过程如下所示：

【递归】方法1：

• 1、找到待翻转的k个节点（注意：若剩余数量小于k的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
• 2、对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭又开区间，所以本轮操作的尾结点其实就是下一轮操作的头结点）。
• 3、对下一轮k个节点也进行翻转操作。
• 4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct slist
{
    int data;
    struct slist *next;
};
struct slist *reverse(struct slist *head,struct slist *tail)
{
    struct slist *pre = NULL;
    struct slist *next = NULL;
    while(head != tail)
    {
        next = head ->next;
        head ->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
struct slist *reverseKGroup(struct slist* head, int k)
{
    if(head == NULL || head ->next == NULL)
        return head;
    struct slist *newHead,*tail = head;
    int i;
    for(i = 0;i < k;i++)
    {
        //剩余数量小于k的话，不需要反转
        if(tail == NULL)
            return head;
        tail = tail ->next;
    }
    //反转前K个元素
    newHead = reverse(head,tail);
    //下一轮的开始的地方就是tail
    head ->next = reverseKGroup(tail,k);

    return newHead;
}

void input(struct slist *head)
{
    struct slist *p = head ->next; //p是工作指针
    while(p != NULL)
    {
        printf("%d\t",p ->data);
        p = p ->next;
    }
}
void create(struct slist *head)
{
    //尾插法建立单链表
    struct slist *r,*temp; //r是尾指针，temp是临时结点
    int i,x;
    r = head;
    printf("请输入元素：\n");
    scanf("%d",&x);
    while(x != 9999)
    {
        temp = (struct slist *)malloc(sizeof(struct slist));
        temp ->data = x;
        temp ->next = r ->next;
        r ->next = temp;
        r = temp;
        scanf("%d",&x);
    }
}
int main()
{
    struct slist *head;//head是头结点

    head = (struct slist *)malloc(sizeof(struct slist));
    head ->next = NULL;
    create(head);
    input(head);

    int k;
    printf("\n请输入K：");
    scanf("%d",&k);
    head ->next= reverseKGroup(head ->next,k);
    input(head);

    return 0;
}

【递归】方法2：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct slist
{
    int data;
    struct slist *next;
};
struct slist *reverseKGroup(struct slist* head, int k)
{
    struct slist *cur = head;
    int count = 0;
    // 找到待翻转的k个节点
    while(cur != NULL && count != k)
    {
        cur = cur ->next;
        count++;
    }
    if(count == k)
    {
        cur = reverseKGroup(cur,k);
        while(count != 0)
        {
            count--;
            struct slist *tmp = head ->next;
            head ->next = cur;
            cur = head;
            head = tmp;
        }
        head = cur;
    }
    //若剩余数量小于k的话，则不需要反转，因此直接返回待翻转部分的头结点即可
    return head;  //head为头指针
}

void input(struct slist *head)
{
    struct slist *p = head ->next; //p是工作指针
    while(p != NULL)
    {
        printf("%d\t",p ->data);
        p = p ->next;
    }
}
void create(struct slist *head)
{
    //尾插法建立单链表
    struct slist *r,*temp; //r是尾指针，temp是临时结点
    int i,x;
    r = head;
    printf("请输入元素：\n");
    scanf("%d",&x);
    while(x != 9999)
    {
        temp = (struct slist *)malloc(sizeof(struct slist));
        temp ->data = x;
        temp ->next = r ->next;
        r ->next = temp;
        r = temp;
        scanf("%d",&x);
    }
}
int main()
{
    struct slist *head;//head是头结点

    head = (struct slist *)malloc(sizeof(struct slist));
    head ->next = NULL;
    create(head);
    input(head);

    int k;
    printf("\n请输入K：");
    scanf("%d",&k);
    head ->next= reverseKGroup(head ->next,k);
    input(head);

    return 0;
}

3 栈（Stack）

3.1 特点

栈的最大特点就是后进先出（LIFO）。对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以查看栈顶部的元素，只能够向栈的顶部压⼊数据，也只能从栈的顶部弹出数据。

3.2 实现

利用一个单链表来实现栈的数据结构。而且，因为我们都只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在O(1)的时间内完成。

3.3 应用场景

在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。

如果打算用一个数组外加一个指针来实现相似的效果，那么，一旦数组的长度发生了改变，哪怕只是在最后添加一个新的元素，时间复杂度都不再是 O(1)，而且，空间复杂度也得不到优化。

3.4 【 20】有效的括号

解题思路

利用一个栈，不断地往里压左括号，一旦遇上了一个右括号，我们就把栈顶的左括号弹出来，表示这是一个合法的组合，以此类推，直到最后判断栈里还有没有左括号剩余。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max 20
#define Stack char
int isValid(char * p)
{
    int len=strlen(p);

    if(len == 1)
        return 0;
    int top=1,i;
    Stack s[Max];  //堆栈存储
    for(i=0; i<len; i++)
    {
        switch(p[i])
        {
        case '(':
        case '[':
        case '{':
            s[top++]=p[i];  //进栈
            break;
        case ')':
            if(s[top-1]=='(')
                top--;  //出栈
            else return 0;
            break;
        case ']':
            if(s[top-1]=='[')
                top--;  //出栈
            else return 0;
            break;
        case '}':
            if(s[top-1]=='{')
                top--;//出栈
            else return 0;
            break;
        }
    }
    if(top==0)
        return 1;  //输出1表示匹配成功
    else
        return 0;   //输出0表示匹配失败
}
int main()
{
    char s[Max];
    printf("请输入括号:");
    scanf("%s",s);

    if(isValid(s) != 0)
        printf("true");
    else
        printf("false");
    return 0;
}

3.5【739】每日温度

方法一：从左到右依次遍历  O(n^2)

针对每个温度值 向后进行依次搜索 ，找到比当前温度更高的值，这是最容易想到的办法。

其原理： 从左到右除了最后一个数其他所有的数都遍历一次 ，最后一个数据对应的结果肯定是 0，就不需要计算。

遍历的时候，每个数都去向后数，直到找到比它大的数，数的次数就是对应输出的值。

#include <stdio.h>
#include <stdlib.h>

void dailyTemperatures(int* T, int TSize){
    int i,j,result[TSize];
    for(i = 0;i < TSize;i++)
    {
        int cur = T[i];
        if(cur < 100)
        {
            for(j = i+1;j < TSize;j++)
            {
                if(T[j] > cur)
                {
                    result[i] = j - i;
                    break;
                }
            }
            if(j == TSize)
                result[i] = 0;
        }
    }
    for(i = 0;i < TSize;i++)
    {
        printf("%d\t",result[i]);
    }
}
int main()
{
    int length,T[] = {73, 65, 85, 71, 69, 72, 76, 79};
    length = sizeof(T) / sizeof(T[0]);
    dailyTemperatures(T,length);
    return 0;
}

//LeetCode可以通过，但超时，因为时间复杂度为O(2^2)
int* dailyTemperatures(int* T, int TSize,int* returnSize){
    int i,j;
    int *result = malloc(sizeof(int)*TSize);  //动态数组
    *returnSize = TSize;
    for(i = 0;i < TSize;i++)
    {
        int cur = T[i];
        if(cur <= 100)
        {
            for(j = i+1;j < TSize;j++)
            {
                if(T[j] > cur)
                {
                    result[i] = j - i;
                    break;
                }
            } 
            //若之后不再升高，则为0
            if(j == TSize)
                result[i] = 0;
        }
    }
    return result;
}

方法二：从右到左依次遍历

关键是要减少为每个数寻找值遍历次数。如下图所示，绿色部分区域会给多次遍历， 如果我们能减少这部分区域的遍历次数，就能整体提高运算效率。

如果我们先从计算右边，那么我们计算过的位置就不需要重复计算，如图所示：

当前我们需要计算 7575 位置，然后向右遍历到 7171，因为我们已经计算好了 7171 位置对应的值为 22，那么我们就可以直接跳 22 为在进行比较，利用了已经有的结果，减少了遍历的次数。

#include <stdio.h>
#include <stdlib.h>

void dailyTemperatures(int* T, int TSize)
{
    int i,j;
    int *result = malloc(sizeof(int)*TSize);  //动态数组
    //从右向左遍历
    result[TSize - 1] = 0; //最后一个一定为0
    for(i = TSize - 2; i >= 0; i--)
    {
        // j+= result[j]是利用已经有的结果进行跳跃
        for(j = i+1; j < TSize; j+=result[j])
        {
            if(T[j] > T[i])
            {
                result[i] = j - i;
                break;
            }
            //遇到0表示后面不会有更大的值，那当然当前值就应该也为0
            else if(result[j] == 0)
            {
                result[i] = 0;
                break;
            }
        }
    }
    for(i = 0; i < TSize; i++)
    {
        printf("%d\t",result[i]);
    }
}
int main()
{
    int length,T[] = {73, 65, 85, 71, 69, 72, 76, 79};
    length = sizeof(T) / sizeof(T[0]);
    dailyTemperatures(T,length);
    return 0;
}

方法三：堆栈    O(n)

可以运用一个堆栈 stack 来快速地知道需要经过多少天就能等到温度升高。从头到尾扫描一遍给定的数组 T，如果当天的温度比堆栈 stack 顶端所记录的那天温度还要高，那么就能得到结果。

• 对第一个温度23度，堆栈为空，把它的下标压入堆栈；
• 下一个温度24度，高于23度高，因此23度温度升高只需1天时间，把23度下标从堆栈里弹出，把24度下标压入；
• 同样，从24度只需要1天时间升高到25度；
• 21度低于25度，直接把21度下标压入堆栈；
• 19度低于21度，压入堆栈；
• 22度高于19度，从19度升温只需1天从 21 度升温需要 2 天；
• 由于堆栈里保存的是下标，能很快计算天数；
• 22 度低于 25 度，意味着尚未找到 25 度之后的升温，直接把 22 度下标压入堆栈顶端；
• 后面的温度与此同理。

该方法只需要对数组进行一次遍历，每个元素最多被压入和弹出堆栈一次，算法复杂度是 O(n)。

利用堆栈，还可以解决如下常见问题：

• 求解算术表达式的结果（LeetCode 224、227、772、770)
• 求解直方图里最大的矩形区域（LeetCode 84）