Gantikan setiap nod dalam senarai terpaut dengan kiraan melebihinya menggunakan C++

Memandangkan senarai terpaut, kita perlu mencari elemen yang lebih besar daripada sebelah kanan elemen semasa dalam senarai terpaut yang diberikan. Kiraan elemen ini perlu digantikan dengan nilai nod semasa.

Mari kita ambil senarai terpaut yang mengandungi aksara berikut dan gantikan setiap nod dengan kiraan yang melebihinya -

4 -> 6 -> 1 -> 4 -> 6 -> 8 -> 5 -> 8 -> 3

Mula ke belakang dan lewati senarai terpaut (jadi kita tidak perlu risau tentang elemen semasa ke kiri). Struktur data kami menjejaki elemen semasa dalam susunan yang disusun. Menggantikan elemen semasa dalam struktur data yang diisih dengan jumlah bilangan elemen di atasnya.

Melalui kaedah rekursif, senarai pautan akan dilalui ke belakang. Pilihan lain ialah PBDS. Menggunakan PBDS membolehkan kami mencari elemen yang kurang daripada kunci tertentu. Kita boleh menambah elemen semasa dan menolaknya daripada elemen yang lebih kecil.

PBDS tidak membenarkan elemen pendua. Walau bagaimanapun, kita memerlukan elemen berulang untuk mengira. Untuk menjadikan setiap entri unik, kami akan memasukkan pasangan (pertama = elemen, kedua = indeks) ke dalam PBDS. Untuk mencari jumlah elemen sama dengan elemen semasa, kami akan menggunakan peta cincang. Peta cincang menyimpan bilangan kejadian setiap elemen (pemetaan integer-ke-integer asas).

Contoh

Berikut ialah program C++ untuk menggantikan setiap nod dalam senarai terpaut dengan nombor transendentalnya -

#include <iostream>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define oset tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

class Node {
   public:
   int value;
   Node * next;
   Node (int value) {
      this->value = value;
      next = NULL;
   }
};
void solve (Node * head, oset & os, unordered_map < int, int >&mp, int &count){
   if (head == NULL)
   return;
   solve (head->next, os, mp, count);
   count++;
   os.insert (
   {
      head->value, count}
   );
   mp[head->value]++;
   int numberOfElements = count - mp[head->value] - os.order_of_key ({ head->value, -1 });
   head->value = numberOfElements;
}
void printList (Node * head) {
   while (head) {
      cout << head->value << (head->next ? "->" : "");
      head = head->next;
   }
   cout << "\n";
}
int main () {
   Node * head = new Node (43);
   head->next = new Node (65);
   head->next->next = new Node (12);
   head->next->next->next = new Node (46);
   head->next->next->next->next = new Node (68);
   head->next->next->next->next->next = new Node (85);
   head->next->next->next->next->next->next = new Node (59);
   head->next->next->next->next->next->next->next = new Node (85);
   head->next->next->next->next->next->next->next->next = new Node (37);
   oset os;
   unordered_map < int, int >mp;
   int count = 0;
   printList (head);
   solve (head, os, mp, count);
   printList (head);
   return 0;
}

Output

43->65->12->46->68->85->59->85->30
6->3->6->4->2->0->1->0->0

Arahan

Jadi, untuk elemen pertama, elemen = [65, 46, 68, 85, 59, 85], iaitu 6

Elemen kedua, elemen = [68, 85, 85] iaitu 3

Semua elemen dan sebagainya

Kesimpulan

Soalan ini memerlukan pemahaman tertentu tentang struktur data dan rekursi. Kita perlu menyusun kaedah dan kemudian, berdasarkan pemerhatian dan pengetahuan, memperoleh struktur data yang memenuhi keperluan kita. Jika anda menyukai artikel ini, baca lebih lanjut dan nantikan.

Atas ialah kandungan terperinci Gantikan setiap nod dalam senarai terpaut dengan kiraan melebihinya menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!