Hướng dẫn này sẽ chỉ ra các cách tiếp cận khác nhau để tìm ký tự duy nhất đầu tiên trong một chuỗi nhất định. Chẳng hạn, kết quả phải là "n" nếu chuỗi đã cho là "stringstutorial" và "S" nếu chuỗi đã cho là "StringsTutorial" Show
Giải trìnhĐầu vào. "hướng dẫn về dây" Giải trình Bước 1. Tạo danh sách tần số của các ký tự cho chuỗi đã cho tần số ['s'] = 2 tần số ['t'] = 3 tần số ['r'] = 2 tần số ['i'] = 2 tần số ['n'] = 1 tần số ['g'] = 1 tần số ['u'] = 1 tần số ['o'] = 1 tần số ['a'] = 1 tần số ['l'] = 1 Bước 2. Tìm ký tự đầu tiên có tần số đơn vị Tạo bản đồ băm tần sốNếu một ký tự chỉ xuất hiện một lần trong chuỗi đã cho, ký tự đó được coi là ký tự không lặp lại. Tính tần suất của mỗi chữ cái trong chuỗi chuỗi và xác định chữ cái nào có tần số bằng 1 là các bước để định vị các ký tự duy nhất đó. Bản đồ băm, ánh xạ các ký tự theo tần số tương ứng của chúng và cho phép chúng tôi sửa đổi đồng thời tần suất của các ký tự mà chúng tôi đã gặp trong thời gian không đổi, là một công cụ hiệu quả cho công việc này. Trong hệ thống ASCII, 256 ký tự duy nhất là giới hạn. Vì vậy, độ dài tối đa của bản đồ băm là 256. Đọc lại chuỗi và chữ cái đầu tiên có tần số bằng một là giải pháp thuật toán
Mã số đầu ra The first unique character is n Tìm ký tự duy nhất bằng cách duyệt qua chuỗi chỉ một lầnPhương thức chính yêu cầu thời gian chạy O(n), mặc dù chúng ta có thể làm cho nó nhanh hơn trong ứng dụng. Mảng đếm được xây dựng trong bước đầu tiên của quy trình bằng cách duyệt qua văn bản lặp đi lặp lại trong thời gian chạy O(n). Bước này có ý nghĩa. Tuy nhiên, phần thứ hai, nơi chúng tôi phát lại trình lặp không lặp lại ban đầu của chuỗi, không phải là một ý kiến hay Chuỗi được dự đoán lâu hơn nhiều so với bộ ký tự của chúng tôi trong hoàn cảnh thực tế. Hãy xem xét các chuỗi DNA, có thể chứa hàng tỷ chữ cái và chỉ có một bảng chữ cái gồm bốn chữ cái. Điều gì xảy ra nếu ký tự duy nhất ở cuối chuỗi? Tạo Hash Map và Traversing String OnceThay vì sử dụng bản đồ băm, hãy tạo một mảng tần số có độ dài của danh sách ký tự là 256. Bằng cách thêm vào mảng tần suất, chúng tôi có thể lưu trữ không chỉ tần suất mà còn cả vị trí xuất hiện đầu tiên của chữ cái, chẳng hạn như (5, 36) cho chữ cái, cho biết rằng nó đã được ghi năm lần và ban đầu xuất hiện ở vị trí 36. Để xác định vị trí ký tự duy nhất đầu tiên, chúng ta chỉ cần quét mảng tần số chứ không phải chuỗi. Dưới đây là việc thực hiện ý tưởng này Mã số đầu ra First unique character is n Tạo danh sách tần số và lặp lại chỉ một lầnTạo danh sách tần suất tối đa 256 ký tự. Chúng ta có thể khởi tạo tất cả các mục trong danh sách này thành -1. Chúng tôi sẽ lặp lại các ký tự của chuỗi và kiểm tra xem các phần tử danh sách có ký tự cụ thể này có chỉ số là 1 hay không. Nếu nó là -1, chúng ta sẽ đổi nó thành j; Tất cả các ký tự lặp lại cuối cùng sẽ được thay đổi thành -2, trong khi tất cả các ký tự duy nhất sẽ vẫn giữ nguyên chỉ mục mà chúng xuất hiện lần đầu. Chúng ta có thể nhanh chóng tìm ra chỉ mục nhỏ nhất hoặc ban đầu bằng cách lặp lại tất cả các ký tự duy nhất Mã số đầu ra The first unique character is n Sử dụng các Hàm dựng sẵn của PythonSử dụng hàm Counter() để xác định tần số của tất cả các ký tự Đi qua chuỗi và tìm phần tử nào có tần số 1. In ký tự duy nhất và phá vỡ vòng lặp ở đó Mã số đầu ra The first unique character is: n Sử dụng hàm find() của chuỗiSau chữ cái hiện tại, tra cứu từng chữ cái tiếp theo. Nếu nó trả về -1, điều đó có nghĩa là chữ cái chỉ xuất hiện một lần, đó là chỉ số hiện tại Mã số đầu ra The first unique character is: n Sử dụng hàm đếm()Nếu số đếm () của một ký tự trong một chuỗi là 1, điều đó cho biết ký tự đó là duy nhất và không lặp lại. Chúng tôi sẽ ngắt vòng lặp và in ký tự duy nhất đầu tiên mà chúng tôi tìm thấy Giả sử chúng ta có một chuỗi và chúng ta phải tìm ký tự duy nhất đầu tiên trong chuỗi. Vì vậy, nếu chuỗi giống như "người", chữ cái đầu tiên có số lần xuất hiện là 'o'. Vì vậy, chỉ mục sẽ được trả về, đó là 2 ở đây. Nếu không có ký tự nào thì trả về -1 Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Ví dụChúng ta hãy xem triển khai sau đây để hiểu rõ hơn - Bản thử trực tiếp class Solution(object): def firstUniqChar(self, s): """ :type s: str :rtype: int """ frequency = {} for i in s: if i not in frequency: frequency[i] = 1 else: frequency[i] +=1 for i in range(len(s)): if frequency[s[i]] == 1: return i return -1 ob1 = Solution() print(ob1.firstUniqChar("people")) print(ob1.firstUniqChar("abaabba")) Đầu vào"people" "abaabba" đầu ra2 -1 Làm cách nào để tìm số ký tự duy nhất trong tệp văn bản Python?fh = open('my. txt','r'). read() unique_chars = set(fh) len(unique_chars) # cho độ dài.
Làm cách nào để tìm tất cả các ký tự không lặp lại trong một chuỗi bằng Python?Thuật toán . Bước 1. - lưu trữ chuỗi trong một biến giả sử Chuỗi Bước 2. - hãy để nó là "prepinsta" Bước 3. - Bắt đầu lặp qua chuỗi Bước 4. - Khởi tạo biến đếm Bước 5. - Một lần nữa bắt đầu lặp qua cùng một chuỗi Bước 6. - Biến đếm tăng dần khi tìm thấy ký tự trong chuỗi Làm cách nào để kiểm tra xem có các chữ cái lặp lại trong chuỗi Python không?Tạo một chuỗi và lưu trữ nó trong một biến. Để so sánh ký tự đã chọn với các ký tự còn lại trong chuỗi, một vòng lặp bên trong sẽ được sử dụng. Nếu một trận đấu được tìm thấy, số lượng được tăng lên 1. Nếu số ký tự nhiều hơn 1 sau khi vòng lặp bên trong kết thúc, thì sẽ có các ký tự trùng lặp trong chuỗi . |