楊婭娟刷題筆記

楊婭娟刷題筆記前言在學(xué)習(xí)計(jì)算機(jī)科學(xué)的過(guò)程中，刷題是一種常見(jiàn)的學(xué)習(xí)方法。通過(guò)刷題，我們可以鞏固基礎(chǔ)知識(shí)，提高解決問(wèn)題的能力。本文檔記錄了我的刷題筆記，旨在總結(jié)和分享刷題的經(jīng)驗(yàn)和技巧。目錄數(shù)據(jù)結(jié)構(gòu)數(shù)組鏈表?xiàng)：完?duì)列算法遞歸與回溯動(dòng)態(tài)規(guī)劃貪心算法數(shù)據(jù)結(jié)構(gòu)數(shù)組數(shù)組是一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，可以存儲(chǔ)相同類(lèi)型的元素。常見(jiàn)的數(shù)組操作包括增刪改查等。一維數(shù)組一維數(shù)組是最基本的數(shù)組形式，可以使用下標(biāo)訪(fǎng)問(wèn)元素。#初始化一個(gè)一維數(shù)組

arr=[1,2,3,4,5]

#訪(fǎng)問(wèn)數(shù)組元素

print(arr[0])#輸出：1

print(arr[2])#輸出：3

#修改數(shù)組元素

arr[1]=10

print(arr)#輸出：[1,10,3,4,5]

#數(shù)組長(zhǎng)度

print(len(arr))#輸出：5二維數(shù)組二維數(shù)組是一種元素為一維數(shù)組的數(shù)組，可以理解為表格或矩陣。#初始化一個(gè)二維數(shù)組

matrix=[[1,2,3],

[4,5,6],

[7,8,9]]

#訪(fǎng)問(wèn)二維數(shù)組元素

print(matrix[0][0])#輸出：1

print(matrix[1][2])#輸出：6

#修改二維數(shù)組元素

matrix[1][1]=10

print(matrix)#輸出：[[1,2,3],[4,10,6],[7,8,9]]

#二維數(shù)組行數(shù)和列數(shù)

print(len(matrix))#輸出：3

print(len(matrix[0]))#輸出：3鏈表鏈表是一種非連續(xù)的數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)組成，通過(guò)指針將節(jié)點(diǎn)串聯(lián)起來(lái)。單鏈表單鏈表是一種常見(jiàn)的鏈表形式，每個(gè)節(jié)點(diǎn)包含一個(gè)值和指向下一個(gè)節(jié)點(diǎn)的指針。#定義單鏈表的節(jié)點(diǎn)類(lèi)

classListNode:

def__init__(self,val=0):

self.val=val

self.next=None

#創(chuàng)建單鏈表

head=ListNode(1)

node1=ListNode(2)

node2=ListNode(3)

head.next=node1

node1.next=node2

#遍歷單鏈表

cur=head

whilecur:

print(cur.val)

cur=cur.next

#插入新節(jié)點(diǎn)

new_node=ListNode(4)

new_node.next=head

head=new_node

#刪除節(jié)點(diǎn)

head=head.next雙鏈表雙鏈表在單鏈表的基礎(chǔ)上，每個(gè)節(jié)點(diǎn)多了一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針。#定義雙鏈表的節(jié)點(diǎn)類(lèi)

classListNode:

def__init__(self,val=0):

self.val=val

self.prev=None

self.next=None

#創(chuàng)建雙鏈表

head=ListNode(1)

node1=ListNode(2)

node2=ListNode(3)

head.next=node1

node1.prev=head

node1.next=node2

node2.prev=node1

#遍歷雙鏈表（正向）

cur=head

whilecur:

print(cur.val)

cur=cur.next

#遍歷雙鏈表（反向）

cur=node2

whilecur:

print(cur.val)

cur=cur.prev

#插入新節(jié)點(diǎn)

new_node=ListNode(4)

new_node.next=head

head.prev=new_node

head=new_node

#刪除節(jié)點(diǎn)

head=head.next

head.prev=None棧和隊(duì)列棧和隊(duì)列是兩種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。棧棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，可以使用列表來(lái)模擬棧的行為。#創(chuàng)建一個(gè)棧

stack=[]

#入棧

stack.append(1)

stack.append(2)

stack.append(3)

#出棧

top=stack.pop()

print(top)#輸出：3

#棧是否為空

print(len(stack)==0)#輸出：False隊(duì)列隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，可以使用collections模塊中的deque來(lái)實(shí)現(xiàn)隊(duì)列。fromcollectionsimportdeque

#創(chuàng)建一個(gè)隊(duì)列

queue=deque()

#入隊(duì)

queue.append(1)

queue.append(2)

queue.append(3)

#出隊(duì)

front=queue.popleft()

print(front)#輸出：1

#隊(duì)列是否為空

print(len(queue)==0)#輸出：False算法遞歸與回溯遞歸是一種通過(guò)函數(shù)體內(nèi)調(diào)用自身的方式來(lái)解決問(wèn)題的方法。回溯是一種通過(guò)不斷嘗試可能的解決方案來(lái)找到問(wèn)題解決方法的方法。遞歸遞歸算法通常有一個(gè)遞歸終止條件，通過(guò)不斷迭代地調(diào)用自身來(lái)逐步解決問(wèn)題。#階乘

deffactorial(n):

ifn==0orn==1:

return1

else:

returnn*factorial(n-1)

#斐波那契數(shù)列

deffibonacci(n):

ifn==0orn==1:

returnn

else:

returnfibonacci(n-1)+fibonacci(n-2)回溯回溯算法通常用于在一組可能的解決方案中搜索正確的解。#八皇后問(wèn)題

defsolve_n_queens(n):

defbacktrack(row):

ifrow==n:

results.append(board[:])

else:

forcolinrange(n):

ifis_queen_valid(row,col):

board[row][col]='Q'

backtrack(row+1)

board[row][col]='.'

defis_queen_valid(row,col):

foriinrange(row):

ifboard[i][col]=='Q':

returnFalse

fori,jinzip(range(row-1,-1,-1),range(col+1,n)):

ifboard[i][j]=='Q':

returnFalse

fori,jinzip(range(row-1,-1,-1),range(col-1,-1,-1)):

ifboard[i][j]=='Q':

returnFalse

returnTrue

board=[['.'for_inrange(n)]for_inrange(n)]

results=[]

backtrack(0)

returnresults動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃是一種通過(guò)將問(wèn)題分解為子問(wèn)題并保存子問(wèn)題的解來(lái)解決問(wèn)題的方法。#斐波那契數(shù)列

deffibonacci(n):

ifn==0orn==1:

returnn

dp=[0]*(n+1)

dp[0]=0

dp[1]=1

foriinrange(2,n+1):

dp[i]=dp[i-1]+dp[i-2]

returndp[n]貪心算法貪心算法是一種通過(guò)每次選擇當(dāng)前局部最優(yōu)解來(lái)獲取全局最優(yōu)解的方法。#跳躍游戲

defcan_jump(nums):

last_pos=len(nums)-1

foriin