資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在 Python 中查詢排序雙向連結串列中乘積為給定值的數對
假設我們有一個排序的、包含唯一正數的雙向連結串列；我們需要找到連結串列中乘積等於給定值 x 的數對。需要注意的是，這需要在不佔用額外空間的情況下解決。
因此，如果輸入類似 L = 1 ⇔ 2 ⇔ 4 ⇔ 5 ⇔ 6 ⇔ 8 ⇔ 9 並且 x = 8，則輸出將為 (1, 8), (2, 4)
為了解決這個問題，我們將遵循以下步驟：
curr := 頭節點, nxt := 頭節點
當 nxt.next 不為空時，執行迴圈
nxt := nxt.next
found := False
當 curr 和 nxt 不為空，且 curr 和 nxt 不同，並且 nxt.next 不等於 curr 時，執行迴圈
如果 (curr.data * nxt.data) 等於 x，則
found := True
顯示數對 curr.data, nxt.data
curr := curr.next
nxt := nxt.prev
否則，
如果 (curr.data * nxt.data) < x，則
curr := curr.next
否則，
nxt := nxt.prev
如果 found 為 False，則
顯示 "未找到"
示例
讓我們來看下面的實現以更好地理解：
class ListNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insert(head, data):
node = ListNode(0)
node.data = data
node.next = node.prev = None
if (head == None):
(head) = node
else :
node.next = head
head.prev = node
head = node
return head
def get_pair_prod(head, x):
curr = head
nxt = head
while (nxt.next != None):
nxt = nxt.next
found = False
while (curr != None and nxt != None and curr != nxt and nxt.next != curr) :
if ((curr.data * nxt.data) == x) :
found = True
print("(", curr.data, ", ", nxt.data, ")")
curr = curr.next
nxt = nxt.prev
else :
if ((curr.data * nxt.data) < x):
curr = curr.next
else:
nxt = nxt.prev
if (found == False):
print( "Not found")
head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
get_pair_prod(head, x)輸入
head = None head = insert(head, 9) head = insert(head, 8) head = insert(head, 6) head = insert(head, 5) head = insert(head, 4) head = insert(head, 2) head = insert(head, 1) x = 8
輸出
( 1 , 8 ) ( 2 , 4 )
更新於：2020年8月25日
120 次檢視
廣告