数据结构与算法 - 栈应用

这篇文章主要罗列一些常见的算法题,涉及到栈的使用等。

进制转换

将不同进制的数转化为十进制的数并输出

首先我们以八进制转十进制为例,八进制原理是逢八就进一,所以八进制10代表的是十进制的8,11代表的是9 = 8^1+1 ,所以9除以8=1余1这就是我们对进制转换的核心逻辑所在:除8取余法

由于我们的操作步骤和读书步骤是相反的即八进制的797转为10进制就是1435,所以我们使用栈的结构来处理,因为栈是先进后出,只要余数陆续进栈再出栈就是我们想要的数。

void conversion(int N){

    SqStack S;
    SElemType e;
    //1.初始化一个空栈S
    InitStack(&S);

    //2.每次取余数直到结果为0为止,把每次的余数进栈
    while (N) {
        PushData(&S, N%8);
        N = N/8;
    }

    //3.出栈得到我们想要的十进制数据
    while (!StackEmpty(S)) {
        Pop(&S, &e);
        printf("%d\n",e);
    }
}

二进制以及十六进制也一样,除8改为相应的进制数即可,这里要注意十六进制的字母的问题即可,具体你可以下去尝试写写。

每日温度

这道理来自 LeetCode -739

根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

暴力法

暴力法很容易想到,从第一个元素开始依次跟后面的每个元素进行比较。

int  *dailyTemperatures_1(int* T, int TSize, int* returnSize){

    int *result = (int *)malloc(sizeof(int) * TSize);
    *returnSize = TSize;
    result[TSize-1] = 0;

    for(int i = 0;i < TSize-1;i++)
        if(i>0 && T[i] == T[i-1])
            result[i] = result[i-1] == 0?0:result[i-1]-1;
        else{
            for (int j = i+1; j < TSize; j++) {
                if(T[j] > T[i]){
                    result[i] = j-i;
                    break;
                }
                if (j == TSize-1) {
                    result[i] = 0;
                }
            }
        }

    return result;
}

倒序跳跃法

倒序的来进行对比的话就可以省略部分的比较,比如当我们已经知道71那天的温度会在2天之后变大,而75又大于71,那么中间的71和69就可以忽略,直接可以从比71大的第一天开始遍历即可,数据量大的情况下时间优化还是很大的。

  1. 从右到左遍历. 因为最后一天的气温不会再升高,默认等于0
  2. i 从[TSize-2,0]; 从倒数第二天开始遍历比较. 每次减一
  3. j 从[i+1,TSize]遍历, j+=result[j],可以利用已经有结果的位置进行跳跃,从而减少遍历次数
    1. 若T[i]<T[j],那么result = j - i
    2. 若reuslt[j] == 0,则表示后面不会有更大的值,那么当前值就应该也是0
int  *dailyTemperatures_2(int* T, int TSize, int* returnSize){

    int *result = (int *)malloc(sizeof(int) * TSize);
    *returnSize = TSize;
    result[TSize-1] = 0;

    for (int i=TSize-2; i >= 0; i--) {
        for (int j = i+1; j < TSize; j+=result[j]) {
            if (T[i] < T[j]) {
                result[i] = j-i;
                break;
            }else
            {
                if (result[j] == 0) {
                    result[i] = 0;
                    break;
                }
            }
        }
    }

    return result;
}

单调递减栈

  1. 初始化一个栈,栈中存储的是元素的索引值index

  2. 遍历整个温度数组从[0,TSize]

    1. 如果当前的栈为空,则直接入栈
    2. 如果当前的元素小于栈顶元素,则入栈
    3. 如果栈顶元素<当前元素,则将当前元素索引index-栈顶元素index,计算完毕则将当前栈顶元素移除,将当前元素索引index 存储到栈中; 出栈后,只要栈不为空.继续比较,直到栈顶元素不能满足T[i] > T[stack_index[top-1]]
    4. while循环结束后,当前元素也需要入栈
intdailyTemperatures_3(int* T, int TSize, int* returnSize) {

    int* result = (int*)malloc(sizeof(int)*TSize);
    // 用栈记录T的下标。
    int* stack_index = malloc(sizeof(int)*TSize);
    *returnSize = TSize;
    // 栈顶指针。
    int top = 0;
    int tIndex;

    for (int i = 0; i < TSize; i++)
        result[i] = 0;

    for (int i = 0; i < TSize; i++) {
        // 若当前元素大于栈顶元素,栈顶元素出栈。即温度升高了,所求天数为两者下标的差值。
        while (top > 0 && T[i] > T[stack_index[top-1]]) {
            tIndex = stack_index[top-1];
            result[tIndex] = i - tIndex;
            top--;
        }

        // 当前元素入栈。
        stack_index[top] = i;
        top++;
    }

    return result;
}

集中方案的具体效率如何,我在LeetCode上的测试结果如下:

每一个方法都有优劣之分,不能单纯的以一个维度去考虑,具体情况还要结合实际的应用场景。

括号匹配

假设表达式中允许包含两种括号:圆括号 和 方括号 ,他们嵌套顺序随意,但是要求每一个括号都是一一对应的,就像我们写代码的各种if判断的花括号一样,所以([][()])[([][])] 都是正确的 ,而 [(]((])) 都是错误的,如何判断某个表达式是否合法?

当我们碰到字符串的匹配以及来回比较的时候,我们可以考虑使用栈的数据结构:碰到左括号入栈,碰到右括号就出栈,如果最终栈为空说明是一一配对的,否则不合法:

 1// 括号匹配
2Status IsCorrect(char *string) {
3    Stack S;
4    InitStack(&S);
5
6    int i = 0;
7    char temp = string[0];
8    while (temp) {
9        printf("string is %c \n",temp);
10        if (temp == '[') {
11            PushData(&S, '[');
12        } else if (temp == '(') {
13            PushData(&S, '(');
14        } else if (temp == ')') {
15            char top;
16            GetTop(S, &top);
17            if (top == '(') {
18                Pop(&S, &top);
19            } else {
20                PushData(&S, ')');
21                // return FALSE;
22            }
23        } else if (temp == ']') {
24            char top;
25            GetTop(S, &top);
26            if (top == '[') {
27                Pop(&S, &top);
28            } else {
29                PushData(&S, ']');
30                // return FALSE;
31            }
32        }
33        i ++;
34        temp = string[i];
35    }
36
37    return IsEmpty(S)?SUCCESS:FALSE;
38}

这里所写的代码是把所有的字符串都过一遍,最终判断栈是否为空,其实上面 21 行 和 30 行 都可以进行优化,如果加右边括号的时候,只要判断栈顶不是左边相匹配的括号即可判断非法,这样可能尽快的结束任务。

杨辉三角

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

1
2
3
4
5
6
7
8
9
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

这道题来自 Leetcode - 118 ,从给的实例我们就可以看出结果是要我们输出一个二维数组,然后每一行的第一个元素和最后一个元素都是1,初次之外 arr[i][j] = arr[i-1][j-1]+arr[i-1][j] 以此类推:

int** generate(int numRows, int* returnSize){
    *returnSize = numRows;
    int **res = (int **)malloc(sizeof(int*)*numRows);
    for (int i = 0; i < numRows; i++) {
        res[i] = (int *)malloc(sizeof(int)*(i+1));
        res[i][0] = 1;
        res[i][i] = 1;

        for (int j = 1; j < i; j++) {
            res[i][j] = res[i-1][j] + res[i-1][j-1];
        }
    }
    return res;
}

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数

这道题来自于LeetCode - 70,其实主要考的是动态规划和递归思想。

递归

递归法就是我们首先要找到我们想要的结果,往前推依次拆分,比如这道题可以这么思考,我们爬到n阶只有两种方式

  • n-1 阶爬 1 个台阶
  • n-2 阶爬 2个台阶

那么问题就简化了 f(n) = f(n-1)+f(n-2) 而且我们知道 f(1) = 1 ,f(2) = 2 那么递归的出口有了那么代码就容易了:

int ClimbStairs(int n){
    if (n<1)  return 0;
    if (n == 1return 1;
    if (n == 2return 2;
    return ClimbStairs(n-1) + ClimbStairs(n-2);
}

动态规划

其实个人的理解很简答,递归就是自上而下,而动态规划是自下而上,最终动态规划都转变为由循环迭代完成计算。

对比上面的递归,动态规划的思路就是:而且我们知道 f(1) = 1 ,f(2) = 2 那么 f(3) = f(1)+f(2) 紧接着 f(4) = f(3)+f(2)…..直到我们想到达的n 为止。这就是动态规划,乍看一眼,这不是跟递归的思路一样的吗,其实差不多,上面不是说了吗,一个自顶而下一个自底而上,话不多说,看代码就知道区别所在了。

int ClimbStairs(int n){
    if(n==1return 1;
    int temp = n+1;
    int *sum = (int *)malloc(sizeof(int) * (temp));
    sum[0] = 0;
    sum[1] = 1;
    sum[2] = 2;
    for (int i = 3; i <= n; i++) {
        sum[i] = sum[i-1] + sum[i-2];
    }
    return sum[n];
}

字符串编码

给定一个经过编码的字符串,返回它解码后的字符串。
编码规则是:k[encoded_string] ,表示其中方括号内部的 encoded_string 重复k次。注意k保证为正整数。你可以认为输入的字符串总是合法的。输入的字符串中没有其他额外的空格等。
例如:
s = “3[a]2[bc]”,返回 “aaabcbc”
s = “3[a2[c]]” 返回 “accaccacc”
s = “2[abc]3[cd]ef” 返回 “abcabccdcdcdef”

其实这道题开起来挺复杂,其实也是对数字和方括号的匹配问题,这里我们不考虑那么复杂,以一个简单的例子来展开思索 12[a] 因为例子给的都是个位数,其实题中一个隐藏的数字问题是超过个位数的判断问题。

  1. 遍历字符串 S,如果当前字符不为方括号”]” 则入栈stack中
  2. 如果当前字符遇到了方括号”]” 则:
    1. 首先找到要复制的字符,例如stack=”12[a”,那么我要首先获取字符a;将这个a保存在另外一个栈去tempStack
    2. 接下来,要找到需要备份的数量,例如stack=”12[a”,因为出栈过字符”a”,则当前的top指向了”[“,也就是等于2
    3. 而12对于字符串是2个字符, 我们要通过遍历找到数字12的top上限/下限的位置索引, 此时上限curTop = 2, 下限通过出栈,top = -1
    4. 根据范围[-1,2],读取出12保存到strOfInt 字符串中来, 并且将字符”12\0”,转化成数字12
    5. 当前top=-1,将tempStack中的字符a,复制12份入栈到stack中来
    6. 为当前的stack扩容, 在stack字符的末尾添加字符结束符合’\0’
char * decodeString(char * s){

    /*.
     1.获取字符串长度
     2.设置默认栈长度50
     3.开辟字符串栈(空间为50)
     4.设置栈头指针top = -1;
     */

    int len = (int)strlen(s);
    int stackSize = 50;
    charstack = (char*)malloc(stackSize * sizeof(char));
    int top = -1;

    //遍历字符串,在没有遇到"]" 之前全部入栈
    for (int i = 0; i < len; ++i) {
        if (s[i] != ']') {
            //优化:如果top到达了栈的上限,则为栈扩容;
            if (top == stackSize - 1) {
                stack = realloc(stack, (stackSize += 50) * sizeof(char));
            }
            //将字符入栈stack
            stack[++top] = s[i];
            printf("#① 没有遇到']'之前# top = %d\n",top);
        }
        else {
            int tempSize = 10;
            char* temp = (char*)malloc(tempSize * sizeof(char));
            int topOfTemp = -1;

            printf("#② 开始获取要复制的字符信息之前 # top = %d\n",top);
            //从栈顶位置开始遍历stack,直到"["结束;
            //把[a]这个字母a 赋值到temp栈中来;
            //简单说,就是将stack中方括号里的字符出栈,复制到temp栈中来;
            while (stack[top] != '[') {

                //优化:如果topOfTemp到达了栈的上限,则为栈扩容;
                if (topOfTemp == tempSize - 1) {
                    temp = realloc(temp, (tempSize += 10) * sizeof(char));
                }
                //temp栈的栈顶指针自增;
                ++topOfTemp;
                //将stack栈顶字符复制到temp栈中来;
                temp[topOfTemp] = stack[top];
                //stack出栈,则top栈顶指针递减;
                top--;
            }
            printf("#② 开始获取要复制的字符信息之后 # top = %d\n",top);

            //找到倍数数字.strOfInt字符串;
            //注意:如果是大于1位的情况就处理
            char strOfInt[11];
            //p记录当前的top;
            int curTop = top;
            printf("#③ 开始获取数字,数字位置上限 # curTop = %d\n",curTop);

            //top--的目的是把"["剔除,才能找到数字;
            top--;
            //遍历stack得出数字
            //例如39[a] 就要找到这个数字39.
            //p指向当前的top,我就知道上限了; 那么接下来通过循环来找它的数字下限;
            //结束条件:栈指针指向为空! stack[top] 不等于数字
            while (top != -1 && stack[top] >= '0' && stack[top] <= '9') {
                top--;
            }
            printf("#③ 开始获取数字,数字位置下限 # top = %d\n",top);

            //从top-1遍历到p之间, 把stack[top-1,p]之间的数字复制到strOfInt中来;
            //39中3和9都是字符. 我们要获取到这2个数字,存储到strOfInt数组
            for (int j = top + 1; j < curTop; ++j) {
                strOfInt[j - (top + 1)] = stack[j];
            }
            //为字符串strOfInt数组加一个字符结束后缀'\0'
            strOfInt[curTop - (top + 1)] = '\0';

            //把strOfInt字符串转换成整数 atoi函数;
            //把字母复制strOfInt份到stack中去;
            //例如39[a],就需要把复制39份a进去;
            int curNum = atoi(strOfInt);
            for (int k = 0; k < curNum ; ++k) {

                //从-1到topOfTemp 范围内,复制curNum份到stackTop中去;
                int kk = topOfTemp;
                while (kk != -1) {

                    //优化:如果stack到达了栈的上限,则为栈扩容;
                    if (top == stackSize - 1) {
                        stack = realloc(stack, (stackSize += 50) * sizeof(char));
                    }

                    //将temp栈的字符复制到stack中;
                    //stack[++top] = temp[kk--];
                    ++top;
                    stack[top] = temp[kk];
                    kk--;

                }
            }
            free(temp);
            temp = NULL;
        }
    }

    //realloc 动态内存调整;
    //void *realloc(void *mem_address, unsigned int newsize);
    //构成字符串stack后, 在stack的空间扩容.
    char* ans = realloc(stack, (top + 1) * sizeof(char));
    ans[++top] = '\0';

    //stack 栈不用,则释放;
    free(stack);
    return ans;
}

去除重复字母

给你一个仅包含小写字母的字符串,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)

1
2
3
例如:
输入:"bcabc" ===> 输出 "abc"
输入:"cbacdcbc"===> 输出 "acdb"

很明显题目涉及到元素的来回比较,可以考虑使用栈的思想,由于要保证返回结果字典序最小类似 book < peek ,所以我们考虑维护一个类似单调递增栈的意思具体下面会讲,另外我们需要一个数组保存每个字母出现的总次数,每入栈一次就对相应字母的次数进行 -1 处理,思路概述:

  1. 创建一个数组保存每个字母出现的次数,很显然只需要创建一个 26 个容量的数组即可
  2. 遍历字符串,如果栈是空直接入栈,否则进行判断:
    1. 如果栈中存在相同的字符,直接对相应字符存在的数量进行减一处理
    2. 如果当前字符大于栈顶元素,那么直接入栈
    3. 如果当前字符小于栈顶元素,继续判断栈顶元素后面是否还有,如果有那么出栈直到栈顶当前字符大于栈顶元素。
1
2
3
4
5
6
以 bcabc 为例:
创建数组保存每个元素出现的次数 a:1次,b:2次,c:2次
count[] = {1,2,2,0,0...};
创建空栈 Stack
首先 b 入栈 [b] 并对b的次数-1,当c来的时候进行判断,栈中没有c,接着判断c>b 直接入栈 [b,c]并对c的数量进行-1,接下来碰到a,栈中没有a,栈顶c>a那么判断c在后面是否还有,查到c还会出现一次,对c进行出栈,继续对栈顶b和a进行比较依旧是对栈顶b进行出栈,这个时候栈应该是[a],以此类推,后续都是进行入栈,最终结果就是[a,b,c]即是结果
[]->[b]->[b,c]->[b]->[]->[a]->[a,b]->[a,b,c]
char *MinString(char *string) {
    // 边界判断
    if (string == NULL || strlen(string) == 0return "";
    if (strlen(string) == 1return string;
    // 用一个数组保存每个字母出现的次数
    int record[26] = {0};
    unsigned long len = strlen(string);
    int top = -1;
    char *stack = (char *)malloc(len*sizeof(char)+1);
    stack = memset(stack0, len*sizeof(char)+1);
    for (int i = 0; i < len; i++) {
        record[string[i]-'a']++;
    }

    for (int i = 0; i < len; i++) {
        // 判断当前字符是否已经在栈中
        int exist = 0;
        for (int j = 0; j <= top; j ++) {
            if (stack[j] == string[i]) {
                exist = 1;
            }
        }

        if (exist == 1) {// 如果存在直接对数组中相应字母数量减一
            record[string[i]-'a']--;
        } else {
            // 如果栈为空或者栈顶小于当前元素直接入栈,并减少数量
            if (top == -1 || stack[top] < string[i]) {
                top++;
                stack[top] = string[i];
                record[string[i]-'a']--;
            } else {
                // 否则一直出栈直到栈顶元素小于当前元素
                while (top>=0 && record[stack[top]-'a'] > 0 && stack[top] > string[i]) {
                    top--;
                }
                // 入栈新元素,并减少数量
                stack[++top] = string[i];
                record[string[i]-'a']--;
            }
        }
    }
    // 字符串末尾补\0
    stack[++top] = '\0';
    return stack;
}

总结

这篇文章罗列了最近学习的算法问题,作以小结,后续还会讲自己学习的一些算法问题总结到文章中去,希望能够将各个题目讲清楚,有问题还请留言沟通。