内容简介:今天持续做题ing,python有意思~今天的题有点虐心...兴许是我太笨了...会努力学习的!
写在前面的话
今天持续做题ing,python有意思~
今天的题有点虐心...兴许是我太笨了...
会努力学习的!
动态规划我来啦~
开始做题
第一题
难度:简单
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过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 了,要重做!!!!
看了其他的人的题解,使用的是 无限逼近中位值
的办法,理论基础应该是 泰勒公式
。
(万万没想到居然用到了泰勒公式....
手工执行了下算法,反而理解的更快,但是泰勒公式还得再复习下。
总结
今天的做题就到这里啦,还有很多要学习的地方~
数据结构与算法要加油呀!
以上所述就是小编给大家介绍的《小李飞刀:做题第六弹!》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
XML 在线格式化
在线 XML 格式化压缩工具
RGB CMYK 转换工具
RGB CMYK 互转工具