写在前面的话今天持续做题ing，python有意思今天的题有点虐心…兴许是我太笨了…会努力学习的！动态规划我来啦开始做题第一题459. 重复的子字符串难度：简单给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。我的题解：class Solution(object): def repeatedSubstringPattern(self, s): """ :type s: str :rtype: bool """ if len(s) <= 1 : return False res = [] n = 0 length = len(s) for i in range(1,length): if s[i] == s[0]: res.append(i) for i in range(1,length): a = s[:i] length_a = len(a) n = length/length_a if a * n == s: return True return False我的思路：参考了小佳扬的思路后，重新写了一遍。主要是因为如果存在重复的话，第一个字母开始就会形成重复最小字符串的长度可以被字符串长度给整除那么就记录下第一个字母每次出现的地方，检查每次字符出现的前一段字符串是否可以形成重复。其他：写的时候遇到一个坑，一直遇到报错integer division or modulo by zero检查了一圈发现，是在第二个循环的时候，i从0开始作为除数，所以产生了报错。第二题5. 最长回文子串 —-超时需要再解答难度：中等给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。我的题解：class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ l = len(s) if len(s) <= 1: return s length = 0 for i in range(0,l): for j in range(i+1,l+1): res = s[i:j] if res == res[::-1]: #逆向相等 if (len(res) > length): mark = res #存储数据 length = len(res) return mark 我的思路：用的是最暴力的解法，双重循环，逐个字段进行比较，复杂度应该是O(N²)（这个复杂度超时很必然啊，被pia飞….其他：这题超时了，要重做!!!!可以执行通过较短的字符串，但是超过一定长度之后就会超时。建议使用动态规划，好好学习!!!重新做一次。第三题69. x 的平方根 —-超出内存需要再解答难度：简单实现int sqrt(int x)函数。计算并返回x的平方根，其中x是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。我的题解：class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ for i in range(x): if i**2 <= x and (i+1)**2 >x: return i我的思路：因为只取整数部分，所以值会介于i的平方及i+1的平方之间。其他：这题Memory Error了，要重做!!!!看了其他的人的题解，使用的是无限逼近中位值的办法，理论基础应该是泰勒公式。（万万没想到居然用到了泰勒公式….手工执行了下算法，反而理解的更快，但是泰勒公式还得再复习下。总结今天的做题就到这里啦，还有很多要学习的地方~数据结构与算法要加油呀！