Рубрики

Подход на основе очереди для первого неповторяющегося символа в потоке

Учитывая поток символов, и мы должны найти первый неповторяющийся символ каждый раз, когда символ вставляется в поток.

Примеры:

Input  : a a b c
Output : a -1 b b

Input  : a a c
Output : a -1 c

Мы уже обсуждали подход, основанный на двунаправленном списке, в предыдущем посте .

Подходить-

  1. Создайте массив count размером 26 (при условии наличия только символов нижнего регистра) и инициализируйте его нулем.
  2. Создайте очередь типа данных char.
  3. Сохраните каждый символ в очереди и увеличьте его частоту в массиве хэшей.
  4. Для каждого символа потока мы проверяем начало очереди.
  5. Если частота символа в начале очереди равна единице, то это будет первый неповторяющийся символ.
  6. Иначе, если частота больше 1, тогда мы выталкиваем этот элемент.
  7. Если очередь стала пустой, это означает, что нет повторяющихся символов, поэтому мы выведем -1.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для подхода на основе очереди
// найти первый неповторяющийся символ
#include <bits/stdc++.h>

using namespace std;

const int MAX_CHAR = 26;

  
// функция для поиска первого неповторяющегося
// символ потока sa

void firstnonrepeating(char str[])

{

    queue<char> q;

    int charCount[MAX_CHAR] = { 0 };

  

    // пройти весь поток

    for (int i = 0; str[i]; i++) {

  

        // вставляем каждый символ в очередь

        q.push(str[i]);

  

        // увеличиваем счетчик частоты

        charCount[str[i] - 'a']++;

  

        // проверяем неповторяющийся символ

        while (!q.empty()) {

            if (charCount[q.front() - 'a'] > 1)

                q.pop();

            else {

                cout << q.front() << " ";

                break;

            }

        }

  

        if (q.empty())

            cout << -1 << " ";

    }

    cout << endl;

}

  
// Функция драйвера

int main()

{

    char str[] = "aabc";

    firstnonrepeating(str);

    return 0;

}

Джава

// Java-программа для подхода на основе очереди
// найти первый неповторяющийся символ

  

import java.util.LinkedList;

import java.util.Queue;

  

public class NonReapatingCQueue {

    final static int MAX_CHAR = 26;

  

    // функция для поиска первого неповторяющегося

    // символ потока

    static void firstNonRepeating(String str)

    {

        // подсчитать массив размером 26 (при условии

        // присутствуют только символы нижнего регистра)

        int[] charCount = new int[MAX_CHAR];

  

        // Очередь для хранения символов

        Queue<Character> q = new LinkedList<Character>();

  

        // пройти весь поток

        for (int i = 0; i < str.length(); i++) {

            char ch = str.charAt(i);

  

            // вставляем каждый символ в очередь

            q.add(ch);

  

            // увеличиваем счетчик частоты

            charCount[ch - 'a']++;

  

            // проверяем неповторяющийся символ

            while (!q.isEmpty()) {

                if (charCount[q.peek() - 'a'] > 1)

                    q.remove();

                else {

                    System.out.print(q.peek() + " ");

                    break;

                }

            }

            if (q.isEmpty())

                System.out.print(-1 + " ");

        }

        System.out.println();

    }

  

    // Функция драйвера

    public static void main(String[] args)

    {

        String str = "aabc";

        firstNonRepeating(str);

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Python3 программа для подхода на основе очереди
# найти первый неповторяющийся символ

from queue import Queue 

  
# функция, чтобы найти первый не
# повторяющийся символ sa Stream

def firstnonrepeating(Str):

    global MAX_CHAR

    q = Queue()

    charCount = [0] * MAX_CHAR 

      

    # пройти весь поток

    for i in range(len(Str)):

  

        # нажмите каждый символ в очереди

        q.put(Str[i]) 

  

        # увеличить счетчик частоты

        charCount[ord(Str[i]) - 

                  ord('a')] += 1

  

        # проверка на не pepeating

        # персонаж

        while (not q.empty()): 

            if (charCount[ord(q.queue[0]) - 

                          ord('a')] > 1): 

                q.get() 

            else:

                print(q.queue[0], end = " "

                break

  

        if (q.empty()): 

            print(-1, end = " ")

    print()

  
Код водителя

MAX_CHAR = 26

Str = "aabc"

firstnonrepeating(Str)

  
# Этот код предоставлен PranchalK

C #

using System;

using System.Collections.Generic;

  
// C # Программа для подхода на основе очереди
// найти первый неповторяющийся символ

  

  

public class NonReapatingCQueue

{

    public const int MAX_CHAR = 26;

  

    // функция для поиска первого неповторяющегося

    // символ потока

    public static void firstNonRepeating(string str)

    {

        // подсчитать массив размером 26 (при условии

        // присутствуют только символы нижнего регистра)

        int[] charCount = new int[MAX_CHAR];

  

        // Очередь для хранения символов

        LinkedList<char> q = new LinkedList<char>();

  

        // пройти весь поток

        for (int i = 0; i < str.Length; i++)

        {

            char ch = str[i];

  

            // вставляем каждый символ в очередь

            q.AddLast(ch);

  

            // увеличиваем счетчик частоты

            charCount[ch - 'a']++;

  

            // проверяем неповторяющийся символ

            while (q.Count > 0)

            {

                if (charCount[q.First.Value - 'a'] > 1)

                {

                    q.RemoveFirst();

                }

                else

                {

                    Console.Write(q.First.Value + " ");

                    break;

                }

            }

            if (q.Count == 0)

            {

                Console.Write(-1 + " ");

            }

        }

        Console.WriteLine();

    }

  

    // Функция драйвера

    public static void Main(string[] args)

    {

        string str = "aabc";

        firstNonRepeating(str);

    }

}

  
// Этот код предоставлен Shrikant13

Выход:

a -1 b b

Видео:

Эта статья предоставлена Нитешем Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подход на основе очереди для первого неповторяющегося символа в потоке

0.00 (0%) 0 votes