Bir sətirdə ilk təkrarlanmayan simvol tapın


SimBaxılıb 240

Verilən simvol axınında (simli) ilk təkrarlanmayan simvolu tapın.

misal

Giriş sətri: ababcef

Çıxış: c

Zamanın mürəkkəbliyi: O (1)

Alqoritm

Burada ikiqat əlaqəli siyahıdan istifadə edirik, DLL təkrarlanmayan bütün xarakterləri sıraya daxil edir.

1. Boş bir DLL yaradın, inDLL [] və asci dəyərlərinin təkrarlanan [] ölçüsü.

2. inDLL [] DLL qovşaqlarının göstəricilərini ehtiva edir. inDLL [x] x, başqa NULL göstəricisinə malikdir.

3. Təkrarlanan [] massivi bool dəyərlərinə malikdir, x iki və ya daha çox dəfə təkrarlanarsa, təkrarlanan [x] doğrudur, əks halda yalan.

4. İnDLL [] 'i NULL dəyərləri ilə başlayın və təkrarlanan [x] səhvdir.

5. DLL-nin başı ilk təkrarlanmayan xarakterdir.

6. Hər yeni xarakter üçün x,

   a) Təkrarlanan [x] doğrudursa, bu işarəni görməyin.

b) Təkrarlanan [x] səhvdirsə və inDLL [x] boşdursa x-ı DLL-ə əlavə edin və yeni DLL düyünü inDLL [x] -də saxlayın.

c) Yenidən [x] yalan və inDLL [x] Null deyilsə, inDLL [x] istifadə edərək x x DLL düyünü alın və düyünü çıxarın. inDLL [x] -i Null olaraq qeyd edin və [x] -i doğrudur.

C ++ Proqramı

#include <bits/stdc++.h>

#define ASCII_VALUES 256
using namespace std;
 
// A linked list DLLNode
struct DLLNode
{
    char data;
    struct DLLNode *next, *prev;
};
//function to insert node at beginning of DLL
void insertAtbeginning(struct DLLNode **head_ref, struct DLLNode **tail_ref,char x)
{
    struct DLLNode *temp = new DLLNode;
    temp->data = x;
    temp->prev = temp->next = NULL;
    if (*head_ref == NULL)
    {
        *head_ref = *tail_ref = temp;
        return;
    }
    (*tail_ref)->next = temp;
    temp->prev = *tail_ref;
    *tail_ref = temp;
}
 
//Function to remove node
void DeleteNode(struct DLLNode **head_ref, struct DLLNode **tail_ref,struct DLLNode *temp)
{
    if (*head_ref == NULL)
    {
        return;
    }
    if (*head_ref == temp)
    {
        *head_ref = (*head_ref)->next;
    }
    if(*tail_ref == temp)
    {
        *tail_ref = (*tail_ref)->prev;
    }
    if (temp->next != NULL)
    {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL)
    {
        temp->prev->next = temp->next;
    }
    delete(temp);
}
 
void FindFirst()
{
    struct DLLNode *inDLL[ASCII_VALUES];
    bool repeated[ASCII_VALUES];
    // Initialize the above two arrays
    struct DLLNode *head = NULL, *tail = NULL;
    for (int i = 0; i < ASCII_VALUES; i++)
    {
        inDLL[i] = NULL;
        repeated[i] = false;
    }
    //Traverse for all charcters
    char string[] = "ababcef";
    for (int i = 0; string[i]; i++)
    {
        char x = string[i];
        cout<<"Reading charcter "<<x<<" from string \n";
        //If charchter occurred less than twice.
        if (!repeated[x])
        {
            if (inDLL[x] == NULL)//If it  is not in DLL add it in beginning
            {
                insertAtbeginning(&head, &tail, string[i]);
                inDLL[x] = tail;
            }
            else//If its already there remove this character from DLL
            {
                DeleteNode(&head, &tail, inDLL[x]);
                inDLL[x] = NULL;
                repeated[x] = true; // Also mark it as repeated
            }
        }
        if (head != NULL)//Current first non-repating character (head)
        {
            cout<<"First non-repeating character till now: "<<head->data<<endl;
        }
    }
}
 
//Main function
int main()
{
    FindFirst();
    return 0;
}

Yoxla

 

Şərh yaz

Translate »