1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Link bài tập: Count Number of Distinct Integers After Reverse Operations

Bạn được cho một mảng nums chứa các số nguyên dương.

Bạn cần lấy mỗi số nguyên trong mảng này, đảo ngược các chữ số của nó, và thêm nó vào cuối mảng. Bạn phải áp dụng phép tính này cho các số nguyên gốc trong mảng nums.

Hãy trả về số lượng số nguyên duy nhất trong mảng cuối cùng sau khi thực hiện phép tính này.

Ví dụ 1:

Input: nums = [1,13,10,12,31]
Output: 6
Giải thích: Sau khi bao gồm số đảo ngược của mỗi số, mảng kết quả là [1,13,10,12,31,1,31,1,21,13].
Lưu ý rằng đối với số nguyên 10, sau khi đảo ngược nó, nó trở thành 01, tương đương với số 1.
Số lượng số nguyên duy nhất trong mảng này là 6 (Các số 1, 10, 12, 13, 21 và 31).

Ví dụ 2:

Input: nums = [2,2,2]
Output: 1
Giải thích: Sau khi bao gồm số đảo ngược của mỗi số, mảng kết quả là [2,2,2,2,2,2].
Số lượng số nguyên duy nhất trong mảng này là 1 (Số 2).

Ràng buộc:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

3. Phân tích

3.1. Gợi ý

Cấu trúc dữ liệu nào cho phép chúng ta chứa dữ liệu duy nhất không trùng lặp?

  • Đúng, đó chính là cấu trúc dữ liệu set.

    Làm thế nào để đảo ngược các chữ số của một số và trả về số đã đảo ngược?

  • Chúng ta phải tự tạo ra một function làm nhiệm vụ này. Tham số đầu vào của function sẽ là số cần được đảo ngược.

3.2. Ý tưởng

Vì Leetcode sử dụng Go phiên bản 1.18, mà phiên bản này không có cấu trúc dữ liệu set nên ta sẽ phải tự làm bằng cách sử dụng cấu trúc dữ liệu map.

Để tạo ra được cấu trúc dữ liệu set từ map thì key chính là phần tử trong mảng nums, còn value sẽ là true hoặc false.

map := make(map[int]bool)

Ta sẽ lặp qua mảng nums, thêm các phần tử vào map, cứ phần tử nào được thêm vào map thì ta gán value = true, bên cạnh đó ta cũng gán các số đảo ngược của phần tử đó.
Cuối cùng kết quả trả về chính là kích thước của map.

4. Code chạy bằng cơm

Hãy cùng xem ví dụ 1:
leet-code-2442-0

Đầu tiên ta tạo ra một map:
leet-code-2442-1

Bây giờ ta lặp từ đầu đến cuối mảng nums, trong mỗi bước lặp, ta sẽ thêm phần tử của nums cùng số đảo ngược của phần tử đó vào map.
Tại vị trí i = 0, thêm phần tử 1 vào trong map, đồng thời thêm cả số đảo ngược của phần tử này:
leet-code-2442-2

Tại vị trí i = 1, làm tương tự như trên:
leet-code-2442-3

Tại vị trí i = 2, ta thêm phần tử 10 vào map, tuy nhiên số đảo ngược của 10 là 1 đã có trong map rồi nên sẽ không sinh thêm kích thước của map:
leet-code-2442-4

Cứ như vậy đến cuối mảng nums, ta sẽ có được map chứa các phần tử không trùng lặp. Trả về kết quả là kích thước của map.

5. Code bằng máy

Code Golang của chúng ta như sau:

func countDistinctIntegers(nums []int) int {
	map := make(map[int]bool)

	for _, v := range nums {
		map[v]=true
		map[reverse(v)]=true
	}
	return len(numbers)
}

func reverse(num int) int {
	sum := 0
	for num != 0 {
		sum = sum*10 + num%10
		num/=10
	}
	return sum
}

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!