資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在已排序的單鏈表中查詢和為給定值的一對數 (C++)
假設我們有一個單鏈表和一個值 x；我們需要找到一對節點，其值的和等於 x。需要注意的是，我們不能使用額外的空間，並且期望的時間複雜度為 O(n)。
例如，如果輸入是 4→7→8→9→10→11→12，x = 19，則輸出將是 [(7, 12), (8, 11), (9, 10)]
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 `convert_to_xor()`，它將接收起始節點作為引數。
`prev := NULL`
當 `start` 不為 NULL 時，執行以下操作：
`next_list_node := start 的下一個節點`
`start 的下一個節點 := next_list_node 的地址與 prev 地址的異或`
`prev := start`
`start := next_list_node`
在主方法中，執行以下操作：
`first := start`
`next_list_node := NULL, prev := NULL, second := start`
當 `second` 的下一個節點不等於 `prev` 時，執行以下操作：
`temp := second`
`second := (second 的下一個節點的地址) 與 (prev 地址) 的異或`
`prev := temp`
`next_list_node := NULL`
`prev := NULL`
`flag := false`
當 (first 不等於 NULL 且 second 不等於 NULL 且 first 不等於 second 且 first 不等於 next_list_node) 時，執行以下操作：
如果 first 的資料 + second 的資料等於 x，則：
顯示 first 的資料和 second 的資料
`flag := true`
`temp := first`
`first := (first 的下一個節點的地址) 與 (prev 地址) 的異或`
`prev := temp`
`temp := second`
`second := (second 的下一個節點的地址) 與 (next_list_node 地址) 的異或`
`next_list_node := temp`
否則
如果 first 的資料 + second 的資料 < x，則
`temp := first`
`first := (first 的下一個節點的地址) 與 (prev 地址) 的異或`
`prev := temp`
否則
`temp := second`
`second := (second 的下一個節點的地址) 與 (next_list_node 地址) 的異或`
`next_list_node := temp`
如果 flag 為 false，則：
沒有找到這樣的數對
示例 (C++)
讓我們來看下面的實現，以便更好地理解：
#include<bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode *next;
ListNode(int data) {
this->data = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v) {
ListNode *start = new ListNode(v[0]);
for (int i = 1; i < v.size(); i++) {
ListNode *ptr = start;
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return start;
}
ListNode* XOR (ListNode *a, ListNode *b) {
return (ListNode*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
void convert_to_xor(ListNode *start) {
ListNode *next_list_node;
ListNode *prev = NULL;
while (start != NULL) {
next_list_node = start->next;
start->next = XOR(next_list_node, prev);
prev = start;
start = next_list_node;
}
}
void get_pared_sum(ListNode *start, int x) {
ListNode *first = start;
ListNode *next_list_node = NULL, *prev = NULL;
ListNode *second = start;
while (second->next != prev) {
ListNode *temp = second;
second = XOR(second->next, prev);
prev = temp;
}
next_list_node = NULL;
prev = NULL;
bool flag = false;
while (first != NULL && second != NULL && first != second && first != next_list_node) {
if ((first->data + second->data)==x) {
cout << "(" << first->data << ","<< second->data << ")" << endl;
flag = true;
ListNode *temp = first;
first = XOR(first->next,prev);
prev = temp;
temp = second;
second = XOR(second->next, next_list_node);
next_list_node = temp;
}
else{
if ((first->data + second->data) < x) {
ListNode *temp = first;
first = XOR(first->next,prev);
prev = temp;
}
else{
ListNode *temp = second;
second = XOR(second->next, next_list_node);
next_list_node = temp;
}
}
}
if (flag == false)
cout << "No pair found" << endl;
}
int main() {
vector<int> v = {4,7,8,9,10,11,12};
ListNode* start = make_list(v);
int x = 19;
convert_to_xor(start);
get_pared_sum(start,x);
}輸入
{4,7,8,9,10,11,12}輸出
(7,12) (8,11) (9,10)
110 次瀏覽
