小李飞刀:做题第六弹!

栏目: 编程工具 · 发布时间: 5年前

内容简介:今天持续做题ing,python有意思~今天的题有点虐心...兴许是我太笨了...会努力学习的!

写在前面的话

今天持续做题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 了,要重做!!!!

看了其他的人的题解,使用的是 无限逼近中位值 的办法,理论基础应该是 泰勒公式

(万万没想到居然用到了泰勒公式....

手工执行了下算法,反而理解的更快,但是泰勒公式还得再复习下。

总结

今天的做题就到这里啦,还有很多要学习的地方~

数据结构与算法要加油呀!


以上所述就是小编给大家介绍的《小李飞刀:做题第六弹!》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法学

算法学

哈雷尔 / 霍红卫 / 高等教育 / 2007-6 / 39.00元

本书主要论述计算机科学的基本概念、思想、方法和结果。全书内容由 5个部分组成。“预备知识”部分包括算法学中的基本概念、算法结构、算法所操纵的数据以及描述算法所用的程序设计语言。“方法和分析”部分包括算法设计的方法、算法的正确性和效率、评价算法的方法。“局限性和健壮性”部分包括可执行算法的固有局限性以及实现这些算法的计算机的固有局限性、不可计算性和不可判定性、算法学的通用性及其健壮性。此外,还讨论了......一起来看看 《算法学》 这本书的介绍吧!

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具