当前位置：首页 > news >正文

LeetCode高频题：子串权值定义为，最长有效括号子序列的长度，请你返回字符串s的所有子串权值的和是多少

news 来源：原创 2024/5/7 10:43:47

LeetCode高频题：子串权值定义为，最长有效括号子序列的长度，请你返回字符串s的所有子串权值的和是多少？

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
在这里插入图片描述

基础知识：
【1】括号匹配问题：判断一个字符串是否为有效的括号匹配
【2】括号匹配问题：括号字符串是否有效匹配，无效的话还需要加多少个括号才能完全匹配
【3】括号匹配问题：括号字符串的最大匹配嵌入深度是多少
【4】括号匹配问题：括号字符串的有效匹配子串最大长度是多少

文章目录

LeetCode高频题：子串权值定义为，最长有效括号子序列的长度，请你返回字符串s的所有子串权值的和是多少？
@[TOC](文章目录)

题目
一、审题
二、解题
总结

题目

在这里插入图片描述

一、审题

示例：如上，注意是子序列，不是子串哦，子串超级困难【看上面【4】，非常重要】

二、解题

分析
())())

你看看这个有效子序列最长的咋搞

其实你中途给统计左括号有几个？left个
然后遇到右括号，如果left>0，则可以消耗一个left括号，配对为一对，right=1记录了
如果遇到右括号，发现left<=0，显然没有办法配对，right就不要增加了

在这里插入图片描述
最长的有效括号子序列长度就是right的2倍，因为配对呗

所以
你只需要遍历给你的字符串s的每一个子串，查上面的最长有效子序列长度，把结果加ans就行

手撕代码：

public static class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String s = in.nextLine();//())())
            int ans = 0;
            for (int i = 0; i < s.length(); i++) {
                for (int j = i; j < s.length(); j++) {
                    ans += f(s.substring(i, j + 1));
                }
            }
            System.out.println(ans);
        }

        //最长括号子序列长度
        public static int f(String s){
            int l = 0, r = 0;
            char[] str = s.toCharArray();
            for (int i = 0; i < str.length; i++) {
                if (str[i] == '(') l++;
                else if (l > 0) {
                    l--;
                    r++;
                }
            }
            return r << 1;
        }
    }