20240718训练题目

20. 有效的括号

题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

AC代码

class Solution {
public:
    bool isValid(string s) {
        map<char,int>m{{'(',1},{'[',2},{'{',3},{')',4},{']',5},{'}',6}};// 设置权重，便于比较有效符号对
        stack<int>st;// 储存 符号对 的 前符号
        bool ans=true;
        for(auto c : s)
        {
            int t=m[c];
            if(t>=1&&t<=3)  st.push(t);
            else if(!st.empty()&&t==st.top()+3) st.pop();
            else // 出现无效符号
            {
                ans=false;
                break;
            }
        }
        if(!st.empty())ans=false;// 最后有多余的前符号，则字符串无效
        return ans;
    }
};

496. 下一个更大元素 I

题目

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

AC代码

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        map<int,int>mp;
        for(int i=0;i<nums2.size();i++)    mp[nums2[i]]=i+1;// 标记 nums2 的下标
        vector<int>ans; // 储存答案
        for(int i=0;i<nums1.size();i++)
        {
            int x=nums1[i],y=mp[nums1[i]];
            int f=0;
            for(int j=y;j<nums2.size();j++)// 寻找 右边 较大值
            {
                if(nums2[j]>x)
                {
                    f=1;
                    ans.push_back(nums2[j]);
                    break;
                }
            }
            if(f==0)ans.push_back(-1);
        }
        return ans;
    }
};

739. 每日温度

题目描述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

AC代码

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n=temperatures.size();
        vector<int> ans(n);
        stack<int>q;
        for(int i=0;i<n;i++)
        {
            while(!q.empty()&&temperatures[i]>temperatures[q.top()])// 找到第 i 位左边的第一个比第 i 位数的数
            {
                int t=q.top();
                ans[t]=i-t;// 储存按要求的答案
                q.pop();
            }
            q.push(i);
        }
        return  ans;
    }
}; 

856. 括号的分数

题目

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

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

输入

S 是平衡括号字符串，且只含有 ’ ( ’ 和 ’ ) ’ 。

2 <= S.length <= 50

AC代码

class Solution {
public:
    int scoreOfParentheses(string s) {
        int ans=0,n=s.size(),t=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='(')   t++;
            else    t--;
            if(s[i]==')'&&s[i-1]=='(')
            {
                ans+=1<<t; // 加上 2 的符号对数
            }
        }
        return ans;
    }
};

32. 最长有效括号

题目

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

AC代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans=0;
        stack<int>st;
        st.push(-1);
        for(int i=0;i<s.size();i++)
        {
           if(s[i]=='(')    st.push(i);
           else
           {
                st.pop();
                if(st.empty())
                    st.push(i);
                else
                    ans=max(ans,i-st.top());// 匹配到完整字符串
           }
        }
        return ans;
    }
};