[Leetcode] 190. Reverse Bits

Hôm nay mình sẽ mở đầu cho series giải đề trên leetcode 🥳  Vì khả năng còn rất có hạn nên mình sẽ chọn những bài dễ làm trước hehe. 

Bài đầu tiên là 190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Constraints:

The input must be a binary string of length 32

Example 1
Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2
Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Phân tích đề

Theo đề bài yêu cầu thì mình cần chuyển một số nguyên về số nhị phân(có 32 bit), đảo ngược n và chuyển nó về lại giá trị số nguyên tương ứng. 

Như trong ví dụ 1,  n có giá trị số nguyên là 43261596 và ở dạng binary thì 

n = 00000010100101000001111010011100 thì đảo ngược của 

n ở dạng bit từ sau ra trước là: 0011100101111000001010010100000

reverse-bit

Sau khi đã có được số đảo ngược, thì kết quả chính là số đảo ngược đó ở dạng số nguyên, là 3221225471

reverse-bit-output

Và kết quả đúng chính là 3221225471

Để giải được bài này, mình cần biết:

– cách chuyển một số nguyên về một số dạng bit và ngược lại, chuyển một số dạng bit về một số nguyên, ví dụ: 

   – chuyển về binary: 12 = 8 + 4 = 1* 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 = 110

   – chuyển về số nguyên: 1010 = 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 *  2^0 = 8 + 0 + 2 + 0 = 10

– cách đảo ngược một chuỗi, ví dụ ‘1010‘ thành ‘0101’.

Hướng tiếp cận 1:

Chuyển số nguyên về số binary và ngược lại

Chuyển số binary về số nguyên bằng cách chia cho 2

Ở cách này, mình lần lượt chia số đó cho 2 và nhận được kết quả là x và số dư là 0 nếu chia hết cho 2, hoặc 1 nếu chia không hết cho hai. Tiếp tục lấy x chia với 2 cho đến khi nhận kết quả cuối cùng là 0. Khi đó, số binary sẽ được lấy theo thứ tự từ dưới lên trên.

Cách làm này được mô tả như sau:

recursive modulo 2

Trong code sẽ mô tả là:

def number_to_binary(n):
    if n >= 1:
        number_to_binary(n // 2)
        print(n % 2, end=" ")

Code mô tả cho công việc này mình có làm ở đây, bạn có thể fork về tài khoản của mình để thực hành nhé.

Chuyển số nguyên về số binary bằng cách nhân cho 2

Ngược lại, để chuyển từ số binary về số nguyên mình cần thực hiện nhân cho 2 và cộng dồn kết quả với các số dư, chính là các số binary 0 hay 1.

binary-to-int

Như mô tả trên hình, thì mình sẽ lặp qua từng số trong số binary, rồi thực hiện nhân kết quả đang có cho 2 và cộng với số dư chính là số binary ở thời điểm hiện tại. 

Bắt đầu với giá trị 0, số đầu tiên là 1 nên kết quả có được là 0 * 2 + 1 = 1

Tiếp theo, bắt đầu với 1, số tiếp theo là 1 nên kết quả có được là 1 * 2 + 1 = 3

Và tiếp tục thực hiện cho đến hết. 

Code mô tả cho công việc này mình có làm ở đây, bạn có thể fork về tài khoản của mình để thực hành nhé.

def binary_to_number(b):
  n = 0
  for digit in b:
    n = n * 2 + int(digit)

  return n 

Đảo ngược chuỗi ký tự

Cách đơn giản nhất để đảo ngược một chuỗi là mình sẽ đi qua tất cả phần tử và cộng nó vào theo hướng ngược lại, tức là ký tự đầu tiên sẽ được cộng vào cuối cùng. 

Điều này có thể thực hiện với một hàm reverse như sau:

def reverse(self, s):
        """Helper reverse a string"""
        reverse_s = ""
        for char in s:
            reverse_s = char + reverse_s   
        
        return reverse_s

Giải bài toán với hướng tiếp cận 1

Vậy là đã rõ cách chuyển giữa số nguyên và số binary, cách đảo ngược một chuỗi ký tự rồi.

Mình có thể bắt tay vào giải bài này rồi đó, bạn nãy làm thử ở tài khoản leetcode của mình trước khi xem đáp án nha.

Một gợi ý nhỏ nữa là đề bài yêu cầu số binary của mình có 32 bit, nên sau khi chuyển từ số nguyên về số nhị phân rồi, nếu chưa đủ 32 bit thì mình cần thêm số 0 ở phía trước kết quả cho đủ 32 bit trước khi thực hiện đảo ngược thứ tự nhé.

Code

class Solution:
    def reverseBits(self, n: int) -> int:
        print(n)
        n_binary_str = ""
        n_binary_str = self.number_to_binary(n, n_binary_str)
        
        # because n in binary could not enough 32 bit then need to fill 0 until reach 32 bit
        while len(n_binary_str) < 32:
            n_binary_str = "0" + n_binary_str
        
        # reverse the order of the binary
        reverse_binary_str = self.reverse(n_binary_str)
        
        # convert back to interger with binary
        x = int(reverse_binary_str, 2)
        return x
        
        
    def number_to_binary(self, n, n_binary_str):
        """Helper convert number to binary"""
        if n >= 1:
            n_binary_str = str(n % 2) + n_binary_str
            return self.number_to_binary(n // 2, n_binary_str)
        
        return n_binary_str

    
    def binary_to_number(self, binary, n):
        """Helper convert binary to number"""
        if n >= 1:
            n_binary_str = str(n % 2) + n_binary_str
            return self.number_to_binary(n // 2, n_binary_str)
        
        return n_binary_st
    
    def reverse(self, s):
        """Helper reverse a string"""
        reverse_s = ""
        for char in s:
            reverse_s = char + reverse_s   
        
        return reverse_s

Tiếp theo mình sẽ cùng đi thêm một hướng tiếp cận khác thiên về cú pháp của Python hơn.

Hướng tiếp cận 2

Thực ra, ngay từ đầu mình có thể đi theo hướng này liền, cho nó nhanh gọn, nhưng mà mình muốn mình và các bạn đọc bài viết này có thể hiểu thêm về cách chuyển đổi giữa số nguyên và số nhị phân nên mình mới đi theo hướng kia trước. Với hướng tiếp cận 1 thì dù bạn có sử dụng ngôn ngữ nào để thực hiện bài toán thì đều có thể áp dụng được.

Chuyển số nguyên về số binary và ngược lại

Trong Python, có một hàm built-in có thể giúp mình chuyển số nguyên về số nhị phân tên là bin

>>> bin(12)
'0b1100'
>>> bin(12).replace("0b", "")
'1100'

Ngoài ra, còn một cách khác nữa có thể chuyển từ số nguyên sang số nhị phân ở dạng chuỗi bằng cách dùng hàm format với dạng binary, nó sẽ như thế này 

>>> "{0:b}".format(int(12))
'1100'

Và để chuyển ngược từ số nhị phân sang số nguyên mình có thể sử dụng hàm int có sẵn trong Python với base là 2. Hàm này mặc định có base là 10.

>>> int('1100', 2)
12
>>> int('1100', base=2)
12

Đảo ngược chuỗi ký tự​

Trong Python, có vài cách giúp mình đảo ngược một chuỗi ký tự một cách đơn giản hơn so với việc lặp qua chuỗi và cộng dồn ngược lại như cách vừa rồi

Cắt chuỗi trong Python với slicing

Chuỗi trong Python có hỗ trợ slicing, điều này giúp mình cắt lát một chuỗi bất kỳ. Với s là một chuỗi thì s[start:stop:step] sẽ cắt chuỗi từ vị trí start đến vị trí stop, với bước nhảy là step.

Các giá trị mặc định: 

– step có giá trị mặc định là 1, khi đó start có giá trị mặc định là 0, và stop có giá trị mặc định là len(s)

– khi step có giá trị là số âm, thì start sẽ có giá trị mặc định là len(s), còn stop có giá trị mặc định là – len(s) – 1

Cùng xem ví dụ: 

>>> s = "Happy Pythonning!"
>>> s[2:5] # start = 2, stop = 5, step = 1
'ppy'
>>> s[2:] # start = 2, stop = len(s), step = 1
'ppy Pythonning!'
>>> s[:5] # start = 0, stop = 5, step = 1
'Happy'
>>> s[:-1] # start = 0, stop = len(s) + (-1), step = 1
'Happy Pythonning'
>>> s[:len(s)-1] # as above
'Happy Pythonning'
>>> s[:] # start = 0, stop = len(s), step = 1
'Happy Pythonning!'
>>> s[::] # start = 0, stop = len(s), step = 1
'Happy Pythonning!'
>>> s[::-1] # start = len(s), stop = -len(s)-1, step = -1
'!gninnohtyP yppaH'
>>> s[len(s):-len(s)-1:-1] # as above
'!gninnohtyP yppaH'

Bạn có thấy mình đã đảo ngược chuỗi ở trên ở dòng nào chưa? Nó chính là s[::-1] ấy

(Xem thêm ở câu hỏi này trên StackOverflow nhé)

Giải bài toán với hướng tiếp cận 2

Hẳn là bạn đã thấy cách này nó đơn giản như thế nào rồi, và bài giải của mình chỉ đơn giản là như thế này:

class Solution:
    def reverseBits(self, n: int) -> int:
        # chuyển số nguyên về số nhị phân
        n_binary_str = bin(n).replace("0b", "")
        
        # thêm số 0 cho đủ 32 bit
while len(n_binary_str) < 32: n_binary_str = "0" + n_binary_str # đảo ngược thứ tự n_binary_str = n_binary_str[::-1] # chuyển nhị phân về số nguyên return int(n_binary_str, 2)

Tèn ten, nhìn có vẻ rất là Python rồi đấy 

Bản tối ưu từ một bạn comment bên Kipalog

Sau khi mình đăng bài viết trên Kipalog thì có một bạn comment khá hay nên mình lưu lại cách giải này để tham khảo, một vài điểm hay ở đáp án này là:

– chỉ dùng một dòng code

– dùng hàm zfill trong Python để điền số 0 phía trước cho đủ 32 bit

class Solution:
    def reverseBits(self, n: int) -> int:
        return int(bin(n)[2:].zfill(32)[::-1], 2)

Bài tập hôm nay đến đây là hết rồi, ai có cách giải nào xịn hơn thì nhớ comment bày mình với nhé. 

À, mình có tạo một danh sách các bài easy trên Leetcode mà mình thực hành ở đây, bạn có thể Clone về tài khoản leetcode của bạn để thực hành nhé.

Hi vọng bài viết sẽ hữu ích với bạn,

BeautyOnCode.

Please follow and like us:
error

Leave a Reply

Your email address will not be published. Required fields are marked *

RELATED POST

[Leetcode] 94. Binary Tree Inorder Traversal

Tuần này, mình cùng giải tiếp một bài leetcode về binary tree, 94. Binary Tree Inorder Traversal Đề bài: Given the…

Kiểm tra query params và chuyển đổi kiểu dữ liệu khi làm API với NestJS

Dạo này mình đang học một cái gì đó mới. Vì cũng đang làm việc ở backend với vai trò…

Iterable, Iterator và Generator trong Python

Chào cả nhà 🥳! Chào BeautyOnCode  🤣  Just for vui tí, thực ra đó là cách gia đình mình chào nhau…

Export docx file with python-docx in Django app

Exporting files is a frequently happen feature where the user could get their data out.  As the backend side, my…