小李飞刀：做题第八弹！

ztyzz 发布于2019-07-31 10:11 / 3385人阅读

摘要：认真做题的分割线第一题乘积最大子序列难度中等给定一个整数数组，找出一个序列中乘积最大的连续子序列该序列至少包含一个数。

写在前面的话

慢慢转变思路，不再死磕不会做的题，思路可以先借鉴，但是一定要吃透透。
上周末看完看完了《算法图解》，感觉对一些题目的思路有比较大的帮助，但是还是要在实践中理解。

认真做题的分割线

第一题

152. 乘积最大子序列
难度：中等
给定一个整数数组nums，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
我的题解：

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        maxsum = [0 for _ in range(length)]
        minsum = [0 for _ in range(length)]
        maxsum[0] = minsum[0] = nums[0] # 限定最大最小值
        dp = nums[0] #当前状态
        for i in range(1,len(nums)):
            maxsum[i] = max(maxsum[i-1]*nums[i],minsum[i-1]*nums[i],nums[i])
            minsum[i] = min(maxsum[i-1]*nums[i],minsum[i-1]*nums[i],nums[i])
            dp = max(dp,maxsum[i])
        return dp

我的思路：
这题做了两次，主体思路为：每次都找到乘积中的最大正值和最小负值，因为绝对值最大的两个数在下一次计算中才有可能成为最大值。（毕竟题目没有限制非负数）
第一次的时候报错的原因是，我记录了每次的maxsum和minsum，没有记录上一次循环留下的值。
然鹅，上一次的状态会影响到下一次的状态，所以必须记住上一步的最优解。
可以判断是个NP问题，但是动态规划还得多多练习

第二题

202. 快乐数
难度：简单
编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
我的题解：

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        l = []
        while 1:
            l.append(n)
            n = sum([int(i)**2 for i in str(n)])
            if n == 1:
                return True
            elif n in l:
                return False

我的思路：
条件一：要判断每次的值是否各位平方总和为1，得出是快乐数的结论；
条件二：为了得出非快乐数的结论，这个数可能会陷入循环，那么就要记录下每轮的值，并进行比对。
其他：
在评论中发现了一个很有趣的算法，就是用dict记录下肯定会循环的数字的词典，当遇到相关数字的时候就可以跳出了。
一般为{4,16,37,58,89,145,42,20}

第三题

204. 计数质数
难度：简单
统计所有小于非负整数 n 的质数的数量。
我的题解：

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        else:
            output = [1]*n
            output[0],output[1] = 0,0
            for i in range(2,int(n**0.5+1)):
                if output[i] == 1:
                    m = i**2
                    while m < n:
                        output[m] = 0
                        m += i
        return sum(output)

我的思路：
这个算法借鉴了评论里的一个炒鸡有趣的算法，默认查询是否质数的时候，我们习惯用循环判断，这样肯定会超时。
而这个算法呢，叫做厄拉多塞筛法，他给了如下解释：

比如说求20以内质数的个数,首先0,1不是质数.2是第一个质数,然后把20以内所有2的倍数划去.2后面紧跟的数即为下一个质数3,然后把3所有的倍数划去.3后面紧跟的数即为下一个质数5,再把5所有的倍数划去.以此类推

包括他的题解的写法也很有趣，但是我还没弄明白
output[i*i:n:i] = [0] * len(output[i*i:n:i])这一句的意思，还要琢磨下，所以用的是循环的写法。

def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0     
        else:
            # 首先生成了一个全部为1的列表
            output = [1] * n
            # 因为0和1不是质数,所以列表的前两个位置赋值为0
            output[0],output[1] = 0,0
             # 此时从index = 2开始遍历,output[2]==1,即表明第一个质数为2,然后将2的倍数对应的索引
             # 全部赋值为0. 此时output[3] == 1,即表明下一个质数为3,同样划去3的倍数.以此类推.
            for i in range(2,int(n**0.5)+1): 
                if output[i] == 1:
                    output[i*i:n:i] = [0] * len(output[i*i:n:i])
         # 最后output中的数字1表明该位置上的索引数为质数,然后求和即可.
        return sum(output)

总结

小李今天的做题，是痛并快乐着的！

云服务器 GPU云服务器飞刀小李做题 php做题系统

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

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

小李飞刀：做题第十二弹！

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

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

摘要：给定的字符串只含有小写英文字母，并且长度不超过。其他这题了，要重做看了其他的人的题解，使用的是无限逼近中位值的办法，理论基础应该是泰勒公式。万万没想到居然用到了泰勒公式手工执行了下算法，反而理解的更快，但是泰勒公式还得再复习下。写在前面的话今天持续做题ing，python有意思~今天的题有点虐心...兴许是我太笨了...会努力学习的！动态规划我来啦~ 开始做题第一题 459. 重...

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

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

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

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

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

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

AlphaWatch 2019-07-31 10:09 评论0 收藏0