leetcode385-迷你语法分析器

原题

给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。

列表中的每个元素只可能是整数或整数嵌套列表

提示: 你可以假定这些字符串都是格式良好的:

  • 字符串非空
  • 字符串不包含空格
  • 字符串只包含数字0-9, [, - ,,, ]
     

示例 1:

给定 s = "324",

你应该返回一个 NestedInteger 对象,其中只包含整数值 324。
 

示例 2:

给定 s = "[123,[456,[789]]]",

返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表:

1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表:
    i. 一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789

解法

本题解同步发于leetcode题解区:java递归 2ms 100%

捷报:发于leetcode的题解已经成为Java分类下阅读量最高的一篇,也是我写的所有题解中点赞数最多的一篇?

思想

见代码部分

代码

设定一个getNest()函数用于返回一个列表类型的NestedInteger。

重要的思想是通过类的全局字符数组和一个下标值让每次调用递归函数都知道要处理哪个位置。

class Solution {
    //递归函数通过字符数组和cur下标确定要处理的位置l
    char[] chars;
    int cur = 0;
    public NestedInteger deserialize(String s) {
        chars = s.toCharArray();
        //本身不是一个集合而是一个整数的情况
        if(chars[0]!='[') return new NestedInteger(Integer.valueOf(s));
        //调用递归函数返回根集合
        return getNest();
    }
    public NestedInteger getNest(){
        NestedInteger nest = new NestedInteger();
        int num = 0;//num用于缓存用逗号分割的整数类型的值
        boolean negative = false;//当前记录的整数是不是负数
        while(cur!=chars.length-1){
            cur ++;
            if(chars[cur]==',') continue;
            if(chars[cur]=='[') nest.add(getNest());//遇到[递归获取子集合
            else if(chars[cur]==']') return nest;
            else if(chars[cur]=='-') negative = true;
            else{//是数字的情况
                if(negative) num = 10*num - (chars[cur]-48);
                else num = 10*num + (chars[cur]-48);
                //如果下一个字符是,或者]说明当前数字已经记录完了,需要加入集合中
                if(chars[cur+1]==','||chars[cur+1]==']'){ 
                    nest.add(new NestedInteger(num));
                    num = 0;
                    negative = false;
                }
            }
        }
        return null;
    }
}

2020/06/08编辑:写这篇题解的时候刚开始用Java刷题不久,写的代码不是很优雅,这个代码有几处地方可以修改一下让代码更清晰规范一些:

  • 这段代码中的48代表的就是字符'0',建议使用'0'替换48
  • negative是布尔型,其实可以优化成整型sign,后面就不需要用if-else进行判断,代码更加精炼。

这些都不是大问题,只是建议大家写代码时考虑写的整洁、优雅一些,这也是我们程序员的一种能力,优化后的代码如下:

class Solution {
    //递归函数通过字符数组和cur下标确定要处理的位置
    char[] chars;
    int cur = 0;
    public NestedInteger deserialize(String s) {
        chars = s.toCharArray();
        //本身不是一个集合而是一个整数的情况
        if(chars[0]!='[') return new NestedInteger(Integer.valueOf(s));
        //调用递归函数返回根集合
        return getNest();
    }
    public NestedInteger getNest(){
        NestedInteger nest = new NestedInteger();
        int num = 0;//num用于缓存用逗号分割的整数类型的值
        int sign = 1;//当前记录的整数的符号,1代表整数,-1代表负数
        while(cur!=chars.length-1){
            cur ++;
            if(chars[cur]==',') continue;
            if(chars[cur]=='[') nest.add(getNest());//遇到[递归获取子集合
            else if(chars[cur]==']') return nest;
            else if(chars[cur]=='-') sign = -1;
            else{//是数字的情况
                num = 10*num + sign * (chars[cur]-'0');
                //如果下一个字符是,或者]说明当前数字已经记录完了,需要加入集合中
                if(chars[cur+1]==','||chars[cur+1]==']'){ 
                    nest.add(new NestedInteger(num));
                    num = 0;
                    sign = 1;
                }
            }
        }
        return null;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode385-%e8%bf%b7%e4%bd%a0%e8%af%ad%e6%b3%95%e5%88%86%e6%9e%90%e5%99%a8/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月27日 20:32
下一篇 2020年1月29日

相关推荐

  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例: 输入: [1,2,1,3,2,5] 输出: [3,5…

    算法 2020年4月28日
    0150
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    0100
  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • leetcode56-合并区间

    原题 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]…

    算法 2020年4月16日
    0160
  • leetcode876-链表的中间结点

    原题 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入: [1,2,3,4,5] 输出: 此列表中的结…

    算法 2020年3月23日
    090
  • leetcode131-分割回文串

    原题 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], …

    算法 2020年5月22日
    0100
  • leetcode69-x的平方根

    原题 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例1: 输入:…

    算法 2019年12月30日
    040
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0110
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0710
  • leetcode205-同构字符串

    原题 给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换,同时保留字符的顺…

    算法 2019年12月21日
    0220

发表回复

登录后才能评论