2021-11-3
题目
1.Sqrt（x）
2.爬楼梯
3.无重复字符的最长字串
题解
1.Sqrt（x）
本题思路是当一个数的算数平方根不是整数时，这个数肯定时大于该算数平方根的整数部分的幂乘积，小于整数部分加一的幂乘积，所以我们就遍历来找到这个整数，就是我们想要的数，然后返回！！
2.爬楼梯
这个题我最开始用的时回溯加剪枝，但是到最后我发现这个在数值等于38的时候超时，所以肯定不能用回溯了，还有一个方法就是用斐波那契数列。
3.无重复字符的最长字串
这个题是我之前没有写出来的一个滑块题，因为它的滑块长度是会变化的，最开始我有点把握不住这个长度，看了一些大佬的题解才写出来的。
由于我的表达太差，我还是直接给大家上官方的题解思路吧。
代码
1.Sqrt（x）
class Solution: def mySqrt(self, x: int) -> int: if x == 1: return 1 if x == 0: return 0 for i in range(x): if x >=i*i and (i+1)*(i+1) > x: return i
2.爬楼梯
1.
class Solution: def climbStairs(self, n: int) -> int: def trace(tag,res): if tag < 0: return if tag == 0: res.append( 1) return for i in range(1,3): trace(tag-i,res) return len(res) return trace(n,[])
2.
class Solution: def climbStairs(self, n: int) -> int: dp = {} dp[1] = 1 dp[2] = 2 for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]
3.无重复字符的最长字串
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s : return 0 looku = set() left = 0 max_len = 0 cur_len = 0 for i in range(len(s)): cur_len += 1 while s[i] in looku: looku.remove(s[left]) left += 1 cur_len -=1 looku.add(s[i]) if max_len < cur_len: max_len = cur_len return max_len
