資訊專欄INFORMATION COLUMN
摘要：認真做題的分割線第一題乘積最大子序列難度中等給定一個整數(shù)數(shù)組，找出一個序列中乘積最大的連續(xù)子序列該序列至少包含一個數(shù)。
寫在前面的話
慢慢轉(zhuǎn)變思路，不再死磕不會做的題，思路可以先借鑒，但是一定要吃透透。
上周末看完看完了《算法圖解》，感覺對一些題目的思路有比較大的幫助，但是還是要在實踐中理解。
152. 乘積最大子序列
難度：中等
給定一個整數(shù)數(shù)組nums，找出一個序列中乘積最大的連續(xù)子序列（該序列至少包含一個數(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] #當前狀態(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
我的思路：
這題做了兩次，主體思路為：每次都找到乘積中的最大正值和最小負值，因為絕對值最大的兩個數(shù)在下一次計算中才有可能成為最大值。（畢竟題目沒有限制非負數(shù)）
第一次的時候報錯的原因是，我記錄了每次的maxsum和minsum，沒有記錄上一次循環(huán)留下的值。
然鵝，上一次的狀態(tài)會影響到下一次的狀態(tài)，所以必須記住上一步的最優(yōu)解。
可以判斷是個NP問題，但是動態(tài)規(guī)劃還得多多練習
202. 快樂數(shù)
難度：簡單
編寫一個算法來判斷一個數(shù)是不是“快樂數(shù)”。
一個“快樂數(shù)”定義為：對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和，然后重復這個過程直到這個數(shù)變?yōu)?1，也可能是無限循環(huán)但始終變不到 1。如果可以變?yōu)?1，那么這個數(shù)就是快樂數(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，得出是快樂數(shù)的結(jié)論；
條件二：為了得出非快樂數(shù)的結(jié)論，這個數(shù)可能會陷入循環(huán)，那么就要記錄下每輪的值，并進行比對。
其他：
在評論中發(fā)現(xiàn)了一個很有趣的算法，就是用dict記錄下肯定會循環(huán)的數(shù)字的詞典，當遇到相關(guān)數(shù)字的時候就可以跳出了。
一般為{4,16,37,58,89,145,42,20}
204. 計數(shù)質(zhì)數(shù)
難度：簡單
統(tǒng)計所有小于非負整數(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)
我的思路：
這個算法借鑒了評論里的一個炒雞有趣的算法，默認查詢是否質(zhì)數(shù)的時候，我們習慣用循環(huán)判斷，這樣肯定會超時。
而這個算法呢，叫做厄拉多塞篩法，他給了如下解釋：
比如說求20以內(nèi)質(zhì)數(shù)的個數(shù),首先0,1不是質(zhì)數(shù).2是第一個質(zhì)數(shù),然后把20以內(nèi)所有2的倍數(shù)劃去.2后面緊跟的數(shù)即為下一個質(zhì)數(shù)3,然后把3所有的倍數(shù)劃去.3后面緊跟的數(shù)即為下一個質(zhì)數(shù)5,再把5所有的倍數(shù)劃去.以此類推
包括他的題解的寫法也很有趣，但是我還沒弄明白
output[i*i:n:i] = [0] * len(output[i*i:n:i])這一句的意思，還要琢磨下，所以用的是循環(huán)的寫法。
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
else:
# 首先生成了一個全部為1的列表
output = [1] * n
# 因為0和1不是質(zhì)數(shù),所以列表的前兩個位置賦值為0
output[0],output[1] = 0,0
# 此時從index = 2開始遍歷,output[2]==1,即表明第一個質(zhì)數(shù)為2,然后將2的倍數(shù)對應的索引
# 全部賦值為0. 此時output[3] == 1,即表明下一個質(zhì)數(shù)為3,同樣劃去3的倍數(shù).以此類推.
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é)
小李今天的做題，是痛并快樂著的！
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/43392.html
摘要：寫在前面今天沒有叨逼叨但是又一次錯過了競賽愛睡覺的小李下周要上班，下下周一定要參加了握拳認真做題的分割線第一題兩地調(diào)度公司計劃面試人。第人飛往市的費用為，飛往市的費用為。示例輸入輸出解釋第一個人去市，費用為。 寫在前面 今天沒有叨逼叨...但是又一次錯過了競賽...愛睡覺的小李...下周要上班，下下周一定要參加了（握拳 認真做題的分割線 第一題 1029. 兩地調(diào)度公司計劃面試2N人。...
摘要：給定的字符串只含有小寫英文字母，并且長度不超過。其他這題了，要重做看了其他的人的題解，使用的是無限逼近中位值的辦法，理論基礎(chǔ)應該是泰勒公式。萬萬沒想到居然用到了泰勒公式手工執(zhí)行了下算法，反而理解的更快，但是泰勒公式還得再復習下。 寫在前面的話 今天持續(xù)做題ing，python有意思~今天的題有點虐心...興許是我太笨了...會努力學習的！動態(tài)規(guī)劃我來啦~ 開始做題 第一題 459. 重...
摘要：第二題漢明距離難度簡單兩個整數(shù)之間的漢明距離指的是這兩個數(shù)字對應二進制位不同的位置的數(shù)目。給出兩個整數(shù)和，計算它們之間的漢明距離。第三題買賣股票的最佳時機難度簡單給定一個數(shù)組，它的第個元素是一支給定股票第天的價格。 寫在前面 這幾天斷斷續(xù)續(xù)做了題目，也在慢慢體會一些數(shù)據(jù)思維。終于不用邊做視頻邊寫題目啦~開心~把這幾天的題解發(fā)一下~ 認真做題的分割線 第一題 977. 有序數(shù)組的平方難度...
摘要：不過可能還沒有抓到動態(tài)規(guī)劃的真諦，總覺得哪里需要再校正下思路。這題也是動態(tài)規(guī)劃的題目，目標總是要分解為子問題。總結(jié)看算法圖解的時候，涉及動態(tài)規(guī)劃的小結(jié)中有這樣的每種動態(tài)規(guī)劃解決方案都涉及網(wǎng)格。 寫在前面的話 感覺做題越多遇到的寫法越多，有種躍躍欲試的感覺~ 認真做題 第一題 70. 爬樓梯難度：簡單假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少...
摘要：給定一個大小為的數(shù)組，找到其中的眾數(shù)。第五題合并兩個有序數(shù)組難度簡單給定兩個有序整數(shù)數(shù)組和，將合并到中，使得成為一個有序數(shù)組。說明初始化和的元素數(shù)量分別為和。第六題二叉樹的最大深度難度簡單給定一個二叉樹，找出其最大深度。 寫在前面的話 做做做題，慢慢上手了就覺得刷題速度變快了，果然還是有點笨~希望最后一竅快點通吧~ 開始做題 第一題 169. 求眾數(shù)難度：簡單給定一個大小為 n 的數(shù)組...
閱讀 2153·2021-10-14 09:43
閱讀 2208·2019-08-30 15:55
閱讀 741·2019-08-30 14:23
閱讀 2035·2019-08-30 13:21
閱讀 1250·2019-08-30 12:50
閱讀 2210·2019-08-29 18:46
閱讀 2293·2019-08-29 17:28
閱讀 2381·2019-08-29 17:21
