Mọi người giải rồi thảo luận cho vui nhé, Đạt chọn random.
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Cài đặt theo mẫu dưới
class Solution {
public:
int reverse(int x) {
}
};
Mọi người giải rồi thảo luận cho vui nhé, Đạt chọn random.
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Cài đặt theo mẫu dưới
class Solution {
public:
int reverse(int x) {
}
};
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;
}
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ó.
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 ?
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
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().