小李飛刀：做題第八彈！

ztyzz 發布于2019-07-31 10:11 / 3405人閱讀

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

寫在前面的話

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

認真做題的分割線

第一題

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做題系統

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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