精华内容
下载资源
问答
  • LeetCode301——删除无效的括号

    千次阅读 2019-06-01 18:52:21
    我的LeetCode代码仓:... ... 题目描述: 知识点:回溯 思路一:回溯法(用栈来判断括号是否匹配) 由于没有任何剪枝操作,该回溯过程穷举了所有可能的情形,时间复杂度是O(2 ^ n)...

    我的LeetCode代码仓:https://github.com/617076674/LeetCode

    原题链接:https://leetcode-cn.com/problems/remove-invalid-parentheses/

    题目描述:

    知识点:回溯

    思路一:回溯法(用栈来判断括号是否匹配)

    由于没有任何剪枝操作,该回溯过程穷举了所有可能的情形,时间复杂度是O(2 ^ n),其中n为括号个数。空间复杂度是O(m),其中m为字符串的长度。

    JAVA代码:

    public class Solution {
    
        private Set<String> set;
    
        private String input;
    
        private int maxLen = 0;
    
        public List<String> removeInvalidParentheses(String s) {
            set = new HashSet<>();
            input = s;
            removeInvalidParentheses(0, "", new LinkedList<>());
            return new ArrayList<>(set);
        }
    
        private void removeInvalidParentheses(int index, String valid, LinkedList<Character> linkedList) {
            if (index == input.length()) {
                if (linkedList.isEmpty()) {
                    if (maxLen < valid.length()) {
                        maxLen = valid.length();
                        set.clear();
                        set.add(valid);
                    } else if (maxLen == valid.length()) {
                        set.add(valid);
                    }
                }
                return;
            }
            char c = input.charAt(index);
            if (c == '(') {
                removeInvalidParentheses(index + 1, valid, new LinkedList<>(linkedList));
                linkedList.push(c);
                removeInvalidParentheses(index + 1, valid + c, linkedList);
            } else if (c == ')') {
                if (linkedList.isEmpty()) {
                    removeInvalidParentheses(index + 1, valid, linkedList);
                } else {
                    removeInvalidParentheses(index + 1, valid, new LinkedList<>(linkedList));
                    linkedList.pop();
                    removeInvalidParentheses(index + 1, valid + c, linkedList);
                }
            } else {
                removeInvalidParentheses(index + 1, valid + c, linkedList);
            }
        }
    
    }
    

    LeetCode解题报告:

    思路二:回溯法(用左括号的数量和右括号的数量来判断是否是有效字符串)

    时间复杂度是O(2 ^ n),其中n为括号个数。空间复杂度是O(m),其中m为字符串的长度。但少了思路一中的入栈和出栈操作,因此速度上会有所提升。

    JAVA代码:

    public class Solution {
    
        private Set<String> set;
    
        private String input;
    
        private int maxLen = 0;
    
        public List<String> removeInvalidParentheses(String s) {
            set = new HashSet<>();
            input = s;
            removeInvalidParentheses(0, "", 0, 0);
            return new ArrayList<>(set);
        }
    
        private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount) {
            if (leftCount < rightCount) {
                return;
            }
            if (index == input.length()) {
                if (leftCount == rightCount) {
                    if (maxLen < valid.length()) {
                        maxLen = valid.length();
                        set.clear();
                        set.add(valid);
                    } else if (maxLen == valid.length()) {
                        set.add(valid);
                    }
                }
                return;
            }
            char c = input.charAt(index);
            if (c == '(') {
                removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
                removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount);
            } else if (c == ')') {
                removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
                removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1);
            } else {
                removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount);
            }
        }
    
    }
    

    LeetCode解题报告:

    思路三:回溯(带剪枝操作)

    如上图所示,Solution1和Solution2的结果可以由很多种回溯过程得到,这些回溯过程对于我们来说其实是多余的,因为得到的是完全相同的结果。对比上图中的6种解决方案,我们发现需要删除的左括号数都是2个,需要删除的右括号数都是0个。事实上,只要题目给出了相应的字符串,我们就能确定需要删除的左括号个数和右括号个数,使得删除的总括号数最少。

    一旦确定了需要删除的左括号个数和右括号个数,我们的回溯过程就能大大简化。

    递归出口

    在递归遍历完字符串之后,只要满足需要删除的左括号个数和右括号个数均为0,该结果就是满足条件的一个答案。

    递归过程

    (1)如果当前字符是左括号,如果需要删除的左括号个数leftRem大于0,可以考虑忽略该左括号。当然,还有一种情形是不忽略该左括号。

    (2)如果当前字符是右括号,如果需要删除的右括号个数rightRem大于0,可以考虑忽略该右括号。当然,还有一种情形——当左括号个数leftCount大于右括号个数rightCount时,不忽略该右括号。

    (3)如果当前字符既不是左括号也不是右括号,直接将该字符加进结果即可。

    时间复杂度在最坏情况下依然是O(2 ^ n),其中n为括号的数量。空间复杂度是O(m),其中m为字符串的长度。

    JAVA代码:

    public class Solution {
    
        private Set<String> set;
    
        private String input;
    
        public List<String> removeInvalidParentheses(String s) {
            set = new HashSet<>();
            input = s;
            int left = 0, right = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    left++;
                } else if (c == ')') {
                    if (left == 0) {
                        right++;
                    } else {
                        left--;
                    }
                }
            }
            removeInvalidParentheses(0, "", 0, 0, left, right);
            return new ArrayList<>(set);
        }
    
        private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount, int leftRem, int rightRem) {
            if (index == input.length()) {
                if (leftRem == 0 && rightRem == 0) {
                    set.add(valid);
                }
                return;
            }
            char c = input.charAt(index);
            if (c == '(') {
                if (leftRem > 0) {
                    removeInvalidParentheses(index + 1, valid, leftCount, rightCount, leftRem - 1, rightRem);
                }
                removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount, leftRem, rightRem);
            } else if (c == ')') {
                if (rightRem > 0) {
                    removeInvalidParentheses(index + 1, valid, leftCount, rightCount, leftRem, rightRem - 1);
                }
                if (rightCount < leftCount) {
                    removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1, leftRem, rightRem);
                }
            } else {
                removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount, leftRem, rightRem);
            }
        }
    
    }
    

    LeetCode解题报告:

     

    展开全文
  • POJ-1400(删除冗余括号

    千次阅读 2014-08-15 21:58:08
    题目:http://poj.org/problem?id=1400 一开始在判断括号内是否全是忘了括号内嵌

    题目:http://poj.org/problem?id=1400

    一开始在判断括号内是否全是乘或除时忘了括号内还有括号的情况,WA了两次之后找到了数据,对比答案之后才发现这个问题……删括号规则:

    (1)括号前是除号,不能删

    (2)括号前是乘号或减号,如果括号内全是乘除法或者被括号括起来的运算

    (3)括号前是加法,如果括号后面是加法、括号后面是减法、括号内全是乘除法或者被括号括起来的运算


    #include <string>
    #include <iostream>
    using namespace std;
    
    inline bool isOperator(char c){
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
    bool allMulOrDiv(const string& exp)
    {
        for(int i = 0, len = exp.size(); i < len; ++i){
            if(exp[i] == '('){
                int cnt = 1;
                for(++i; true; ++i){
                    if(exp[i] == '(') ++cnt;
                    else if(exp[i] == ')'){
                        --cnt;
                        if(!cnt) break;
                    }
                }
                ++i;
            }
            if(exp[i] == '+' || exp[i] == '-') return false;
        }
        return true;
    }
    int findMatchedLeft(const string& exp, int r)
    {
        int countOfRight = 1;
        for(--r; r >= 0; --r){
            if(exp[r] == ')') ++countOfRight;
            else if(exp[r] == '('){
                --countOfRight;
                if(!countOfRight) break;
            }
        }
        return r;
    }
    string& simplify(string& exp)
    {
        int left, right = 0;
        char head, tail, can;
        while((right = exp.find(')', right)) != string::npos){
            left = findMatchedLeft(exp, right);
        //get info
            if(left && isOperator(exp[left-1])) head = exp[left-1];
            else head = '+';
            if(right+1 < exp.size() && isOperator(exp[right+1])) tail = exp[right+1];
            else tail = '+';
        //analyze
            if(right - left == 2) can = 1;
            else if(head == '/') can = 0;
            else if(head == '*' || head == '-') can = allMulOrDiv(exp.substr(left+1, right-left-1));
            else can = tail == '+' || tail == '-' || allMulOrDiv(exp.substr(left+1, right-left-1));
        //process
            if(can){
                exp.erase(left, 1).erase(right - 1, 1);
                --right;
            }
            else ++right;
        }
    
        return exp;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        int test;
        cin >> test;
        while(cin.get() != '\n') cin.get();
        string exp;
        while(test--){
            getline(cin, exp);
            cout << simplify(exp) << "\n";
        }
        return 0;
    }

    展开全文
  • 括号

    2018-09-09 22:00:17
    2. 若A是合法的括号串,则(A)则是合法的括号串 3. 若A,B是合法的括号串,则AB也是合法的括号串。 小A现在希望删掉S中若干个字符,使得剩下的字符串是一个合法的括号串。小A想知道有多少不同的方案。两个方案是...

    题目描述

    小A有一个只包含左右括号的字符串S。但他觉得这个字符串不够美观,因为它不是一个合法的括号串。一个合法的括号串是这样定义的:
    1. ()是合法的括号串
    2. 若A是合法的括号串,则(A)则是合法的括号串
    3. 若A,B是合法的括号串,则AB也是合法的括号串。

    小A现在希望删掉S中若干个字符,使得剩下的字符串是一个合法的括号串。小A想知道有多少不同的方案。两个方案是不同的,当且仅当他们删除的位置不同。比如当S是(()时,有两种方案。分别是删掉第一个位置,或是删掉第二个位置。

    输入描述:

    第一行一个整数n,代表S的长度。
    第二行输入n个字符,字符要么是(,要么是)。代表串S。

    输出描述:

    一行一个整数,代表不同的方案数。答案对10^9+7取模。

    示例1

    输入

    8
    )(()(())

    输出

    30

    备注:

    20%: n <= 20
    40%: n <= 100
    60%: n <= 1000
    100%: n <= 10000

    思路

    动态规划,但是只需要使用一维的DP
    dp[j]就意味着还有多少个左括号 也就是‘(’;
    原因十分的简单,根据题目要求我们就可以知道,左括号需要和右括号匹配,但是只有一个右括号是没有什么用的。
    打个比方 :
    () 就可以成为一个合法的括号串;
    )( 就不可以成为一个合法的括号串。

    代码

    #include<bits/stdc++.h>
    using namespace std;
    
    #define mod 1000000007
    char ch[10001];
    long long dp[10001];
    
    int main()
    {
        int n;
        cin>>n;
        cin>>ch;
        dp[0]=1;
        for(int i=0;i<n;i++)
        {
            if(ch[i]=='(')
            {
                for(int j=n-i;j>=0;j--)
                    dp[j+1]=(dp[j+1]+dp[j])%mod;
            }
            else
            {
                for(int j=1;j<=n-i;j++)
                    dp[j-1]=(dp[j-1]+dp[j])%mod;
            }
        }
        cout<<((dp[0]-1)+mod)%mod;
        return 0;
    }

    来源:nkw

    展开全文
  • 删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。 说明:输入可能包含了除(和)以外的字符。 示例 1: 输入: "()())()" 输出: ["()()()", "(())()"] 示例 2: 输入: "(a)())()" 输出: ["(a)...

    删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。

    说明: 输入可能包含了除 ( 和 ) 以外的字符。

    示例 1:

    输入: "()())()"
    输出: ["()()()", "(())()"]
    

    示例 2:

    输入: "(a)())()"
    输出: ["(a)()()", "(a())()"]
    

    示例 3:

    输入: ")("
    输出: [""]

    这道题翻译了discuss的最高票解答(能看懂答案就不错了)

    这道题的基本思想是找到多余的括号(注意是所有的),所以基本思路是采用回溯法找到所有有效解,然后加入答案中,先来看几点启发:

    1:怎么找到多余的括号,在Valid Parentheses中,通过stack或者两个计数器left和right分别记录左括号和右括号的个数,可以验证一个左右括号是否符合要求。

    2:如何限制在指定序列中的有效括号数,比如str=()()),采用计数方法(left和right计数器)来统计,发现left=2,right=3,由于left-right>=0,所以当前的子字符串多了一个右括号,需要删除一个),我们可以删除str[1],形成str=(()),也可以删除str[3],形成str=()(),为了避免重复出现答案,这里规定只删除第一个不符合要求的左括号,因为第二种情况会在后面的回溯中遍历到)。

    我们规定几个变量的意思:start_to_count开始计数左右括号的位置,start_to_remove开始准备删除第一个不符合要求右括号的起始搜索点(start_to_remove<=start_to_count)

    class Solution {
    public:
        void Core(string s,vector<string> & res,int start_to_count,int start_to_remove,vector<char> &par){
            int count=0; //采用计数器来统计左右括号数
            for(int i=start_to_count;i<s.size();i++){
                if(s[i]==par[0]){
                    count++; //遇到左括号就+1
                }
                if(s[i]==par[1]){
                    count--; //遇到右括号就-1
                }
                if(count>=0) continue; 如果左括号个数>=右括号个数,继续寻找
                
                for(int j=start_to_remove;j<=i;j++){ //能进到for循环表示count小于0,表示一定要删除一个右括号,那么从start_to_remove开始寻找,找到第一个不满足要求的右括号的位置。
                    if(s[j]==par[1] && (j==start_to_remove || s[j-1]!=par[1])){ //第一个多余的右括号的下标是s[j]==par[1],但是也要考虑边界条件:比如j是第一个元素这种情况
                        Core(s.substr(0,j)+s.substr(j+1),res,i,j,par); //那么删除第一个右括号后的有效字符串就是把第j个字符删掉的剩下的字符串,即new_str=s.substr(0,j)+s.substr(j+1),由于前面i个(下标)字符已经是有效的字符,且把第j个字符给删了,还要考虑新字符串new_str的长度少了1,那么新的开始搜索的字符下标new_start_to_count=i+1-1=i,同理new_start_to_remove=j+1-1,所以递归调用自身,对应参数设置如上所示。
                    }
                }
                return;  //return这里已经处理了剩下子串的所有情况,直接返回,不然会有重复数据。
            }
            reverse(s.begin(),s.end()); //反转原字符,从右往左搜索删除多余的左字符
            if(par[0]=='('){
                vector<char> tmp={')','('};
                Core(s,res,0,0,tmp);
            }
            else res.push_back(s);
        }
        vector<string> removeInvalidParentheses(string s) {
            vector<char> par={'(',')'};
            vector<string> res;
            Core(s,res,0,0,par);
            return res;
        }
    };

     

     

    展开全文
  • 删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。 说明:输入可能包含了除(和)以外的字符。 示例 1: 输入: "()())()" 输出: ["()()()", "(())()"] 示例 2: 输入: "(a)())()" 输出: ["(a)...
  • 给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。返回所有可能的结果。答案可以按任意顺序返回。 示例 1: 输入:s = "()())()" 输出:["(())()","()()()"] 示例 2: ...
  • 1. 逐个删除多余括号(1)思路先从左往右遍历,并删除多余的右括号。设计两个下标指针,分别记录最后删除...处理完右括号后,对字符串进行反向,同样方法处理左括号,得到所求答案。(3)结果 执行用时 :0 ms, 在所
  • 有效括号字符串为空("")、"(" + A + ")"或A + B,其中A和B都是有效的括号字符串,+代表字符串的连接。例如,"","()","(())()"和"(()(()))"都是有效的括号字符串。 如果有效字符串S非空,且不存在将其拆分为S = A+...
  • 301. 删除无效的括号 难度困难 删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。 说明: 输入可能包含了除 ( 和 ) 以外的字符。 示例 1: 输入: "()())()" 输出: ["()()()", "(())()"] 示例 2: ...
  • 有效的括号删除有序数组中的重复项、实现strStr

    千次阅读 多人点赞 2021-08-16 18:16:36
    有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 小编菜解 public static boolean isValid(String s) { if (s.length()%2 != 0) return false; Map hashMap = new HashMap(){...
  • 括号处理相关问题

    2021-07-26 16:16:41
    删除无效的括号 给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。 public class Solution { /** * 思路分析: * 1 ...
  • word批量删除单选、多选题的答案

    千次阅读 2020-04-28 23:07:08
    1、批量删除多选题的答案 Ctrl+H是替换的快捷键 使用菜单-编辑-定位中的替换功能!如果(BD)是英文括号,先查找替换,把英文括号换成中文的!然后再定位查找替换,使用高级-通配符,输入中文的括号(*),替换成...
  • 本计算器回退功能是直接删除到空 ** 代码含有大量注释 本代码算法为本人独立实现,利用List保存后缀表达式,任何中缀表达式都可以无异常的输入输出,算法过程,每一行都注释解释清晰,保证高质量
  • 第一步删除第一个左括号,第二步删除某一个右括号,要保证删除之后的括号序列还是合法的,求将括号删到空为止一共有多少种不同的删除方法,两种方法不同当且仅当存在某一步右括号删除位置不同,答案膜1e9+7 ...
  • 一、问题如何使用正则去掉大括号({**})及里面包含的值;二、代码public class test222 { public static void main(String[] args) { String str="{A}123{aaa}456{bbb}"; str=str.replaceAll("\\{[^}]*\\}","");...
  • 1249. 移除无效的括号

    2020-01-20 21:57:12
    你需要从字符串中删除最少数目的 '(' 或者 ')'(可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下任意一条要求: 空字符串或只包含小写字母...
  • 第一步删除第一个左括号,第二步删除某一个右括号,要保证删除之后的括号序列还是合法的,求将括号删到空为止一共有多少种不同的删除方法,两种方法不同当且仅当存在某一步右括号删除位置不同,答案膜1e9+7 ...
  • 你需要从字符串中删除最少数目的 '(' 或者 ')'(可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下任意一条要求: 空字符串或只包含小写字母...
  • 你需要从字符串中删除最少数目的 '(' 或者 ')' (可以删除任意位置的括号),使得剩下的「括号字符串」有效。 输入:s = "lee(t(c)o)de)" 输出:"lee(t(c)o)de" 解释:"lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行...
  • 7-1 使用函数删除字符串中的字符 (10 分) 输入一个正整数 repeat (0<repeat<10),做 repeat 次下列运算: 输入一个字符串 str,再输入一个字符 c,将字符串 str 中出现的所有字符 c 删除。 要求定义并调用函数...
  • 括号(判定性dp)

    2019-08-04 01:29:26
    headNav=acm 来源:牛客网 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 524288K,其他语言1048576K ...给你一个合法的括号序列s1,每次你可以删除一个"()" 你可以删除0个或者多个"()" 求能...
  • 你需要从字符串中删除最少数目的 '(' 或者 ')'(可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下任意一条要求: 空字符串或只包含小写字母...
  • 提示用户输入用户名,判断用户是否存在,如果存在,要提醒用户是否删除并新建,输入yes就删除,输入no则不删除;用户不存在时,也提醒用户不存在,输入yes新建,输入no则不新建。 答案: #!/bin/bash read...
  • 2209: [Jsoi2011]括号序列 Time Limit: 20 Sec Memory Limit: 259 MB Submit: 894 Solved: 423 [Submit][Status] Description Input 输入数据的第一行包含两个整数N和Q,分别表示括号序列的长度,以及...
  • 你需要从字符串中删除最少数目的 ‘(’ 或者 ‘)’ (可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下 任意一条 要求: 空字符串或只包含...
  • Python快速编程入门课后习题答案

    万次阅读 多人点赞 2019-11-24 13:03:43
    五、程序分析题 第十二章 一、选择题 二、判断题 三、填空题 四、简答题 END 前言 本文整理了填空、选择、判断等一些课后习题答案,具体的编程题可以见:Python快速编程入门课后程序题答案。 第一章 一、填空题 ...
  • 你需要从字符串中删除最少数目的 '(' 或者 ')' (可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下 任意一条 要求: 空字符串或只包含小写...
  • 你需要从字符串中删除最少数目的 '(' 或者 ')'(可以删除任意位置的括号),使得剩下的「括号字符串」有效。 请返回任意一个合法字符串。 有效「括号字符串」应当符合以下任意一条要求: 空字符串或只包含小写字母...
  • 把文本复制到 新建文本.txt,然后重命名为 新建文本.txt.bat,然后放入需要已经重新命名(带括号)好的图片文件夹,可以去除括号。 3 参考 某百度知道答案 转载于:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,779
精华内容 12,311
关键字:

删除括号内的答案