30 ngày chống COVID cùng Leetcode | Ngày 01
Nhiệm vụ ngày hôm nay khá đơn giản, đọc đề bài tôi có thể nghĩ ngay đến dùng Toán để giải quyết, tôi thích cách mà leetcode đưa ra vấn đề là làm thế nào để giải với thuật toán chạy tuyến tính O(n) và không dùng cấu trúc dữ liệu.
Ta có công thức : 2*(sumSet) - sum = single number, lại có một vấn đề ở đây, dù là công thức Toán nhưng tôi đã dùng cấu trúc dữ liệu Set để tính tổng không lặp.
Đã Apcept trên Leetcode, nhưng vẫn chưa thỏa mãn tôi, còn tiêu chí Leetcode chơi khó tôi là không dùng cấu trúc dữ liệu, liệu tôi có thể làm được không ??
May mắn là tôi đã học môn Toán rời rạc, dù từ lúc chưa học nó, tôi đã được dạy là dùng Bit để giải quyết vấn đề rất là hay, trong các phép toán Bit, tôi thích XOR nhất, và nó hoàn toàn giúp tôi trong trường hợp này.
Ta có: a^a = 0 , 0^a = a. Nên a^a^b = 0^b = b => Vấn đề đã được giải quyết !
Đã xanh trên Leetcode, với độ phức tạp O(1) và không gian O(1) (không tính mảng Leetcode tạo) tôi hoàn toàn tự tin về cách giải bài toán này. Như thế có thể an tâm làm việc khác rồi, khá tốt cho một khởi đầu, cảm ơn Leetcode !
Hẹn các bạn ở những bài viết sau !
Ta có công thức : 2*(sumSet) - sum = single number, lại có một vấn đề ở đây, dù là công thức Toán nhưng tôi đã dùng cấu trúc dữ liệu Set để tính tổng không lặp.
Đã Apcept trên Leetcode, nhưng vẫn chưa thỏa mãn tôi, còn tiêu chí Leetcode chơi khó tôi là không dùng cấu trúc dữ liệu, liệu tôi có thể làm được không ??
May mắn là tôi đã học môn Toán rời rạc, dù từ lúc chưa học nó, tôi đã được dạy là dùng Bit để giải quyết vấn đề rất là hay, trong các phép toán Bit, tôi thích XOR nhất, và nó hoàn toàn giúp tôi trong trường hợp này.
Ta có: a^a = 0 , 0^a = a. Nên a^a^b = 0^b = b => Vấn đề đã được giải quyết !
Đã xanh trên Leetcode, với độ phức tạp O(1) và không gian O(1) (không tính mảng Leetcode tạo) tôi hoàn toàn tự tin về cách giải bài toán này. Như thế có thể an tâm làm việc khác rồi, khá tốt cho một khởi đầu, cảm ơn Leetcode !
Hẹn các bạn ở những bài viết sau !
Nhận xét
Đăng nhận xét