តម្រង់ជួរវិធីសាស្រ្តសម្រាប់តួអក្សរដែលមិនធ្វើម្តងទៀតនៅក្នុងស្ទ្រីម


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Flipkart ក្រុមហ៊ុន Microsoft PayU ក្រុមហ៊ុន Yahoo
ហាស់ បញ្ជីភ្ជាប់ ជួរ ខ្សែអក្សរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ វិធីសាស្រ្តផ្អែកលើជួរសម្រាប់តួអក្សរដែលមិនធ្វើម្តងទៀតនៅក្នុងស្ទ្រីម” ចែងថាអ្នកត្រូវបានផ្តល់ឱ្យនូវខ្សែដែលមានអក្សរតូច តួអក្សររកតួអក្សរដែលមិនធ្វើម្តងទៀតនៅពេលណាដែលតួអក្សរថ្មីត្រូវបានបន្ថែមទៅស្ទ្រីមហើយប្រសិនបើមិនមានតួអក្សរមិនធ្វើម្តងទៀត -1 ។

ឧទាហរណ៍

aabcddbe
a -1 b b b b c c

ការពន្យល់: ដូចដែលយើងអាចឃើញថាទិន្នផលមានតួអក្សរមិនធ្វើម្តងទៀតនៅគ្រប់ទីកន្លែងលើកលែងតែសន្ទស្សន៍ទីពីរ។ ប៉ុន្តែរហូតដល់សន្ទស្សន៍ ២ តួអក្សរទាំងអស់ត្រូវបានធ្វើម្តងទៀត។ ដូច្នេះ -2 ត្រូវបានបោះពុម្ពនៅសន្ទស្សន៍ 1 ។

abcdabcd
a a a a b c d -1

 

តម្រង់ជួរវិធីសាស្រ្តសម្រាប់តួអក្សរដែលមិនធ្វើម្តងទៀតនៅក្នុងស្ទ្រីម

ក្បួនដោះស្រាយសម្រាប់តួអក្សរដែលមិនធ្វើម្តងទៀតនៅក្នុងស្ទ្រីម

បញ្ហាខាងលើអាចត្រូវបានដោះស្រាយដោយប្រើក ជួរ។ ដូច្នេះយើងគ្រាន់តែត្រូវការរក្សាជួរតួអក្សរហើយមួយ អារេ ប្រេកង់។ អារេរក្សាទុកប្រេកង់នៃរាល់តួអក្សរនៅក្នុងចរន្ត។
ដូច្នេះសម្រាប់គ្រប់តួអក្សរទាំងអស់នៅក្នុងចរន្ត។ ហើយបន្ទាប់មកបង្កើនភាពញឹកញាប់នៃតួអក្សរនោះហើយរុញវាទៅជួរ។ ពិនិត្យតួអក្សរនៅដើមជួរប្រសិនបើប្រេកង់នៃតួអក្សរនោះគឺ 1 ត្រឡប់តួអក្សរ។ ផ្សេងទៀតលេចចេញតួអក្សរហើយពិនិត្យមើលតួអក្សរបន្ទាប់។ ប្រសិនបើជួរក្លាយជាទទេសូមត្រឡប់ -1 ហើយបន្តដំណើរការតួអក្សរផ្សេងទៀតនៅក្នុងស្ទ្រីម។

  1. បង្កើតជួរនៃតួអក្សរនិងអារេមួយដែលផ្ទុកភាពញឹកញាប់នៃរាល់តួអក្សរ។
  2. ម្តងមួយដំណើរការធាតុចូលនៃស្ទ្រីម។
  3. សម្រាប់ការបញ្ចូលតួអក្សរបច្ចុប្បន្ននៅក្នុងស្ទ្រីមបង្កើនប្រេកង់ហើយរុញវាទៅជួរ។
  4. ពិនិត្យមើលតួអក្សរនៅជួរជួរដេកប្រសិនបើប្រេកង់នៃតួអក្សរនោះគឺ 1 បោះពុម្ពតួអក្សរផ្សេងទៀតត្រូវដកតួអក្សរដំបូងនៅក្នុងជួរហើយធ្វើជំហានទី 4 ម្តងទៀត។
  5. ប្រសិនបើជួរក្លាយជាទទេក្នុងអំឡុងពេលជំហានទី 4 បោះពុម្ព -1 ហើយបន្តដំណើរការតួអក្សរបន្ទាប់។

ការវិភាគស្មុគស្មាញសម្រាប់តួអក្សរដែលមិនធ្វើម្តងទៀតនៅក្នុងស្ទ្រីម

ដោយសារយើងបានឆ្លងកាត់ស្ទ្រីមអោយបានច្បាស់ម្តងហើយរាល់តួអក្សរអាចនឹងត្រូវរុញទៅជួរហើយដកចេញពីជួរពិតប្រាកដតែម្តង។ ដូច្នេះ
ស្មុគស្មាញពេលវេលា = អូរ (n)
ភាពស្មុគស្មាញនៃលំហ = អូរ (n)
ដែល n ជាចំនួនតួអក្សរសរុបនៅក្នុងចរន្ត។

លេខកូដ

កូដចាវ៉ាសម្រាប់តួអក្សរដែលមិនធ្វើម្តងទៀតនៅក្នុងស្ទ្រីម

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