Một chút phép thuật thuật toán cổ xưa hoặc giải một chuỗi nhiệm vụ hấp dẫn từ LeetCode

Cách đây một thời gian, tôi tình cờ thấy một loạt nhiệm vụ thú vị trên trang web leetcode.com. Bản thân các nhiệm vụ không quá khó nhưng cách giải quyết của chúng khá hấp dẫn. Hơn nữa, những vấn đề kiểu này thường xuất hiện trong các cuộc phỏng vấn tại các công ty lớn và việc hiểu các phương pháp giải quyết chúng có thể khá có lợi.

Nhiệm vụ đầu tiên là 136. Số đơn (Dễ)

Cho một mảng số nguyên không trống trong đó mọi phần tử xuất hiện hai lần ngoại trừ một phần tử, bạn cần tìm phần tử không có cặp. Giải quyết vấn đề với độ phức tạp về thời gian O(n) và với bộ nhớ bổ sung không đổi.

Ví dụ 1:

Đầu vào: nums = [1, 3, 3, 2, 6, 2, 1]

Đầu ra: 6

Ví dụ 2:

Đầu vào: nums = [12, 1, 1, 7, 1, 12, 1]

Đầu ra: 7

Ví dụ 3:

Đầu vào: nums = [6]

Đầu ra: 6

Chúng ta sẽ tận dụng thuộc tính hàm XOR, thuộc tính này chỉ mang lại 1 khi toán hạng của nó khác nhau. Bằng cách duyệt qua tất cả các phần tử của mảng và thực hiện XOR theo bit trên chúng, chúng ta sẽ loại bỏ tất cả các giá trị bit giống nhau. Kết quả là những gì còn lại sẽ là kết quả mong muốn.

Đây là mã giải pháp Python3 ngắn:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

Chúng tôi chỉ sử dụng nhiều bộ nhớ bổ sung khi một số nguyên chiếm giữ và tìm giải pháp trong một lần truyền qua mảng đã cho, mang lại cho chúng tôi độ phức tạp O(n). Đây là một giải pháp ngắn gọn và thanh lịch.

Bài toán thứ hai là 137. Số đơn II (Độ khó trung bình)

Cho một mảng số nguyên không trống trong đó mỗi phần tử xuất hiện ba lần ngoại trừ một phần tử và chỉ một phần tử xuất hiện một lần, chúng ta cần tìm phần tử duy nhất này. Giải quyết vấn đề với độ phức tạp về thời gian O(n) và với bộ nhớ bổ sung không đổi.

Ví dụ 1:

Đầu vào: nums = [3, 1, 3, 3]

Đầu ra: 1

Ví dụ 2:

Đầu vào: nums = [12, 1, 1, 5, 1, 12, 12]

Đầu ra: 5

Ví dụ 3:

Đầu vào: nums = [6]

Đầu ra: 6

Thật không may, chúng ta không thể sử dụng thủ thuật trước đó trong trường hợp này vì chúng ta không thể biến các bit ghép đôi ở vị trí cần thiết thành số 0. Sẽ rất hấp dẫn khi chuyển đổi mảng đã cho sang định dạng từ nhiệm vụ trước đó và sau đó giải quyết nó theo cách tương tự.

Lập luận theo cách này, thật dễ dàng nhận thấy rằng nếu chúng ta biết rằng chúng ta đã gặp số N hai lần (hoặc ba lần) khi duyệt mảng, chúng ta có thể thêm một XOR bổ sung có N vào tổng mà chúng ta đang nhận được. Điều này sẽ làm cho XOR cuối cùng có số này là chẵn, do đó loại bỏ nó khỏi tổng cuối cùng và phần còn lại sẽ là câu trả lời của chúng ta.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

Thật không may, giải pháp này sẽ yêu cầu tối đa (len(nums)-1)/3 về mặt bộ nhớ, không thể coi là mức tiêu thụ liên tục, vì vậy chúng ta sẽ phải tìm giải pháp khác.

Hãy thử thay đổi cách tiếp cận của chúng tôi.

Trước đó, chúng tôi đã sử dụng XOR (đại diện cho phép cộng modulo 2). Nếu chúng ta triển khai phép cộng modulo 3, chúng ta có thể dễ dàng áp dụng thủ thuật từ ví dụ trước.

Nếu chúng ta có thể đặt một số vào câu trả lời ngay lần đầu tiên gặp nó, đặt nó vào bộ tích lũy lần thứ hai và loại bỏ cả câu trả lời và bộ tích lũy ở lần thứ ba, điều đó sẽ giúp chúng ta giải quyết vấn đề trong một lần truyền qua danh sách có mức tiêu thụ bộ nhớ bổ sung chính xác bằng hai số nguyên, đáp ứng yêu cầu nhiệm vụ.

Vì vậy, hãy áp dụng phép thuật bitwise hơn một chút:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

Bằng cách này, tất cả các số ba đều bị loại bỏ bằng 0 và chúng ta chỉ còn lại số chỉ xuất hiện một lần.

Nhiệm vụ thứ ba là 260. Số đơn III (Độ khó trung bình)

Cho một mảng số nguyên không trống trong đó mọi phần tử xuất hiện hai lần, ngoại trừ hai phần tử chỉ xuất hiện một lần, chúng ta cần tìm các phần tử duy nhất này. Mục tiêu là giải quyết vấn đề với độ phức tạp về thời gian O(n) và với bộ nhớ bổ sung không đổi và thứ tự của các phần tử duy nhất không quan trọng.

Ví dụ 1:

Đầu vào: nums = [1, 2, 1, 3, 2, 5]

Đầu ra: [3, 5]

Ví dụ 2:

Đầu vào: nums = [1, -2]

Đầu ra: [-2, 1]

Rõ ràng, chúng ta có thể dễ dàng loại bỏ tất cả các số được ghép nối bằng phép toán XOR, như chúng ta đã làm khi giải bài toán đầu tiên. Khi đó, độ phức tạp của nhiệm vụ nằm ở việc xác định bất kỳ số duy nhất nào, sau đó số thứ hai có thể được tính toán dễ dàng bằng cách XOR nó với tổng XOR của chúng ta.

Để đạt được điều này, chúng ta chỉ cần tìm bất kỳ bit nào khác nhau giữa các số duy nhất này. Sau đó, chúng tôi lặp lại mảng một lần nữa, thực hiện phép tính tổng XOR và chia kết quả thành hai nhóm - đối với các số có bit này được đặt và đối với các số có bit này bằng 0. Kết quả là, chúng tôi thu được các phần tử duy nhất mong muốn.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

Mặc dù phải lặp qua mảng hai lần nhưng độ phức tạp vẫn là O(n) và mức tiêu thụ bộ nhớ chỉ là 2 số nguyên.

Lưu ý: Mặc dù thực tế là int trong Python không hoàn toàn giống với int trong các ngôn ngữ khác, nhưng chúng ta sẽ coi kích thước của nó là một hằng số