Python小白 Leetcode刷題歷程 No.61-No.65 旋轉鏈表负芋、不同路徑漫蛔、不同路徑Ⅱ、最小路徑和旧蛾、有效數(shù)字 (有題干 有代碼 有思路心得)

Python小白 Leetcode刷題歷程 No.61-No.65 旋轉鏈表莽龟、不同路徑、不同路徑Ⅱ锨天、最小路徑和毯盈、有效數(shù)字

寫在前面:

作為一個計算機院的大學生,總覺得僅僅在學校粗略的學習計算機專業(yè)課是不夠的病袄,尤其是假期大量的空檔期搂赋,作為一個小白,實習也莫得路子益缠,又不想白白耗費時間脑奠。于是選擇了Leetcode這個平臺來刷題庫。編程我只學過基礎的C語言幅慌,現(xiàn)在在自學Python宋欺,所以用Python3.8刷題庫。現(xiàn)在我Python掌握的還不是很熟練,算法什么的也還沒學齿诞,就先不考慮算法上的優(yōu)化了酸休,單純以解題為目的,復雜程度什么的以后有時間再優(yōu)化祷杈。計劃順序五個題寫一篇日志雨席,希望其他初學編程的人起到一些幫助,寫算是對自己學習歷程的一個見證了吧吠式。

有一起刷LeetCode的可以關注我一下,我會一直發(fā)LeetCode題庫Python3解法的抽米,也可以一起探討特占。

覺得有用的話可以點贊關注下哦,謝謝大家云茸!
········································································································································································
題解框架:

    1.題目是目,難度
    2.題干,題目描述
    3.題解代碼(Python3(不是Python,是Python3))
    4.或許有用的知識點(不一定有)
    5.解題思路
    6.優(yōu)解代碼及分析(當我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會寫在這里)

········································································································································································

No.61.旋轉鏈表

難度:中等
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if (not head) or (not head.next) :
            return None if not head else head
        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head
        
        new_tail = head
        for i in range(n - k%n -1):
            new_tail =new_tail.next
        new_head =new_tail.next
        new_tail.next = None
        return new_head

或許有用的知識點:
這道題可以使用快慢指針的思想标捺。

解題思路:
鏈表中的點已經相連懊纳,一次旋轉操作意味著:先將鏈表閉合成環(huán),再找到相應的位置斷開這個環(huán),確定新的鏈表頭和鏈表尾亡容。所以嗤疯,我們首先找到舊的尾部并將其與鏈表頭相連old_tail.next = head,整個鏈表閉合成環(huán)闺兢,同時計算出鏈表的長度n茂缚;找到新的尾部,第 (n-k%n-1)個節(jié)點屋谭,新的鏈表頭是第(n-k%n)個節(jié)點脚囊;斷開環(huán) new_tail.next = None,并返回新的鏈表頭 new_head即可桐磁。

優(yōu)解代碼及分析:
優(yōu)解代碼(Python3.8)

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        # 下面有 if n==0 ...判斷了悔耘,所以開頭的判斷可以省略
        #if not head or k<=0:
        #    return head
        # 創(chuàng)建一個啞節(jié)點,快指針我擂,慢指針衬以,統(tǒng)計節(jié)點個數(shù)的cur
        dummy = ListNode(-1)
        cur,n,fast,low,dummy.next = head,0,dummy,dummy,head
        # 統(tǒng)計鏈表個數(shù)
        while cur:
            cur,n = cur.next,n+1
        # 邊界條件不要忘記處理了   
        if n==0 or k%n==0:
            return head
        # 還有一個邊界條件不要忘了,k可能大于n校摩,所以要取模
        n = k%n
        # 快指針先移動n步
        while fast.next and n>0:
            fast,n = fast.next,n-1
        # 快指針泄鹏,慢指針一起移動,找到需要切割的點
        while fast.next:
            low,fast = low.next,fast.next
        # 改變鏈表的指向關系秧耗,注意這里的步驟不要亂了
        # 先讓fast節(jié)點指向head(也就是dummy.next)
        # 再是head(也就是dummy.next)指向low的下一個節(jié)點
        # 這兩步如果弄反了就會出現(xiàn)節(jié)點丟失了
        # 最后不要忘記將low.next置空
        fast.next,dummy.next,low.next = head,low.next,None
        return dummy.next

分析;
雙指針法寫起來思路比較清楚备籽,代碼比較簡單,代碼中有著極詳細的注釋,應該比較容易理解车猬。

No.62.不同路徑

難度:中等
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        #第一行/第一列每個格都只有一種走法
        dp = [[1]*n] + [[1]+[0]*(n-1) for _ in range(m-1)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

或許有用的知識點:
這道題要用到動態(tài)規(guī)劃的方法霉猛。

解題思路:
這道題可以使用動態(tài)規(guī)劃的方法,套用動態(tài)規(guī)劃的模板珠闰,對于這道題惜浅,假設dp[i][j]是從左上角到第i行第j列的方格有多少總走法,動態(tài)規(guī)劃的三要素分別為:
狀態(tài):第一行和第一列都只有一種走法伏嗜,其他格子走法=上面一格的走法+左邊一格的走法
狀態(tài)轉移方程:dp[i][j] = dp[i-1][j] + dp[i][j-1]
邊界條件: dp = [[1]n] + [[1]+[0](n-1) for _ in range(m-1)]
空間復雜度:O(n2)

優(yōu)解代碼及分析:
優(yōu)解代碼(Python3.8)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        cur = [1]*n
        for i in range(1,m):
            for j in range(1,n):
                cur[j] += cur[j-1]
        return cur[n-1]

分析:
其實也是動態(tài)規(guī)劃的思想坛悉,只不過將創(chuàng)建的空間減少了一個維度,空間復雜度O(n)承绸。

No.63.不同路徑Ⅱ

難度:中等
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if (not obstacleGrid) or (not obstacleGrid[0]):
            return 0
        l_row = len(obstacleGrid)
        l_col = len(obstacleGrid[0])
        dp = [ [0]*l_col for _ in range(l_row)]
        #首位置
        dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0
        if dp[0][0] == 0:
            return 0
        #第一行
        for j in range(1,l_col):
            if obstacleGrid[0][j] != 1:
                dp[0][j] = dp[0][j-1]
        #第一列
        for i in range(1,l_row):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = dp[i-1][0]
        #剩余位置
        for i in range(1,l_row):
            for j in range(1,l_col):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[l_row-1][l_col-1]

或許有用的知識點:
這道題要用到動態(tài)規(guī)劃的方法裸影。

解題思路:
這道題根上一道題‘No.62.不同路徑’很相似,是上一題的加強版军熏。
這道題可以使用動態(tài)規(guī)劃的方法轩猩,套用動態(tài)規(guī)劃的模板,對于這道題荡澎,假設dp[i][j]是從左上角到第i行第j列的方格有多少總走法均践,動態(tài)規(guī)劃的三要素分別為:
狀態(tài):第一行和第一列都只有一種走法,其他格子走法=上面一格的走法+左邊一格的走法摩幔;但如果這一格有障礙物彤委,該格的dp=0。
狀態(tài)轉移方程:if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1]
邊界條件:
(#首位置)dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0 或衡;
(#第一行)if obstacleGrid[0][j] != 1: dp[0][j] = dp[0][j-1]葫慎;
(#第一列)if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1]。

No.64.最小路徑和

難度:中等
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if (not grid) or (not grid[0]):
            return 0
        m = len(grid)
        n = len(grid[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = grid[0][0]           #首位
        for j in range(1,n):            #第一行
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1,m):            #第一列
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
        return dp[m-1][n-1]

或許有用的知識點:
這道題要用到動態(tài)規(guī)劃的方法薇宠。

解題思路:
這道題可以使用動態(tài)規(guī)劃的方法偷办,套用動態(tài)規(guī)劃的模板,對于這道題澄港,假設dp[i][j]是從左上角到第i行第j列的方格路徑的數(shù)字總和最小值椒涯,動態(tài)規(guī)劃的三要素分別為:
狀態(tài):第一行和第一列都只有一種走法,其他格子的路徑的數(shù)字總和最小值=(上面一格的路徑的數(shù)字總和最小值+第i行第j列的方格的數(shù)字) 和 (左邊一格的路徑的數(shù)字總和最小值+第i行第j列的方格的數(shù)字)二者之間的最小值回梧。
狀態(tài)轉移方程:dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
邊界條件:
(#首位置) dp[0][0] = grid[0][0] 废岂;
(#第一行)for j in range(1,n): dp[0][j] = dp[0][j-1] + grid[0][j];
(#第一列)for i in range(1,m): dp[i][0] = dp[i-1][0] + grid[i][0]狱意。

No.65.有效數(shù)字

難度:困難
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def isNumber(self, s: str) -> bool:
        state = [
            {},
            # 狀態(tài)1,初始狀態(tài)(掃描通過的空格)
            {"blank": 1, "sign": 2, "digit": 3, ".": 4},
            # 狀態(tài)2,發(fā)現(xiàn)符號位(后面跟數(shù)字或者小數(shù)點)
            {"digit": 3, ".": 4},
            # 狀態(tài)3,數(shù)字(一直循環(huán)到非數(shù)字)
            {"digit": 3, ".": 5, "e": 6, "blank": 9},
            # 狀態(tài)4,小數(shù)點(后面只有緊接數(shù)字)
            {"digit": 5},
            # 狀態(tài)5,小數(shù)點之后(后面只能為數(shù)字,e,或者以空格結束)
            {"digit": 5, "e": 6, "blank": 9},
            # 狀態(tài)6,發(fā)現(xiàn)e(后面只能符號位, 和數(shù)字)
            {"sign": 7, "digit": 8},
            # 狀態(tài)7,e之后(只能為數(shù)字)
            {"digit": 8},
            # 狀態(tài)8,e之后的數(shù)字后面(只能為數(shù)字或者以空格結束)
            {"digit": 8, "blank": 9},
            # 狀態(tài)9, 終止狀態(tài) (如果發(fā)現(xiàn)非空,就失敗)
            {"blank": 9}
        ]
        cur_state = 1
        for c in s:
            if c.isdigit():
                c = "digit"
            elif c in " ":
                c = "blank"
            elif c in "+-":
                c = "sign"
            if c not in state[cur_state]:
                return False
            cur_state = state[cur_state][c]
        if cur_state not in [3, 5, 8, 9]:
            return False
        return True

或許有用的知識點:
這道題要用到有限狀態(tài)機(FSM)湖苞,或者說有限狀態(tài)機的一種特殊狀態(tài)——有限自動機(DFA)的思想(在數(shù)字電路基礎、Verilog详囤、離散數(shù)學等大學專業(yè)課中應該學習過)财骨。

解題思路:
以下為一個考慮到各種情況的有限自動機模型镐作,狀態(tài)機的結構可以結合代碼中的注釋一起理解。(自己設計一個狀態(tài)機有時不能一開始就考慮到所有情況隆箩,要多測試不同情況)该贾。我們的代碼先創(chuàng)建一個state包含狀態(tài)機的所有狀態(tài)與內容,之和將字符串中的字符依次放入狀態(tài)機運行捌臊,最后查看狀態(tài)機的狀態(tài)是否在指定狀態(tài)即可杨蛋。


在這里插入圖片描述
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市理澎,隨后出現(xiàn)的幾起案子逞力,更是在濱河造成了極大的恐慌,老刑警劉巖糠爬,帶你破解...
    沈念sama閱讀 216,591評論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件寇荧,死亡現(xiàn)場離奇詭異,居然都是意外死亡秩铆,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,448評論 3 392
  • 文/潘曉璐 我一進店門灯变,熙熙樓的掌柜王于貴愁眉苦臉地迎上來殴玛,“玉大人,你說我怎么就攤上這事添祸」鏊冢” “怎么了?”我有些...
    開封第一講書人閱讀 162,823評論 0 353
  • 文/不壞的土叔 我叫張陵刃泌,是天一觀的道長凡壤。 經常有香客問我,道長耙替,這世上最難降的妖魔是什么亚侠? 我笑而不...
    開封第一講書人閱讀 58,204評論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮俗扇,結果婚禮上硝烂,老公的妹妹穿的比我還像新娘。我一直安慰自己铜幽,他們只是感情好滞谢,可當我...
    茶點故事閱讀 67,228評論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著除抛,像睡著了一般狮杨。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上到忽,一...
    開封第一講書人閱讀 51,190評論 1 299
  • 那天橄教,我揣著相機與錄音,去河邊找鬼。 笑死颤陶,一個胖子當著我的面吹牛颗管,可吹牛的內容都是我干的。 我是一名探鬼主播滓走,決...
    沈念sama閱讀 40,078評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼垦江,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了搅方?” 一聲冷哼從身側響起比吭,我...
    開封第一講書人閱讀 38,923評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎姨涡,沒想到半個月后衩藤,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經...
    沈念sama閱讀 45,334評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡涛漂,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,550評論 2 333
  • 正文 我和宋清朗相戀三年赏表,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片匈仗。...
    茶點故事閱讀 39,727評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡瓢剿,死狀恐怖,靈堂內的尸體忽然破棺而出悠轩,到底是詐尸還是另有隱情间狂,我是刑警寧澤,帶...
    沈念sama閱讀 35,428評論 5 343
  • 正文 年R本政府宣布火架,位于F島的核電站鉴象,受9級特大地震影響,放射性物質發(fā)生泄漏何鸡。R本人自食惡果不足惜纺弊,卻給世界環(huán)境...
    茶點故事閱讀 41,022評論 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望骡男。 院中可真熱鬧俭尖,春花似錦、人聲如沸洞翩。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,672評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽骚亿。三九已至已亥,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間来屠,已是汗流浹背虑椎。 一陣腳步聲響...
    開封第一講書人閱讀 32,826評論 1 269
  • 我被黑心中介騙來泰國打工震鹉, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人捆姜。 一個月前我還...
    沈念sama閱讀 47,734評論 2 368
  • 正文 我出身青樓传趾,卻偏偏與公主長得像,于是被迫代替她去往敵國和親泥技。 傳聞我的和親對象是個殘疾皇子浆兰,可洞房花燭夜當晚...
    茶點故事閱讀 44,619評論 2 354

推薦閱讀更多精彩內容