İki və ya daha çox uzunluğun təkrarlanan nəticəsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic
SimBaxılıb 421

Problem bəyanat

“İki və ya daha çox uzunluğun təkrar ardıcıllığı” problemində “s” simli verdik. İki 0r daha çox uzunluqda hər hansı bir ardıcıllığın olub olmadığını tapın. Alt ardıcıllıqlar eyni vəziyyətdə eyni xarakterə sahib olmamalıdır.

Giriş Formatı

"S" simli olan ilk və yalnız bir sətir.

Çıxış formatı

Eyni mövqedə eyni xarakter daşımamalı olan iki və ya daha çox uzunluqda təkrarlanan bir ardıcıllıq varsa, "Bəli" yazdırın. Əks təqdirdə “Xeyr” yazdırın.

Məhdudiyyətlər

  • 1 <= | s | <= 10 ^ 6
  • s [i] kiçik İngilis əlifbası olmalıdır

misal

abdabc
Yes

Explanation: Burada “ab” verilən sətirdə mövcud olan təkrarlanan ardıcıllıqdır.

ppq
No

Explanation: Burada “pq” təkrarlanan ardıcıllıqdır, lakin q hər iki alt ardıcıllıqla eyni mövqedədir.

İki və ya daha çox uzunluğun təkrarlanan ardıcıllığının alqoritmi

Bu problem klassik dəyişiklikdir ən uzun ümumi ardıcıllıq problem. Dinamik proqramlaşdırma həlli O (n.) Alır2) zaman və məkan. Bu yazıda O (n) zaman və məkan yanaşması müzakirə olunur.

  1. Bütün təkrarlanmayan simvolları simdən silirik.
  2. Simvolların tezliklərini saxlamaq üçün bir sıra yaradın.
  3. Giriş sətrini keçin və bütün simvolların tezliklərini sayma massivində saxlayın.
  4. Bir simvolun sayı 3-dən çoxdursa, doğru qayıdın. (palindrom olan, lakin alt ardıcıllıq mövcud olan “ppp” kimi şərtləri nəzərə alaraq.)
  5. Yerdəki bütün təkrarlanmayan simvolları sətirdən çıxarırıq.
  6. Nəticə sətrinin palindrom olub olmadığını yoxlayın.
  7. Palindrom çap edərsə "Yox". Uzunluq tək olduğu halda, orta simvol əvvəlki ilə eyni olduqda doğru qayıdır. ("Ppp" şərt)
  8. çap "Bəli", simli palindrom deyilsə.

Həyata keçirilməsi

İki və ya daha çox uzunluğun təkrarlanan nəticəsi üçün C ++ proqramı

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

bool isPalindrome(string s, int l, int h) 
{ 
  while (h > l) 
    if (s[l++] != s[h--]) 
      return false; 
  return true; 
} 

int check(string s) 
{  
  int n = s.length(); 
  int freq[256];
  memset(freq,0,sizeof(freq));
  for (int i = 0; i < n; i++) 
  { 
    freq[s[i]]++; 
    if (freq[s[i]] > 2) 
      return true; 
  } 
  int k = 0; 
  for (int i = 0; i < n; i++) 
    if (freq[s[i]] > 1) 
      s[k++] = s[i]; 
  s[k] = '\0'; 
  if(isPalindrome(s, 0, k-1)) 
  { 
    if(k & 1) 
      return s[k/2] == s[k/2 - 1]; 
    return false; 
  } 
  return true; 
} 

int main() 
{ 
  string s;
  cin>>s;
  if(check(s)) 
    cout<<"Yes"<<endl; 
  else
    cout<<"No"<<endl; 
  return 0; 
} 

İki və ya daha çox uzunluğun təkrarlanan sonrakı nəticəsi üçün Java proqramı

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static int isPalindrome(String s, int l, int h)  
    { 
        while(h > l) 
            if(s.charAt(l++) != s.charAt(h--)) 
                return 0; 
        return 1; 
    }
    
    public static int  check(String s)
    {
        int n = s.length(); 
  int freq[] = new int[256];
        for(int i=0;i<256;i++)
  {
      freq[i]=0;
  }
  for (int i = 0; i < n; i++) 
  { 
    freq[s.charAt(i)]++; 
    if(freq[s.charAt(i)]>2) 
      return 1; 
  } 
  int k = 0;  
        for(int i = 0; i < n; i++)  
            if(freq[s.charAt(i)] > 1)  
                s.replace(s.charAt(k++),  
                            s.charAt(i));  
        s.replace(s.charAt(k), '\0'); 
        if(isPalindrome(s, 0, k - 1)==1)  
        {  
            if ((k & 1) == 1)  
            { 
                if (k / 2 >= 1) 
                    return (s.charAt(k / 2) == s.charAt(k / 2 - 1))? 1: 0; 
            } 
            return 0;  
        }  
        return 1;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
  if(check(s)!=1)
  {
      System.out.println("No");
  }
  else
  {
      System.out.println("Yes");
  }
    }
}
dwjebkufbfbfewdbfeb
Yes

İki və ya daha çox uzunluğun təkrarlanan nəticəsi üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n verilən sətrin ölçüsüdür "S". Burada bəzi əməliyyatları yalnız xətti vaxtda həyata keçiririk.

Kosmik Mürəkkəblik

O (1) çünki yalnız hər charın frekasını saxlamaq üçün istifadə etdiyimiz 256 ölçülü bir sıra elan edirik.

Translate »