数据结构(8)-栈相关题目
括号匹配检查
给定一个只包括 (，)，{，}，[，]的字符串，判断字符串是否有效。注意空字符串可被认为是有效字符串。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例1：输入：() 输出：true
示例2：输入：()[]{} 输出：true
示例3：输入: ([)] 输出: false
示例4：输入：{[]} 输出：true
思路：
此题目可以借用栈先进后出的思想来处理，首先将第一个字符入栈，后面的如果与之成对就出栈，依次遍历字符串进行入栈出栈的操作，到字符串遍历结束之后，查看栈中是否还有元素，有就说明字符串中存在不匹配的括号，是无效的，没有则说明字符串中的括号正好成对的，则是有效的。
实现如下：
bool isValid(char * s){
// 判断字符串的长度 长度为0 有效
if (*s == 0) {
return true;
}
// 长度为奇数的 肯定是无效的
int len = (int)strlen(s);
if (len == 0 || (len % 2 == 1)) {
return false;
}
// 初始化栈、栈顶指针 将第一个元素先入栈
char Stack[len];
Stack[0] = s[0];
int top = 0;
// 遍历数组 如果是左括号直接入栈
// 如果是右括号则和栈顶括号对比成对就出栈 不成对则出栈
for (int i = 1; i < len; i++) {
if (top == -1) {
top += 1;
Stack[top] = s[i];
} else {
char stackTop = Stack[top];
switch (s[i]) {
case ')':
if (stackTop == '(') {
top -= 1;
} else {
top += 1;
Stack[top] = s[i];
}
break;
case '}':
if (stackTop == '{') {
top -= 1;
} else {
top += 1;
Stack[top] = s[i];
}
break;
case ']':
if (stackTop == '[') {
top -= 1;
} else {
top += 1;
Stack[top] = s[i];
}
break;
default:
top += 1;
Stack[top] = s[i];
break;
}
}
}
return top == -1;
}
每日气温
根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用0来代替。
例如，给定一个列表：
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
输出应该是：
[1, 1, 4, 2, 1, 1, 0, 0]
提示：气温列表长度的范围是[1, 30000]。每个气温的值的均为华氏度，都是在[30, 100]范围内的整数。
思路1：
遍历数组，找到比对应数大的下标相减即可得到对应的新值，然后开始计算下一个。需要注意的点，找不到比自己大就为0，最后一个肯定没有比自己大的，默认为0。
int* dailyTemperatures(int* T, int TSize, int* returnSize) {
*returnSize = TSize;
int *result = (int *)malloc(sizeof(int) * TSize);
// 最后一个数 肯定是0
result[TSize-1] = 0;
for (int i = 0; i < TSize - 1; i++) {
if (i > 0 && T[i] == T[i-1]) {
// 如果上一个数和当前数相等就没有必要进行比较 把原来的结果减1即可
// 如果上一个数是整个数组里面最大的 即result[i-1] == 0 则不能减1
result[i] = result[i-1] == 0 ? result[i-1]: result[i-1] - 1;
} else {
for (int j = i + 1; j < TSize; j++) {
// 找到比自己大 下标相减
if (T[j] > T[i]) {
result[i] = j - i;
break;
}
// 找不到赋值为0
if (j == TSize - 1) {
result[i] = 0;
}
}
}
}
return result;
}
思路2：
反向遍历, 跳跃，在某种情况下减少遍历的次数。比如当我们遍历到71的时候，已经知道了比69的大的数是72，先让71和69比较，因为71大于69，循环还得继续，然后71和72比较，需要让j加1步。而我们遍历到75的时候，已经知道了比71的大的数是72，先让75和71比较，因为75大于71，循环还得继续，此时就可以使用71的结果，也就是2，j加2步，直接比较75和72。比较完75和72，此时就可以使用72和76的比较结果，j加1步，比较75和76。以此类推，进行遍历。
其实这样遍历主要是当前数值比后面数值大的时候能够使用已知的结果，跳过不必要的比较，如果小于后面的数组，还是一步一步进行比较。
int* dailyTemperatures(int* T, int TSize, int* returnSize) {
*returnSize = TSize;
int *result = (int *)malloc(sizeof(int) * TSize);
result[TSize-1] = 0;
for (int i = TSize - 2; i >= 0; i--) {
if (T[i] == T[i+1]) {
result[i] = result[i+1] == 0 ? 0: (result[i+1] + 1);
} else {
// 此处 j += result[j] 就是使用已知的比较结果 减少比较次数
for (int j = i + 1; j < TSize; j += result[j]) {
if (T[j] > T[i]) {
result[i] = j - i;
break;
}
// 最大的数时
if (result[j] == 0) {
result[i] = 0;
break;
}
}
}
}
return result;
}
思路3：
借助一个栈来存储数组元素对应的下标。先将第一个元素的下标入栈，从第二个元素开始遍历数组，如果当前元素大于栈顶下标对应的元素，则用当前元素下标减去栈顶存储的下标，即为结果，并将栈顶下标出栈，进行下一轮运算，直到当前元素小于等于栈顶下标对应的元素为止，然后将当前元素的下标入栈；如果当前元素小于等于栈顶元素，则将当前元素的下标入栈。遍历完成之后，栈中所剩的下标则是找不到后面比自己大的元素的下标，都赋值为0即可。
int* dailyTemperatures(int* T, int TSize, int* returnSize) {
*returnSize = TSize;
int *result = (int *)malloc(sizeof(int) * TSize);
// 借助栈存储下标
int IndexStack[TSize];
// 将第一个元素下标先入栈
IndexStack[0] = 0;
int top = 0;
for (int i = 1; i < TSize; i++) {
// 如果当前元素比栈中对应的元素大 则可以将元素出栈 并得出对应的结构
while (top > -1 && T[i] > T[IndexStack[top]]) {
result[IndexStack[top]] = i - IndexStack[top];
top -= 1;
}
// 如果当前元素小于等于栈中对应的元素 入栈等待后续看有没有比自己大的元素
top += 1;
IndexStack[top] = i;
}
// 栈中剩余的元素 则是后面没有比自己大的 那就都是0
while (top > -1) {
result[IndexStack[top]] = 0;
top -= 1;
}
return result;
}
进制转换
将大于0的十进制整数转换为八进制。
思路：
进制转换都是除去转换的数，知道商为0为止，然后把余数逆序，即可得到转换之后的数值。如十进制8转换为2进制的数，用8除以2得到余数0商4，再用4除以2得到余数0商2，再用2除以2得到余数0商1，再用1除以2得到余数1商0，二进制的结果就是1000。
char * converDecimalToOctal(int num) {
char *result = (char *)malloc(sizeof(char) * 100);
// 用栈存储结果 出栈即为逆序
int numStack[100];
int top = -1;
while (num > 0) {
top += 1;
numStack[top] = num % 8;
num = num / 8;
}
char letter[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
result[top+1] = '\0';
for (int i = 0; top > -1; i++) {
result[i] = letter[numStack[top]];
top -= 1;
}
return result;
}
字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。编码规则为：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"
思路：
以3[a2[c]]为例，遍历字符串s，将字符入栈，如果遇到]则遍历将栈顶元素出栈，直到[，即得到c，丢弃[，此时栈顶为2，再判断栈顶是否是数字，如果是数字则继续出栈直到不是数字为止；如果不是数字，则停止出栈。此时出栈的字符为2c,处理出栈的这些字符，将数字挑出来，进行遍历加倍，将得到的结果cc遍历入栈。继续遍历字符串s，重复上述操作，直到遍历结束。得到最终出栈的字符串，进行处理即可。
实现如下：
char * decodeString(char * s) {
int strLenth = (int)strlen(s);
// 初始化一个栈来作为辅助处理工具
int stackSize = 50;
char* CharStack = (char*)malloc(stackSize * sizeof(char));
int top = -1;
for (int i = 0; i < strLenth; i++) {
// 遇到右括号出栈处理
if (s[i] == ']') {
// subStrStack 用来装需要处理的子串
// subNumSatack 用来装子串的次数
int numStackSize = 10;
char* subStrStack = (char *)malloc(sizeof(char) * numStackSize);
int subStrTop = -1;
int strStackSize = 10;
char* subNumSatack = (char *)malloc(sizeof(char) * strStackSize);
int subNumTop = -1;
for (int j = 0; top > -1; j++) {
if (CharStack[top] == '[') {
top -= 1;
} else if (CharStack[top] >= '0' && CharStack[top] <= '9') {
// 处理数字
if (subNumTop == numStackSize - 1) {
subNumSatack = realloc(subNumSatack, sizeof(char) * (numStackSize *= 2));
}
subNumTop += 1;
subNumSatack[subNumTop] = CharStack[top];
top -= 1;
// 如果数字字符的前一个字符不是数字了就跳出循环
if (top > -1 && (CharStack[top] < '0' || CharStack[top] > '9')) {
break;
}
} else {
// 处理字母
if (subStrTop == strStackSize - 1) {
subStrStack = realloc(subStrStack, sizeof(char) * (strStackSize *= 2));
}
subStrTop += 1;
subStrStack[subStrTop] = CharStack[top];
top -= 1;
}
}
// 将次数栈转为字符串
char* subNumStr = malloc((subNumTop + 2) * sizeof(char));
subNumStr[subNumTop+1] = '\0';
for (int k = 0; subNumTop > -1; k++) {
subNumStr[k] = subNumSatack[subNumTop];
subNumTop -= 1;
}
// 处理出栈的这些字符，将数字挑出来，进行遍历加倍，将得到的结果遍历入栈。
int subNum = atoi(subNumStr);
for (int m = 0; m < subNum; m++) {
int sTop = subStrTop;
while (sTop > -1) {
if (top == stackSize - 1) {
CharStack = realloc(CharStack, (stackSize *= 2) * sizeof(char));
}
top += 1;
CharStack[top] = subStrStack[sTop];
sTop -= 1;
}
}
free(subNumSatack);
free(subStrStack);
} else {
// 不是右括号就入栈
if (top == stackSize - 1) {
CharStack = realloc(CharStack, (stackSize *= 2) * sizeof(char));
}
top += 1;
CharStack[top] = s[i];
}
}
char* result = realloc(CharStack, (top + 2) * sizeof(char));
result[++top] = '\0';
return result;
}
杨辉三角
在杨辉三角中，每个数是它左上方和右上方的数的和。给定一个非负整数numRows，生成杨辉三角的前numRows行。
示例：
输入： 5
输出：
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
思路：
杨辉三角的规律如下：
a[ij]
a[00] = 1
a[10] = 1, a[11] = 1
a[20] = 1, a[21] = 2, a[22] = 1
a[30] = 1, a[31] = 3, a[32] = 3, a[33] = 1
a[40] = 1, a[41] = 4, a[42] = 6, a[43] = 4, a[44] = 1
实现如下：
int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
*returnSize = numRows;
*returnColumnSizes = (int *)malloc(numRows * sizeof(int));
int **result = (int **)malloc(sizeof(int *) * numRows);
for (int i = 0; i < numRows; i++) {
(*returnColumnSizes)[i] = i + 1;
result[i] = (int*)malloc(sizeof(int) * (i + 1));
result[i][0] = 1;
result[i][i] = 1;
for (int j = 1; j < i; j++) {
result[i][j] = result[i-1][j-1] + result[i-1][j];
}
}
return result;
}
爬楼梯
假设你正在爬楼梯，需要n阶才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
示例 1：
输入： 2，输出： 2
解释： 有两种方法可以爬到楼顶，1 阶 + 1 阶、2 阶
示例 2：
输入：3，输出： 3
解释： 有三种方法可以爬到楼顶。1 阶 + 1 阶 + 1 阶、1 阶 + 2 阶、2 阶 + 1 阶。
首先，我们需要找出爬楼梯的规则：
1: 1
2: 1+1 => 2
3: 1+1+1 2+1 1+2 => 3
4: 1+1+1+1 2+2 1+2+1 2+1+1 1+1+2 => 5
5: 1+1+1+1+1 2+1+1+1 1+2+1+1 1+1+2+1 1+1+1+2 2+2+1 1+2+2 2+1+2 => 8
......
可以看出，最终的结果和与之相邻的前两个结果是有直接联系的。比如说3=2+1、5=3+2、8=5+3。。。。。。我们可以得到规则：An = A(n-1) + A(n-2)。
思路1：递归。An = A(n-1) + A(n-2)的结果最终会变成A1 + A2来处理，而A1、A2的结果是已知的，所以可以直接使用递归的方式来处理。实现如下：
int climbStairs(int n) {
if (n <= 2) {
return n;
}
return climbStairs(n-1) +climbStairs(n-2);
}
思路2：迭代。
int climbStairs(int n) {
if (n <= 2) {
return n;
}
int *sum = (int *)malloc(sizeof(int) * (n + 1));
sum[1] = 1;
sum[2] = 2;
for (int i = 3; i <= n; i++) {
sum[i] = sum[i-1] + sum[i-2];
}
return sum[n];
}
由上述两种思路可以看出，递归是自己调用自己，是一个从n到1的过程，即从将目标分解到我们已知结果的过程；而迭代则是使用心得结果代替自己，是一个从1到n的过程，即从我们已知的结果逐渐接近目标的过程。
字母去重
给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
输入: "bcabc" 输出: "abc"
输入: "cbacdcbc" 输出: "acdb"
思路：
- 字典序就是按照英文字母的排序方式，即
'a' < 'b' < ... < 'z' - 不能打乱相对位置，比如
"cbacdcbc"输出的是"acdb"，不能改为"abcd" - 使用辅助数组记录字母出现的次数、对字符串去除重复
- 使用辅助栈来进行排序，当前元素小于栈顶元素、且后续还存在和栈顶元素相等的元素，就需要将栈顶出栈、循环执行此操作
char * removeDuplicateLetters(char * s) {
int strLenth = (int)strlen(s);
if (strLenth <= 1) {
return s;
}
// 小写字母只有26个
// 记录每个字母出现了多少次
int charCount[26] = {0};
// 记录字母是否已经被存入栈中 存入就不继续存了
int charExist[26] = {0};
// 计算出现的次数
for (int i = 0; i < strLenth; i++) {
char curChar = s[i];
charCount[curChar - 'a'] += 1;
}
char *charStack = (char *)malloc(sizeof(char) * strLenth);
int top = -1;
for (int i = 0; i < strLenth; i++) {
if (charExist[s[i] - 'a'] > 0) {
// 已经被存入了 直接抛弃 将记录的出现次数减1
charCount[s[i] - 'a'] -= 1;
} else {
while (top > -1 && charCount[charStack[top] - 'a'] > 1 && charStack[top] > s[i]) {
// 如果栈中存在元素 且栈顶元素后面还会再次出现(确定当前的位置是否是最小字典序的) 而且栈顶元素大于当前元素(字典序且不打乱其他位置) 就将栈顶元素出栈
charCount[charStack[top] - 'a'] -= 1;
charExist[charStack[top] - 'a'] -= 1;
top -= 1;
}
// 将当前元素入栈
top += 1;
charStack[top] = s[i];
charExist[charStack[top] - 'a'] += 1;
}
}
char* result = realloc(charStack, (top + 2) * sizeof(char));
result[++top] = '\0';
return result;
}
总结
上述的例子中，我们的解决问题用到了栈思想、分治法。
分治法
分治法就是将问题分解为多个小问题一一解决的一种方法。比如爬楼梯问题，我们将n阶楼梯最终拆解到了1阶2阶的问题。
其精髓如下：
- 分--将问题分解为规模更小的子问题；
- 治--将这些规模更小的子问题逐个击破；
- 合--将已解决的子问题合并，最终得出“母”问题的解
采取"分治法"进行递归求解的问题需满足以下三个条件:
- 能将一个问题拆分为多个子问题，而新问题和原问题解法相同或类同
- 可以通过拆分使得问题简化
- 必须有一个明确的递归出口，或称为边界
栈思想
大部分问题我们都采用了栈思想来解决问题，即使用其先进后出的特性。比如括号匹配问题。那么一般情况下，什么问题适合用栈思想解决了?
- 数据是线性的
- 问题中常常涉及到数据的来回比较、匹配问题
- 问题中涉及到数据的转置。例如进制问题、链表倒序打印问题等
