資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中雙向連結串列中查詢具有給定和的配對
在這個問題中，我們給定一個雙向連結串列和一個值 sum。我們的任務是在雙向連結串列中找到具有給定和的配對。
讓我們舉個例子來理解這個問題，
輸入
head − 2 <-> 5 <-> 6 <-> 9 <-> 12 x = 11
輸出
(2, 9), (5, 6)
解釋
For pairs (2, 9), the sum of values is 11 For pairs (5, 6), the sum of values is 11
解決方案方法
解決這個問題的一個簡單方法是遍歷整個連結串列，並逐個獲取元素，並在剩餘的連結串列中查詢其和為 sum 的元素。這是透過使用巢狀迴圈來完成的。
程式說明我們解決方案的工作原理，
示例
#include<iostream>
using namespace std;
struct Node {
int data;
struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
struct Node *first = head;
int pairCount = 0;
while (first != NULL) {
struct Node *second = first -> next;
while(second != NULL){
if ((first->data + second->data) == sum) {
pairCount++;
cout<<"("<<first->data<<",
"<<second->data<<")\n";
}
second = second -> next;
}
first = first -> next;
}
if (!pairCount)
cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
struct Node *temp = new Node;
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else{
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
int main() {
struct Node *head = NULL;
insert(&head, 12);
insert(&head, 9);
insert(&head, 6);
insert(&head, 5);
insert(&head, 2);
int sum = 11;
cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
findSumPairs(head, sum);
return 0;
}輸出
Pair in the linked list with sum = 11 : (2, 9) (5, 6)
另一種更有效的方法是利用連結串列已排序的事實。為此，我們將使用兩個指標，一個 start 指標最初指向連結串列的頭部。另一個 end 指標最初指向連結串列的最後一個節點。
現在，我們將它們加起來以找到 sumVal，然後將其與
given sum. If sumVal > sum, move end pointer leftwards. If sumVal < sum, move start pointer rightwards. If sumVal == sum, print both values, move start pointer rightwards.
當指標彼此交叉時，退出迴圈。此外，我們將計算找到的配對數量，如果它等於 0，則列印“未找到此類配對！”
程式說明我們解決方案的工作原理，
示例
#include<iostream>
using namespace std;
struct Node {
int data;
struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
struct Node *start = head;
struct Node *end = head;
while (end->next != NULL)
end = end->next;
int pairCount = 0;
while (start != NULL && end != NULL && start != end &&
end->next != start) {
if ((start->data + end->data) == sum) {
pairCount++;
cout<<"("<<start->data<<", "<<end->data<<")\n";
start = start->next;
end = end->prev;
}
else if ((start->data + end->data) < sum)
start = start->next;
else
end = end->prev;
}
if (!pairCount)
cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
struct Node *temp = new Node;
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else{
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
int main() {
struct Node *head = NULL;
insert(&head, 12);
insert(&head, 9);
insert(&head, 6);
insert(&head, 5);
insert(&head, 2);
int sum = 11;
cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
findSumPairs(head, sum);
return 0;
}輸出
Pair in the linked list with sum = 11 : (2, 9) (5, 6)
更新於: 2021年3月16日
219 次檢視
廣告