Bir sıra Palindrome etmək üçün Birləşdirmə Əməliyyatlar minimum sayı

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon
Geyim RiyaziyyatBaxılıb 435

Problem bəyanat

“Array Palindrom etmək üçün Birləşdirmə Əməliyyatlar Minimum” problemində bir cavab verdik array “A []”. Bir sıra palindromu etmək üçün lazım olan minimum birləşmə_operasiya sayını tapın. Diqqət, palindrom, irəli kimi geriyə oxuyan bir söz, söz və ya ardıcıllıqdır.

Giriş Formatı

Bir n tam ədədi olan ilk sətir.

Boşluqla ayrılmış n tam ədədi olan ikinci sətir (”“).

Çıxış formatı

Bir sıra palindromu yaratmaq üçün minimum birləşmə_operasiya sayını ifadə edən bir tam ədədi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 5
  • 1 <= a [i] <= 10 ^ 6

misal

5
23 45 65 45 23
0

Explanation: Verilən massiv onsuz da palindromdur, buna görə aparılan əməliyyatların sayı 0-dır.

4
1 7 9 1
1

Explanation: Birləşdirmə əməliyyatlarının sayı 1. 7-i çıxarmaq, 9-u palindrom düzəldir.

5
1 3 8 6 1
2

Burada palindrom etmək üçün birləşdirmə əməliyyatlarının minimum sayı 2-dir.

Alqoritm

1. I, j dəyişənləri yaradın. massivin başlanğıcını və j sonuna işarə edəcəyəm.
J-dən az və ya bərabər olana qədər

  • Arr [i] = arr [j] olarsa, elementləri birləşdirməyə ehtiyac yoxdur. Artım i və azalma j
  • Arr [i]> arr [j] olarsa, j indeksində birləşmə əməliyyatı edin, yəni arr [j-1] = arr [j-1] + arr [j], j azaldın və birləşmə əməliyyatlarının sayını hesablayın 1
  • Arr [i] <arr [j] varsa, i indeksində birləşmə əməliyyatı edin, yəni arr [i + 1] = arr [i + 1] + arr [i], i artırın və birləşmə əməliyyatlarının sayını sayın 1.

Həyata keçirilməsi

Bir sıra palindromu yaratmaq üçün minimum birləşdirmə əməliyyatları üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int ans = 0;
  for (int i=0,j=n-1; i<=j;)
  {
    if(a[i]==a[j])
    {
      i++;
      j--;
    }
    else if(a[i]>a[j])
    {
      j--;
      a[j]+=a[j+1] ;
      ans++;
    }
    else
    {
      i++;
      a[i]+=a[i-1];
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Bir Array Palindrome etmək üçün Birləşdirmə Əməliyyatları Minimum sayda Java Proqramı

import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        int ans = 0;
  for (int i=0,j=n-1; i<=j;)
  {
    if(a[i]==a[j])
    {
      i++;
      j--;
    }
    else if(a[i]>a[j])
    {
      j--;
      a[j]+=a[j+1] ;
      ans++;
    }
    else
    {
      i++;
      a[i]+.
=a[i-1];
      ans++;
    }
  }
  System.out.println(ans);
    }
}
7
1 2 3 5 3 2 4
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada serialı bir dəfə ziyarət edirik və istədiyiniz cavabı tapırıq.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yer elan etmirik.

Translate »