精华内容
下载资源
问答
  • Minimum Add to Make Parentheses Valid 英文题目: Given a string S of ‘(’ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(’ or ‘)’, and in any positions ) so that the result....

    【leetcode】921. Minimum Add to Make Parentheses Valid

    英文题目:

    Given a string S of ‘(’ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(’ or ‘)’, and in any positions ) so that the resulting parentheses string is valid.
    Formally, a parentheses string is valid if and only if:
    ·It is the empty string, or
    ·It can be written as AB (A concatenated with B), where A and B are valid ·strings, or

    It can be written as (A), where A is a valid string.
    Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

    中文释义:题目给你一个字符串,根据括号匹配的规则找出不能正常匹配的括号的个数,例如,“()()”这个就是正常匹配,但是“())”这个就不能正常匹配,最右边的右括号缺少一个左括号来匹配。

    Example 1:

    Input: “())”
    Output: 1

    Example2:

    Input: “(((”
    Output: 3

    Example3:

    Input: “()”
    Output: 0

    Example 4:

    Input: “()))((”
    Output: 4

    解题思路

    括号匹配一般用的都是栈这种数据结构,这题也是用栈来解决,首先我们可以分两部分来解决这个问题,先将字符串转为字符数组,然后遍历字符数组。1、若栈为空,该字符直接入栈。2、若栈不为空,且字符为“(”,直接入栈,再判断栈顶是否有“)”,这些前面“)”都是不能匹配的右括号,用while循环出栈,直到栈顶不为“)”,出栈一个未匹配的数量就加1。3、遇到字符为“)”,就先判断栈顶是否为“(”,若是,则出栈,若不是,则“)”入栈。4、遍历完字符数组后,再计算栈的长度,此时栈内剩下的元素都是没有匹配的括号。

    源代码(java)
    代码片.

    public  int minAddToMakeValid(String S) {
            char[] chars = S.toCharArray();
            int result = 0;
            Stack<Character> stack = new Stack<Character>();
            for (int i = 0; i < chars.length; i++) {
                //若栈为空,直接入栈
                if (stack.empty()) {
                    stack.push(chars[i]);
                } else {
                    //遇到左括号
                    if (chars[i] == '(') {
                        //直接入栈
                        stack.push(chars[i]);
    
                        //判断栈顶是否有")"
                        if (stack.peek() == ')') {
                            //有就出栈,直到栈空或者栈顶元素不是")"
                            while (!stack.empty() && stack.peek() != ')') {
                                stack.pop();
                                result++;
                            }
                        }
                        //左括号入栈
                    }
                    //遇到右括号
                    if (chars[i] == ')') {
                        //判断栈顶是否有"(",有就出栈
                        if (stack.peek() == '(') {
                            stack.pop();
                        }
    
                        //栈顶不是"(",右括号进栈
                        else {
                            stack.push(chars[i]);
                        }
                    }
                }
            }
            //遍历栈内还有未匹配的括号
            while (!stack.empty()) {
                stack.pop();
                result++;
            }
            return result;
        }
    
    展开全文
  • 英文:https://leetcode.com/problems/valid-parentheses/ 题目描述: Given a string s containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. ...

    题目地址:

    中文:https://leetcode-cn.com/problems/valid-parentheses/
    英文:https://leetcode.com/problems/valid-parentheses/

    题目描述:

    Given a string s containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

    An input string is valid if:

    1. Open brackets must be closed by the same type of brackets.
    2. Open brackets must be closed in the correct order.

    Example 1:

    Input: s = "()"
    Output: true
    

    Example 2:

    Input: s = "()[]{}"
    Output: true
    

    Example 3:

    Input: s = "(]"
    Output: false
    

    Example 4:

    Input: s = "([)]"
    Output: false
    

    Example 5:

    Input: s = "{[]}"
    Output: true
    

    Constraints:

    1 <= s.length <= 10^4
    s consists of parentheses only ‘()[]{}’.

    思路:

    括号匹配,经典使用栈的题目。
    扫描整个字符串,如果有左括号就入栈,如果有右括号就与栈顶匹配,如果匹配不上就有问题,返回错误,匹配完后看栈内还有没有剩下的括号没有匹配,如果没有的话就返回正确,有的话就返回错误。

    题解:

    class Solution {
        public boolean isValid(String s) {
            boolean res = false;
            Stack<String> stk = new Stack<String>();
            int len = s.length();
            for(int i=0;i<len;i++){
                String str = s.substring(0,1);
                if(str.equals("[")||str.equals("(")||str.equals("{")) stk.push(str);
                else if(str.equals(")")&&!stk.empty()&&stk.peek().equals("(")) stk.pop();
                else if(str.equals("]")&&!stk.empty()&&stk.peek().equals("[")) stk.pop();
                else if(str.equals("}")&&!stk.empty()&&stk.peek().equals("{")) stk.pop();
                else return false;
                s = s.substring(1);
            }
            if(stk.empty()) res = true;
            return res;
        }
    }
    
    展开全文
  • 1、题目名称 Valid Anagram (易位构词) 2、题目地址 https://leetcode.com/problems/valid-anagram/ 3、题目内容 英文:Given two strings s and t, write a function to deter...

    1、题目名称

    Valid Anagram (易位构词)

    2、题目地址

    https://leetcode.com/problems/valid-anagram/

    3、题目内容

    英文:Given two strings s and t, write a function to determine if t is an anagram of s.

    中文:给出两个字符串,写一个函数判断t是否是s的易位构词

    例如:

    s = "anagram", t = "nagaram", return true.

    s = "rat", t = "car", return false.

    4、题目分析

    易位构词游戏的规则可以参考相关的 维基百科页面 :易位构词是一类文字游戏。它的规则是将组成一个词或短句的字母重新排列顺序,原文中所有字母的每次出现都被使用一次,这样构造出另外一些新的词或短句。现在我们要判断的就是给出两个字符串s和t,判断字符串t能否由s通过易位构词产生。

    5、一个超时的方法

    在做这个题的时候我第一个想到的方法就是,将s和t两个字符串先转换成数组,然后分别对两个数组进行排序,再对两个排序后的数组进行逐位比较。如果发现两个数组中不一致的地方,则返回false,否则返回true。对应的Java代码如下:

    /**
     * 功能说明:LeetCode 242 - Valid Anagram
     * 开发人员:Tsybius2014
     * 开发时间:2015年8月4日
     */
    public class Solution {
    
        /**
         * 判断两个字符串是否为易位构词
         * @param s 字符串1
         * @param t 字符串2
         * @return
         */
        public boolean isAnagram(String s, String t) {
            
            if (s == null || t == null || s.length() != t.length()) {
                return false;
            }
            
            char[] charListS = s.toCharArray();
            char[] charListT = t.toCharArray();
            
            char temp;
            
            //对字符串s和t进行排序
            for (int i = 0; i < charListS.length; i++) {
                for (int j = i + 1; j < charListT.length; j++) {
                    if (charListS[i] > charListS[j]) {
                        temp = charListS[i];
                        charListS[i] = charListS[j];
                        charListS[j] = temp;
                    }
                    if (charListT[i] > charListT[j]) {
                        temp = charListT[i];
                        charListT[i] = charListT[j];
                        charListT[j] = temp;
                    }
                }
            }
    
            //逐个字符比较排序结果
            for (int i = 0; i < charListS.length; i++) {
                if (charListS[i] != charListT[i]) {
                    return false;
                }
            }
            
            return true;
        }
    }

    但是,使用这段代码,OJ返回的结果是超时(Time Limit Exceeded)

    6、解题方法1

    我又想出了一个办法,即循环考察字符串s中的各字符,将字符串t中找到的第一个一样的字符换成字符' '。如果在替换过程中,发现t中已经没有合适的字符进行替换,则返回false。如果直到s中的字符循环完都没有返回false,可认为s与t中所用到的每个字母的数量都是一致的。

    Java代码如下:

    /**
     * 功能说明:LeetCode 242 - Valid Anagram
     * 开发人员:Tsybius2014
     * 开发时间:2015年8月4日
     */
    public class Solution {
    
        /**
         * 判断两个字符串是否为易位构词
         * @param s 字符串1
         * @param t 字符串2
         * @return
         */
        public boolean isAnagram(String s, String t) {
            
            if (s == null || t == null || s.length() != t.length()) {
                return false;
            }
            
            char[] charListS = s.toCharArray();
            char[] charListT = t.toCharArray();
            
            boolean b = false;
            
            //逐个用s的字符对t进行替换
            for (int i = 0; i < charListS.length; i++) {
                b = false;
                for (int j = 0; j < charListT.length; j++) {
                    if (charListS[i] == charListT[j]) {
                        charListT[j] = ' ';
                        b = true;
                        break;
                    }
                }
                if (!b) {
                    return false;
                }
            }
            
            return true;
        }
    }

    这段代码的Runtime为1640ms

    7、解题方法2

    其实上面提到的那个超时(TLE)的方法,如果用Arrays.sort函数对数组进行排序,就可以比自己用两个for循环要快很多。

    Java代码如下:

    import java.util.Arrays;
    
    /**
     * 功能说明:LeetCode 242 - Valid Anagram
     * 开发人员:Tsybius2014
     * 开发时间:2015年8月4日
     */
    public class Solution {
    
        /**
         * 判断两个字符串是否为易位构词
         * @param s 字符串1
         * @param t 字符串2
         * @return
         */
        public boolean isAnagram(String s, String t) {
            
            if (s == null || t == null || s.length() != t.length()) {
                return false;
            }
            
            char[] charListS = s.toCharArray();
            char[] charListT = t.toCharArray();
            
            Arrays.sort(charListS);
            Arrays.sort(charListT);
            
            for (int i = 0; i < charListS.length; i++) {
                if (charListS[i] != charListT[i]) {
                    return false;
                }
            }
            
            return true;
        }
    }

    这个方法用了336ms

    8、解题方法3

    最后还有一种方法,思路是我在Discuss中看到的,即通过一个长度为26的整形数组,对应英文中的26个字母a-z。从前向后循环字符串s和t,s中出现某一字母则在该字母在数组中对应的位置上加1,t中出现则减1。如果在s和t中所有字符都循环完毕后,整型数组中的所有元素都为0,则可认为s可由易位构词生成t。

    Java代码如下:

    /**
     * 功能说明:LeetCode 242 - Valid Anagram
     * 开发人员:Tsybius2014
     * 开发时间:2015年8月4日
     */
    public class Solution {
    
        /**
         * 判断两个字符串是否为易位构词
         * @param s 字符串1
         * @param t 字符串2
         * @return
         */
        public boolean isAnagram(String s, String t) {
            
            if (s == null || t == null || s.length() != t.length()) {
                return false;
            }
    
            //字母统计
            int[] letterCounter = new int[26];
            for (int i = 0; i < s.length(); i++) {
                letterCounter[s.charAt(i) - 'a']++;
                letterCounter[t.charAt(i) - 'a']--;
            }
            
            //如果s的各个字母数量与t一致,那么letterCounter数组的元素应该全部为0
            for (int count : letterCounter) {
                if (count != 0) {
                    return false;
                }
            }
            
            return true;
        }
    }

    附:使用JavaScript语言实现的解题代码(2016年1月23日加入)

    方法1:

    /**
     * 判断两个字符串是否为易位构词
     * @param {string} s 字符串1
     * @param {string} t 字符串2
     * @return {boolean}
     */
    var isAnagram = function(s, t) {
        if (s === null || t === null || s.length != t.length) {
            return false;
        }
        s = s.split('').sort(); //将字符串转换为数组后进行排序
        t = t.split('').sort();
        for (var i = 0; i < s.length; i++) {
            if (s[i] != t[i]) {
                return false;
            }
        }
        return true;
    };

    方法2:

    /**
     * 判断两个字符串是否为易位构词
     * @param {string} s 字符串1
     * @param {string} t 字符串2
     * @return {boolean}
     */
    var isAnagram = function(s, t) {
        if (s === null || t === null || s.length != t.length) {
            return false;
        }
        var counter = { };
        counter.length = 26;
        var i;
        for (i = 0; i < counter.length; i++) {
            counter[i] = 0;
        }
        for (i = 0; i < s.length; i++) {
            counter[s.charCodeAt(i) - 97]++; //获取字符串指定位置字符的ASC码
            counter[t.charCodeAt(i) - 97]--;
        }
        for (i = 0; i < counter.length; i++) {
            if (counter[i] !== 0) {
                return false;
            }
        }
        return true;
    };

    END

    转载于:https://my.oschina.net/Tsybius2014/blog/487807

    展开全文
  • 英文 https://leetcode.com/problems/valid-sudoku/description/ 解法1 逐行扫描,维护扫描位置的行和列和块集合。 分析: 1.需要维护的集合个数分析:行集合为1个,列集合为9个,块集合为3个。 1)按行扫描,前后.....

    题目链接

    中文

    https://leetcode-cn.com/problems/valid-sudoku/description/

    英文

    https://leetcode.com/problems/valid-sudoku/description/

    解法1

    逐行扫描,维护扫描位置的行和列和块标志数组。

    分析:
    1.标志数组大小为9,用于存放1~9是否在该检查区域出现,若出现则判定为不是数独。当检查区域结束时,维护的数组复位为全部不出现。
    2.需要维护的数组个数分析:行扫描情况下,行数组为1个,列数组为9个,块数组为3个。
    1)每行扫描结束时检查区域结束,因此只需 1 个行数组。
    2)列数组的结束区域全部在最后一行,知道最后一行结束才可以结束列数组,每行9列,因此列数组为9个。
    3)块数组每扫描3行到达一次结束区域,复位一次,一共9列,每3列一个块,因此块数组为3个。
    2.查重策略:每加入一个非空字符,对当前维护数组的该字符标志位判断,若该字符标志位为true,则不满足数独要求,终止算法,返回假 flase。若该字符标志位为flase,继续下一步。
    3.数组更新策略:可以通过当前列j来判断将该字符更新哪个数组。
    1)行数组有 1 个,每次扫描都更新该数组。
    2)块数组有3个,更新的数组可以根据当前列j来判断,分别3个区域:0 ~ 2更新一号数组,3 ~5更新2号数组,6 ~ 8更新3号数组,因此可以用 j%3来选择更新的数组下标。
    3)列数组有9个,更新数组下标和当前列号一致。
    4.复位策略:行数组每行复位一次,块数组每3行复位一次,列数组结束才复位。
    代码:

    class Solution {
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            vector<bool> used(9,false);
            vector<vector<bool> > cols(9,used);
            vector<vector<bool> > squ(3,used);
            for(int i=0;i < board.size();++i){
                //复位工作
                vector<bool> row(used);
                if(i%3==0)
                    for(int k=0;k<3;++k)
                        squ[k] = used;
                for(int j=0;j<board[i].size();++j)
                {
                    char c = board[i][j];
                    if(c!='.')
                    {
                        c = c - '1';
                        if( row[c] ==true)
                            return false;
                        row[c]=true;
                        int sn = j/3;
                        if(squ[sn][c]==true)
                            return false;
                        squ[sn][c]=true;
                        if(cols[j][c]==true)
                            return false;
                        cols[j][c]=true;
                    }
                }
            }
            return true;
            
        }
    };
    

    复杂度分析:
    时间复杂度:O(n2):扫描列表复杂度为n2
    空间复杂度:O(1),维护数组大小为(列数组9 + 块数组 3 + 行数组 1)*数组大小9 = 117.

    解法2 记录字符出现的所有位置,并比对位置判断

    来源 leetCode

    struct Pos {
        int x, y;
    };
    
    class Solution {
    public:
    	/*
    		判断两个位置是否在同一列、同一行或者同一个3*3的块中
    		若在 返回 false
    		若不在 返回 true
    	*/
        bool judge(Pos& a, Pos& b) {
            if(	a.x == b.x || //同一列
            	a.y == b.y || //同一行
            	(a.x/3 == b.x/3) && (a.y/3 == b.y/3)) //同一块
                return false;
            return true;
        }
        bool isValidSudoku(vector<vector<char>>& board) {
            //存储0~9所在的所有位置
            vector<vector<Pos> > v(10);
            //遍历所有元素 时间复杂度 n*n
            for(int x = 0; x < 9; ++x) {
                for(int y = 0; y < 9; ++y) {
                    if(board[x][y] == '.') continue;
                    int idx = board[x][y] - '0';
                    Pos pos = {x, y};
                   //当字符出现过时
                    if(!v[idx].empty()) {
                        //对出现过的所有位置进行对比,判断是否不满足数独条件
                        for(auto p : v[idx]) {
                            if(!judge(p, pos))
                                return false;
                        }
                    }
                    //将出现位置添加到位置数组中
                    v[idx].push_back(pos);
                }
            }
            return true;
        }
    };
    

    复杂度分析:
    时间复杂度:n3,遍历n2,比对位置最差为n(相同字符最多同时出现9次),最好为1
    空间复杂度:O(1),若每个位置都不为空,最高需要占用9*9=81个Pos结构的空间,占用空间和元素个数一致。

    展开全文
  • https://leetcode.com/problems/valid-palindrome/ 给定一个字符串,问其在忽略大小写的情况下是否是回文串。忽略英文字母和数字以外的所有字符。 双指针。左指针先走到第一个英文字母或数字,右指针也如此,然后...
  • 1、题目名称 Valid Palindrome(回文字符串) 2、题目地址 https://leetcode.com/problems/valid-palindrome/ 3、题目内容 英文:Given a string, determine if it is a palindrom...
  • 今年双十一购物节来得又早又快!前几天,第一波“抢先购”的锣鼓已敲响,有童鞋表示:“付定金时感觉什么都买得起,...挺住~小U的正式提问来了:大家知道这几天传遍全网的“尾款”“定金”“直播带货”等词用英文怎...
  • 英文题目: Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. An input string is valid if: 1.Open brackets must be ...
  • 1、题目名称 Valid Parentheses(合理的括号搭配) 2、题目地址 https://leetcode.com/problems/valid-parentheses/ 3、题目内容 英文:Given a string containing just the charact...
  • 给定一个字符串,题目保证只有英文字母。如果其每个字母出现的次数相同,则返回YES,否则如果删去其中一个字符,能使得每个字母出现次数相同,则也返回YES,否则返回NO。 由上面可以知道,返回YES的情况有下面几个:...
  • 1.编辑器 我使用的是win10+vscode+leetcode+python3 ...Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. An input...
  • 有效的字符包括英文和数字 分析:前后判断。。 答案: class Solution { public: bool isPalindrome(string s) { if (s.empty()) return true; int leftIdx = 0; int rightIdx = s.size() - 1; s = ...
  • leetcode笔记:Valid Palindrome

    千次阅读 2015-08-31 13:42:14
    这道题考察回文数(palindrome),这一概念起源于在数学中一类数字,这类数字拥有这样的特征:设n是一任意自然数。...同理,可以定义英文/中文的回文数,概念和以上的类似,本题就是检测字符串是否为回文数。
  • no valid settings file could be found qt中文意思是 找不到有效的设置文件。 此时,只需要删除项目中的.user 文件,再打开,打开后再点C开头那个英文,重新配置,重新构建,就可以了。
  • 文章目录1....Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be c
  • 今天软件突然出现 not a valid file name 提示,各种方法测试了,都不行,后来 把软件安装目录改成英文名称就正常了
  • 我的网站在公司做的运行一切都没问题,回家后咋自己的电脑上出现了Connection must be valid and open.这个问题。 我最后还是在英文网站的一个不起眼的小角落中发先解决办法。 先说一下这个bug的引起原因有几种! ...
  • 题目 给定一个只包含'('和')'的字符串,找出最长的包含有效括号的子串的长度。 示例1: 输入: "(()" ...解释: 最长有效括号子串为"()" ...链接(英文版):https://leetcode.com/problems/longest-...
  • 1、题目名称 Valid Number(判断字符串中内容是否为数字) 2、题目地址 https://leetcode.com/problems/valid-number/ 3、题目内容 英文:Validate if a given string is numeric. 中文:给出一...
  • 英文字面意思来看:找不到可用证书。 出现原因:可能因为在迁移开发环境时出现的差错或连接单位或公司网络没有得到认证。 总而言之,就是Android Studio没有获得使用网络的权限,无法访问...
  • 异常:Invalid character found in the request target.The valid characters are defined in RFC 7230 and RFC3986 升级tomcat之后就出现该问题,网上查询了下,是由于RFC 3986规范定义了Url中只允许包含英文字母...
  • Valid Palindrome II验证回文字符串 Ⅱ【Easy】【Python】【双指针】 题目 英文题目链接 Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. ...
  • ORA-01843: not a valid month解决办法

    千次阅读 2014-04-26 16:01:55
    遇到ORA-01843:not a valid month的错误,根据搜索,知道是nls_date_language这个参数引起的问题,在nls_date_language参数设置为 AMERICAN的时候,是可以显示英文月份的,所以查看nls_date_language这个...
  • 1.编辑器 我使用的是win10+vscode+leetcode+python3 环境配置参见我的博客: 链接 2.第一百二十二题 (1)题目 英文
  • 升级tomcat8及更高版本带来的问题 ...解析,而 RFC 3986规范定义了Url中只允许包含英文字母(a-zA-Z)、数字(0-9)、-_.~4个特殊字符以及所有保留字符 (RFC3986中指定了以下字符为保留字符:! * ’ ( ) ; : @ & = +
  • No architectures to compile for (ONLY_ACTIVE_ARCH=YES, active arch=x86_64, VALID_ARCHS=i386).问题描述: 看懂了英文你就解决了这个问题。 EDIT:As far as I know (please point it out if there’s ...
  • Tomcat 报 The valid characters are defined in RFC 7230 and RFC 3986!! 1.下面是原本的代码 在tomcat1.0.6版以上增加了新特性,严格按照 RFC 3986规范进行访问解析,而 RFC 3986规范定义了Url中只允许包含英文字母...
  • 今天在做一个请求的时候,tomcat出现The valid characters are defined in RFC 7230 and RFC 3986这个错误,因为我的get请求包含中文字符,现在高版本的的tomcat是很规范的,Url中只允许包含英文字母(a-zA-Z)、...
  • UE4蓝图API翻译【节点】---? Is Valid

    千次阅读 2018-04-14 20:45:54
    所以当书写、交流、等实际使用时切记: 须以英文为准 若你对我的翻译感兴趣,请点击【博客进度/模板共享】 改节点未在文档找到对应的,所以一下内容为本人摘录。 官网地址 ? Is Valid 翻译 是有效的?...
  • 今天上午搭建交叉编译环境,安装arm-linux-gcc时,source /etc/profile的时候,老是跳出“路径 not a valid identifier”,检查了半天也不知道什么原因,后来在网上看到有人说是中英文的问题,我回头检查一看,果然...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 312
精华内容 124
热门标签
关键字:

valid英文