Ар бир персонажды алмаштырган Суроодон кийин Палиндромдун бар экендигин текшериңиз


Кыйынчылык деңгээли катуу
Көп суралган Amazon Facebook Flipkart Гугл Netflix
таштанды аркан

"Ар бир персоналды алмаштырган суроодон кийин Палиндромдун бар экендигин текшериңиз" деген көйгөй сизге a берилген деп айтат аркан жана жок. Суроолордун ар биринде экиден болот бүтүн катары киргизүү мааниси i1 жана i2 жана "ch" деп аталган бир белги киргизүү. Маселенин коюлушу i1 жана i2 индекстериндеги маанилерди берилген 'ch' белгиси менен өзгөртүүнү жана анын палиндром экендигин же жок экендигин аныктоону суранат.

Эскертүү: 0 <i1ден кичине же ага барабар, ал эми i2 - саптын узундугуна аз же барабар.

мисал

Ар бир персонажды алмаштырган Суроодон кийин Палиндромдун бар экендигин текшериңиз

String: india, Query=2.
Query 1: i1 = 0, i2 = 4, ch = i
Query 2: i1 = 1, i2 = 3, ch = n
Query 1: No
Query 2: Yes

түшүндүрүү

1-суроо: Индия инди ордуна келгенден кийин болот

Суроо 2: indi алмаштырылгандан кийин индий болуп калат

String: english, Query=3.
Query 1: i1 = 0, i2 = 6, ch = e
Query 2: i1 = 1, i2 = 5, ch = s
Query 3: i1 = 2, i2 = 4, ch = i
Query 1: No
Query 2: No
Query 3: Yes

түшүндүрүү

1-суроо: англисче алмаштырылгандан кийин англисче болуп калат

2-суроо: englise алмаштырылгандан кийин esglise болуп калат

3-суроо: esglise алмаштырылгандан кийин пайда болот

Algorithm

  1. Декларация a коюлган.
  2. Биринчи жарым жылдагы бардык тең эмес индекстерди Сактагычта сактаңыз.
  3. Өзгөртүү белги берилген индекстеги берилген белгилердин мааниси менен (i1 жана i2).
    1. I1> n / 2 болсо, анда i1 = n-1-i1 жана i2> n / 2 кылыңыз, эгер чын болсо, анда тиешелүүлүгүнө жараша i2 = n-1-i2 кылыңыз.
    2. Эми str [i1] == str [n-1-i1] алмаштырылгандан кийин, эгер анын чын экендиги аныкталса, анда i1 Топтомдо бар же жок экендигин текшерип, эгер бар болсо, аны алып салат.
      1. Башка нерсе Setке i1 кошот.
    3. Бул процессти i2 үчүн дагы кайталаңыз.
  4. 3-кадамдан баштап берилген суроолордун жалпы санына чейин кайталаңыз.
  5. Эгер бош болсо, анда палиндром жок болсо, ал жок болот.

түшүндүрүү

Бизде бир сап жана бир нече Суроолор берилген, анда андагы бүтүн жана символдордун мааниси камтылган, биз белгилерди берилген символ менен жана айрым индекстер боюнча i1 жана i2 деп берилген, андан кийин биз керек болгондон кийин өзгөртүшүбүз керек. ар бир аткарылган суроодон кийин түзүлгөн сап палиндром экендигин же жок экендигин аныктоо. Идеяны колдонуу болуп саналат Хеширлөө. Бул көйгөйдү чечүү үчүн Setти колдонобуз. Биз өзүнчө функцияны жасайбыз, бир функциясы - суроо алуу, дагы бир функциясы - палиндромду текшерүү. Негизинен, ал функция бир аз мода менен иштейт. Ар бир чалуудан улам биз ошол функцияны аткарабыз. Ал Set иш-аракеттерин аткарат жана анын ордуна биз Setтин бош же бош эместигин текшеребиз. Бул бош, бул палиндром дегенди билдирет, антпесе жок.

Келгиле, бир мисал карап көрөлү:

мисал

String: india, Query = 2, ал i1, i2 жана ch кириштерин 2 жолу алат дегенди билдирет.

Биз саптын биринчи жарымындагы бирдей эмес индекстерди сакташыбыз керек

Ошентип, бүт жипти басып өткөндөн кийин, бизде мындай Set болот,

Набору: [0, 1]

1-суроо үчүн, i1 = 0, i2 = 4, ch = i, "индия" сабы "indii" болуп калат дегенди билдирет.

i1 1 болуп i0 бойдон калат, i2 0 болуп калат, адегенде i1 өтүп, str [i1] == str [n-1-i1] экендигин текшерип, анын чын экендигин, андан кийин i1 сетинде бар экендигин текшерет, ал дагы бар, демек, ал i1 дегенди 0 топтомдон алып салат.

Андан кийин i2 да 0 болот, андыктан эч нерсе болбойт.

2-суроо боюнча, i1 = 1, i2 = 3, ch = n, "indii" сабы "indni" болуп калат дегенди билдирет.

i1 i1 бойдон калса, i1 2 болуп калат, адегенде i1 өтүп, str [i1] == str [n-1-i1] экендигин текшерип, анын чын экендигин, андан кийин i1 сетинде бар экендигин текшерет, ал дагы бар, демек, ал i1 дегенди 1 топтомдон алып салат. Андан кийин аткарылган бардык суроолордон кийин, Setдин бош экендигин, эми ал бош экендигин текшерип, ал ооба деп басылып чыгат, анткени топтомдо эки маани 1 жана 0 болгон жана биз экөөнү тең алып салдык.

Ар бир персонажды алмаштырган Суроодон кийин Палиндромду текшерүү үчүн C ++ коду

#include<unordered_set>
#include<iostream>

using namespace std;
void checkPalindrome(string &str, int index, int n,unordered_set<int> &SET)
{
    if (str[index] == str[n-1-index])
    {
        if (SET.find(index) != SET.end())
            SET.erase(SET.find(index)) ;
    }
    else
        SET.insert(index);
}
void getQuery(string &str, int query)
{
    int n = str.length();
    unordered_set<int> SET;
    for (int i=0; i<n/2; i++)
        if (str[i] != str[n-1-i])
            SET.insert(i);

    for (int QueryNo=1; QueryNo<=query; QueryNo++)
    {
        cout << "Values for query " << QueryNo <<endl;
        int i1, i2;
        char ch;
        cout << "Enter i1 ";
        cin >> i1;
        cout << "Enter i2 ";
        cin >> i2;
        cout << "Enter ch ";
        cin >> ch;

        str[i1] = str [i2] = ch;

        if (i1 > n/2)
            i1 = n- 1 -i1;
        if (i2 > n/2)
            i2 = n -1 - i2;

        checkPalindrome(str, i1, n, SET );
        checkPalindrome(str, i2, n, SET );

        cout << "Output for query " << QueryNo << " => ";
        SET.empty()? cout << "YES"<<endl<<endl : cout << "NO"<<endl<<endl;
    }
}
int main()
{
    string str = "india";
    int query = 2 ;
    getQuery(str, query);
    return 0;
}
Values for query 1
Enter i1 0
Enter i2 4
Enter ch i
Output for query 1 => NO

Values for query 2
Enter i1 1
Enter i2 3
Enter ch n
Output for query 2 => YES

Ар бир персонажды алмаштырган Суроодон кийин Палиндромду текшерүү үчүн Java коду

import java.util.Scanner;
import java.util.HashSet;

class SearchPalindrome
{
    private static Scanner sc=new Scanner(System.in);
    public static void checkPalindrome(String str, int i, int n,HashSet<Integer> SET)
    {
        if (str.charAt(i) == str.charAt(n-1-i))
        {
            if (SET.contains(i))
                SET.remove(i) ;
        }
        else
            SET.add(i);
    }
    public static void Query(String str, int Q)
    {
        int n = str.length();
        HashSet<Integer> SET=new HashSet<>();
        for (int i=0; i<n/2; i++)
            if (str.charAt(i) != str.charAt(n-1-i))
                SET.add(i);

        for (int query=1; query<=Q; query++)
        {
      System.out.println("Values for query " + query);
            int i1, i2;
            char ch;
            System.out.print("Enter i1 " );
            i1=sc.nextInt();
            System.out.print("Enter i2 ");
            i2=sc.nextInt();
            System.out.print("Enter ch ");
            ch=sc.next().charAt(0);


            char[] strChars = str.toCharArray();
            strChars[i1] = ch;

            strChars[i2] = ch;
            str = String.valueOf(strChars);

            if (i1 > n/2)
                i1 = n- 1 -i1;
            if (i2 > n/2)
                i2 = n -1 - i2;

            checkPalindrome(str, i1, n, SET );
            checkPalindrome(str, i2, n, SET );

            System.out.print("Output for query " + query + " => ");

            if(SET.isEmpty())
                System.out.println("YES\n\n");
            else
                System.out.println("NO\n");
        }
    }
    public static void main(String args[])
    {
        String str = "india";
        int query = 2 ;
        Query(str, query);

    }
}
Values for query 1
Enter i1 0
Enter i2 4
Enter ch i
Output for query 1 => NO

Values for query 2
Enter i1 1
Enter i2 3
Enter ch n
Output for query 2 => YES

Комплекстик анализ

Убакыт татаалдыгы

O (Q + N) кайда "Q" сурамдардын саны жана "N" жиптин узундугу. Алгач, биз жиптин жарым узундугуна чейин цикл иштетебиз жана картага бардык тең эмес индекстерди кошуп, андан кийин O (1) убакытты талап кылган сурамдарды эсептейбиз. Убакыттын татаалдыгы сызыктуу болуп калат.

Космостун татаалдыгы

O (N), анткени биз картага киргизүү тизмегинин элементтерин кошуп жатабыз. Эң начар учурда, бизде бирдей эмес белгилер болушу мүмкүн. Бул бизге O (N) мейкиндигин талап кылат.