Ngày 30 tháng nohu.com 56 10 năm 2019 - Lĩnh vực Công nghệ Thông tin
1. Mô tả bài toán Cho một chuỗi ký tự, hãy sắp xếp lại các ký tự này dựa trên tần suất xuất hiện của chúng theo thứ tự giảm dần.
Ví dụ 1:
Đầu vào: "tree"
Đầu ra: "eert"
Giải thích: Ký tự 'e' xuất hiện 2 lần, trong khi 'r' và 't' chỉ xuất hiện mỗi lần 1 lần. Vì vậy, 'e' sẽ đứng trước 'r' và 't'. Kết quả "eetr" là một đáp án hợp lệ.
Ví dụ 2:
Đầu vào: "cccaaa"
Đầu ra: "cccaaa"
Giải thích: Cả 'c' và 'a' đều xuất hiện 3 lần. Do đó, "aaaccc" cũng là một đáp án hợp lệ. Lưu ý rằng kết quả "cacaca" không đúng vì các ký tự giống nhau cần phải đứng liền kề với nhau.
Ví dụ 3:
Đầu vào: "Aabb"
Đầu ra: "bbAa"
Giải thích: 'b' xuất hiện 2 lần, trong khi 'A' và 'a' mỗi cái xuất hiện 1 lần. Kết quả "bbAa" là hợp [79king1](/post/4175/) lệ. Lưu ý rằng các ký tự giống nhau phải được nhóm lại với nhau.
Nguồn gốc bài toán: LeetCode
2. Ý tưởng giải quyết
a) Duyệt qua chuỗi một lần để tạo ra bảng ánh xạ (map) với key là ký tự và value là số lần xuất hiện tương ứng của nó. b) Tiếp tục duyệt qua bảng ánh xạ vừa tạo để xây dựng một bảng ánh xạ mới, nơi mà key là số lần xuất hiện và value là mảng các ký tự có cùng tần suất đó. Đồng thời, thu thập tất cả các giá trị tần suất vào một mảng. c) Sắp xếp mảng tần suất theo thứ tự giảm dần. Sau đó duyệt qua mảng này, đối với mỗi giá trị tần suất, truy vấn vào bảng ánh xạ mới để lấy ra các ký tự tương ứng và lặp lại chúng theo đúng số lần xuất hiện. Cuối cùng, ghép nối các ký tự này thành một chuỗi mới và trả về kết quả.
3. Mã nguồn Golang
func frequencySort(s string) string {
charCounts := make(map[rune]int)
for _, c := range s {
charCounts[c] += 1
}
var counts []int
countChars := make(map[int][]rune)
for c, count := range charCounts {
if chars, ok := countChars[count]; ok {
countChars[count] = append(chars, c)
} else {
countChars[count] = []rune{c}
counts = append(counts, count)
}
}
sort.Slice(counts, func(i, j int) bool {
return counts[i] > counts[j]
})
var chars []rune
for _, count := range counts {
for _, c := range countChars[count] {
i := count
for i > 0 {
chars = append(chars, c)
i--
}
}
}
return string(chars)
}
#Golang #ThuậtToán