Friday, March 13, 2020

Tìm ký tự không lặp lại đầu tiên trong Chuỗi java

Đây là câu hỏi khởi đầu cho các công ty sản phẩm, vì vậy hãy chắc chắn rằng bạn đi qua nó. Viết chương trình java để tìm ký tự không lặp lại đầu tiên trong Chuỗi.
Trong các bài kiểm tra viết hoặc trong cuộc phỏng vấn kỹ thuật của Amazon, bạn có thể dễ dàng tìm thấy câu hỏi này. Vì vậy, để giúp bạn chuẩn bị phỏng vấn, chúng tôi đang trả lời câu hỏi này trong bài viết này.
Tìm ký tự không lặp lại đầu tiên trong Chuỗi java

Trước tiên, chúng ta cần hiểu câu hỏi, chúng ta cần viết một thuật toán cho ký tự không lặp lại đầu tiên trong một chuỗi, ví dụ
nếu bạn nhập một từ "stress" thì nó sẽ in ra màn hình chữ "t"
Bây giờ chúng ta hay đi tìm logic cho nó nhé.
Như chúng ta biết một ký tự không lặp lại chỉ xảy ra một lần trong chuỗi, vì vậy nếu chúng ta lưu trữ số lần mỗi bảng chữ cái xuất hiện trong chuỗi, nó sẽ giúp chúng ta xác định các ký tự không phải là ký tự lặp lại trong chuỗi. Vì vậy, chúng ta cần quét toàn bộ chuỗi và xác định số đếm cuối cùng của mỗi ký tự. Bây giờ quét các giá trị cuối cùng của mỗi ký tự trong chuỗi, ký tự đầu tiên trong chuỗi có số 1 cuối cùng là ký tự không lặp lại đầu tiên trong chuỗi.

Thuật toán của việc tìm kiếm

1. Đầu tiên tạo bảng băm đếm ký tự.
For each character
            If there is no value stored in the character
                     set it to 1 .
            else
                     increment the value of the character by 1 .
2. Tìm chuỗi
For each character
           return character if the count in hash table is 1 .
           If no character have count 1 , return null
Sau đây là code thực hiện tìm ký tự không trung lặp
public class FirstNonRepeated {
 
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
     
        System.out.println(" Please enter the input string :" );
        Scanner in = new Scanner (System.in);
        String s=in.nextLine();
        char c=firstNonRepeatedCharacter(s);
        System.out.println("The first non repeated character is :  " + c);
    }
 
    public static Character firstNonRepeatedCharacter(String str)
    {
        HashMap<Character,Integer>  characterhashtable=
                     new HashMap<Character ,Integer>();
        int i,length ;
        Character c ;
        length= str.length();  // Scan string and build hash table
        for (i=0;i < length;i++)
        {
            c=str.charAt(i);
            if(characterhashtable.containsKey(c))
            {
                // increment count corresponding to c
                characterhashtable.put(  c ,  characterhashtable.get(c) +1 );
            }
            else
            {
                characterhashtable.put( c , 1 ) ;
            }
        }
        // Search characterhashtable in in order of string str
     
        for (i =0 ; i < length ; i++ )
        {
            c= str.charAt(i);
            if( characterhashtable.get(c)  == 1 )
            return c;
        }
        return null ;
    }

No comments:

Post a Comment