ဇာတ်ကောင်အစားထိုးတိုင်း Query ပြီးနောက် Palindrome ကိုစစ်ဆေးပါ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ Facebook က Flipkart Google Netflix နဲ့
hash ကြိုး

“ Query ဇာတ်ကောင်အစားထိုးပြီးနောက်တိုင်း Palindrome ကိုစစ်ဆေးပါ” ပြproblemနာကသင့်အားသင့်အားပေးထားသည်ဟုဆိုသည် ကြိုး အဘယ်သူမျှမ။ မေးမြန်းမှုတစ်ခုစီတွင် query နှစ်ခုရှိသည် ကိန်း အဖြစ်တန်ဖိုးများကို input ကို i1 နှင့် i2 နှင့်အက္ခရာ input ကို 'ch' ဟုခေါ်သည်။ ပြstatementနာကဖော်ပြချက်မှာ i1 နဲ့ i2 ညွှန်းကိန်းတန်ဖိုးများကို ch 'character နဲ့ပြောင်းလဲပြီး palindrome ဟုတ်မဟုတ်ဆုံးဖြတ်ပေးဖို့ဖြစ်တယ်။

မှတ်ချက် - 0 <i1 သည် i2 နှင့်ညီသည် ဖြစ်၍ iXNUMX သည် string ၏အရှည်ထက်နည်းသည်သို့မဟုတ်ညီသည်။

နမူနာ

ဇာတ်ကောင်အစားထိုးတိုင်း Query ပြီးနောက် Palindrome ကိုစစ်ဆေးပါ

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

ရှင်းလင်းချက်

Query 1: india အစားထိုးပြီးနောက်အိန္ဒိယဖြစ်လာသည်

မေးမြန်းချက် 2: indii အစားထိုး indni ပြီးနောက်ဖြစ်လာသည်

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

ရှင်းလင်းချက်

Query 1: အင်္ဂလိပ်ဟာအစားထိုးအပြီးတွင်ဖြစ်လာသည်

Query 2: အစားထိုးအပြီးသတ်ပြီးနောက် anglise ဖြစ်လာသည်

Query 3: esglise သည်အစားထိုး esilise ပြီးနောက်ဖြစ်လာသည်

algorithm

  1. a) ကြေညာပါ အစုံ.
  2. ပထမတစ်ဝက်တွင်မတူညီသောအညွှန်းများအားလုံးကို Set တွင်သိမ်းထားပါ။
  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. အခြားအရာများကို i1 သို့ထည့်ပါ။
    3. i2 အတွက်လည်းဒီလုပ်ငန်းစဉ်ကိုပြန်လုပ်ပါ။
  4. အဆင့် ၃ မှပေးထားသောမေးမြန်းမှုအရေအတွက်အထိပြန်လုပ်ပါ။
  5. အကယ်၍ Set ထားလျှင်пустလျှင်၎င်းသည် palindrome မဟုတ်ပါ။

ရှင်းလင်းချက်

ကျွန်ုပ်တို့အား String နှင့် Query အချို့ပေးထားသည်။ ၎င်းတွင် integer နှင့် character input တန်ဖိုးအချို့ပါ ၀ င်သည်။ အက္ခရာများကိုပြောင်းရန်သို့မဟုတ်အစားထိုးရန်လိုအပ်သည်။ အချို့သော indices များတွင် i1 နှင့် i2 အဖြစ်ပေးထားပြီးပြီးနောက်ကျွန်ုပ်တို့လိုအပ်သည်။ တစ်ခုချင်းစီကိုစုံစမ်းမှုဖျော်ဖြေပြီးနောက်ဖွဲ့စည်းခဲ့ string ကို palindrome သို့မဟုတ်မလျှင်ဆုံးဖြတ်ရန်။ အကြံဥာဏ်ကိုအသုံးပြုရန်ဖြစ်သည် ဟေး။ ဤပြproblemနာကိုဖြေရှင်းရန် Set ကိုကျွန်ုပ်တို့အသုံးပြုမည်။ သီးခြား function တစ်ခုလုပ်မယ်။ function တစ်ခုက query ကိုယူမယ်။ နောက် function က palindrome ကိုစစ်ဆေးရမယ်။ အခြေခံအားဖြင့်၎င်း function သည်နည်းနည်းချင်းစီအလုပ်လုပ်သည်။ ခေါ်ဆိုမှုတစ်ခုစီကြောင့်၎င်းလုပ်ဆောင်ချက်ကိုကျွန်ုပ်တို့ပြုလုပ်သည်။ ကျနော်တို့သတ်မှတ်မည်အချည်းနှီးဖြစ်စေမစစ်ဆေးသောအခါသူကသတ်မှတ်အပေါ်နှင့်ပြန်လာအတွက်စစ်ဆင်ရေးလုပ်ဆောင်တယ်။ ၎င်းသည်အချည်းနှီးဖြစ်သည်။ ဆိုလိုသည်မှာ string သည် palindrome ဖြစ်သည်။ မဟုတ်ပါ။

ဥပမာတစ်ခုကိုသုံးသပ်ကြည့်ကြစို့။

နမူနာ

String: india, Query = 2 သည် i1, i2 နှင့် ch တို့ကို ၂ ကြိမ်သွင်းသည်။

ကျနော်တို့ string ကို၏ပထမတစ်ဝက်၏မညီမျှမှုအညွှန်းကိန်းသိုလှောင်ရန်လိုအပ်သည်

ဒါကြောင့် string တစ်ခုလုံးကိုဖြတ်ပြီးပြီးရင်ငါတို့ဒီလို Set ကိုလုပ်ပါလိမ့်မယ်။

သတ်မှတ်ချက် - [0, 1]

1st query အတွက်, i1 = 0, i2 = 4, ch = i,“ india” ဆိုတဲ့စာကြောင်းက“ indii” ဖြစ်လာတယ်။

i1 သည် 1 အဖြစ် i0 အဖြစ်တည်ရှိနေသည်။ i2 သည် 0 ဖြစ်လာသည်။ ပထမ၊ i1 သည် str [i1] == str [n-1-i1] ဟုတ်မဟုတ်စစ်ဆေးပါလိမ့်မည်။ ထို့နောက်မှန်သည်၊ ဒါ့အပြင် i1 ကိုဆိုလိုတာက 1 ကို set ထဲကနေဖယ်ရှားပစ်လိမ့်မယ်။

ထိုအခါ i2 သည် 0 ဖြစ်သဖြင့်ဘာမျှဖြစ်မလာပါ။

2nd query အတွက်, i1 = 1, i2 = 3, ch = n,“ indii” string ကို“ indni” ဖြစ်လာတယ်။

i1 ကို 1 အဖြစ် i1 အဖြစ်တည်ရှိသည်။ i2 သည် 1 ဖြစ်လာသည်။ ပထမ၊ i1 သည် str [i1] == str [n-1-i1] ဟုတ်မဟုတ်စစ်ဆေးပါလိမ့်မည်၊ ထို့နောက်မှန်သည်၊ ဒါ့အပြင် i1 ကိုဆိုလိုတာက 1 ကို set ထဲကနေဖယ်ရှားလိမ့်မယ်။ ထို့နောက်မေးမြန်းမှုအားလုံးပြီးသွားပါက Set သည်ဗလာဟုတ်၊ မဟုတ်ဟုတ်ဟုတ်ဟုတ်သည်ကိုစစ်ဆေးလိမ့်မည်။ အစုတစ်ခုတွင်တန်ဖိုး 1 နှင့် ၁ ရှိ၍ ၎င်းနှစ်ခုလုံးကိုဖယ်ရှားလိုက်သည်။

အက္ခရာအစားထိုးတိုင်း Query ပြီးနောက် Palindrome ကိုစစ်ဆေးရန် 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

Palindrome ကိုစစ်ဆေးရန် Java ကုဒ်တိုင်း Query အစားထိုးပြီးနောက်

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (Q + N) ဘယ်မှာ "မေး" မေးမြန်းချက်များ၏နံပါတ်နှင့်ဖြစ်ပါတယ် "N" string ကို၏အရှည်သည်။ ပထမ ဦး ဆုံး မှစ၍ ကျွန်ုပ်တို့သည် loop ၏ထက်ဝက်အရှည်အထိ loop ကို run ပြီးမတူညီသောအညွှန်းများအားလုံးကို map ထဲသို့ထည့်ပြီး O (1) အချိန်တစ်ခုချင်းစီကိုယူသောမေးမြန်းချက်များကိုတွက်ချက်သည်။ အချိန်ရှုပ်ထွေး linear ဖြစ်လာသည်။

အာကာသရှုပ်ထွေးမှု

အို (N)၊ ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ input sequence ရဲ့ element တွေကိုမြေပုံထဲကိုထည့်လိုက်လို့ပါ။ နှင့်အဆိုးဆုံးကိစ္စတွင်, ငါတို့ညွှန်းကိန်းအားလုံးမှာအားလုံးမညီမျှမှုဇာတ်ကောင်ရှိနိုင်ပါသည်။ ဒါကကျွန်တော်တို့ကိုအို (N) နေရာတစ်ခုပေးရမယ်။