정수 값을 포함하는 정렬된 이중 연결 목록이 제공됩니다. 목표는 곱이 주어진 값 x와 같은 트리플렛을 찾는 것입니다. 입력 연결 목록이 3−4−1−2이고 x가 6이면 개수는 1이 됩니다(triplet (3,1,2) )
예를 들어
입력
linked list: [ 3−4−13−5−10−10−0 ] x=20
출력
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 2
설명
Triplets will be: ( 3,4,13 ) and ( 10,10,0 )
입력
linked list: [ 4−3−1−5−2−4−2 ] x=8
출력
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 6
설명
Triplets will be: ( 4,3,1), (1,5,2), (3,1,4), (1,5,2), (4,2,2) and (2,4,2),
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
이 접근 방식에서.
-
우리는 연결 리스트 노드를 int 데이터 부분과 자기 참조 다음 및 이전 포인터를 포함하는 구조체로 사용합니다.
-
insert_node(struct block** head, int data) 함수는 데이터가 있는 연결 리스트의 선두에 노드를 추가합니다.
-
함수 Product_x(struct block* head, int x)는 이중 연결 리스트와 정수 x의 헤드에 대한 포인터를 가져와서 데이터 부분의 곱을 x로 갖는 노드의 트리플렛 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
구조체 블록 유형의 세 포인터 temp_1, temp_2 및 temp_3을 가져옵니다.
-
연결 목록의 헤드를 가리키는 temp_1, temp_1 옆을 가리키는 temp_2, temp_3 다음을 가리키는 temp_3부터 시작하여 처음 세 노드를 가리키는 세 개의 포인터가 있습니다.
-
이 포인터를 사용하여 마지막 노드까지 트래버스합니다.
-
위의 모든 포인터의 현재 데이터 부분의 곱이 x인 경우. ((temp_1−>data + temp_2−>data + temp_3−>data) ==x) 그런 다음 카운트를 증가시킵니다.
-
결국 우리는 세 쌍의 수를 세고 count에 저장했습니다.
-
결과로 카운트를 반환합니다.
예시
#include <iostream>
using namespace std;
struct block{
int data;
struct block *next, *prev;
};
void insert_node(struct block** head, int data){
struct block* ptr = new block();
ptr−>data = data;
ptr−>next = NULL;
ptr−>prev = NULL;
if ((*head) == NULL){
(*head) = ptr;
} else {
ptr−>next = *head;
(*head)−>prev = ptr;
(*head) = ptr;
}
}
int sum_x(struct block* head, int x){
int count = 0;
struct block *temp_1, *temp_2, *temp_3;
for (temp_1 = head; temp_1!= NULL; temp_1 = temp_1−>next){
for (temp_2 = temp_1−>next; temp_2 != NULL; temp_2 = temp_2−>next){
for (temp_3 = temp_2−>next; temp_3!= NULL; temp_3 = temp_3−>next){
if ((temp_1−>data + temp_2−>data + temp_3−>data) == x){
count++;
}
}
}
}
return count;
}
int main(){
struct block* head = NULL;
insert_node(&head, 200);
insert_node(&head, 100);
insert_node(&head, 16);
insert_node(&head, 14);
insert_node(&head, 10);
insert_node(&head, 10);
insert_node(&head, 2);
int x = 22;
cout<<"Count of triplets in a sorted doubly linked list whose sum is equal to a given value x
are: "<<sum_x(head, x);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 1