小李飞刀：做题第六弹！

BigNerdCoding 发布于2019-07-31 10:08 / 3046人阅读

摘要：给定的字符串只含有小写英文字母，并且长度不超过。其他这题了，要重做看了其他的人的题解，使用的是无限逼近中位值的办法，理论基础应该是泰勒公式。万万没想到居然用到了泰勒公式手工执行了下算法，反而理解的更快，但是泰勒公式还得再复习下。

写在前面的话

今天持续做题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了，要重做!!!!
看了其他的人的题解，使用的是无限逼近中位值的办法，理论基础应该是泰勒公式。
（万万没想到居然用到了泰勒公式....
手工执行了下算法，反而理解的更快，但是泰勒公式还得再复习下。

总结

今天的做题就到这里啦，还有很多要学习的地方~
数据结构与算法要加油呀！

idc机房托管混合云飞刀小李做题 php做题系统

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43301.html

小李飞刀：做题第十弹！

摘要：第二题汉明距离难度简单两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数和，计算它们之间的汉明距离。第三题买卖股票的最佳时机难度简单给定一个数组，它的第个元素是一支给定股票第天的价格。写在前面这几天断断续续做了题目，也在慢慢体会一些数据思维。终于不用边做视频边写题目啦~开心~把这几天的题解发一下~ 认真做题的分割线第一题 977. 有序数组的平方难度...

bingo 2019-07-31 10:13 评论0 收藏0
小李飞刀：做题第七弹！

摘要：给定一个大小为的数组，找到其中的众数。第五题合并两个有序数组难度简单给定两个有序整数数组和，将合并到中，使得成为一个有序数组。说明初始化和的元素数量分别为和。第六题二叉树的最大深度难度简单给定一个二叉树，找出其最大深度。写在前面的话做做做题，慢慢上手了就觉得刷题速度变快了，果然还是有点笨~希望最后一窍快点通吧~ 开始做题第一题 169. 求众数难度：简单给定一个大小为 n 的数组...

AlphaWatch 2019-07-31 10:09 评论0 收藏0
小李飞刀：做题第十二弹！

摘要：写在前面今天没有叨逼叨但是又一次错过了竞赛爱睡觉的小李下周要上班，下下周一定要参加了握拳认真做题的分割线第一题两地调度公司计划面试人。第人飞往市的费用为，飞往市的费用为。示例输入输出解释第一个人去市，费用为。写在前面今天没有叨逼叨...但是又一次错过了竞赛...爱睡觉的小李...下周要上班，下下周一定要参加了（握拳认真做题的分割线第一题 1029. 两地调度公司计划面试2N人。...

yagami 2019-07-31 10:19 评论0 收藏0
小李飞刀：做题第八弹！

摘要：认真做题的分割线第一题乘积最大子序列难度中等给定一个整数数组，找出一个序列中乘积最大的连续子序列该序列至少包含一个数。写在前面的话慢慢转变思路，不再死磕不会做的题，思路可以先借鉴，但是一定要吃透透。上周末看完看完了《算法图解》，感觉对一些题目的思路有比较大的帮助，但是还是要在实践中理解。认真做题的分割线第一题 152. 乘积最大子序列难度：中等给定一个整数数组nums，找出一个...

ztyzz 2019-07-31 10:11 评论0 收藏0
小李飞刀：做题第九弹！

摘要：不过可能还没有抓到动态规划的真谛，总觉得哪里需要再校正下思路。这题也是动态规划的题目，目标总是要分解为子问题。总结看算法图解的时候，涉及动态规划的小结中有这样的每种动态规划解决方案都涉及网格。写在前面的话感觉做题越多遇到的写法越多，有种跃跃欲试的感觉~ 认真做题第一题 70. 爬楼梯难度：简单假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少...

Bamboy 2019-07-31 10:11 评论0 收藏0