成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

小李飛刀：做題第九彈！

Bamboy / 1661人閱讀

摘要：不過可能還沒有抓到動(dòng)態(tài)規(guī)劃的真諦，總覺得哪里需要再校正下思路。這題也是動(dòng)態(tài)規(guī)劃的題目，目標(biāo)總是要分解為子問題?？偨Y(jié)看算法圖解的時(shí)候，涉及動(dòng)態(tài)規(guī)劃的小結(jié)中有這樣的每種動(dòng)態(tài)規(guī)劃解決方案都涉及網(wǎng)格。

寫在前面的話

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

認(rèn)真做題
第一題

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

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

我的思路：
這題是一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃的題目，第二步所需要的步數(shù)其實(shí)是基于第一步，第三步則基于第二步。
用筆計(jì)算就可以看出，有一定的規(guī)律，新的一步的最優(yōu)解等于前面一步的最優(yōu)解+之前所有步數(shù)的最優(yōu)解。
不過可能還沒有抓到動(dòng)態(tài)規(guī)劃的真諦，總覺得哪里需要再校正下思路。

第二題

771. 寶石與石頭
難度：簡(jiǎn)單
給定字符串J代表石頭中寶石的類型，和字符串S代表你擁有的石頭。S中每個(gè)字符代表了一種你擁有的石頭的類型，你想知道你擁有的石頭中有多少是寶石。
J中的字母不重復(fù)，J和S中的所有字符都是字母。字母區(qū)分大小寫，因此"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里的每個(gè)字母多帶帶存成哈希表的一個(gè)鍵，且對(duì)應(yīng)的值為1。
這樣當(dāng)S進(jìn)行搜索的時(shí)候，對(duì)應(yīng)將值相加即可得到結(jié)果。

第三題

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

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
認(rèn)真的寫了個(gè)字典，然后對(duì)應(yīng)的寫一下，效率也還可以，但是只能用于數(shù)量少的情況下，還可以看下有沒有其他的寫法。

第四題

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)] #建立二維數(shù)組
        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]

我的思路：
非常粗暴的畫了網(wǎng)格圖，然后發(fā)現(xiàn)了規(guī)律，
dp[i][j] = dp[i-1][j] + dp[i][j-1],
和少棉在討論的時(shí)候，非常真摯的為了為什么他知道需要是左邊的值加上上方的值，
給的說法是最優(yōu)解的目標(biāo)就是從左上角到該位置的最優(yōu)解，局部最優(yōu)再到全局最優(yōu)。
這題也是動(dòng)態(tài)規(guī)劃的題目，目標(biāo)總是要分解為子問題。

總結(jié)

看《算法圖解》的時(shí)候，涉及動(dòng)態(tài)規(guī)劃的小結(jié)中有這樣的

每種動(dòng)態(tài)規(guī)劃解決方案都涉及網(wǎng)格。


單元格中的值通常就是你要優(yōu)化的值


每個(gè)單元格都是一個(gè)子問題，因?yàn)槟阈枰紤]如何將問題分解為子問題。

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

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

相關(guān)文章

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

    摘要：寫在前面今天沒有叨逼叨但是又一次錯(cuò)過了競(jìng)賽愛睡覺的小李下周要上班，下下周一定要參加了握拳認(rèn)真做題的分割線第一題兩地調(diào)度公司計(jì)劃面試人。第人飛往市的費(fèi)用為，飛往市的費(fèi)用為。示例輸入輸出解釋第一個(gè)人去市，費(fèi)用為。 寫在前面 今天沒有叨逼叨...但是又一次錯(cuò)過了競(jìng)賽...愛睡覺的小李...下周要上班，下下周一定要參加了（握拳 認(rèn)真做題的分割線 第一題 1029. 兩地調(diào)度公司計(jì)劃面試2N人。...

    yagami 評(píng)論0 收藏0

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

    摘要：給定的字符串只含有小寫英文字母，并且長(zhǎng)度不超過。其他這題了，要重做看了其他的人的題解，使用的是無限逼近中位值的辦法，理論基礎(chǔ)應(yīng)該是泰勒公式。萬萬沒想到居然用到了泰勒公式手工執(zhí)行了下算法，反而理解的更快，但是泰勒公式還得再復(fù)習(xí)下。 寫在前面的話 今天持續(xù)做題ing，python有意思~今天的題有點(diǎn)虐心...興許是我太笨了...會(huì)努力學(xué)習(xí)的！動(dòng)態(tài)規(guī)劃我來啦~ 開始做題 第一題 459. 重...

    BigNerdCoding 評(píng)論0 收藏0

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

    摘要：第二題漢明距離難度簡(jiǎn)單兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對(duì)應(yīng)二進(jìn)制位不同的位置的數(shù)目。給出兩個(gè)整數(shù)和，計(jì)算它們之間的漢明距離。第三題買賣股票的最佳時(shí)機(jī)難度簡(jiǎn)單給定一個(gè)數(shù)組，它的第個(gè)元素是一支給定股票第天的價(jià)格。 寫在前面 這幾天斷斷續(xù)續(xù)做了題目，也在慢慢體會(huì)一些數(shù)據(jù)思維。終于不用邊做視頻邊寫題目啦~開心~把這幾天的題解發(fā)一下~ 認(rèn)真做題的分割線 第一題 977. 有序數(shù)組的平方難度...

    bingo 評(píng)論0 收藏0

  • 小李飛刀：做題第八彈！

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

    ztyzz 評(píng)論0 收藏0

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

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

    AlphaWatch 評(píng)論0 收藏0

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

0條評(píng)論

閱讀需要支付1元查看
<