数据结构与算法-栈练习题

0. 栈思想

利用栈的特性(先进后出)来解决问题，适合的题目类型：

  • 数据是线性的
  • 问题中常常设计到数据的来回比较、匹配问题，如括号匹配、每日温度、字符串解码、去掉重复字母等问题。
  • 问题中涉及到数据的转置，如进制问题、链表倒序打印等。

1. 括号匹配检验

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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef char SElemType;

/* 链栈结构 */
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *StackNodePtr;

typedef struct {
    StackNodePtr top;
} LinkStack;

Status Push(LinkStack *S, SElemType e) {
    if (!S) return ERROR;
    StackNodePtr node = (StackNodePtr)malloc(sizeof(StackNode));
    node->data = e;
    node->next = S->top; // 头插法
    S->top = node; // 更换头结点
    return OK;
}

Status Pop(LinkStack *S, SElemType *e) {
    if (!S || !S->top) return ERROR;
    *e = S->top->data;
    StackNodePtr node = S->top;
    S->top = S->top->next; // 更换头结点
    free(node);
    return OK;
}

Status BracketsCheck(char *string) {
    LinkStack stack;
    stack.top = NULL;
    char *p = string;
    while (*p) {
        if (*p == '[' || *p == '(') {
            if (!Push(&stack, *p)) {
                return FALSE;
            }
        } else if (*p == ']') {
            char bracket = 0;
            if (!Pop(&stack, &bracket) || bracket != '[') {
                return FALSE;
            }
        } else if (*p == ')') {
            char bracket = 0;
            if (!Pop(&stack, &bracket) || bracket != '(') {
                return FALSE;
            }
        }
        p++;
    }
    return TRUE;
}

int main(int argc, const char * argv[]) {
    if (BracketsCheck("[]()")) {
        printf("括号格式正确\n");
    } else {
        printf("括号格式错误\n");
    }
    return 0;
}

2. 每日气温

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

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

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

思路1

  1. 栈里面的值，是从大到小排列的，栈底温度最高，栈顶温度最低
  2. 如果栈里面有值，当前温度比比栈顶温度更高，依次弹出温度更低的节点，并和当前索引进行计算获取像个天数
  3. 新的温度入栈，原栈顶的一系列温度更低的节点都被弹出了，现在新的温度就是最低的温度
typedef struct Temp {
    int index;
    int temp;
} Temp;

int* dailyTemperatures(int* T, int TSize, int* returnSize) {
    int *ans = (int *)calloc(TSize, sizeof(int ));
    Temp *stack = (Temp *)malloc(sizeof(Temp) * TSize);
    *returnSize = TSize;
    int top = -1;
    for (int i = 0; i < TSize; i++) {
        if (top > -1 && T[i] > stack[top].temp) { // 栈中有值，且当前温度比栈顶温度更高
            for (; top > -1 && T[i] > stack[top].temp; top--) { // 遍历比栈顶温度低的温度
                ans[stack[top].index] = i - stack[top].index; // 计算相隔天数
            }
        }
        // 入栈当前温度
        top++;
        stack[top].index = i;
        stack[top].temp = T[i];
    }
    return ans;
}

int main(int argc, const char * argv[]) {
    int temperatures[8] = {73, 74, 75, 71, 69, 72, 76, 73};
    int returnSize;
    int *result = dailyTemperatures(temperatures, 8, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 0;
}

思路2

  1. 从后往前进行计算，缓存第 j 天再过 x 天温度更高
  2. 当前温度还是从前往后遍历
    • 比如第 j-1 天比第 j 天温度更高，那么我们直接跳过 x 天就可以拿到更高的温度，而不需要依次比较
  3. 如果第 j 天后没有哪一天温度更高，则结束查找
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--) {
        // 从当前位置后一个位置开始向后遍历，T[i]为当前温度，T[j]为索引温度
        // 通过result[j]可以知道需要前进的天数，来获取更高的温度
        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;
}

3. 爬楼梯问题

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

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

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

3.1 暴力递归

根据之前的步数，尝试走1步或者2步，看会不会到达阶梯总数。

结束条件：

  • 阶梯总数比走过的步数小 n < setp，则这不是一种可行的方法，返回0。
  • 阶梯总数等于走过的步数 n == setp，则这是一种方法，返回1。

通过画图，我们可以发现这是一个树形结构。

时间复杂度：O(2^n)

空间复杂度：O(n)

static int climb_stairs(int step, int n) {
        if (step > n) {
            return 0;
        } else if (step == n) {
            return 1;
        }
        return climb_stairs(step + 1, n) + climb_stairs(step + 2, n);
    }

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

3.2 动态规划

第 i 阶可以由以下两种方法得到：

  1. 在第(i-1)阶后向上爬1阶。
  2. 在第(i-2)阶后向上爬 2 阶。

令 a[i] 表示能到达第 i 阶的方法总数：
a[i] = a[i-1] + a[i-2]
这里我们使用一个数组来进行结果的统计。

时间复杂度：O(n)

空间复杂度：O(n)

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

3.3 进一步优化

我们发现，这就是一个斐波那契数列，且下一个参数只和前两个项有关，那么这两项之前的空间是没有必要的。

我们只是有2个参数来保留前两项的结果就行了。

时间复杂度：O(n)

空间复杂度：O(1)

int climbStairs (int n) {
    if (n == 1) return 1;
    int first = 1, second = 2;
    for (int i = 3, third = 0; i <= n; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return second;
}

4. 去除重复字符

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

示例 1:

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

示例 2:

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

思路：

  • 字符a-z一共26个，加上结束符\0有27个，所以我们申请一个大小为27的char类型的栈。
  • 先遍历一遍，看每个字符出现的次数。
    • 后期遍历的时候可以知道，是否还可以删除。(使得每个字母只出现一次)
  • 再加入一个标记，数组里面是否已经存在某个字符了。
    • 存在、后面还有，就可以删除，后面会添加回来。
  • 要求字典序，那么数组中的字符基本是由小到大排列的。(不是一定是，因为还要满足每个字母只出现一次)

核心的处理：

  • 当前字符没有入栈
    • 栈不是空栈、当前字符比栈顶字符小、栈顶的元素后面还有时，我们可以把满足这些条件的栈顶元素弹出。（后面还有机会再加回来）
    • 再入栈当前字符。(此时如果前面没有再也不出现的字符，这个就是最小的字符)
  • 结束遍历时，栈顶加上结束符\0，就是我们的目标字符串了。
char * removeDuplicateLetters(char *s) {
    if (!s || strlen(s) < 2) return s;
    int top = -1; // 栈顶
    char *stack = malloc(sizeof(char) * 27); // 给后面配置\0多加1
    char inStack[26] = {0}; // 是否入栈
    int charCount[26] = {0}; // 字符剩余总数
    // 统计单个字符总数
    char *p = s;
    while (*p) {
        charCount[*p - 'a']++;
        p++;
    }
    p = s;
    int idx = 0; //字符索引
    while (*p) {
        idx = *p - 'a'; // 当前字符在数组中的索引值
        charCount[idx]--; // 更新元素的剩余次数
        if (!inStack[idx]) { // 当前字符没有入栈
            // 是否需要出栈栈顶字符
            while (top != -1 // 空栈不处理
                   && *p < stack[top] // 当前字符比栈顶字符小
                   && charCount[stack[top] - 'a'] > 0) { // 栈顶字符在后面还有，就可以出栈
                inStack[stack[top] - 'a'] = 0; // 栈顶弹出，就没有入栈了
                --top; // 出栈
            }
            // 当前字符没有入栈，就可以入栈
            stack[++top] = *p;
            inStack[idx] = 1;
        }
        p++; // 继续遍历
    }
    stack[++top] = '\0'; // 循环已保证栈底到栈顶是排好序的了，加上结束符
    return stack;
}

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".

#define MAXSIZE 2000

typedef char* StrType;
typedef struct StrStackNode
{
    int multi;
    StrType data;
    struct StrStackNode *next;
} StrStackNode, *StrStackNodePtr;

typedef struct
{
    StrStackNodePtr top;
    int count;
} StrLinkStack;

void PushStr(StrLinkStack *S, int multi, StrType e) {
    StrStackNodePtr node = (StrStackNodePtr)malloc(sizeof(StrStackNode));
    node->multi = multi;
    node->data = e;
    node->next = S->top;
    S->top = node;
}

void PopStr(StrLinkStack *S, int *multi, StrType *e) {
    StrStackNodePtr node = S->top;
    *multi = node->multi;
    *e = node->data;
    S->top = S->top->next;
    free(node);
}

char * decodeString(char *s)
{
    int multi = 0;
    StrType res = (StrType)malloc(sizeof(char) * MAXSIZE); // 记录当前的字符串
    *res = '\0';
    StrLinkStack strStack = {NULL, 0};
    StrType p = s;
    while (*p) {
        if(*p >= '0' && *p <= '9') { // 计算出现次数
            multi = multi * 10 + *p - '0';
        } else if (*p == '[') { // 入栈'['之前的次数和字符串
            PushStr(&strStack, multi, res);
            multi = 0;
            res = (StrType)malloc(sizeof(char) * MAXSIZE);
            *res = '\0';
        } else if (*p == ']') { // 出栈'['之前的次数和字符串
            StrType curStr = res; // 当前是嵌套最深的字符串，如3[a2[cd]]中的cd
            int curMulti = 0;
            PopStr(&strStack, &curMulti, &res); // 出栈，如3[a2[cd]]中的2和"a"
            StrType tmp = (StrType)malloc(sizeof(char) * MAXSIZE);
            *tmp = '\0';
            for (int i = 0; i < curMulti; i++) { // 拼接，如3[a2[cd]]中的2[cd]
                strcat(tmp, curStr);
            }
            strcat(res, tmp); // 拼接，如3[a2[cd]]中的"a"和2[cd]生成的cdcd
        } else {
            strncat(res, p, 1); // 在字符串中追加一个字符
        }
        p++;
    }
    return res;
}

6. 杨辉三角

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

示例：

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

思路：

如果要求第n行的显示可能还会考虑递归。这里要求每行都要返回，直接就按题目意思，使用动态规划就好了。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    int size, i;
    int **res = (int **)malloc(sizeof(int *) * numRows);
    int *columnSizes = (int *)malloc(sizeof(int) * numRows);
    for (int j = 0; j < numRows; j++) {
        size = j + 1;
        columnSizes[j] = size;
        res[j] = (int *)malloc(sizeof(int) * size);
        res[j][0] = 1;
        res[j][size-1] = 1;
        if (j > 1)
            for (i = 1; i < size-1; i++)
                res[j][i] = res[j-1][i-1] + res[j-1][i];
    }
    *returnColumnSizes = columnSizes;
    *returnSize = numRows;
    return res;
}

int main(int argc, const char * argv[]) {
    int **res, *returnColumnSizes;
    int returnSize;
    int numRows = 5;
    res = generate(numRows, &returnSize, &returnColumnSizes);
    for (int i = 0; i < returnSize; i++) {
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d ", res[i][j]);
        }
        printf("\n");
    }
    free(res);
    free(returnColumnSizes);
    return 0;
}
// 输出
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

7. 七进制数

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

示例 1:

输入: 100
输出: "202"

示例 2:

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

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

思路：

  • 范围 [-1e7, 1e7] 。

    int main(int argc, const char * argv[]) {
    int i = 1;
    int num = 1e7;
    while (num) {
        num = num / 7;
        i++;
    }
    printf("%d\n", i);
    return 0;
}
// 输出
10

    考虑到还有负号-，所以数组的长度至少为11。

  • 进制转换

    100 = 2*7^2+0*7^1+2*7^0

    100\ \%\ 7=2

    (100-2)/7=2*7^1+0*7^0

    我们可以看到通过不断取余%和求商/操作，就可以拿到7^k的系数，再加上'0'就是我们的字符表示了。

  • 二进制字符表示是从高位到低位的，但我们上面的操作是从低位到高位进行获取的，所以我们把顺序数组改成栈的表示。最后出栈显示最终结果。

char * convertToBase7(int num) {
    if (num == 0) return "0";
    int top = -1;
    char *stack = (char *)malloc(sizeof(char) * 11);
    // 确定正负
    int flag = 0;
    if (num < 0) {
        flag = 1;
        num = -num;
    }
    // 进制转换，入栈
    char rest;
    while (num > 0) {
        rest = num % 7 + '0';
        num = num / 7;
        stack[++top] = rest;
    }
    if (flag) stack[++top] = '-';
    // 出栈输出结果
    int count = top + 1;
    char *res = (char *)malloc(sizeof(char) * (count + 1));
    int i = 0;
    for (; i < count; i++) {
        res[i] = stack[top--];
    }
    res[i] = '\0';
    free(stack);
    return res;
}

8. 删除字符串中的所有相邻重复项

个人发现的一道比较有意思的题，有点像祖玛游戏，中间消除之后，如果两个相同元素相遇仍然可以消除。

leetcode 1047

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

思路：

这里为了不适用额外的存储空间，使用了双指针思想和栈思想。

快指针进行遍历，慢指针表示栈顶，最后添加结束符。

char * removeDuplicates(char * S){
    int top = 0;
    for (int i = 0; S[i]; i++, top++) {
         S[top] = S[i];
         if (top > 0 && S[top] == S[top - 1])
             top -= 2;
    }
    S[top] = '\0';
    return S;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,684评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,143评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,214评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,788评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,796评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,665评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,027评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,679评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,346评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,664评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,766评论 1赞 331
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,412评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,015评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,974评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,073评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,501评论 2赞 343

推荐阅读更多精彩内容