【golang】leetcode初级-有效的括号&缺失数字
第一题 有效的括号
题目
文章图片
解题思路
显然，要使所有的括号匹配，最容易想到的方法就是栈
每读到一个左括号，便将其入栈，每读到一个右括号，便将其出栈
如果读完字符串之后栈内仍有元素，说明有多余的左括号
如果读到右括号时栈为空，说明有多余的右括号
文章图片
代码
func isValid(s string) bool {
n := len(s)
//如果是奇数，可以直接判定字符串是错的
if n % 2 == 1 {
return false
}
//字符串的匹配
pairs := map[byte]byte{
')': '(',
']': '[',
'}': '{',
}
stack := []byte{}for i := 0;
i < n;
i++ {
if pairs[s[i]] > 0 {
if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
return false
}
//出栈
stack = stack[:len(stack)-1]
} else {
//出栈
stack = append(stack, s[i])
}
}
return len(stack) == 0
}
复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。
第二题 缺失数字 题目
文章图片
解题思路
思考题目的线索
我们可以发现，除了缺失的这个数，其他的数都是连续的
如果我们能将这个数组排序，就能直观的搜索到缺失的数
代码
func missingNumber(nums []int) int {
sort.Ints(nums)
for i:=0;
irange循环
func missingNumber(nums []int) int {
sort.Ints(nums)
for i, num := range nums {
if num != i {
return i
}
}
return len(nums)
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/missing-number/solution/diu-shi-de-shu-zi-by-leetcode-solution-naow/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。复杂度分析
【【golang】leetcode初级-有效的括号& 缺失数字】
文章图片
显然
在时间复杂度上仍有很大的优化空间
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。排序的时间复杂度是 O(nlogn)，遍历数组寻找丢失的数字的时间复杂度是 O(n)，因此总时间复杂度是 O(nlogn)。
空间复杂度：O(logn)，其中 n 是数组 nums 的长度。空间复杂度主要取决于排序的递归调用栈空间。
更优秀的解法
文章图片
这样我们就将其转化为之前已经解决过的简单问题
详见
https://segmentfault.com/a/11...
文章图片
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长