So sánh phiên bản trên LeetCode 165 - 88vin

calendar Feb 12, 2025 · 3 phút đọc · 88vin  ·
Chia sẻ trên: linkedin copy

25/07/2019 Công nghệ thông tin

1. Mô tả bài toán Hãy so sánh hai số phiên bản, gọi là version1 và version2. Nếu version1 lớn hơn version2, trả về 1; nếu version1 nhỏ hơn version2, trả về -1; nếu chúng bằng nhau, trả về 0. Bạn có thể giả định rằng các số phiên bản không rỗng và chỉ chứa các chữ số cùng với ký tự “.”. Trong ngữ cảnh này, ký tự “.” không phải là dấu thập phân mà được sử dụng để phân tách chuỗi m88vin - cổng game quốc tế số.

Ví dụ, 2.5 không có nghĩa là "hai rưỡi" hay "còn thiếu nửa đến ba", mà là phiên bản chính thứ 2 với phiên bản phụ thứ 5. Chúng ta cũng có thể giả định rằng mỗi cấp độ của số phiên bản có giá trị mặc định là 0. Ví dụ, số phiên bản 3.4 có phiên bản chính (level 1) và phiên bản phụ (level 2) lần lượt là 3 và 4. Các level tiếp theo như level 3 và level 4 đều có giá trị mặc định là 0.

Ví dụ 1:

Ví dụ 2:

  • Đầu vào: version1 = “1.0.1”, version2 = “1”
  • Đầu ra: 1

Ví dụ 3:

  • Đầu vào: version1 = “7.5.2.4”, version2 = “7.5.3”
  • Đầu ra: -1

Ví dụ 4:

  • Đầu vào: version1 = “1.01”, version2 = “1.001”
  • Đầu ra: 0
  • Giải thích: Bỏ qua các số 0 đứng đầu, “01” và “001” đều tương đương với số 1.

Ví dụ 5:

  • Đầu vào: version1 = “1.0”, version2 = “1.0.0”
  • Đầu ra: 0
  • Giải thích: Số phiên bản thứ nhất không có phần level 3, do đó level 3 được coi là 0.

Nguồn gốc xèng bài toán: LeetCode

2. Cách tiếp cận giải quyết Cách tiếp cận khá đơn giản: Sử dụng hai con trỏ i và j lần lượt chỉ vào vị trí ban đầu của version1 và version2. Hai con trỏ i và j sẽ di chuyển đồng thời từ trái sang phải. Khi gặp một phần được phân cách bởi dấu chấm “.”, chúng ta sẽ tiến hành so sánh xem các phần này có giống nhau hay không. Nếu khác nhau, thoát khỏi vòng lặp và trả về kết quả ngay lập tức. Nếu bằng nhau, hai con trỏ i và j sẽ tiếp tục di chuyển để tìm phần tiếp theo và lặp lại quá trình so sánh cho đến khi hết cả hai chuỗi hoặc có sự khác biệt.

3. Mã nguồn Golang

 1func compareVersion(version1 string, version2 string) int {
 2    i, j := 0, 0
 3    v1, v2 := 0, 0
 4    for i < len(version1) || j < len(version2) {
 5        // Xử lý từng phần của version1
 6        for ; i < len(version1); i++ {
 7            if '.' == version1[i] {
 8                i++
 9                break
10            }
11            if 0 == v1 && '0' == version1[i] {
12                continue
13            }
14            v1 = 10*v1 + int(version1[i]-'0')
15        }
16        
17        // Xử lý từng phần của version2
18        for ; j < len(version2); j++ {
19            if '.' == version2[j] {
20                j++
21                break
22            }
23            if 0 == v2 && '0' == version2[j] {
24                continue
25            }
26            v2 = 10*v2 + int(version2[j]-'0')
27        }
28        
29        // So sánh hai phần vừa xử lý
30        if v1 != v2 {
31            break
32        }
33        v1, v2 = 0, 0
34    }
35    
36    // Quyết định kết quả cuối cùng
37    if v1 > v2 {
38        return 1
39    }
40    if v1 < v2 {
41        return -1
42    }
43    return 0
44}

Từ khóa: #Golang #ThuậtToán