小李飛刀：做題第九彈！

Bamboy 發布于2019-07-31 10:11 / 1642人閱讀

摘要：不過可能還沒有抓到動態規劃的真諦，總覺得哪里需要再校正下思路。這題也是動態規劃的題目，目標總是要分解為子問題。總結看算法圖解的時候，涉及動態規劃的小結中有這樣的每種動態規劃解決方案都涉及網格。

寫在前面的話

感覺做題越多遇到的寫法越多，有種躍躍欲試的感覺~

認真做題

第一題

70. 爬樓梯
難度：簡單
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定n是一個正整數。
我的題解：

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        old = 1
        new = 1
        for i in range(2,n+1):
            old,new = new,new+old
        return newv

我的思路：
這題是一個標準的動態規劃的題目，第二步所需要的步數其實是基于第一步，第三步則基于第二步。
用筆計算就可以看出，有一定的規律，新的一步的最優解等于前面一步的最優解+之前所有步數的最優解。
不過可能還沒有抓到動態規劃的真諦，總覺得哪里需要再校正下思路。

第二題

771. 寶石與石頭
難度：簡單
給定字符串J代表石頭中寶石的類型，和字符串S代表你擁有的石頭。S中每個字符代表了一種你擁有的石頭的類型，你想知道你擁有的石頭中有多少是寶石。
J中的字母不重復，J和S中的所有字符都是字母。字母區分大小寫，因此"a"和"A"是不同類型的石頭。
我的題解：

class Solution(object):
    def numJewelsInStones(self, J, S):
        """
        :type J: str
        :type S: str
        :rtype: int
        """
        num = 0
        if not J or not S:
            return 0
        map = {}
        for i in J:
            map[i] = 1
        for j in S:
            if j in map:
                num += map[j]
        return num

我的思路：
這題用了hash表的思路，將J里的每個字母多帶帶存成哈希表的一個鍵，且對應的值為1。
這樣當S進行搜索的時候，對應將值相加即可得到結果。

第三題

709. 轉換成小寫字母
難度：簡單
實現函數 ToLowerCase()，該函數接收一個字符串參數 str，并將該字符串中的大寫字母轉換成小寫字母，之后返回新的字符串。
我的題解：

class Solution(object):
    def toLowerCase(self, str):
        """
        :type str: str
        :rtype: str
        """
        s = list(str)
        map = {"A":"a","B":"b","C":"c","D":"d","E":"e","F":"f","G":"g","H":"h","I":"i","J":"j","K":"k","L":"l","M":"m","N":"n","O":"o","P":"p","Q":"q","R":"r","S":"s","T":"t","U":"u","V":"v","W":"w","X":"x","Y":"y","Z":"z"}
        for i in range(len(s)):
            if s[i] in map:
                s[i] = map[s[i]]
        s1="".join(s)
        return s1

我的思路：
這題....大概寫法非常土了....emmm
認真的寫了個字典，然后對應的寫一下，效率也還可以，但是只能用于數量少的情況下，還可以看下有沒有其他的寫法。

第四題

62. 不同路徑
難度：中等
我的題解：

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0 for _ in range(m)] for _ in range(n)] #建立二維數組
        for i in range(n):
            for j in range(m):
                if i ==0 or j ==0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]

我的思路：
非常粗暴的畫了網格圖，然后發現了規律，
dp[i][j] = dp[i-1][j] + dp[i][j-1],
和少棉在討論的時候，非常真摯的為了為什么他知道需要是左邊的值加上上方的值，
給的說法是最優解的目標就是從左上角到該位置的最優解，局部最優再到全局最優。
這題也是動態規劃的題目，目標總是要分解為子問題。

總結

看《算法圖解》的時候，涉及動態規劃的小結中有這樣的

每種動態規劃解決方案都涉及網格。

單元格中的值通常就是你要優化的值

每個單元格都是一個子問題，因為你需要考慮如何將問題分解為子問題。

云服務器 GPU云服務器飛刀小李做題 php做題系統

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43407.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
小李飛刀：做題第八彈！

摘要：認真做題的分割線第一題乘積最大子序列難度中等給定一個整數數組，找出一個序列中乘積最大的連續子序列該序列至少包含一個數。寫在前面的話慢慢轉變思路，不再死磕不會做的題，思路可以先借鑒，但是一定要吃透透。上周末看完看完了《算法圖解》，感覺對一些題目的思路有比較大的幫助，但是還是要在實踐中理解。認真做題的分割線第一題 152. 乘積最大子序列難度：中等給定一個整數數組nums，找出一個...

ztyzz 2019-07-31 10:11 評論0 收藏0
小李飛刀：做題第七彈！

摘要：給定一個大小為的數組，找到其中的眾數。第五題合并兩個有序數組難度簡單給定兩個有序整數數組和，將合并到中，使得成為一個有序數組。說明初始化和的元素數量分別為和。第六題二叉樹的最大深度難度簡單給定一個二叉樹，找出其最大深度。寫在前面的話做做做題，慢慢上手了就覺得刷題速度變快了，果然還是有點笨~希望最后一竅快點通吧~ 開始做題第一題 169. 求眾數難度：簡單給定一個大小為 n 的數組...

AlphaWatch 2019-07-31 10:09 評論0 收藏0