2022-01-07每日刷题打卡

2022-01-07每日刷题打卡

力扣——每日一题

1614. 括号的最大嵌套深度

如果字符串满足以下条件之一,则可以称之为 有效括号字符串(valid parentheses string,可以简写为 VPS):

字符串是一个空字符串 “”,或者是一个不为 “(” 或 “)” 的单字符。
字符串可以写为 AB(A 与 B 字符串连接),其中 A 和 B 都是 有效括号字符串 。
字符串可以写为 (A),其中 A 是一个 有效括号字符串 。
类似地,可以定义任何有效括号字符串 S 的 嵌套深度 depth(S):

depth("") = 0
depth© = 0,其中 C 是单个字符的字符串,且该字符不是 “(” 或者 “)”
depth(A + B) = max(depth(A), depth(B)),其中 A 和 B 都是 有效括号字符串
depth("(" + A + “)”) = 1 + depth(A),其中 A 是一个 有效括号字符串
例如:""、"()()"、"()(()())" 都是 有效括号字符串(嵌套深度分别为 0、1、2),而 “)(” 、"(()" 都不是 有效括号字符串 。

给你一个 有效括号字符串 s,返回该字符串的 s 嵌套深度 。

示例 1:

输入:s = “(1+(2*3)+((8)/4))+1”
输出:3
解释:数字 8 在嵌套的 3 层括号中。

看到括号匹配的问题,第一时间想到的就是栈,准备一个字符类型的栈sta和一个记录最大元素数的变量max,遍历字符串,每有一个‘(’,就把它入栈,然后判断max和当前栈元素哪个大,取大的那个赋给max,遍历到‘)’后就把栈元素出栈。最后返回max。

class Solution {
public:
    int maxDepth(string s) {
        stack<char>sta;
        int max_deep=0;
        for(auto i:s)
        {
            if(i=='(')
            {
                sta.push(i);
                max_deep=max_deep<sta.size()?sta.size():max_deep;
            }
            else if(i==')')
                sta.pop();
        }
        return max_deep;
    }
};

但写完后发现,好像并不需要栈,只需要一个变量记录最大元素max,一个变量ans记录当前元素数量即可。遍历到‘(’时ans++,并和max比较,遍历到‘)’时ans–,最后返回max。

class Solution {
public:
    int maxDepth(string s) {
        stack<char>sta;
        int max_deep=0;
        for(auto i:s)
        {
            if(i=='(')
            {
                sta.push(i);
                max_deep=max_deep<sta.size()?sta.size():max_deep;
            }
            else if(i==')')
                sta.pop();
        }
        return max_deep;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(!nums.size())return {-1,-1};
        int i=0,j=nums.size()-1,mid,left,right;
        while(i<j)
        {
            mid=(i+j)/2;
            if(nums[mid]>=target)j=mid;
            else i=mid+1;
        }
        if(nums[i]!=target)return {-1,-1};
        left=i;
        i=0,j=nums.size()-1;
        while(i<j)
        {
            mid=(i+j+1)/2;
            if(nums[mid]<=target)i=mid;
            else j=mid-1;
        }
        return {left,j};
    }
};
上一篇:【2022.01.07】拾回树莓派,折腾docker


下一篇:js 去掉字符串中包含的html