数据结构与算法-栈相关算法
1.括号匹配检验:
假设表达式中允许包含两种括号:圆括号与⽅括号,其嵌套顺序随意,即() 或者[([][])]都是正 确的.⽽这[(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的⽅法可⽤”期待的急迫 程度"这个概念来描述.例如,考虑以下括号的判断: [ ( [ ] [ ] ) ]
2.每⽇⽓温: (LeetCode-中等)
题⽬: 根据每⽇⽓温列表，请重新⽣成⼀个列表，对应位置的输⼊是你需要再等待多久温度才 会升⾼超过该⽇的天数。如果之后都不会升⾼，请在该位置0来代替。例如，给定⼀个列 表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：⽓温 列表⻓度的范围是 [1, 30000]。每个⽓温的值的均为华⽒度，都是 在 [30, 100] 范围内的整数
1.暴力法，双重循环
1.第一层循环从左到右开始遍历，从0到size-2，最后一个为零，不需要遍历。
2.第二层循环从[i+1,size]开始遍历，找到第一个大于它的值，计算结果，跳出当前循环。
思路：
1.创建一个result数组存储结果
2.默认result[TSize-1] = 0,最后一个不需要计算，默认给0
3.遍历原温度数组，[0,TSize-2]
①如果当前i>0,并且当前元素和上一个元素相等，那么就没有必要循环，判断一下
result[i-1]是否等于0，如果等于0让result[i]=0，否则result[i] = result[i-1]-1
②遍历[j=i-1,TSize-1],如果T[j]>T[i],那么result[i] = j-i，跳出循环；如果是T[j]已经是最后一个元素，那么result[i] = 0
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;
}
2.跳跃对比法法
1.最后一天依旧为0
2.i从[size-2,0]反向遍历，
3.j从[i+1,size]开始遍历
j+=result[j]
①如果T[i]<T[j],result[i] = j-i;
②result[j] == 0,result[i] = 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;
}
3. 栈思想解决，递减栈
1.创建一个result数组存储结果
2.初始化一个栈，用来存储索引
3.遍历数组[0,size-1],
①如果栈顶元素<当前元素并且top>0 进入循环result[top] = 当前元素的index-栈顶元素的index,将栈顶元素出栈，直到不满足T[stack[top-1]]<T[i]
②如果当前栈为空，入栈
③如果栈顶元素大于当前元素，入栈
④如果循环结束，当前元素入栈
int* dailyTemperatures_4(int* T, int TSize, int* returnSize) {
int* result = (int*)malloc(sizeof(int)*TSize);
*returnSize = TSize;
int* stack_index = (int*)malloc(sizeof(int)*TSize);
int top = 0;//栈顶指针
int tIndex;//栈顶元素
//将所有结果赋值0
for (int i=0; i<TSize; i++) {
result[i] = 0;
}
for (int i=0; i<TSize; i++) {
//判断栈顶元素与当前元素大小
while (top>0&&T[stack_index[top-1]]<T[i]) {
tIndex = stack_index[top-1];
result[tIndex] = i-tIndex;
top--;
}
//入栈
stack_index[top] = i;
top++;
}
return result;
}
3.爬楼梯问题:(LeetCode-中等)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不 同的⽅法可以爬到楼顶呢？注意：给定 n 是⼀个正整数å 去除重复字⺟(LeetCode-困难) 给你⼀个仅包含⼩写字⺟的字符串，请你去除字符串中重复的字⺟，使得每个字⺟只出现⼀ 次。需保证返回结果的字典序最⼩（要求不能打乱其他字符的相对位置）
1.递归求解法
递推公式：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==1) return 1;
if (n==2) return 2;
return ClimbStairs(n-1) + ClimbStairs(n-2);
}
2。动态规划法
这里解释一下动态规划法：
动态规划（英语：Dynamic programming，简称 DP）是⼀种在数学、管理科学、计算机科学、经济学和⽣物信息学中使⽤的，通过把原问题分解为相对简单的⼦问题的⽅式求解复杂问题的⽅法。
动态规划常常适⽤于有重叠⼦问题和最优⼦结构性质的问题，动态规划⽅法所耗时间往往远少于朴素解法。
动态规划背后的基本思想⾮常简单。⼤致上，若要解⼀个给定问题，我们需要解其不同部分（即⼦问题），再根据⼦问题的解以得出原问题的解。动态规划往往⽤于优化递归问题，例如斐波那契数列，如果运⽤递归的⽅式来求解会重复计算很多相同的⼦问题，利⽤动态规划的思想可以减少计算量。
通常许多⼦问题⾮常相似，为此动态规划法试图仅仅解决每个⼦问题⼀次，具有天然剪枝的功能，从⽽减少计算量：⼀旦某个给定⼦问题的解已经算出，则将其记忆化存储，以便下次需要同⼀个⼦问题解之时直接查表。这种做法在重复⼦问题的数⽬关于输⼊的规模呈指数增⻓时特别有⽤。
int ClimbStairs_2(int n) {
if (n==1)
return 1;
int *sum = (int *)malloc(sizeof(int)*(n+1));
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];
}
4.字符串编码(LeetCode-中等)
给定⼀个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中⽅括号内部的 encoded_string 正好重复 k 次。 注意 k 保证为正整数。你可以认为输⼊字符串总是有效的；输⼊字符串中没有额外的空格， 且输⼊的⽅括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只 表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输⼊。 例如: s = "12[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
