核心内容摘要
KVM虚拟化性能优化全攻略：在Ubuntu服务器上榨干你的硬件资源
文章目录摘要描述题解答案题解代码分析
特殊情况处理
使用栈来维护嵌套结构
数字解析
处理逗号和右括号
完整解析流程示例
边界情况处理示例测试及结果示例 1单个整数示例 2嵌套列表示例 3包含负数示例 4空列表示例 5多层嵌套时间复杂度空间复杂度实际应用场景场景一JSON 解析场景二配置文件解析场景三表达式求值场景四代码解析场景五数据序列化和反序列化
总结摘要这道题其实挺有意思的它要求我们实现一个语法分析器来解析嵌套列表的字符串表示。
听起来像是编译原理的内容但实际上用栈或者递归就能搞定。
关键点在于如何正确处理嵌套结构以及如何区分整数和列表。
这道题的核心在于如何解析类似[123,[456,[789]]]这样的字符串把它转换成嵌套的数据结构。
今天我们就用 Swift 来搞定这道题顺便聊聊这种解析技术在实际开发中的应用场景比如 JSON 解析、配置文件解析、表达式求值等等。
描述题目要求是这样的给定一个字符串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 * 10^4s由数字、方括号[]、负号-、逗号,组成用例保证s是可解析的NestedInteger输入中的所有值的范围是[-10^6, 10^6]这道题的核心思路是什么呢我们需要遍历字符串遇到[就创建一个新的嵌套列表遇到]就结束当前列表遇到数字就解析成整数遇到逗号就分隔元素。
我们可以用栈来维护嵌套结构也可以用递归的方式来处理。
题解答案下面是完整的 Swift 解决方案/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * class NestedInteger { * // Return true if this NestedInteger holds a single integer, rather than a nested list. * public func isInteger() - Bool * * // Return the single integer that this NestedInteger holds, if it holds a single integer * // Return nil if this NestedInteger holds a nested list * public func getInteger() - Int? * * // Set this NestedInteger to hold a single integer. * public func setInteger(value: Int) * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public func add(elem: NestedInteger) * * // Return the nested list that this NestedInteger holds, if it holds a nested list * // Return nil if this NestedInteger holds a single integer * public func getList() - [NestedInteger]? * } */classSolution{funcdeserialize(_s:String)-NestedInteger{// 如果字符串不以 [ 开头说明是单个整数ifs.first![{letnumInt(s)??0letniNestedInteger()ni.setInteger(value:num)returnni}varstack:[NestedInteger][]varnum:Int?nilvarisNegativefalseforcharins{ifchar[{// 遇到 [创建一个新的 NestedInteger 并压入栈letniNestedInteger()stack.append(ni)}elseifchar-{// 遇到负号标记为负数isNegativetrue}elseifchar.isNumber{// 遇到数字累积数字letdigitInt(String(char))??0num(num??
*10digit}elseifchar,||char]{// 遇到逗号或 ]处理之前累积的数字ifletnnum{letvalueisNegative?-n:nletniNestedInteger()ni.setInteger(value:value)// 将数字添加到栈顶的列表中ifletlaststack.last{last.add(elem:ni)}else{// 如果栈为空说明这是最外层的单个数字stack.append(ni)}numnilisNegativefalse}// 如果是 ]结束当前列表ifchar]{ifstack.count1{// 弹出当前列表添加到父列表中letcurrentstack.removeLast()stack.last?.add(elem:current)}}}}// 返回栈底的元素最外层的列表returnstack.first??NestedInteger()}}题解代码分析让我们一步步分析这个解决方案
特殊情况处理首先我们需要处理最简单的情况如果字符串不以[开头说明这是一个单独的整数不需要解析嵌套结构。
ifs.first![{letnumInt(s)??0letniNestedInteger()ni.setInteger(value:num)returnni}这种情况对应示例 1输入是324直接解析成整数返回即可。
使用栈来维护嵌套结构对于嵌套列表的情况我们需要用栈来维护当前的嵌套层级varstack:[NestedInteger][]栈的作用是当遇到[时创建一个新的NestedInteger并压入栈表示开始一个新的嵌套列表当遇到]时弹出栈顶的NestedInteger表示结束当前的嵌套列表当遇到数字时将数字添加到栈顶的NestedInteger中
数字解析我们需要处理数字的解析包括多位数字的累积负数的处理varnum:Int?nilvarisNegativefalse当遇到数字字符时我们累积数字elseifchar.isNumber{letdigitInt(String(char))??0num(num??
*10digit}当遇到负号时我们标记为负数elseifchar-{isNegativetrue}
处理逗号和右括号当遇到逗号,或右括号]时说明一个数字或列表元素结束了我们需要处理之前累积的数字elseifchar,||char]{// 处理之前累积的数字ifletnnum{letvalueisNegative?-n:nletniNestedInteger()ni.setInteger(value:value)// 将数字添加到栈顶的列表中ifletlaststack.last{last.add(elem:ni)}else{stack.append(ni)}numnilisNegativefalse}// 如果是 ]结束当前列表ifchar]{ifstack.count1{letcurrentstack.removeLast()stack.last?.add(elem:current)}}}这里的逻辑是如果有累积的数字创建一个包含该数字的NestedInteger并添加到栈顶的列表中如果是]说明当前列表结束了如果栈中还有父列表就将当前列表添加到父列表中
完整解析流程示例让我们用一个例子来理解整个解析过程。
假设输入是[123,[456,[789]]]遇到[创建新的NestedInteger压入栈。
栈[list1]遇到
1、
3累积数字123遇到,创建包含123的NestedInteger添加到list1。
栈[list1]list1包含[123]遇到[创建新的NestedInteger压入栈。
栈[list1, list2]遇到
4、
6累积数字456遇到,创建包含456的NestedInteger添加到list2。
栈[list1, list2]list2包含[456]遇到[创建新的NestedInteger压入栈。
栈[list1, list2, list3]遇到
7、
9累积数字789遇到]创建包含789的NestedInteger添加到list3。
然后弹出list3添加到list2。
栈[list1, list2]list2包含[456, [789]]遇到]弹出list2添加到list1。
栈[list1]list1包含[123, [456, [789]]]遇到]结束。
返回list
边界情况处理代码中处理了几个重要的边界情况单个整数如果字符串不以[开头直接解析为整数空列表如果遇到[]会创建一个空的NestedInteger负数正确处理负号将数字标记为负数栈为空如果栈为空但遇到数字说明这是最外层的单个数字示例测试及结果让我们用几个例子来测试一下这个解决方案示例 1单个整数输入s 324执行过程检查第一个字符3不是[进入单个整数分支解析整数Int(
324创建NestedInteger并设置值为324返回结果**结果**返回包含整数324的NestedInteger示例 2嵌套列表输入s [123,[456,[789]]]执行过程第一个字符是[进入嵌套列表解析创建list1压入栈解析数字123添加到list1遇到,继续遇到[创建list2压入栈解析数字456添加到list2遇到,继续遇到[创建list3压入栈解析数字789添加到list3遇到]弹出list3添加到list2遇到]弹出list2添加到list1遇到]结束**结果**返回包含[123, [456, [789]]]的NestedInteger示例 3包含负数输入s [-123,[456]]执行过程遇到[创建list1遇到-标记isNegative true解析数字123因为是负数所以值是-123添加到list1遇到,继续遇到[创建list2解析数字456添加到list2遇到]弹出list2添加到list1遇到]结束**结果**返回包含[-123, [456]]的NestedInteger示例 4空列表输入s []执行过程遇到[创建list1遇到]结束当前列表**结果**返回空的NestedInteger不包含任何元素示例 5多层嵌套输入s [[[1]]]执行过程遇到[创建list1遇到[创建list2遇到[创建list3解析数字1添加到list3遇到]弹出list3添加到list2遇到]弹出list2添加到list1遇到]结束**结果**返回包含[[[1]]]的NestedInteger时间复杂度让我们分析一下这个算法的时间复杂度时间复杂度O(n)其中n是字符串s的长度。
分析遍历字符串我们需要遍历整个字符串一次时间复杂度 O(n)栈操作每个字符最多进行一次栈操作压入或弹出栈操作的时间复杂度是 O(
数字解析每个数字字符只处理一次时间复杂度 O(
创建 NestedInteger每个元素最多创建一次NestedInteger时间复杂度 O(
所以总时间复杂度是 O(n)这是最优的因为我们至少需要遍历一次字符串来解析它。
对于题目约束s.length 5 * 10^4这个时间复杂度是完全可接受的。
空间复杂度让我们分析一下这个算法的空间复杂度空间复杂度O(n)其中n是字符串s的长度。
分析栈空间栈的深度最多等于嵌套的层数。
在最坏情况下比如[[[[...]]]]栈的深度是 O(n)。
但实际上由于字符串格式的限制嵌套层数不会太深NestedInteger 对象我们需要创建 O(n) 个NestedInteger对象每个数字和每个列表都需要一个对象临时变量num、isNegative等临时变量占用 O(
空间所以总空间复杂度是 O(n)这是必要的因为我们需要存储解析后的数据结构。
实际应用场景这种语法解析技术在实际开发中应用非常广泛场景一JSON 解析JSON 解析器的工作原理和这道题类似都是解析嵌套的数据结构。
比如解析{name: John, age: 30, hobbies: [reading, coding]}这样的 JSON 字符串需要处理对象、数组、字符串、数字等不同类型的嵌套结构。
在实际项目中我们可以使用 Swift 的Codable协议来解析 JSON但理解底层的解析原理对于调试和优化很有帮助。
场景二配置文件解析很多配置文件都使用嵌套结构比如 YAML、XML、TOML 等。
解析这些配置文件时我们需要处理嵌套的键值对、列表等结构。
比如解析这样的 YAML 配置database:host:localhostport:3306connections:-name:primarypool:10-name:secondarypool:5解析器需要处理嵌套的对象和列表结构。
场景三表达式求值在计算器或表达式求值器中我们需要解析数学表达式比如1 2 * (3
。
虽然这种表达式不是嵌套列表但解析思路类似使用栈来处理运算符优先级和括号嵌套。
场景四代码解析在编译器或解释器中我们需要解析源代码构建抽象语法树AST。
这个过程也需要处理嵌套的结构比如函数定义、类定义、控制流语句等。
场景五数据序列化和反序列化在数据序列化和反序列化中我们需要将内存中的数据结构转换成字符串或者将字符串解析回数据结构。
这个过程也需要处理嵌套结构。
总结这道题虽然看起来复杂但实际上是一个经典的栈应用问题。
通过使用栈来维护嵌套结构我们可以清晰地处理各种情况。
关键点
总结栈的应用使用栈来维护嵌套列表的层级关系字符分类处理根据不同的字符[、]、数字、,、-进行不同的处理数字累积多位数字需要累积处理边界情况需要处理单个整数、空列表、负数等特殊情况算法优势时间复杂度低只需要遍历一次字符串O(n)实现简单逻辑清晰容易理解和维护扩展性好可以很容易地扩展到处理更复杂的语法实际应用语法解析技术在 JSON 解析、配置文件解析、表达式求值、代码解析等场景中都有广泛应用。
理解这种解析技术不仅能帮助我们解决类似的算法题还能让我们更好地理解各种解析器的工作原理。
希望这篇文章能帮助你理解语法解析的基本思路以及如何在实际开发中应用这种技术