Đảo ngược bit leetcode giải pháp javascript

Trong bài đăng này, chúng tôi sẽ giải quyết vấn đề số nguyên đảo ngược từ leetcode và tính toán độ phức tạp của thời gian và không gian. Hãy bắt đầu nào

Câu hỏi có thể được tìm thấy tại vấn đề số nguyên đảo ngược leetcode

Vấn đề nói rằng chúng tôi được cung cấp một số nguyên có chữ ký 32 bit và chúng tôi cần đảo ngược các chữ số của nó

• Nếu giá trị tuyệt đối của số vượt quá 231 sau khi đảo số, chúng ta cần trả về 0

Chúng tôi sẽ thảo luận về hai giải pháp trong bài viết này và so sánh sự phức tạp về thời gian và không gian của chúng

• Đảo ngược dựa trên chuỗi
• Đảo ngược dựa trên số

Trong phương pháp này, chúng tôi sẽ chuyển đổi số thành một chuỗi và đảo ngược nó. Chúng tôi cũng sẽ sử dụng một số phương thức sẵn có trong JavaScript để thao tác chuỗi và phép toán

Ý tưởng rất đơn giản

• Lấy giá trị tuyệt đối của số
• chuyển đổi thành chuỗi
• tạo một mảng ký tự
• đảo ngược nó lại
• tham gia nó trở lại một chuỗi
• phân tích chuỗi thành một số (không bắt buộc trong JavaScript)

Hãy xem một triển khai đơn giản của logic trên

var reverse = function(x) {
    
  const reversedInt = parseInt(Math.abs(x).toString().split('').reverse().join(''));
  
  if (reversedInt > 2**31) return 0;
  
  return reversedInt * Math.sign(x);
    
};

Không có gì lạ mắt xảy ra ở đây, Hãy xem xét giải pháp

Dòng đầu tiên có hầu hết logic ở đây. Chúng tôi bao bọc mọi thứ bên trong một hàm parseInt, (để chuyển đổi chuỗi thành số nguyên), bây giờ, các bước như sau

• ta lấy giá trị tuyệt đối của số
• chuyển đổi số thành một chuỗi
• tách chuỗi và chuyển đổi nó thành một mảng
• đảo ngược mảng
• nối các phần tử của mảng

điều này mang lại cho chúng tôi số bị đảo ngược ở định dạng chuỗi và sau đó parseInt chuyển đổi nó thành một số

Tiếp theo, chúng tôi kiểm tra xem số nguyên bị đảo ngược có lớn hơn giới hạn đã cho hay không, nếu có, chúng tôi trả về 0 (các ràng buộc được đề cập)

Ở dòng cuối cùng, ta kiểm tra dấu của số X ban đầu rồi nhân với số bị đảo ngược để được số nguyên cùng dấu

Đây là tất cả những gì chúng tôi cần để giải quyết vấn đề, sau khi chúng tôi gửi nó, đây là số liệu thống kê

Status: Accepted
Runtime: 68ms
Memory: 35.8MB

Thời gian và không gian phức tạp

Chúng tôi sử dụng một loạt các phương thức có độ phức tạp tuyến tính, nhưng chúng được xâu chuỗi chứ không phải lồng nhau, vì vậy thời gian chạy sẽ phụ thuộc vào số lượng chữ số trong đầu vào. Chúng ta có thể nói O(len X)

Độ phức tạp của không gian

Chúng tôi có một số làm đầu vào, sử dụng một biến khác để lưu trữ số bị đảo ngược, do đó độ phức tạp của không gian là không đổi, O(1)

Bây giờ, chúng ta không cần phải chuyển đổi rõ ràng chuỗi thành số, JavaScript có thể tự động làm điều đó cho chúng ta (tất nhiên là có tính thêm phí)

Nhìn vào đoạn trích dưới đây

var reverse = function(x) {
    
    const reversedInt = Math.abs(x).toString().split('').reverse().join('');
    
    if (reversedInt > 2**31) return 0;
    
    return reversedInt * Math.sign(x);
    
};

Khi chúng tôi chạy cái này, đây là số liệu thống kê

Status: Accepted
Runtime: 84ms
Memory: 35.8MB

Bây giờ, tại sao nó hoạt động? . Chuỗi được chuyển đổi thành một số khi chúng ta so sánh nó với 231 và nhân với dấu. Đọc thêm

Thời gian và không gian phức tạp

Chà, về mặt tiệm cận thì nó vẫn như vậy, tuy nhiên, việc truyền kiểu ẩn sẽ kéo dài thêm thời gian để thực thi, điều mà chúng ta thấy trong số liệu thống kê

Trong phương pháp này, chúng tôi sẽ chọn từng chữ số của một số và đảo ngược số mà không chuyển đổi nó thành chuỗi

Ý tưởng rất đơn giản

• kiểm tra xem số có nhỏ hơn 0 không
• nếu số nhỏ hơn 0, lấy giá trị tuyệt đối của nó
• khởi tạo một biến reversed với 0
• lặp qua số cho đến khi nó nhỏ hơn hoặc bằng 0 (tại một thời điểm nó sẽ như vậy)
• bây giờ, nhân biến bị đảo ngược với 10 và thêm chữ số cuối cùng của số vào nó
• xóa chữ số tận cùng của X
• khi vòng lặp kết thúc, chúng ta sẽ có số bị đảo ngược
• nếu số bị đảo ngược lớn hơn 231, trả về 0
• nếu không, hãy trả về số nguyên bị đảo ngược với dấu thực của nó

Hãy xem một triển khai đơn giản của logic trên

var reverse = function(x) {
    const isNegative = x< 0 ? true : false;
    
    if (isNegative){
        x = x *-1;
    }
    
    let reversed = 0;
    while(x>0){
        reversed = (reversed * 10) + (x % 10);
        
        x = parseInt(x/10);
    }
    
    if(reversed > 2**31){
        return 0;
    }
    
    return isNegative? reversed * -1 : reversed;
};

Vì vậy, như đã thảo luận ở trên, trước tiên, chúng tôi xác định xem số đó có âm không và lấy giá trị tuyệt đối của số

Lặp đi lặp lại lấy chữ số cuối cùng của số và thêm nó vào số bị đảo ngược. Ví dụ: nếu chúng tôi có 1 và chúng tôi muốn nối thêm 3 với nó để nó trở thành 13, chúng tôi sẽ nhân 1 với 10 và thêm 3 vào nó. Điều này đúng với bất kỳ số nào, nếu chúng ta cần thêm bất kỳ thứ gì vào cuối số, chúng ta nhân với 10 và cộng số cần thêm

Chia cho 10 và lấy số nguyên, chỉ cần xóa chữ số cuối cùng của số đó. ( Hãy tự mình thử )

Tiếp theo, logic khá đơn giản nếu số bị đảo ngược lớn hơn 231 trả về 0 nếu không thì trả về số bị đảo ngược có dấu

Đây là số liệu thống kê mà chúng tôi chạy mã này

Status: Accepted
Runtime: 72ms
Memory: 35.9MB

Thời gian và không gian phức tạp

Thật không may, chúng tôi đã không cải thiện độ phức tạp của thời gian. Đó là O(len X) ( lưu ý vòng lặp chạy len X lần). Tương tự với không gian, O(1)

Vì vậy, chúng tôi đã giải quyết vấn đề số nguyên đảo ngược bằng 2 phương pháp, mặc dù độ phức tạp là như nhau, thật tốt khi biết cả hai cách tiếp cận. Trong một cuộc phỏng vấn, bạn có thể được yêu cầu không sử dụng các phương thức Toán học/Chuỗi/Mảng, sau đó bạn có thể sử dụng phương pháp đảo ngược dựa trên số nguyên

Tôi hy vọng bạn thích giải quyết câu hỏi này. Đây là nó dành cho cái này, bạn có thể tìm thấy mã nguồn hoàn chỉnh cho bài đăng này trên Github Repo của tôi. Hẹn gặp lại bạn trong lần sau

Đây rồi các bạn, bạn đã làm cho nó đến cuối bài viết. Đăng ký kênh youtube của tôi để cập nhật thường xuyên. Theo dõi tôi trên twitter, gửi thư cho tôi hoặc để lại nhận xét tại đây nếu bạn vẫn còn thắc mắc và tôi sẽ cố gắng hết sức để giúp bạn. Cảm ơn