数据结构
网络
关系数据库管理系统 (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 次查看
广告