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

作者: 收纳箱 | 来源:发表于2020-04-12 11:13 被阅读0次

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

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

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

从后往前进行计算，缓存第 $j$ 天再过 $x$ 天温度更高
当前温度还是从前往后遍历
- 比如第 $j-1$ 天比第 $j$ 天温度更高，那么我们直接跳过 $x$ 天就可以拿到更高的温度，而不需要依次比较
如果第 $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$ 阶可以由以下两种方法得到：

在第 $(i-1)$ 阶后向上爬1阶。
在第 $(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;
}

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

0. 栈思想

1. 括号匹配检验

2. 每日气温

思路1

思路2

3. 爬楼梯问题

3.1 暴力递归

3.2 动态规划

3.3 进一步优化

4. 去除重复字符

5. 字符串解码

6. 杨辉三角

7. 七进制数

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读