小李飞刀：刷题第三弹！

冷不防 2022-03-02 08:24 231阅读 0赞

## 刷题第三天 ##

正式刷题第三天。  
之前看了个说法，挺认可的。  
就是不要太在意一天的能呈现的价值，但是要在意累计的价值。  
之前很多时候我会对今天一天没有完成的计划而沮丧，事实上，算法的实践，统计学的学习这些都是需要时间去积累去吃透。  
所以，持之以恒的学习更为重要。  
现在的目标是每天2题，当适合的时候就提高每天的题量！

## 第一题 ##

**20. 有效的括号**  
**难度：简单**  
**类型：堆栈**

> 给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串，判断字符串是否有效。  
> 有效字符串需满足：  
> 左括号必须用相同类型的右括号闭合。  
> 左括号必须以正确的顺序闭合。  
> 注意空字符串可被认为是有效字符串。

我的解答代码：

class Solution:
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            stack = []
            dic = {'(':')',')':'(','{':'}','}':'{','[':']',']':'['}
            if len(s) < 2:
                return (len(s)==0)
            stack.append(s[0])
            for i in s[1:]:
                if len(stack) == 0:
                    stack.append(i)
                elif i != dic[stack[-1]]:
                    stack.append(i)
                else:
                    stack.pop()
            return (len(stack)==0)

用了堆栈的方法和字典的方法，字典查询速度会比较快。  
然后对比当前字符和对应的堆栈里的最末字符对应的另一半。  
![clipboard.png][]  
错误的一次是因为没有考虑空字符串，当存在为`""`的时候，结果应该为true。  
![clipboard.png][clipboard.png 1]  
相对而言效率还是是可以的。

**本题主要关键点**

*  使用dictionary地图的方式，类似扫描来确认对应的关系。

## 第二题 ##

**66. 加一**  
**难度：简单**  
**类型：??**

> 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。  
> 最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。  
> 你可以假设除了整数 0 之外，这个整数不会以零开头。

我的解题代码是：

class Solution:
        def plusOne(self, digits):
            """
            :type digits: List[int]
            :rtype: List[int]
            """
            a = -1
            for i in digits[::-1]:
                if i != 9 :
                    digits[a] = i+1
                    return digits
                else:
                    digits[a] = 0
                    if (a + len(digits)) == 0:
                        digits.insert(0,1)
                        return digits
                    a = a - 1

用的办法比较土。  
简单来说就是逆序遍历，因为十进制下，逢9进位，所以我们逆向计算有存在9的情况。  
emmm.....感觉这个方法也很适合用递归来做。

![clipboard.png][clipboard.png 2]

效率上居然还可以的，错误过一次，主要原因是因为在数据例子为`[9]`的时候，输出结果应该为`[1,0]`，所以重新进行了调整。

**本题主要关键点**

*  搜索了逆序for in遍历的办法，最后搜到的是用digits\[::-1\]的方法，非常有趣。
 *  因为特殊情况下，可能需要在原来的数据基础上进位，所以需要在数组左侧增加一个数位，用`insert(位置点，数值)`就可以完成了。

## 总结 ##

很多python的方法其实都非常的便捷，简单的代码就可以完成算法的实现。  
还是要多学习方法，比如今天的逆序遍历，以及左侧插入等。  
实践出真知，古人诚不我欺。

[clipboard.png]: /images/20220302/22579e04466b4e7e9ca1d844b3dc2110.png
[clipboard.png 1]: /images/20220302/d7420404cb34447ea46874bd331533c9.png
[clipboard.png 2]: /images/20220302/d5308c6cac494f4fbffabcf403a66f91.png