2023.10.9

第一题：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

题目解（Python3）：

def havefun(s):
    dic = {"?":"?","(":")","{":"}","[":"]"}
    stack = ["?"]
    for i in s:
        if i in dic:
            stack.append(i)
        elif dic[stack.pop()]!=i:
            return False
    return len(stack)==1

代码之前：教程还没看到stack那块，属实是有点超纲了，但是看到这个题目的时候是有一种想法，需要左右匹配的方法，在最后如果全部匹配完成，则说明该字符串有效。若有剩余，则输出False。使用栈的好处是，这个题目很符合栈FILO的特点，因为左括号要与最近的相对括号对应，也像是先进后出了，因为最左边的左括号匹配最右边的右括号。另外想到匹配这个问题，使用dic就是顺理成章的事情了，毕竟只有它的keys与values符合这种匹配的要求。感觉这个思路可以固定一下，即看到需要进行匹配的算法可以想到dic，像这种匹配最近的括号的算法（即先进后出）可以想到用栈，那自然而然的先进先出也可以想到队列。后续涉及到栈和队列的笔记也会补充在基础知识里。

代码中：整体的思路也比较简单，先将需要的对应关系存储到dic当中，提供给后续寻找匹配关系。接着创建栈并遍历整个字符串，在栈方面，因为是左括号在前，因此优先将遇到的左括号入栈，当遇到右括号时，将最近入栈的括号弹出并与之匹配，若匹配成功则不执行任何操作（这里一开始疑惑了一下，代码里只写了当匹配不成功时的操作，匹配成功的操作并没有完整写出，那匹配成功时的括号是怎么弹出栈顶的呢？后来仔细思考一下，在做不匹配判断时是元素先出栈，即pop操作，然后再进行判断，此时元素已经出栈，即使匹配成功，栈的长度也会减1，完美符合后续根据栈的长度判断返回值的特点。），若匹配失败则返回False，最后根据我们一开始的想法，看栈中剩余的长度判断匹配是否成功。

边界问题：边界问题的产生1.POP操作需要栈内有元素，因此需要在栈内预设一个值，防止字符串仅有")"的情况报错。

2.单左括号或左括号结尾的情况下，栈内最后剩我们的预设值和该括号，因此需要在结尾以len(stack)==1判断匹配是否成功。

注：一些代码上的细节，定义dic使用{}，stack使用[]。注意pop和append操作后的（）。另外想输出的情况下，还是要定义s=""  print(havefun(s))

第二题：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题目解（Python3）：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0:
            return 1
        elif n ==1:
            return 1
        else:
            length = n
            a=[None] * (length+1)
            for i in range(2,n+1):
                    a[0]=1
                    a[1]=1
                    a[i]=a[i-1]+a[i-2]
            return a[i]

代码中：除了特殊说明的两个地方之外，就是按部就班的开始循环给定的n，这个题中给的n是不大于45的，不知道是不是处于内存方面的考虑，稍微遇到的一点点问题就是一开始想着生成一个空列表，循环n的同时填充这个列表，生成空列表的时候长度有点没太搞清楚，需要的数组长度从a[0]到a[n]，长度共n+1，当然这是小问题。

边界问题：之前说过了，特殊讨论。

注：在leetcode答题的时候，注意要用return而不是print，不然会输出错误的。

大神的解答：

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n - 1):
            a, b = b, a + b
        return b

比较：简洁无比的写法，使用了占位符_来控制循环的结束，实现了"交替向前"这个想法，空间复杂度极低。且当n=0时，n-1是一个空范围，不会触发循环条件，所以没有迭代操作，函数会立即返回 b，也就是初始值1，省去了额外的if else操作。