Go Java 算法之迷你語法分析器示例詳解
有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
迷你語法分析器
給定一個字符串 s 表示一個整數(shù)嵌套列表,實現(xiàn)一個解析它的語法分析器并返回解析的結(jié)果 NestedInteger 。
列表中的每個元素只可能是整數(shù)或整數(shù)嵌套列表
- 示例 1:
輸入:s = "324",
輸出:324
解釋:你應(yīng)該返回一個 NestedInteger 對象,其中只包含整數(shù)值 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 由數(shù)字、方括號 "[]"、負號 '-' 、逗號 ','組成
- 用例保證 s 是可解析的 NestedInteger
- 輸入中的所有值的范圍是 [-106, 106]
方法一:深度優(yōu)先遍歷(Java)
根據(jù)題意,一個 NestedInteger 實例只能包含下列兩部分之一:1)一個整數(shù);2)一個列表。
列表中的每個元素都是一個 NestedInteger 實例。據(jù)此,NestedInteger 是通過遞歸定義的,因此也可以用遞歸的方式來解析。
注意序列化的String,有2個特殊含義,導(dǎo)致不能用String.split()。否則實現(xiàn)起來會比較困難。
逗號: 表示分割“同層級”的元素
中括號[] : 表示1個List,可以有兄弟節(jié)點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); } } }
時間復(fù)雜度:O(n)
空間復(fù)雜度:O(n)
方法二:棧(Go)
我們只需關(guān)注字符串s
中的[
、]
和,
字符,其他字符均可轉(zhuǎn)為數(shù)字,初始化棧時,將一個空的NestedInteger
加入其中,防止越界。
順序遍歷,3
種情況:
[
:新建列表,入棧
數(shù)字和-
:累加字符串
]
和,
:字符串加完,加入列表
]
:出棧,結(jié)果加入上級列表
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] }
時間復(fù)雜度:O(n)
空間復(fù)雜度:O(n)
以上就是Go Java 算法之迷你語法分析器示例詳解的詳細內(nèi)容,更多關(guān)于Go Java 算法語法分析器的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
關(guān)于Spring MVC同名參數(shù)綁定問題的解決方法
Spring MVC中的參數(shù)綁定還是蠻重要的,最近在使用中遇到了同名參數(shù)綁定的問題,想著總結(jié)分享出來,下面這篇文章主要給大家介紹了關(guān)于Spring MVC同名參數(shù)綁定問題的解決方法,需要的朋友可以參考借鑒,下面來一起看看吧。2017-08-08Springboot整合MongoDB進行CRUD操作的兩種方式(實例代碼詳解)
這篇文章主要介紹了Springboot整合MongoDB進行CRUD操作的兩種方式,本文通過實例代碼給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04