Агымдагы биринчи кайталанбаган каарман үчүн кезекке негизделген ыкма  


Кыйынчылык деңгээли орто
Көп суралган Amazon Flipkart Microsoft PayU Yahoo
таштанды Байланышкан тизме кезек аркан

Маселени билдирүү  

"Агымдагы биринчи кайталанбаган мүнөздөгү кезекке негизделген ыкма" көйгөйүндө сизге кичине тамга бар агым берилгендиги айтылат белги, агымга жаңы символ кошулган сайын биринчи кайталанбай турган белгини табыңыз, эгер кайталанбас символ жок болсо -1.

мисалы,  

aabcddbe
a -1 b b b b c c

түшүндүрүү: Көрүнүп тургандай, экинчи индекстен башка бардык жерлерде биринчи кайталанбаган мүнөзгө ээ. Бирок 2-индекске чейин бардык белгилер кайталанган. Ошентип, -1 индекси 2 боюнча басылып чыгат.

abcdabcd
a a a a b c d -1

 

Агымдагы биринчи кайталанбаган каарман үчүн кезекке негизделген ыкма

Агымдагы биринчи кайталанбаган белгинин алгоритми  

Жогоруда айтылган көйгөйдү а кезек. Демек, биз каармандардын кезегин гана сакташыбыз керек жана an согуштук тизме жыштык. Массив агымдагы бардык белгилердин жыштыгын сактайт.
Ошентип агымдагы ар бир каарман үчүн. Анан ошол мүнөздүн жыштыгын көбөйтүп, кезекке тургузуңуз. Кезектин башындагы белгини текшериңиз, эгер ал белгинин жыштыгы 1 болсо, анда белгини кайтарыңыз. Башкасы, каарманды чыгарып, кийинки каарманы текшериңиз. Эгерде кезек бош болуп калса, -1 кайтып келип, агымдагы башка белгилерди иштетүүнү улантыңыз.

  1. Каармандардын кезегин жана ар бир белгинин жыштыгын сактай турган массивди түзүңүз.
  2. Агымдын киргизүүлөрүн бир-бирден иштеп чыгыңыз.
  3. Учурдагы символдорду агымга киргизүү үчүн, жыштыгын көбөйтүп, кезекке тургузуңуз.
  4. Кезектин алдындагы белгини текшериңиз, эгер ал белгинин жыштыгы 1 болсо, анда белгини басып чыгарыңыз, болбосо кезектеги биринчи белгини алып салып, 4-кадамды кайталаңыз.
  5. Эгерде 4-кадам учурунда кезек бош болуп калса, -1 басып чыгарып, кийинки белгини иштетүүнү улантыңыз.
ошондой эле
Дөңгөлөк массивди колдонуп, Dequeди ишке ашыруу

Агымдагы биринчи кайталанбаган мүнөздөгү татаалдыкты талдоо  

Биз агымды так бир жолу басып өткөндүктөн, ар бир каарман кезекке түртүлүп, кезектен бир жолу чыгарылышы мүмкүн. Ошентип
Убакыт татаалдыгы = O (N)
Космостун татаалдыгы = O (N)
мында n - агымдагы жалпы белгилердин саны.

коду  

Агымдагы биринчи кайталанбаган мүнөздөгү Java коду

import java.util.LinkedList;
import java.util.Queue;

class QueueBasedApproachForFirstNonRepeatingCharacterInAStream {
    private static void firstNonRepeatingCharacter(String stream) {
        // create a array to store frequency of characters
        int freq[] = new int[26];
        // create a queue
        Queue<Character> queue = new LinkedList<>();

        // traverse the stream character by character
        for (int i = 0; i < stream.length(); i++) {
            // current character of stream
            char curr = stream.charAt(i);
            // increase the frequency
            freq[curr - 'a']++;
            // push it to queue
            queue.add(curr);

            while (!queue.isEmpty()) {
                // check the frequency of first character in queue
                char front = queue.peek();
                if (freq[front - 'a'] == 1) {
                    // if freq is 1, print the first character
                    System.out.print(front + " ");
                    break;
                } else {
                    // else remove the first character
                    queue.poll();
                }
            }

            // if queue becomes empty, print -1
            if (queue.isEmpty()) {
                System.out.print("-1 ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        String stream1 = "aabcddbe";
        firstNonRepeatingCharacter(stream1);

        // Example 2
        String stream2 = "abcdabcd";
        firstNonRepeatingCharacter(stream2);
    }
}
a -1 b b b b c c 
a a a a b c d -1

Агымдагы биринчи кайталанбаган каарман үчүн C ++ коду

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

void firstNonRepeatingCharacter(string stream) {
    // create a array to store frequency of characters
    int freq[26];
    for (int i = 0; i < 26; i++) {
        freq[i] = 0;
    }
    // create a queue
    queue<char> q;
    
    // traverse the stream character by character
    for (int i = 0; i < stream.length(); i++) {
        // current character of stream
        char c = stream[i];
        // increase the frequency
        freq[c - 'a']++;
        // push it to queue
        q.push(c);
        
        while (!q.empty()) {
            // check the frequency of first character in queue
            char front = q.front();
            if (freq[front - 'a'] == 1) {
                // if freq is 1, print the first character
                cout<<front<<" ";
                break;
            } else {
                // else remove the first character
                q.pop();
            }
        }
        
        // if queue becomes empty, print -1
        if (q.size() == 0) {
            cout<<"-1 ";
        }
    }
    cout<<endl;
}

int main() {
    // Example 1
    string stream1 = "aabcddbe";
    firstNonRepeatingCharacter(stream1);

    // Example 2
    string stream2 = "abcdabcd";
    firstNonRepeatingCharacter(stream2);
    
    return 0;
}
a -1 b b b b c c 
a a a a b c d -1