精华内容
下载资源
问答
  • 有效的括号字符串

    2020-08-05 21:31:04
    有效的括号字符串 给定一个只包含三种字符的字符串:(、)和*,写一个函数来检验这个字符串是否为有效字符串,有效字符串具有如下规则: 任何左括号(必须有相应的右括号)。 任何右括号)必须有相应的左括号(。 左括号...

    有效的括号字符串

    给定一个只包含三种字符的字符串:()*,写一个函数来检验这个字符串是否为有效字符串,有效字符串具有如下规则:

    • 任何左括号(必须有相应的右括号)
    • 任何右括号)必须有相应的左括号(
    • 左括号(必须在对应的右括号之前)
    • *可以被视为单个右括号),或单个左括号(,或一个空字符串。
    • 一个空字符串也被视为有效字符串。

    示例

    输入: "()"
    输出: True
    
    输入: "(*)"
    输出: True
    
    输入: "(*))"
    输出: True
    

    题解

    /**
     * @param {string} s
     * @return {boolean}
     */
    var checkValidString = function(s) {
        var n = s.length;
        var lSeq = 0;
        for(let i=0;i<n;++i){
            if(s[i] !== ")") ++lSeq;
            else --lSeq;
            if(lSeq < 0) return false; 
        }
        if(lSeq === 0) return true;
        var rSeq = 0;
        for(let i=n-1;i>=0;--i){
            if(s[i] !== "(") ++rSeq;
            else --rSeq;
            if(rSeq < 0) return false;
        }
        return true;
    };
    

    思路

    采用双向遍历的方式,两种极端边界假设,首先假设所有*都为(,因左括号必须在配对的左边,故从左向右遍历,看是否足够覆盖所有),然后假设假设所有*都为),因右括号必须在配对的右边,故从右向左遍历,看是否足够覆盖所有(,如果双向都能够成立,那么就能够满足题目要求条件。具体实现是采用两个计量变量lSeqrSeq,正向扫描时遇到非)时就自增计量变量,否则就自减计量变量,如果计量值负值,那么说明不符合匹配条件,直接返回false,若一次遍历正好完全匹配,则直接返回true,剪枝不再进行逆向遍历,在进行逆向遍历时同理,当逆向扫描到非(时就自增计量变量,否则就自减计量变量,如果计量值负值,那么说明不符合匹配条件,直接返回false,两次遍历都正常完成则返回true

    每日一题

    https://github.com/WindrunnerMax/EveryDay
    

    参考

    https://leetcode-cn.com/problems/valid-parenthesis-string
    
    展开全文
  • 678. 有效的括号字符串 难度:中等 题目描述 解题思路 1、抄的答案 思路好巧妙,反正我自己肯定想不出来 /* * 678. 有效的括号字符串 * 2020/8/24 */ public boolean checkValidString(String...

    678. 有效的括号字符串

    难度:中等
    题目描述
    在这里插入图片描述

    解题思路

    1、抄的答案

    思路好巧妙,反正我自己肯定想不出来
    在这里插入图片描述

    /*
    				  * 678. 有效的括号字符串
    				  * 2020/8/24
    				  */
    				 public boolean checkValidString(String s) {
    					 
    					 int left = 0,right = 0; 
    					 //加上*号之后,未匹配左括号的数量从一个值变成了一个范围,用两个变量来记录这个范围的上界和下界
    					 for (int i = 0; i < s.length(); i++) {
    						char c = s.charAt(i);
    						if(c == '(') {
    							left++;
    							right++;
    						}else if(c == '*') {//如果left不为空,说明左括号比较多,*作为右括号
    							if(left > 0)
    								left--;
    							right++;
    						}else {  //如果是右括号
    							if(left > 0)
    								left--;
    							right--;
    							
    						}
    						if(right < 0) { //right<0 说明把*当作右括号也不够左括号数量
    							return false;
    						}
    					
    					}
    

    在这里插入图片描述

    双栈匹配

    还是可以用传统括号匹配的方式,用栈模拟

    public boolean checkValidString(String s) {
    						Stack<Integer> left = new Stack<>();
    						Stack<Integer> star = new Stack<>();
    						for (int i = 0; i < s.length(); i++) {
    							char c = s.charAt(i);
    							if(c == '(') {
    								left.push(i);
    							}else if(c == '*') {
    								star.push(i);
    							}else { //如果是右括号,寻找匹配
    								if(!left.isEmpty()) {
    									left.pop();
    								}else if(!star.isEmpty()) {
    									star.pop();
    								}else {
    									return false;
    								}
    							}
    						}
    						
    						//处理剩下的,只有左括号下小于※下标才能匹配上
    						while(!left.isEmpty()) {
    							if(!star.isEmpty() && left.pop() < star.pop()) {
    								continue;
    							}else {
    								return false;
    							}
    						}
    						return true;
    
    					}
    

    在这里插入图片描述

    展开全文
  • 678.有效的括号字符串

    2019-03-25 09:44:49
    有效的括号字符串 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( 必须有相应的右括号 )。 任何右括号 ) 必须有相应的左括号...

    有效的括号字符串

    给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:

    1. 任何左括号 ( 必须有相应的右括号 )。
    2. 任何右括号 ) 必须有相应的左括号 ( 。
    3. 左括号 ( 必须在对应的右括号之前 )。
      • 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
    4. 一个空字符串也被视为有效字符串。

    示例 1:

    输入: "()"
    输出: True
    

    示例 2:

    输入: "(*)"
    输出: True
    

    思路+代码+注释:

    public boolean checkValidString(String s) {
            /*
            思路:使用left栈存储(的位置,star栈存储*的位置
            遍历字符串,遇到)如果left不为空弹出一个(,否则看star如果star不为弹出一个*,如果都为空那么无法抵消)返回false。
            遍历完字符串后,在使用star中的*抵消left中的(,如果*的位置在(的左边那么无法抵消左括号返回false,抵消完后如果left栈没有左括号说明(抵消完毕返回true,
            否则返回false
             */
                Stack<Integer> left=new Stack<>();
                Stack<Integer> start=new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c=s.charAt(i);
                if (c=='(')
                {
                    left.add(i);
                }else if (c=='*')
                {
                    start.add(i);
                }else {
                    if (left.size()>0)
                    {
                        left.pop();
                    }else if (start.size()>0)
                    {
                        start.pop();
                    }else {
                        return false;
                    }
                }
            }
            while (left.size()>0 && start.size()>0)
            {
                int lIndex=left.peek();
                int sIndex=start.peek();
                //如果*在(左边那么是无法抵消左括号的,返回false
                if (sIndex<lIndex)
                {
                    return false;
                }else {
                    left.pop();
                    start.pop();
                }
            }
            if (left.size()==0)
            {
                return true;
            }else {
                return false;
            }
        }
    
    展开全文
  • 678. 有效的括号字符串 贪心解法好牛啊,但是我没怎么懂... 给定一个只包含三种字符的字符串:(,)和*,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号(必须有相应的右括号...

    678. 有效的括号字符串

    贪心解法好牛啊,但是我没怎么懂...

    给定一个只包含三种字符的字符串:(  和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:

    1. 任何左括号 ( 必须有相应的右括号 )
    2. 任何右括号 ) 必须有相应的左括号 ( 。
    3. 左括号 ( 必须在对应的右括号之前 )
    4. * 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
    5. 一个空字符串也被视为有效字符串。

    示例 1:

    输入: "()"
    输出: True
    

    示例 2:

    输入: "(*)"
    输出: True
    

    示例 3:

    输入: "(*))"
    输出: True
    

    注意:

    1. 字符串大小将在 [1,100] 范围内。
    class Solution {
        public boolean checkValidString(String s) {
            int left=0;
            int right=0;
            int n=s.length();
            for(int i=0;i<n;i++){
                left+=s.charAt(i)==')'?-1:1;//把星号全都当成左括号
                right+=s.charAt(n-i-1)=='('?-1:1;//把星号全都当成右括号
                if(left<0||right<0)return false;
            }
            return true;
        }
    }

     

    展开全文
  • 有效的括号字符串 (对应leetcode第678题) 题目描述 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( 必须有相应的右括号 )。...
  • 有效的括号字符串 给定一个只包含三种字符的字符串:(,)和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 (必须有相应的右括号 )。 任何右括号 )必须有相应的左...
  • 有效的括号字符串 题目 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( 必须有相应的右括号 )。 任何右括号 ) 必须有相应的...
  • 有效的括号字符串 题目网址:https://leetcode-cn.com/problems/valid-parenthesis-string/ 题目描述: 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符...
  • 678. 有效的括号字符串 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( 必须有相应的右括号 )。 任何右括号 ) 必须有相应的左...
  • 有效的括号字符串 思路分析 按照下面的原则进行匹配:遇到左括号或者*的时候,将这两者的位置压入栈。 遇到右括号,先去匹配左括号。如果左括号不够匹配,再去匹配*,如果两个都不够匹配的话,证明当前字符串不合法...
  • leetcode678有效的括号字符串Valid Parenthesis String 题目描述: 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( ...
  • 给定一个只包含三种字符的字符串:(,)和*,写一个函数来检验这个字符串是否为有效字符串有效字符串具有如下规则: 任何左括号 ( 必须有相应括号 )。 任何右括号 ) 必须有相应括号 ( 。 左括号 ( ...
  • 678. 有效的括号字符串 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( 必须有相应的右括号 )。 任何右括号 ) 必须有相应的左...
  • 678 有效的括号字符串

    2020-07-28 22:09:23
    给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串有效字符串具有如下规则: 任何左括号 ( 必须有相应括号 )。 任何右括号 ) 必须有相应括号 ( 。 左括号 ( ...
  • 有效的括号字符串 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( 必须有相应的右括号 )。 任何右括号 ) 必须有相应的左括号...
  • LeetCode算法题——有效的括号字符串(C++实现)前言:题目官方示例解题思路和具体实现过程:代码总结 前言: 坚持写算法的第二天 题目 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串...
  • 有效的括号字符串之DFS/贪心/双向遍历/双栈
  • 有效的括号字符串 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则: 任何左括号 ( 必须有相应的右括号 )。任何右括号 ) 必须有相应的左括号 ...
  • 给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串有效字符串具有如下规则: 任何左括号 ( 必须有相应括号 )。 任何右括号 ) 必须有相应括号 ( 。 左括号 ( ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,285
精华内容 2,114
关键字:

有效的括号字符串