【刷题日记】385. 迷你语法分析器
本次刷题日记的第 33 篇，力扣题为：【刷题日记】385. 迷你语法分析器 ，中等
一、题目描述：
周五早点回来继续刷每日一题，坚决不落下
乍一看这个题，不知道在说些啥，看上去感觉还是不难滴，要对自己有信心，咱先来细细品读一下
二、这道题考察了什么思想？你的思路是什么？
一起仔细确认一下这个题是需要我们做些啥：
- 题目中给出一个字符串，咱们需要转化成一个题目中给出的对象
type NestedInteger struct { }
- 题目的要求非常明确，但是我们需要如何来实现的，我们可以一起来细细的品读一下题目中给出的示例
瞅一眼，我们大概知道 NestedInteger 对象，自身可以是包含一个整数，也可以是包含 1 个整数 + 1 个 NestedInteger 子对象
仔细分析一下这个 NestedInteger 的情况：
咱们用题目中给出的示例画了一个草图，我们发现题目给出的字符串，其实是层层嵌套 NestedInteger 对象
那么对于这种层层嵌套的题目，我们是不是就可以很容易的想到递归的方式，也就是深度优先算法，先递归到最深处，然后一层一层的向上捅
还有一个总要的点，我们需要看明白题中给出的 NestedInteger 对象的成员方法
就解这道题的话，我们可以使用上述的成员方法，我们会使用到
- SetInteger ，用于将整数设置到 对象中
- Add ， 用于添加子对象 NestedInteger
本题主要的逻辑，就是使用深度优先算法，遍历给出的字符串，不停的递归，当遇到 '[' 的时候，就深入一层，遇到 ']' 就退出本层 ， 遇到 ',' 就表示当前的对象有 2 个元素
通过上述的拆解，思路应该就非常清晰了，剩下的就是来实现咱们的代码了
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码，这里需要非常注意：
- 递归的方式，注意 '[' 和 ']'
- 注意对象中 是 1 个元素，还是 2 个元素的情况，注意 逗号
- 注意负数的情况
编码如下：
func deserialize(s string) *NestedInteger { // 初始化索引，从 0 开始 index := 0 // 定义递归函数 var dfs func() *NestedInteger dfs = func()*NestedInteger{ // 我们需要开始创建一个新的对象 *NestedInteger ， 这个对象，里面包含数字和列表，也可以只有数字 nes := &NestedInteger{} // 1 校验当前的位置是否需要递归创建新对象 if s[index] == '['{ // 向后偏移一位 index++ // 只要当前这一位对应的字符 不是 ] ，则就会开始创建对象 for s[index] != ']'{ nes.Add(*dfs()) // 递归出来之后，校验到当前位置是 , 字符，那么说明，当前 NestedInteger 对象是有数字和列表，需要跳过，，继续遍历 if s[index] == ','{ index++ } } // 程序能走到这里，说明已经找到 [] 了 , 需要 index 继续 +1，对出本轮递归，向上捅的时候，要往后偏移，上层递归直接判断字符即可 index++ return nes } // 2 在当前对象中，读取数字 // 先确定一下数字的符号是否是负数 fushu := (s[index] == '-') if fushu { // 如果是负数，那么咱们记录一下，然后索引向后偏移 index++ } nums := 0 // 此处的循环控制需要注意，我们知道整数是连续的，遇到 逗号，或者[ ] 我们就认为一个整数遍历完成 for ; index < len(s) && unicode.IsDigit(rune(s[index])); index++ { nums = nums*10 + int(s[index] - '0') } // 校验是否需要添加负号 if fushu { nums = -nums } nes.SetInteger(nums) return nes } return dfs() }
看了以上思路和编码，以及编码中的注释，相信，都是比较好理解的了吧，代码呈现的也比较清晰
四、总结：
此处我们可以看到，我们只遍历了一轮 s 字符串，所以时间复杂度是 O(n)
此处的空间复杂度是多少呢？ xmd 可以好好思考一下
原题地址：385. 迷你语法分析器
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
