Giải pháp leetcode số nguyên đảo ngược javascript

Cho một số nguyên 32 bit có dấu x, trả về x với các chữ số của nó bị đảo ngược. Nếu việc đảo ngược x khiến giá trị nằm ngoài phạm vi số nguyên 32 bit có dấu [-2^31, 2^31 - 1], thì trả về 0

Tuyên bố vấn đề lấy từ. https. //leetcode. com/problems/reverse-integer

ví dụ 1

Input: x = 123
Output: 321

ví dụ 2

Input: x = -123
Output: -321

ví dụ 3

Input: x = 120
Output: 21

Ví dụ 4

Input: x = 0
Output: 0

Hạn chế

-2^31 <= x <= 2^31 - 1

Giải trình

Đây là một vấn đề dễ dàng tương tự như đảo ngược một chuỗi. Chúng tôi chỉ có một cách tiếp cận vấn đề này

Chúng tôi liên tục loại bỏ chữ số cuối cùng của số nguyên x và thêm nó vào số nguyên đảo ngược

Chúng tôi nhận được chữ số cuối cùng bằng toán tử modulo% và xóa chữ số cuối cùng bằng cách chia số nguyên x cho 10

lastDigit = x % 10
x = x / 10

Nhưng chúng ta cần cẩn thận với trường hợp một cạnh ở đây. Trong khi đảo ngược số nguyên, chúng ta cần kiểm tra xem giá trị có dẫn đến tràn số nguyên hay không

Dựa trên ngôn ngữ lập trình khác nhau, chúng tôi có thể gặp lỗi Thời gian chạy hoặc đầu ra không mong muốn nếu trường hợp tràn số nguyên không được xử lý

Trong trường hợp Javascript và Golang, trước tiên chúng ta có thể đảo ngược số nguyên và sau đó xác minh xem giá trị có nằm trong phạm vi số nguyên hay không. Nhưng trong trường hợp của C++, chúng tôi cần xác minh nó trong mỗi lần chạy vì nó có thể gây ra lỗi Thời gian chạy

Cho một số nguyên 32-bit có dấu x, trả về x với các chữ số của nó bị đảo ngược. Nếu việc đảo ngược x khiến giá trị nằm ngoài phạm vi số nguyên 32 bit có dấu

Input: x = -123
Output: -321

2, thì hãy trả về

Input: x = -123
Output: -321

3

Ghi chú. Giả sử chúng ta đang xử lý một môi trường chỉ có thể lưu trữ các số nguyên trong phạm vi số nguyên có dấu 32 bit. [−231, 231 − 1]. Với mục đích của vấn đề này, giả sử rằng hàm của bạn trả về 0 khi tràn số nguyên bị đảo ngược

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

________số 8_______

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 ta có 1 và chúng ta muốn nối thêm 3 vào nó để nó trở thành 13, chúng ta 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