小李飛刀：做題第八彈！

ztyzz 發(fā)布于2019-07-31 10:11 / 3473人閱讀

摘要：認(rèn)真做題的分割線第一題乘積最大子序列難度中等給定一個(gè)整數(shù)數(shù)組，找出一個(gè)序列中乘積最大的連續(xù)子序列該序列至少包含一個(gè)數(shù)。

寫(xiě)在前面的話

慢慢轉(zhuǎn)變思路，不再死磕不會(huì)做的題，思路可以先借鑒，但是一定要吃透透。
上周末看完看完了《算法圖解》，感覺(jué)對(duì)一些題目的思路有比較大的幫助，但是還是要在實(shí)踐中理解。

認(rèn)真做題的分割線

第一題

152. 乘積最大子序列
難度：中等
給定一個(gè)整數(shù)數(shù)組nums，找出一個(gè)序列中乘積最大的連續(xù)子序列（該序列至少包含一個(gè)數(shù)）。
我的題解：

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] #當(dāng)前狀態(tài)
        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

我的思路：
這題做了兩次，主體思路為：每次都找到乘積中的最大正值和最小負(fù)值，因?yàn)榻^對(duì)值最大的兩個(gè)數(shù)在下一次計(jì)算中才有可能成為最大值。（畢竟題目沒(méi)有限制非負(fù)數(shù)）
第一次的時(shí)候報(bào)錯(cuò)的原因是，我記錄了每次的maxsum和minsum，沒(méi)有記錄上一次循環(huán)留下的值。
然鵝，上一次的狀態(tài)會(huì)影響到下一次的狀態(tài)，所以必須記住上一步的最優(yōu)解。
可以判斷是個(gè)NP問(wèn)題，但是動(dòng)態(tài)規(guī)劃還得多多練習(xí)

第二題

202. 快樂(lè)數(shù)
難度：簡(jiǎn)單
編寫(xiě)一個(gè)算法來(lái)判斷一個(gè)數(shù)是不是“快樂(lè)數(shù)”。

一個(gè)“快樂(lè)數(shù)”定義為：對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和，然后重復(fù)這個(gè)過(guò)程直到這個(gè)數(shù)變?yōu)?1，也可能是無(wú)限循環(huán)但始終變不到 1。如果可以變?yōu)?1，那么這個(gè)數(shù)就是快樂(lè)數(shù)。
我的題解：

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，得出是快樂(lè)數(shù)的結(jié)論；
條件二：為了得出非快樂(lè)數(shù)的結(jié)論，這個(gè)數(shù)可能會(huì)陷入循環(huán)，那么就要記錄下每輪的值，并進(jìn)行比對(duì)。
其他：
在評(píng)論中發(fā)現(xiàn)了一個(gè)很有趣的算法，就是用dict記錄下肯定會(huì)循環(huán)的數(shù)字的詞典，當(dāng)遇到相關(guān)數(shù)字的時(shí)候就可以跳出了。
一般為{4,16,37,58,89,145,42,20}

第三題

204. 計(jì)數(shù)質(zhì)數(shù)
難度：簡(jiǎn)單
統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量。
我的題解：

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)

我的思路：
這個(gè)算法借鑒了評(píng)論里的一個(gè)炒雞有趣的算法，默認(rèn)查詢(xún)是否質(zhì)數(shù)的時(shí)候，我們習(xí)慣用循環(huán)判斷，這樣肯定會(huì)超時(shí)。
而這個(gè)算法呢，叫做厄拉多塞篩法，他給了如下解釋?zhuān)?/p>

比如說(shuō)求20以?xún)?nèi)質(zhì)數(shù)的個(gè)數(shù),首先0,1不是質(zhì)數(shù).2是第一個(gè)質(zhì)數(shù),然后把20以?xún)?nèi)所有2的倍數(shù)劃去.2后面緊跟的數(shù)即為下一個(gè)質(zhì)數(shù)3,然后把3所有的倍數(shù)劃去.3后面緊跟的數(shù)即為下一個(gè)質(zhì)數(shù)5,再把5所有的倍數(shù)劃去.以此類(lèi)推

包括他的題解的寫(xiě)法也很有趣，但是我還沒(méi)弄明白
output[i*i:n:i] = [0] * len(output[i*i:n:i])這一句的意思，還要琢磨下，所以用的是循環(huán)的寫(xiě)法。

def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0     
        else:
            # 首先生成了一個(gè)全部為1的列表
            output = [1] * n
            # 因?yàn)?和1不是質(zhì)數(shù),所以列表的前兩個(gè)位置賦值為0
            output[0],output[1] = 0,0
             # 此時(shí)從index = 2開(kāi)始遍歷,output[2]==1,即表明第一個(gè)質(zhì)數(shù)為2,然后將2的倍數(shù)對(duì)應(yīng)的索引
             # 全部賦值為0. 此時(shí)output[3] == 1,即表明下一個(gè)質(zhì)數(shù)為3,同樣劃去3的倍數(shù).以此類(lèi)推.
            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中的數(shù)字1表明該位置上的索引數(shù)為質(zhì)數(shù),然后求和即可.
        return sum(output)

總結(jié)

小李今天的做題，是痛并快樂(lè)著的！

云服務(wù)器 GPU云服務(wù)器飛刀小李做題 php做題系統(tǒng)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/43392.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

ztyzz

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

【算法學(xué)習(xí)】1486. 數(shù)組異或操作（java / c / c++ / python / go /

閱讀 2229·2021-10-14 09:43
前端面試題總結(jié)

閱讀 2257·2019-08-30 15:55
TCP/IP基礎(chǔ)總結(jié)性學(xué)習(xí)（2）

閱讀 787·2019-08-30 14:23
[note]大小不固定的圖片、多行文字的水平垂直居中

閱讀 2074·2019-08-30 13:21
CSS相對(duì)定位

閱讀 1290·2019-08-30 12:50
css兩種垂直居中對(duì)齊解決方案

閱讀 2248·2019-08-29 18:46
小程序使用之自定義組件

閱讀 2340·2019-08-29 17:28
【每日一包0014】to-pascal-case,to-sentence-case,to-snake

閱讀 2430·2019-08-29 17:21

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

小李飛刀：做題第八彈！

第一題

第二題

第三題

相關(guān)文章

**小李飛刀：做題第十二彈！**

**小李飛刀：做題第六彈！**

**小李飛刀：做題第十彈！**

**小李飛刀：做題第九彈！**

**小李飛刀：做題第七彈！**

發(fā)表評(píng)論

0條評(píng)論

ztyzz

男|高級(jí)講師

TA的文章

【算法學(xué)習(xí)】1486. 數(shù)組異或操作（java / c / c++ / python / go /

前端面試題總結(jié)

TCP/IP基礎(chǔ)總結(jié)性學(xué)習(xí)（2）

[note]大小不固定的圖片、多行文字的水平垂直居中

CSS相對(duì)定位

css兩種垂直居中對(duì)齊解決方案

小程序使用之自定義組件

【每日一包0014】to-pascal-case,to-sentence-case,to-snake

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

小李飛刀：做題第八彈！

第一題

第二題

第三題

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

小李飛刀：做題第八彈！