ค้นหาจำนวนการดำเนินการรวมขั้นต่ำเพื่อสร้างอาร์เรย์ palindrome ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วยตัวเลขบวก n ตัว ภารกิจของเราคือค้นหาจำนวนการดำเนินการรวมขั้นต่ำเพื่อสร้างอาร์เรย์พาลินโดรม

อาร์เรย์พาลินโดรม คล้ายกับสตริง palindrome องค์ประกอบที่ดัชนี i และ n-i ควรเหมือนกัน

ตัวอย่าง

{5, 1, 7, 2, 7, 1, 5}

คำอธิบายปัญหา − เราจำเป็นต้องสร้างอาร์เรย์พาลินโดรมโดยดำเนินการกับมัน และการดำเนินการเดียวที่ถูกต้องในอาร์เรย์คือการดำเนินการผสาน ซึ่งเราจะเพิ่มองค์ประกอบที่ดัชนี i และ i+1

เราจำเป็นต้องส่งคืนจำนวนขั้นต่ำของการดำเนินการดังกล่าวที่จำเป็นในการสร้างอาร์เรย์ palindrome ที่กำหนด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

arr[] = {4, 1, 7, 6, 1, 5}

ผลลัพธ์

2

คำอธิบาย

เราต้องการการดำเนินการควบรวมสองครั้ง

การรวมองค์ประกอบที่ดัชนี 0 และ 1 ทำให้อาร์เรย์ {5, 7, 6, 1, 5}.

หลังจากรวมองค์ประกอบที่ดัชนี 2 และ 3 แล้ว จะทำให้อาร์เรย์ {5, 7, 7, 5}

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการค้นหาจำนวนการดำเนินการเพื่อสร้างสตริงพาลินโดรม ทำได้โดยใช้ตัวชี้สองตัวเริ่มต้นและสิ้นสุด หากทั้งสองจุดตรงเช่น start ==สิ้นสุดอาร์เรย์จะเป็น palindrome ดังนั้น เราจะวนรอบสำหรับจุดเริ่มต้นและจุดสิ้นสุด และดำเนินการตามเงื่อนไขเหล่านี้ -

• ถ้า arr[start] ==​​arr[end] หมายถึงดัชนีปัจจุบัน อาร์เรย์จะเป็นไปตามเงื่อนไขของ palindrome For จะย้ายไปยังดัชนีถัดไป เช่น. start++ และ end--.

• ถ้า arr[start]> arr[end] ในกรณีนี้ เราจำเป็นต้องดำเนินการผสานสำหรับดัชนีสิ้นสุด และเพิ่ม mergeCount ขึ้น 1

• ถ้า arr[start]

เราจะคืนจำนวนการรวมเมื่อเริ่มต้น ==สิ้นสุด

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;
int findMergeCount(int arr[], int n){
   int mergeCount = 0;
   int start = 0;
   int end = n-1;
   while(start <= end){
      if (arr[start] == arr[end]){
         start++;
         end--;
      }
      else if (arr[start] > arr[end]){
         end--;
         arr[end] += arr[end+1] ;
         mergeCount++;
      } else {
         start++;
         arr[start] += arr[start-1];
         mergeCount++;
      }
   }
   return mergeCount;
}
int main(){
   int arr[] = {4, 1, 7, 6, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The minimum number of merge operations required to make the array palindrome is "<<findMergeCount(arr, n);
   return 0;
}

ผลลัพธ์

The minimum number of merge operations required to make the array palindrome is 2