《六月集训》第十四天——栈

• 前言
• 一、题目一
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 二、题目二
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 三、题目三
• • 1.题目描述
  • 2.解题思路
  • 3.代码详解
• 四、星球推荐

        
刷题坚持每一天，以下题目引用自：力扣（LeetCode）

原题链接：剑指 Offer 31. 栈的压入、弹出序列

        输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

思路：

​         pushed数组内的值依次进栈并和popped内的值比较，存在相等的值进入循环判断出栈，最后判断栈顶为零不为零，为零则为正确序列。

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
    int* stack = (int*)malloc(sizeof(int)*poppedSize);
    int idx = 0;
    int i, j;
    for(i = 0, j = 0; i < poppedSize; ++i){
        stack[idx++] = pushed[i];
        while(idx && popped[j] == stack[idx-1]){
            --idx;
            ++j;
        }
    }
    return idx == 0;
}

原题链接：856. 括号的分数

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
• (A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：
输入： “()”
输出： 1

思路：

​         每个括号都有不同的深度，遍历到左括号深度加一并给当前括号值赋零，遍历到右括号深度减一并把当前值乘于2加到上一值。

int scoreOfParentheses(char * s){
    int len = strlen(s);
    int* stack = (int*)malloc(sizeof(int)*len);
    memset(stack, 0, sizeof(int)*len);
    int idx = 0;
    for(int i = 0; i < len; ++i){ 
        if(s[i] == '('){
            ++idx;
            stack[idx] = 0;
        }
        else if(s[i-1] == '('){
            --idx;
            stack[idx] += 1; 
        }
        else {
            --idx;
            stack[idx] += 2 * stack[idx+1];
        }
    }
    return stack[0];
}

原题链接：1190. 反转每对括号间的子串

给出一个字符串 s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。

示例 1：
输入：s = “(ed(et(oc))el)”
输出：“leetcode”
解释：先反转子字符串 “oc” ，接着反转 “etco” ，然后反转整个字符串。

思路：

​         用栈只记录括号的下标位置。左括号依次进栈，遍历到右括号时就执行当前括号里的字符串翻转。然后当前左括号出栈。

char * reverseParentheses(char * s){
    int len = strlen(s);
    int bra[len];
    char* ans = (char*)malloc(sizeof(char)*len+1);
    int top = 0, idx = 0;
    for(int i = 0; i < len; ++i){
        if(s[i] == '('){
            bra[top++] = idx; 
        }
        else if(s[i] == ')'){
            int left = bra[top-1];
            int right = idx-1;
            while(left < right){
                char cetr = ans[left];
                ans[left] = ans[right];
                ans[right] = cetr;
                ++left;
                --right;
            }
            --top;
        }
        else ans[idx++] = s[i];
    }
    ans[idx] = '';
    return ans;
}

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到520+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。