S2
S2 copied to clipboard
halfrost
0020. Valid Parentheses | LeetCode Cookbook
https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0020.Valid-Parentheses/
python打卡
s = input("Input: s = ")
class na:
def neko():
stack = []
for character in list(s):
opposite = {')': '(', '}': '{', ']': '['}
if character in {'(', '{', '['}:
stack.append(character)
elif len(stack) and stack[-1] == opposite[character]:
stack.pop()
else:
return False
return not len(stack)
print("Output: {0}".format(na.neko()))
只有84%，在哪浪费时间了呢……
@halfrost
@yngwiewang 请问这道题的时间复杂度为什么是log(N)而不是O(N)?
是 O(N) 呀，在哪里看到的 log(N)？
第二章 2.05 页面上是这么写的。话说小于O(n)的算法真的存在吗？都不用检查完所有输入的？
python打卡
s = input("Input: s = ") class na: def neko(): stack = [] for character in list(s): opposite = {')': '(', '}': '{', ']': '['} if character in {'(', '{', '['}: stack.append(character) elif len(stack) and stack[-1] == opposite[character]: stack.pop() else: return False return not len(stack) print("Output: {0}".format(na.neko()))只有84%，在哪浪费时间了呢……
@CHIYOI 我看你的解题思路没有问题，再想提高 runtime time 可能要从语言层面上下手了，我对 Python 还不是特别熟悉，暂时还给不了你提高时间的建议，你可以看看 discussion 里面别人的代码，看看比你时间更优的代码，他们是怎么写的。
@halfrost
@yngwiewang 请问这道题的时间复杂度为什么是log(N)而不是O(N)?
是 O(N) 呀，在哪里看到的 log(N)？
第二章 2.05 页面上是这么写的。话说小于O(n)的算法真的存在吗？都不用检查完所有输入的？
@CHIYOI 我们写的这个 solution 外层的输入函数，不计算时间的。时间复杂度仅针对我们写的这个函数。小于 O(n) 的算法有 O(1) ，O(log n) 和 O(sqrt(n))。
Simplified as:
func isValid(s string) bool {
// 空字符串直接返回 true
if len(s) == 0 {
return true
}
m := make(map[rune]rune)
m['('] = ')'
m['['] = ']'
m['{'] = '}'
stack := make([]rune, 0)
for _, v := range s {
if _, ok := m[v]; ok {
stack = append(stack, v)
} else if len(stack) > 0 && m[stack[len(stack)-1]] == v {
stack = stack[:len(stack)-1]
} else {
return false
}
}
return len(stack) == 0
}
Tested at: https://github.com/suntong/lang/tree/master/lang/Go/src/ds/LeetCode/0020.Valid-Parentheses
@suntong Simplified as:
func isValid(s string) bool { // 空字符串直接返回 true if len(s) == 0 { return true } m := make(map[rune]rune) m['('] = ')' m['['] = ']' m['{'] = '}' stack := make([]rune, 0) for _, v := range s { if _, ok := m[v]; ok { stack = append(stack, v) } else if len(stack) > 0 && m[stack[len(stack)-1]] == v { stack = stack[:len(stack)-1] } else { return false } } return len(stack) == 0 }Tested at: https://github.com/suntong/lang/tree/master/lang/Go/src/ds/LeetCode/0020.Valid-Parentheses
赞赞
