楊婭娟刷題筆記

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

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

#訪問數(shù)組元素

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

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

#修改數(shù)組元素

arr[1]=10

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

#數(shù)組長度

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

matrix=[[1,2,3],

[4,5,6],

[7,8,9]]

#訪問二維數(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é)點組成，通過指針將節(jié)點串聯(lián)起來。單鏈表單鏈表是一種常見的鏈表形式，每個節(jié)點包含一個值和指向下一個節(jié)點的指針。#定義單鏈表的節(jié)點類

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é)點

new_node=ListNode(4)

new_node.next=head

head=new_node

#刪除節(jié)點

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

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é)點

new_node=ListNode(4)

new_node.next=head

head.prev=new_node

head=new_node

#刪除節(jié)點

head=head.next

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

stack=[]

#入棧

stack.append(1)

stack.append(2)

stack.append(3)

#出棧

top=stack.pop()

print(top)#輸出：3

#棧是否為空

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

#創(chuàng)建一個隊列

queue=deque()

#入隊

queue.append(1)

queue.append(2)

queue.append(3)

#出隊

front=queue.popleft()

print(front)#輸出：1

#隊列是否為空

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

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)回溯回溯算法通常用于在一組可能的解決方案中搜索正確的解。#八皇后問題

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動態(tài)規(guī)劃動態(tài)規(guī)劃是一種通過將問題分解為子問題并保存子問題的解來解決問題的方法。#斐波那契數(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]貪心算法貪心算法是一種通過每次選擇當(dāng)前局部最優(yōu)解來獲取全局最優(yōu)解的方法。#跳躍游戲

defcan_jump(nums):

last_pos=len(nums)-1

foriin