栈和队列练习

算法题

代码仓库地址

1. 括号匹配检验

假设表达式中允许包含两种括号：圆括号和方括号,其嵌套的顺序随意,即([]())或[([][])]等为正确的格式，[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。

思路

算法原理
栈后进先出的特性刚好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后，栈stack仍为空
算法流程
- 当前遍历括号是左括号，则入栈
- 当前遍历括号不是左括号：
  - 如果栈为空，则无法匹配，返回-1
  - 如果与栈顶括号匹配成功，出栈
  - 如果与栈顶括号匹配失败，返回-1
- 最后判断栈是否为空
复杂度
- 时间复杂度：O(n)，n是字符串的长度
- 空间复杂度：O(1)

int isValid(char *s) {
    // 空字符串符合
    if(*s == 0) return TRUE;
    // 长度为奇数，一定不符合
    int length = (int)strlen(s);
    if (length & 1) return ERROR;
    
    // 创建顺序栈
    char stack[length];
    int top = -1;

    // 遍历字符串
    for (int i = 0; i < length; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            // 如果是左括号，入栈
            stack[++top] = s[i];
        }else if (top == -1) {
            // 如果不是左括号，栈为空，无法匹配
            return FALSE;
        }else if (s[i] == stack[top] + 1 || s[i] == stack[top] + 2) {
            // 如果不是左括号，栈非空，当前字符和栈顶字符匹配成功，出栈
            stack[top--] = '#';
        }else {
            // 如果不是左括号，栈非空，当前字符和栈顶字符无法匹配
            return FALSE;
        }
    }
    return top == -1; // 判断栈是否为空
}

2. 每日气温

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

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

提示：气温列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。

图解

每日气温

思路

算法原理
我们可以借助栈后进先出的特性来解决这个问题，但是有一点特殊的是，这个栈是递减栈，栈里只有递减元素，记录气温索引位置。
算法流程
- 遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是 递减栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。
复杂度
- 时间复杂度：O(n)，只需要遍历一次数组，每个元素最多被压入或者弹出栈一次
- 空间复杂度：O(n)

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

    // 创建 记录 数组
    int *ans = (int *)malloc(sizeof(int) * TSize);
    
    // 初始化数组元素为0
    memset(ans, 0, TSize * sizeof(int));

    // 创建栈
    int stack[TSize];
    int top = -1;

    // 正序遍历
    for (int i = 0; i < TSize; i++) {
        // 如果栈顶元素小于当前气温，记录下标索引的距离差，同时出栈
        while (top > -1 && T[stack[top]] < T[i]) {
            ans[stack[top]] = i - stack[top];
            top--;
        }
        // 否则将下标索引入栈
        stack[++top] = i;
    }
    *returnSize = TSize;
    return ans;
}

3. 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

思路：

方法一：暴力递归
- 把所有可能的阶数进行组合，也就是1和2。而在之后的每一步中，我们都是反复调用climbStairs函数去模拟爬1阶和2阶的情形，并返回两个函数的返回值之和

// 第一种写法
int climb_Stairs(int i, int n) {
    if (i > n) return 0;
    if (i == n) return 1;
    return climb_Stairs(i+1, n) + climb_Stairs(i+2, n);
}

int climbStairs(int n){
 	 return climb_Stairs(0, n);
}

// 第二种写法
int climbStairs(int n){
    if (n <=2 ) {
        return n;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}

复杂度
- 时间复杂度：O($2^n$) ，树形递归的大小为$2^n$
- 空间复杂度：O(n) ，递归树的深度可以达到n
方法二：动态规划
- 首先，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建
- 第 i 阶可以由以下两种方法得到：
  1. 在第 i - 1阶后向上爬一阶
  2. 在第 i - 2阶后向上爬二阶
- 所以到达第 i 阶的方法总是就是第 i- 1 阶和第 i - 2 阶的方法数之和, 即$dp[i] = dp[i - 1] + dp[i - 2]$

int climbStairsDP(int n){
    if (n == 1) return 1;
    
    int *dp = malloc(sizeof(int) * (n + 1));
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

4. 去除重复字符

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

示例 1:

输入: "bcabc" 输出: "abc"

示例 2:

输入: "cbacdcbc" 输出: "acdb"

思路： 贪心 + 栈

算法原理
- 什么是“字典序”。字符串之间比较和数字之间比较是不太一样的，字符串是从头往后一个字符一个字符比较的，哪个字符大取决于两个字符串中第一个不对应相等的字符。
- 也就是说，任意一个以a开头的字符串都大于任意一个以b开头的字符串
算法流程
- 遍历字符串，获取每个字符的出现次数，保存在计数器中
- 如果栈顶元素比当前元素的字典序大，并且当前元素的位置后面还有栈顶元素，就将栈顶元素出栈，将当前元素入栈
复杂度
- 时间复杂度：O(n) ，虽然外循环里面有一个内循环，但是内循环的次数受栈中剩余字符总数的限制
- 空间复杂度：O(n) ，申请栈的空间为字符串的长度+1

char * removeDuplicateLetters(char * s){
    
    int size = (int)strlen(s);

    // 空字符串
    if (s == NULL || size == 0) {
        return "";
    }
    if (size == 1) {
        return s;
    }
    
    // 计数
    int letter[26]; // 计数器必须初始化
    memset(letter, 0, 26);
    for (int i= 0; i < size; i++) {
        letter[s[i] - 'a']++;
    }
    
    // 创建栈
    char *res = malloc(sizeof(char) * (size + 1));
    memset(res, 0, sizeof(char) * (size + 1));
    int top = -1;
    
    // 遍历字符串
    for (int i = 0; i < size;i++) {
        
        int isExist = 0;
        for (int j = 0; j <= top; j++) {
            // 如果当前字符，已经在栈中
            if (res[j] == s[i]) {
                isExist = 1;
                break;
            }
        }

        if (isExist) {
            letter[s[i] - 'a']--;
            continue;
        }else {
            /* 栈顶元素比当前元素的字典序大，当前元素的位置后面还有栈顶元素，就将栈顶元素出栈 */
            while (top > -1 && res[top] > s[i] && letter[res[top] - 'a'] > 1) {
              // 计数器--
              letter[res[top] - 'a']--;
              // 出栈
              top--;
            }
            // 将当前元素入栈
            res[++top] = s[i];
        }
    }
    
    // 结束标识
    res[++top] = '\0';
    return res;
}

5. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为:k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次，k为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。

示例：

s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

思路：

方法一：辅助栈
算法原理
- 利用栈的先进后出思想，以及C函数sscanf分离数字和字符
算法流程
- 首先遍历字符串，将第一个匹配到]字符之前的所有字符入栈
- 匹配到]之后，将之前的栈中的元素出栈，并通过C函数库将字符和数字分离
- 拼接指定次数的字符压入栈中
- 再继续遍历原字符串，直到结束
复杂度
- 时间复杂度：O(N) ，只需遍历一次字符串
- 空间复杂度：O(N)

#define IsStackEmpty (top == -1)
#define MAX_RESULT_SIZE 10000

char * decodeString(char * s){
    
    int size = (int)strlen(s);
    
    /* 空字符串 */
    if (s == NULL || size == 0) {
        return "";
    }
        
    /* 初始化一个字符串，存储最后的结果 */
    char *ans = malloc(sizeof(char) * MAX_RESULT_SIZE);
    memset(ans, 0, sizeof(char) * MAX_RESULT_SIZE);
    int top = -1;
    
    char *stack = ans;
    char *p = s;
    while (*p != '\0') {
        /* 栈为空，或者不是右括号 */
        if (IsStackEmpty || (*p != ']')) {
            stack[++top] = *p;
        }else {
            char *str = NULL;
    
            /* 如果栈顶元素不是数字  */
            while (!IsStackEmpty && !isdigit(stack[top])) {
                str = &stack[top--];
            }
            /* 如果栈顶元素是数字 */
            while (!IsStackEmpty && isdigit(stack[top])) {
                str = &stack[top--];
            }
            int k;
            char tmp[strlen(s) + 1000];
            /* 解析数字和字符 */
            if (sscanf(str, "%d[%[^]]", &k, tmp) == 2) {
                *str = '\0';
                top += strlen(tmp)*k; /* 这个必须在扩展前操作因为k会变更 */
                while (k > 0){
                    strcat(str, tmp);
                    k--;
                }
            }
        }
        p++;
    }
    ans[++top] = '\0';
    return ans;
}

6. 杨辉三角

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

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例：

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

**思路：**动态规划

算法原理
- 知道一行杨辉三角，就可以根据每对相邻的值计算出它的下一行，这里直接使用动态规划就行了
算法流程
- 第一个循环，先将每行的元素个数记录，同时将每行第一个和最后一个元素赋值为1
- 第二个循环，根据上一行的相邻两个数，算出对应位置的值
复杂度
- 时间复杂度：$O(numRows^2)$，更新总数为1+2+3+...+numRows，根据高斯公式
$$ \frac{numRows(numRows + 1)}{2} $$
- 空间复杂度：$O(numRows^2)$

主要注意，指针和数组的形式

int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    *returnSize = numRows;
    *returnColumnSizes = (int *)malloc(sizeof(int) * numRows);
    int **res = (int **)malloc(sizeof(int *) * numRows);
    
    int i = 0;
    for (; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = i + 1;
        res[i] = (int *)malloc(sizeof(int) * (*returnColumnSizes)[i]);
        res[i][0] = 1;
        res[i][i] = 1;
    }
    
    for (i = 2; i < numRows; i++) {
        for (int j = 1; j < i; j++) {
            res[i][j] = res[i - 1][j- 1] + res[i -1][j];
        }
    }
    return res;
}

7. 七进制数

给定一个整数，将其转化为7进制，并以字符串形式输出。

示例 1:

输入: 101
输出: "203"

示例 2:

输入: -7
输出: "-10"

注意: 输入范围是 [-1e7, 1e7] 。

思路：

算法原理
- 十进制数N和其它d进制数的转换的算法基于原理：
  $$ N = (N / d) * d + N % d $$

N	N / d	N mod d
100	14	3
14	2	0
2	0	2
根据上面的计算过程，可以得到最好的结果为`203`，计算顺序与输出顺序正好相反。

可以借助栈先进后出的特性实现

算法流程
- 按照公式，将每次取余的结果入栈
遍历出栈，即为最终结果
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)

char * convertToBase(int num, int d) {
    
    // 创建栈
    char * stack = malloc(sizeof(char) * 13);
    memset(stack, 0, sizeof(char) * 13);
    int top = -1;
    
    // 入栈
    int N = abs(num);
    while (N) {
        stack[++top] = N % d + '0';
        N = N / d;
    }
    
    // 处理符号
    if (num < 0) {
        stack[++top] = '-';
    }
    
    // 特殊情况 0
    if (num == 0) {
        stack[++top] = '0';
    }
    
    // 出栈
    char *res = malloc(sizeof(char) * (strlen(stack) + 1));
    memset(res, 0, sizeof(char) * (strlen(stack) + 1));
    int i = -1;
    
    while (top > -1) {
        res[++i] = stack[top--];
    }
    
    // 字符串结束标识
    res[++i] = '\0';
    return res;
}

char * converToBase7(int num) {
    return convertToBase(num, 7);
}