Go Java 算法之迷你语法分析器示例详解

目录
  • 迷你语法分析器
  • 方法一：深度优先遍历（Java）
  • 方法二：栈（Go）

迷你语法分析器

给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。

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

  • 示例 1：

输入：s = "324",

输出：324

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

  • 示例 2：

输入：s = "[123,[456,[789]]]",

输出：[123,[456,[789]]]

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

一个 integer 包含值 123

一个包含两个元素的嵌套列表：

i. 一个 integer 包含值 456

ii. 一个包含一个元素的嵌套列表

a. 一个 integer 包含值 789

提示：

  • 1 <= s.length <= 5 * 104
  • s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
  • 用例保证 s 是可解析的 NestedInteger
  • 输入中的所有值的范围是 [-106, 106]

方法一：深度优先遍历（Java）

根据题意，一个 NestedInteger 实例只能包含下列两部分之一：1）一个整数；2）一个列表。

列表中的每个元素都是一个 NestedInteger 实例。据此，NestedInteger 是通过递归定义的，因此也可以用递归的方式来解析。

注意序列化的String，有2个特殊含义，导致不能用String.split()。否则实现起来会比较困难。

逗号： 表示分割“同层级”的元素

中括号[] : 表示1个List，可以有兄弟节点Integer。

如果用逗号分割，可能会割裂了[]的List含义。

class Solution {
    int index = 0;
    public NestedInteger deserialize(String s) {
        if (s.charAt(index) == '[') {
            index++;
            NestedInteger ni = new NestedInteger();
            while (s.charAt(index) != ']') {
                ni.add(deserialize(s));
                if (s.charAt(index) == ',') {
                    index++;
                }
            }
            index++;
            return ni;
        } else {
            boolean negative = false;
            if (s.charAt(index) == '-') {
                negative = true;
                index++;
            }
            int num = 0;
            while (index < s.length() && Character.isDigit(s.charAt(index))) {
                num = num * 10 + s.charAt(index) - '0';
                index++;
            }
            if (negative) {
                num *= -1;
            }
            return new NestedInteger(num);
        }
    }
}

时间复杂度：O（n）

空间复杂度：O（n）

方法二：栈（Go）

我们只需关注字符串s中的[、]和,字符，其他字符均可转为数字，初始化栈时，将一个空的NestedInteger加入其中，防止越界。

顺序遍历，3 种情况：

[ ：新建列表，入栈

数字和-：累加字符串

]和,：字符串加完，加入列表

]：出栈，结果加入上级列表

func deserialize(s string) *NestedInteger {
  if s[0] != '[' {
    integer, _ := strconv.Atoi(s)
    nestedInteger := &NestedInteger{}
    nestedInteger.SetInteger(integer)
    return nestedInteger
  }
  stack, integer := []*NestedInteger{}, ""
  for _, ch := range s {
    switch ch {
      case '[':
        stack = append(stack, &NestedInteger{}) // 入栈
      case ']':
        fallthrough
      case ',':
        if integer != "" {
          int, _ := strconv.Atoi(integer)
          nestedInteger := NestedInteger{}
          nestedInteger.SetInteger(int)
          stack[len(stack) - 1].Add(nestedInteger)
          integer = ""
        }
        if ch == ']' && len(stack) > 1 { // 出栈
          stack[len(stack) - 2].Add(*stack[len(stack) - 1])
          stack = stack[:len(stack) - 1]
        }
      default:
        integer += string(ch)
    }
  }
  return stack[len(stack) - 1]
}

时间复杂度：O（n）

空间复杂度：O（n）

以上就是Go Java 算法之迷你语法分析器示例详解的详细内容，更多关于Go Java 算法语法分析器的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go和Java算法详析之分数到小数

    目录 分数到小数 方法一:模拟竖式计算(Java) 方法一:模拟竖式计算(Go) 总结 分数到小数 给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 . 如果小数部分为循环小数,则将循环的部分括在括号内. 如果存在多个答案,只需返回 任意一个 . 对于所有给定的输入,保证 答案字符串的长度小于 104 . 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5" 示例 2: 输入:num

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

  • Go Java算法之单词规律示例详解

    目录 单词规律 方法一:哈希表(Java) 方法一:哈希表(GO) 单词规律 给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律. 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律. 示例1: 输入: pattern = "abba", s = "dog cat cat dog" 输出: true 示例 2: 输入:pattern = "abba"

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • Go Java算法之比较版本号方法详解

    目录 比较版本号 方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号 给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由 多位数字 组成,可能包含 前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的

  • Go Java算法之解码方法示例详解

    目录 解码方法 方法一:动态规划(Java) 方法二:动态规划——优化(go) 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 : 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法).例如,"11106" 可以映射为: "AAJF" ,将消息分组为 (1 1 1

  • Go Java 算法之迷你语法分析器示例详解

    目录 迷你语法分析器 方法一:深度优先遍历(Java) 方法二:栈(Go) 迷你语法分析器 给定一个字符串 s 表示一个整数嵌套列表,实现一个解析它的语法分析器并返回解析的结果 NestedInteger . 列表中的每个元素只可能是整数或整数嵌套列表 示例 1: 输入:s = "324", 输出:324 解释:你应该返回一个 NestedInteger 对象,其中只包含整数值 324. 示例 2: 输入:s = "[123,[456,[789]]]", 输出:[1

  • Go Java算法最大单词长度乘积示例详解

    目录 最大单词长度乘积 方法一:位运算(java) 方法一:位运算(go) 最大单词长度乘积 给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母.如果不存在这样的两个单词,返回 0 . *示例 1: 输入:words = ["abcw","baz","foo","bar","xtfn","ab

  • java暴力匹配及KMP算法解决字符串匹配问题示例详解

    java暴力匹配及KMP算法解决字符串匹配问题示例详解

    目录 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 二.KMP算法 算法介绍 一个图例介绍KMP算法   代码实现 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD";     1. S[0]为B,P[0]为A,不匹配,执行第②条指令:"如果失配(即S[i]! = P[j]),令i = i - (j - 1),

  • Java实现经典大富翁游戏的示例详解

    Java实现经典大富翁游戏的示例详解

    目录 前言 主要设计 功能截图 代码实现 总结 前言 大富翁,又名地产大亨.是一种多人策略图版游戏.参与者分得游戏金钱,凭运气(掷骰子)及交易策略,买地.建楼以赚取租金.英文原名monopoly意为“垄断”,因为最后只得一个胜利者,其余均破产收场. <大富翁>游戏是用java语言实现,采用了swing技术进行了界面化处理,设计思路用了面向对象思想. 主要需求 可多人参与的大富翁游戏,玩家有初始资金,通过掷骰子,玩家移动指定骰子点数步骤,根据对应格子上的交易策略,来决定是赚钱还是亏钱,其他玩家破

  • Java数组的声明与创建示例详解

    今天在刷Java题的时候,写惯了C++发现忘记了Java数组的操作,遂把以前写的文章发出来温习一下. 首先,数组有几种创建方式? Java程序中的数组必须先进行初始化才可以使用,所谓初始化,就是为数组对象的元素分配内存空间,并为每个数组元素指定初始值,而在Java中,数组是静态的,数组一旦初始化,长度便已经确定,不能再随意更改. 声明数组变量 首先必须声明数组变量,才能在程序中使用数组.下面是声明数组变量的语法: dataType[] arrayRefVar; // 首选的方法 或 dataTy

  • 后端算法题解LeetCode前缀和示例详解

    目录 面试题 01.09. 字符串轮转 方法一:模拟 思路 题解 方法二:搜索子字符串 思路 题解 1480. 一维数组的动态和 方法一:前缀和 思路 题解 724. 寻找数组的中心下标 方法一:前缀和 思路 解题 面试题 01.09. 字符串轮转 面试题 01.09. 字符串轮转 难度:easy 字符串轮转.给定两个字符串 s1 和 s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottle 是 erbottlewat 旋转后的字符串). 示例1: 输入:s1 = "wa

  • Java使用Collections.sort()排序的示例详解

    Java中Collections.sort()排序详解,通过实例代码给大家讲解,具体代码如下所示: public static void main(String[] args) { List<String> list = new ArrayList<String>(); list.add("beijing"); list.add("shanghai"); list.add("hangzhou"); Collections.

  • java时区转换的理解及示例详解

    一.时区的基本概念 GMT(Greenwich Mean Time),即格林威治标准时,是东西经零度的地方.人们将地球人为的分为24等份,每一等份为一个时区,每时区横跨经度15度,时间正好为1小时.往西一个时区,则减去一小时:往东一个时区,则加上一小时.中国在东经120度上,(东经120°-东经0°)所得度数再除以15,即得8. UTC(Coordinated Universal Time),即世界协调时间,是经过平均太阳时(以格林威治时间GMT为准).地轴运动修正后的新时标以及以「秒」为单位的

  • Java使用FileInputStream流读取文件示例详解

    一.File流概念 JAVA中针对文件的读写操作设置了一系列的流,其中主要有FileInputStream,FileOutputStream,FileReader,FileWriter四种最为常用的流 二.FileInputStream 1)FileInputStream概念  FileInputStream流被称为文件字节输入流,意思指对文件数据以字节的形式进行读取操作如读取图片视频等 2)构造方法 2.1)通过打开与File类对象代表的实际文件的链接来创建FileInputStream流对象

  • C/C++语言八大排序算法之桶排序全过程示例详解

    C/C++语言八大排序算法之桶排序全过程示例详解

    基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶,先个位装桶然后出桶,直到最高位入桶出桶完毕. 首先我们要求出一个数组的最大数然后求出他的最大位数 //求最大位数的函数 int getmaxweisu(int* a,int len)// { int max = a[0]; for (int i = 0; i < len; i++) { if (max < a[i]) { max = a[i]; } } int count = 1; while (max/10) { count++

随机推荐