Python小白 Leetcode刷題歷程 No.51-No.55 N皇后囚企、N皇后Ⅱ丈咐、最大子序和、螺旋矩陣龙宏、跳躍游戲 (有題干 有代碼 有思路心得)

Python小白 Leetcode刷題歷程 No.51-No.55 N皇后棵逊、N皇后Ⅱ、最大子序和银酗、螺旋矩陣辆影、跳躍游戲

寫(xiě)在前面:

作為一個(gè)計(jì)算機(jī)院的大學(xué)生,總覺(jué)得僅僅在學(xué)校粗略的學(xué)習(xí)計(jì)算機(jī)專(zhuān)業(yè)課是不夠的黍特,尤其是假期大量的空檔期蛙讥,作為一個(gè)小白,實(shí)習(xí)也莫得路子灭衷,又不想白白耗費(fèi)時(shí)間次慢。于是選擇了Leetcode這個(gè)平臺(tái)來(lái)刷題庫(kù)。編程我只學(xué)過(guò)基礎(chǔ)的C語(yǔ)言,現(xiàn)在在自學(xué)Python迫像,所以用Python3.8刷題庫(kù)∈锰В現(xiàn)在我Python掌握的還不是很熟練,算法什么的也還沒(méi)學(xué)侵蒙,就先不考慮算法上的優(yōu)化了造虎,單純以解題為目的,復(fù)雜程度什么的以后有時(shí)間再優(yōu)化纷闺。計(jì)劃順序五個(gè)題寫(xiě)一篇日志算凿,希望其他初學(xué)編程的人起到一些幫助,寫(xiě)算是對(duì)自己學(xué)習(xí)歷程的一個(gè)見(jiàn)證了吧犁功。

有一起刷LeetCode的可以關(guān)注我一下氓轰,我會(huì)一直發(fā)LeetCode題庫(kù)Python3解法的,也可以一起探討浸卦。

覺(jué)得有用的話可以點(diǎn)贊關(guān)注下哦署鸡,謝謝大家!
········································································································································································
題解框架:

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

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

No.51.N皇后

難度:困難
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res=[]
        if n == 0:
            return res
        nums = [ i for i in range(n)]
        col = set()
        master = set()
        slave = set()
        stack = []

        def backtrack(row):
            if row == n:
                board = solution(stack,n)
                res.append(board)
                return
            
            for i in range(n):
                if (i not in col) and (row+i not in master) and (row-i not in slave):
                    stack.append(nums[i])
                    col.add(i)
                    master.add(row+i)
                    slave.add(row-i)
                    backtrack(row+1)

                    stack.pop()
                    col.remove(i)
                    master.remove(row+i)
                    slave.remove(row-i)
        
        def solution(stack,n):
            return ['.'*stack[i] + 'Q' + '.'*(n-stack[i]-1) for i in range(n)]

        backtrack(0)
        return res

或許有用的知識(shí)點(diǎn):
這道題要用到回溯算法。

在這里插入圖片描述

解題思路:
這道題是樹(shù)形結(jié)構(gòu)怒医,且需要剪枝炉抒,于是我們采用回溯算法。按照回溯算法的模板稚叹,本題我們將行(row)作為回溯函數(shù)的變量焰薄,套用回溯算法的模板,則回溯算法的三個(gè)組成部分分別為:
1.回溯出口:行數(shù)row==n扒袖,將該情況的解法儲(chǔ)存進(jìn)結(jié)果res中塞茅;
2.回溯主體:如果對(duì)于該行的列位置i,如果i滿足無(wú)列沖突(因?yàn)槭侵鹦谢厮菁韭剩虼吮囟ú粫?huì)行沖突)野瘦、無(wú)斜線沖突(橫縱坐標(biāo)之和之差都不沖突),則記錄該位置的行(記錄兩次蚀同,一個(gè)是列表形式為了生成解缅刽,另一個(gè)是set形式為了判斷是否沖突)啊掏、橫縱坐標(biāo)和蠢络、橫縱坐標(biāo)差,之和執(zhí)行回溯函數(shù)backtrack(row+1);
3.狀態(tài)返回:說(shuō)明已經(jīng)結(jié)束了該分支的回溯迟蜜,則刪除剛才記錄的該位置的行刹孔、橫縱坐標(biāo)和、橫縱坐標(biāo)差。
為滿足回溯函數(shù)髓霞,我們考慮創(chuàng)建一個(gè)從1到n的n元素的列表卦睹,和列、橫縱坐標(biāo)和方库、橫縱坐標(biāo)差的空set结序,來(lái)判斷是否沖突;我們用一個(gè)列表纵潦,儲(chǔ)存皇后在每一行的列位置徐鹤,最后定義一個(gè)函數(shù),將這個(gè)列表轉(zhuǎn)換成棋盤(pán)格式的解邀层,最后返回res即可返敬。

No.52.N皇后Ⅱ

難度:困難
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def totalNQueens(self, n: int) -> int:
        res=[]
        if n == 0:
            return res
        col = set()
        master = set()
        slave = set()

        def backtrack(row):
            if row == n:
                res.append('count')
                return
            
            for i in range(n):
                if (i not in col) and (row+i not in master) and (row-i not in slave):
                    col.add(i)
                    master.add(row+i)
                    slave.add(row-i)
                    backtrack(row+1)

                    col.remove(i)
                    master.remove(row+i)
                    slave.remove(row-i)

        backtrack(0)
        return len(res)

或許有用的知識(shí)點(diǎn):
這道題要用到回溯算法。

在這里插入圖片描述

解題思路:
這道題的思路其實(shí)和上一題‘No.51.N皇后’基本一致寥院,而且這道題比上一題‘No.51.N皇后’簡(jiǎn)單劲赠,即閹割版;上一題‘No.51.N皇后’需要我們寫(xiě)出所有解法的內(nèi)容秸谢,本題只需寫(xiě)出解的數(shù)量即可凛澎。
這道題是樹(shù)形結(jié)構(gòu),且需要剪枝估蹄,于是我們采用回溯算法预厌。按照回溯算法的模板,本題我們將行(row)作為回溯函數(shù)的變量元媚,則回溯算法的三個(gè)組成部分分別為:
1.回溯出口:行數(shù)row==n轧叽,將解的個(gè)數(shù)res+=1;
2.回溯主體:如果對(duì)于該行的列位置i刊棕,如果i滿足無(wú)列沖突(因?yàn)槭侵鹦谢厮萏可梗虼吮囟ú粫?huì)行沖突)、無(wú)斜線沖突(橫縱坐標(biāo)之和之差都不沖突)甥角,則記錄該位置的行网严、橫縱坐標(biāo)和、橫縱坐標(biāo)差嗤无,之和執(zhí)行回溯函數(shù)backtrack(row+1);
3.狀態(tài)返回:說(shuō)明已經(jīng)結(jié)束了該分支的回溯震束,則刪除剛才記錄的該位置的行、橫縱坐標(biāo)和当犯、橫縱坐標(biāo)差垢村。
為滿足回溯函數(shù),我們考慮創(chuàng)建列嚎卫、橫縱坐標(biāo)和嘉栓、橫縱坐標(biāo)差的空set,來(lái)判斷是否沖突,并初始化res=0侵佃,最后返回res麻昼。

No.53.最大子序和

難度:簡(jiǎn)單
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l=len(nums)
        if l==0:
            return 0
        dp=[0 for _ in range(l)]
        dp[0]=nums[0]        
        for i in range(1,l):
            dp[i] = max(dp[i-1]+nums[i],nums[i])     
        return max(dp)

或許有用的知識(shí)點(diǎn):
這道題可用使用動(dòng)態(tài)規(guī)劃的方法。
這道題可用使用分治算法來(lái)解決(更為精妙馋辈,我會(huì)在‘優(yōu)解代碼及分析’詳細(xì)說(shuō)明)抚芦。

解題思路:
這道題是求最優(yōu)化解的問(wèn)題,且滿足動(dòng)態(tài)規(guī)劃問(wèn)題的條件迈螟,于是我們用動(dòng)態(tài)規(guī)劃的方法來(lái)做燕垃。這道題套用動(dòng)態(tài)規(guī)劃的模板,的到動(dòng)態(tài)規(guī)劃的三要素分別為:
狀態(tài):從頭到第i個(gè)元素井联,能得到的最大子序和為dp[i]卜壕;則從頭到第i+1個(gè)元素,能得到的最大子序和為的(dp[i]+nums[i+1])和(nums[i+1])中的最大數(shù)值烙常。
狀態(tài)轉(zhuǎn)移方程:dp[i] = max(dp[i-1]+nums[i],nums[i])
邊界條件:dp[0]=nums[0]
之后對(duì)列表從頭到尾動(dòng)態(tài)規(guī)劃即可轴捎。
復(fù)雜度:
時(shí)間復(fù)雜度: O(N)
空間復(fù)雜度: O(1)

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l=len(nums)
        if l <= 1:
            return 0 if l==0 else nums[0]
        else:
            #遞歸計(jì)算左半邊最大子序和
            max_left = self.maxSubArray(nums[0:l//2])
            #遞歸計(jì)算右半邊最大子序和
            max_right = self.maxSubArray(nums[l//2:l])
        
        #計(jì)算中間的最大子序和,從右到左計(jì)算左邊的最大子序和蚕脏,從左到右計(jì)算右邊的最大子序和侦副,再相加
        max_l = nums[l//2 -1]
        tmp = 0
        for i in range(l//2 -1,-1,-1):
            tmp += nums[i]
            max_l = max(tmp, max_l)
        max_r = nums[l//2]
        tmp = 0
        for i in range(l//2,l):
            tmp += nums[i]
            max_r = max(tmp, max_r)
        #返回三個(gè)中的最大值
        return max(max_right,max_left,max_l+max_r)

分析:
官方說(shuō)分治法更為精美,其實(shí)......驼鞭,這道題里分治法比動(dòng)態(tài)規(guī)劃效率低秦驯。代碼中有一些注釋?zhuān)旅嬗幸粡垐D詳細(xì)舉例了這道題分治的過(guò)程。
復(fù)雜度:
時(shí)間復(fù)雜度: O(N*logN)
空間復(fù)雜度: O(1)


在這里插入圖片描述

No.54.螺旋矩陣

難度:中等
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        L_row = len(matrix)
        L_col = len(matrix[0])

        def spiral(depth):
            l_row,l_col = L_row-2*depth,L_col-2*depth
            if l_row<=0 or l_col<=0:
                return []
            if l_row==1:
                return matrix[depth][depth:depth+l_col]
            if l_col==1:
                return [ matrix[i][depth] for i in range(depth,depth+l_row) ]
            res = []
            res += matrix[depth][depth:depth+l_col]
            res += [ matrix[i][depth+l_col-1] for i in range(depth+1,depth+l_row-1) ]
            res += reversed(matrix[depth+l_row-1][depth:depth+l_col])
            res += reversed([ matrix[i][depth] for i in range(depth+1,depth+l_row-1) ])
            return res + spiral(depth+1)

        return spiral(0)

或許有用的知識(shí)點(diǎn):
可以了解一下Python中的reverse()函數(shù)和reversed(),一般用于反轉(zhuǎn)python中大多類(lèi)型的數(shù)據(jù)挣棕,下面是這兩個(gè)函數(shù)的一些介紹:

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

解題思路:
設(shè)置一個(gè)空列表res译隘,定義一個(gè)遞歸函數(shù)spiral,從外到內(nèi)一層一層記錄二維數(shù)組的值并遞歸到下一層即可洛心,最后輸出res固耘,代碼非常好理解。

No.55.跳躍游戲

難度:中等
題目描述:


在這里插入圖片描述

題解代碼(Python3.8)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_jump=0
        l=len(nums)
        for i in range(l):
            max_jump = max(max_jump,i+nums[i])
            if max_jump>=l-1:
                return True
            if max_jump<i+1:
                break
        return False

或許有用的知識(shí)點(diǎn):
這道題可以用到貪心算法词身。

解題思路:
總思路:如果最大跳躍距離大于等于最后一個(gè)位置的索引厅目,就表示能夠到達(dá)最后一個(gè)位置,反之則不能法严。
貪心算法:
定義能達(dá)到的最遠(yuǎn)位置max_jump=0损敷,遍歷數(shù)組,遍歷范圍[0,n-1)深啤;
所能達(dá)到的最遠(yuǎn)位置max_jump=max(max_jump,nums[i]+i)拗馒,表示上一最遠(yuǎn)位置和當(dāng)前索引i和索引i上的步數(shù)之和中的較大者。
如果max_jump大于等于最后一個(gè)位置的索引,就return True墓塌。
注意:數(shù)組遍歷范圍為[0,n-1)瘟忱。
復(fù)雜度分析
時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(1)

其實(shí)這道題和‘No.45.跳躍游戲Ⅱ’思路很相似,‘No.45.跳躍游戲Ⅱ’是這道題的升級(jí)版苫幢,大家可以做一下這道題練習(xí)一下访诱。
No.45.跳躍游戲Ⅱ:
https://blog.csdn.net/LanXiu_/article/details/104177349

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市韩肝,隨后出現(xiàn)的幾起案子触菜,更是在濱河造成了極大的恐慌,老刑警劉巖哀峻,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件涡相,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡剩蟀,警方通過(guò)查閱死者的電腦和手機(jī)催蝗,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)育特,“玉大人丙号,你說(shuō)我怎么就攤上這事$衷” “怎么了犬缨?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)棉浸。 經(jīng)常有香客問(wèn)我怀薛,道長(zhǎng),這世上最難降的妖魔是什么迷郑? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任枝恋,我火速辦了婚禮,結(jié)果婚禮上嗡害,老公的妹妹穿的比我還像新娘鼓择。我一直安慰自己,他們只是感情好就漾,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布呐能。 她就那樣靜靜地躺著,像睡著了一般抑堡。 火紅的嫁衣襯著肌膚如雪摆出。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天首妖,我揣著相機(jī)與錄音偎漫,去河邊找鬼。 笑死有缆,一個(gè)胖子當(dāng)著我的面吹牛象踊,可吹牛的內(nèi)容都是我干的温亲。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼杯矩,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼栈虚!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起史隆,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤魂务,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后泌射,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體粘姜,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年熔酷,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了孤紧。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡拒秘,死狀恐怖坛芽,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情翼抠,我是刑警寧澤咙轩,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站阴颖,受9級(jí)特大地震影響活喊,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜量愧,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一钾菊、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧偎肃,春花似錦煞烫、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至紊馏,卻和暖如春料饥,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背朱监。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工岸啡, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人赫编。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓巡蘸,卻偏偏與公主長(zhǎng)得像奋隶,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子悦荒,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361