LeetCode - Reverse Integer

Trên C, làm nhanh nên thuật toán có vẻ chưa tối ưu lắm, mà lười nghĩ nên thôi :3

 int reverse(int x) {
        int result = 0;
        while(x / 10 != 0 || x % 10 != 0) {
                result = result * 10 + x % 10;
                x /= 10;
        }
        return result;
}

Code của @iamz up lên sẽ bị overflow đấy.

Solution C++

class Solution {
public:
    int reverse(int x) {
        if (!x)
            return 0;
            
        long long result = 0;
        while(x) {
            result = result * 10 + x % 10;
            x /= 10;
            if ( result > INT_MAX || result < INT_MIN )
                return 0;
        }
        
        return (int)result;
    }
};

Kết quả: https://leetcode.com/submissions/detail/36314800/

Có điều chạy chậm quá. Để coi lại

Ra là cần sử dụng thêm lib limit.h để check overflow nữa, em làm vội chả nghĩ gì

Anh cũng đâu biết đâu, chạy thử nó báo lỗi mới biết. Viết lại bằng C thì nó chạy nhanh hơn C++ tí

int reverse(int x) {
    if (!x)
            return 0;
            
    long long result = 0;
    while(x) {
        result = result * 10 + x % 10;
        x /= 10;
        if ( result > INT_MAX || result < INT_MIN )
            return 0;
    }
    
    return (int)result;
}

leetcode.com

Account Login - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Cái submission detail hình như của ai thì chỉ người nấy xem được thôi anh, em click vào nó not found
Thời gian chạy trên C thì nó chỉ ra là 4ms

Code Java cũng giống vậy mà chạy chậm quá

public class Solution {
    public int reverse(int x) {
        if (x == 0)
            return 0;
            
        long result = 0;
        while(x != 0) {
            result = result * 10 + x % 10;
            x /= 10;
            if ( result > Integer.MAX_VALUE || result < Integer.MIN_VALUE )
                return 0;
        }
        
        return (int)result;
    }
}

Phải coi lại mới được. Cái trò này vui, vọc nhiều ngôn ngữ thử xem thử nó thế nào

Xem qua solution runtime thì Java là chạy chậm nhất, trung bình mất khoảng 3s, gấp C khoảng 70-80 lần

Ừm, Java chạy hơi chậm. Hôm trước anh có comment trên FB bảo là Java chậm thì bị chửi dữ quá nên bỏ chạy luôn

Nhưng mà Java cũng có cái hay và mạnh của riêng nó.

trung bình mất khoảng 3s,

Anh đang là: Runtime: 252 ms, mà sao mỗi lần submit lại có tốc độ khác nhau ta? Cùng một code mà lại trả ra tốc độ khác nhau sau mỗi lần submit

Em không làm Java nên em cũng không rõ khoản Java lắm, còn runtime thì nó lệch khoảng bao nhiêu anh? Thường thì em thấy nỗi lần chạy runtime nó thường khác một chút (dùng python em thấy thế) còn C có lẽ do runtime nhỏ quá nên mình không thấy sự khác biệt.

Up luôn Python lên chơi

class Solution:
    # @param {integer} x
    # @return {integer}
    def reverse(self, x):
        if x == 0:
            return 0
        
        sign = 1
        if x < 0:
            x = abs(x)
            sign = -1
        
        result = 0
        while x != 0:
            result = result * 10 + x % 10
            if result > 0x7fffffff:
                return 0
            x = x / 10
        
        return sign * result

C#

public class Solution {
    public int Reverse(int x) {
        if (x == 0)
            return 0;
            
        long result = 0;
        while(x != 0) {
            result = result * 10 + x % 10;
            if ( result > Int32.MaxValue || result < Int32.MinValue )
                return 0;
            x /= 10;
        }
        
        return (int)result;
    }
}

Javascript (runtime nó ảo quá anh ạ ):

var reverse = function(x) { 
    var result = 0; 
    limit = Math.pow(2,31) - 1; 
    while(x) { 
        result = result * 10 + x % 10; 
        x = ~~(x / 10); 
        if(Math.abs(result) > limit) return 0; 
    } 
    return result; 
};

cái này dễ nhất là chuyển thành xâu rồi reverse xâu đó rồi trả về atoi của xâu đã reverse. Nếu xâu có 10 ký tự thì phải ktra ký tự đầu 3 trường hợp: lớn hơn ‘2’, nhỏ hơn ‘2’, bằng ‘2’. Trước đó phải check âm dương, nếu là số âm thì đơn giản trả về -reverse(-x), nhưng bị dính 1 con bug là x == -2147483648 thì -x cũng chính là -2147483648 nên phải tách thành trường hợp riêng nữa

ban đầu ta thử cứ tưởng nó chậm lắm ai dè quá nhanh 12ms, submit cái nữa còn 8ms.

int reverse(int x)
{
    if (x == -2147483648) return 0;
    if (x < 0) return -reverse(-x);
    std::ostringstream oss;
    oss << x;
    std::string s = oss.str();
    std::reverse(s.begin(), s.end());
    if (s.length() < 10) return atoi(s.c_str());
    if (s[0] > '2') return 0;
    if (s[0] < '2') return atoi(s.c_str());
    int y = atoi(s.c_str()+1) + 2000000000;
    return y > 0 ? y : 0;
}

Python , chuyển thành str rồi reverse, runtime mất 60ms

class Solution:
# @param {integer} x
# @return {integer}
def reverse(self, x):
    if x < 0:
        sign = -1
    else:
        sign = 1
    re = int(str(abs(x))[::-1])
    if re > 0x7fffffff:
        return 0
    else:
        return sign*re 

Sao em submit lại vẫn 60ms mà, đâu có thay đổi
Cái này vọc xem code kiểu nào cho tối ưu (cùng 1 ngôn ngữ) cũng vui đây

Anh cho em hỏi hai cái này là sao anh ?
Rồi tại sao lại overflow anh ?

!x

result > INT_MAX || result < INT_MIN

if (!x) tương đương với if (x == 0), trong C/C++ thì số 0 là false và các số còn lại là true. Phủ định của 0 là true.

Cái này là kiểm tra tràn số em. Tràn số là khi kết quả của result nhận được lớn hơn INT_MAX

result > INT_MAX || result < INT_MIN

INT_MAX là giá trị lớn nhất của kiểu int. Chi tiết em xem ở đây

http://www.cplusplus.com/reference/climits/

Mọi người xem hộ em cái này được không
Em đang làm một bài khác về chuyển đổi cơ số, nhưng kiểu em làm thì có vẻ hơi liên quan tới vấn đề này.
Chuyện là em cho dãy hết từng chữ số (digit) vào vector _baseNum, bây giờ em muốn chuyển nó thành số nguyên với thứ tự ngược lại.
VD: 1 3 2 5 3 là vector _baseNum, em cần đưa nó về số nguyên _num thành 35231

Đây là code của em

        int length = _baseNum.size();

        
        for(int i = 0; i < length; i++)
        {
            _num += _baseNum[i] * (int)std::pow(10, i);
            std::cout << _num << '\n'; // à, cái này là để dubug :smile: 
        }

Em thử số xâu nhị phân, nhưng tại sao chữ số cuối đúng là số 1 mà nó cứ thành số 0.
VD: 1101111 nó đổi thành 1111010

Đây là giá trị khi debug

_baseNum: 1 1 0 1 1 1 1
1
11
11
1101
11010 // Tự nhiên 1101 + 10000, nó lại thành 11010 (hàng đơn vị lẽ ra phải là 1)
111010
1111010

do hàm pow khi convert thành int sẽ không chính xác.
Em có thể fix bằng cách viết một hàm pow riêng cho kiểu int hoặc dùng floor().