每日一题：2.删除无效的括号（C++） |
您所在的位置：网站首页 › 括号内记得删除 › 每日一题：2.删除无效的括号（C++） |
|
每日一题：2.删除无效的括号（C++）
题目：给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。 解题思路： 先从括号的规则下手，括号左右配对，由此我们先找到左右括号多出来的个数，找出括号多出的个数后，删除他们就是我们要得到的最长合法字符串 对字符串进行删减工作 先判断当前字符串是否为合法字符串若不合法则进行字符删减工作（3. 4. 5.）进行判断将会导致结果重复的运算免去（剪枝）当要删除的字符个数大于剩余字符个数时终止当前回溯（剪枝）对当前回溯遍历到的字符进行辨别，若未左右括号分别进行删减尝试（回溯 返回 1.） class Solution { public: vector result; //定义公共变量result进行结果的保存 vector removeInvalidParentheses(string s) { int left_remove = 0, right_remove = 0; //定义left_remove\right_remove分别保存左、右括号多出的个数 need_remove(s, &left_remove, &right_remove); //后面定义了need_remove方法对左右括号多出的个数进行判断 try_remove(s, 0, left_remove, right_remove); //后面定义了try_remove（回溯算法）对字符串进行筛选 return result; //返回结果 } void try_remove(string s, int start, int left_remove, int right_remove){//（回溯方法） if(left_remove == 0 && right_remove == 0){ //判断当前字符串内是否存在多出的左右括号 if(whether_valid(s)) result.push_back(s);//删除多余括号个数后，判断是否使字符串达到了合法条件，合法则保存当前结果 return; //此次回溯结束 } for(int i = start; i < s.length(); i++){ //利用for循环遍历当前回溯的字符串 if(i > start && s[i] == '(' && s[i - 1] == '(') continue;//若连着两个相同的括号，则跳过当前循环(剪枝) else if(i > start && s[i] == ')' && s[i - 1] == ')') continue; if((left_remove + right_remove) > s.length() - i) break;//若待删除括号个数大于剩余字符个数则结束当前回溯（字符串已不合法） if(left_remove > 0 && s[i] == '(') //若右括号有多余的个数，且当前遍历字符为右括号，尝试删除 try_remove(s.substr(0,i) + s.substr(i + 1), i, left_remove - 1, right_remove);//进行回溯 else if(right_remove > 0 && s[i] == ')') //与上同理 try_remove(s.substr(0,i) + s.substr(i + 1), i, left_remove, right_remove - 1); } } void need_remove(string s, int* left_remove, int* right_remove){//定义need_remove方法判断左右括号多余个数 for(char temp : s){ //利用for循环遍历字符串 if(temp == '(') *left_remove += 1; //若为左括号，待删除个数加1 else if(temp == ')') { //若为右括号 if(*left_remove != 0){ //若前面有与当前右括号配对的左括号，则左括号待删除个数减1 *left_remove -= 1; } else *right_remove += 1; //否则右括号待删除个数加1 } } } bool whether_valid(string s){ //定义whether_valid方法判断字符串是否合法 int left_brackets = 0; //定义left_brackets定义左括号出现次数 for(char temp : s){ //利用for循环遍历字符串 if(temp == '(') left_brackets ++; //若当前遍历的字符为左括号 left_brackets加1 else if(temp == ')') { //否则left_brackets减1 left_brackets --; if(left_brackets < 0) return false; //若左括号个数小于0，则代表右括号多于左括号，当前字符串不合法 } } return left_brackets == 0; //所有字符串判断完成后，返回结果，若左括号为0，说明左右括号相互匹配，返回1（true）否则返回0（false） } };作者：yi-si-cb（倚肆） 链接：https://leetcode-cn.com/problems/next-greater-element-i/solution/xie-shi-bao-li-suan-fa-by-yi-si-cb-dsk2/ |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |