oj.leetcode.com is an online judge website that provides quick exercise to programming tasks. This is helpful before you go for an interview for a software company. The tasks seem easier than other online judges e.g. Timus, Codeforces which focus on algorithm designs. Leetcode, however, targets small programming tasks that are more suitable for interview purposes, to see if you can actually do coding.
Source: http://oj.leetcode.com/problems/string-to-integer-atoi/
The task asks you to write the implementation of atoi function (C-version), which is to convert a string (const char *) to int. There are some other differences. It should return zero if invalid format is given. It should always return the INT_MAX (2147483647) or INT_MIN (-2147483648) if given value falls outside the range.
The idea is to loop each character and if it is a valid digit, multiply current answer by ten and add its numerical value.
The iteration will give us the O(n) complexity algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | class Solution { public: inline bool isDig(char c) { return (c >= '0') && (c <= '9'); } int atoi(const char *str) { // Note: The Solution object is instantiated only once and is reused by each test case. if (str == NULL) return 0; int len = strlen(str); // get length bool plus = true; int i; // skip spaces at the begining for (i = 0; (i < len) && (str[i] == ' '); i ++); if (i == len) return 0; char sgn = str[i]; // check sign if (sgn == '+') { plus = true; i ++; } else if (sgn == '-') { plus = false; i ++; } else if (!isDig(sgn)) { return 0; // invalid number format } long long r = 0; for (; (i < len) && (isDig(str[i])); i ++) { r *= 10; r += str[i] - 48; if (r > 2147483648) break; } if (plus) { if (r > 2147483647) return 2147483647; return r; } else { if (-r < -2147483648) return -2147483648; return -r; } } }; |
class Solution {
public:
inline bool isDig(char c) {
return (c >= '0') && (c <= '9');
}
int atoi(const char *str) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (str == NULL) return 0;
int len = strlen(str); // get length
bool plus = true;
int i;
// skip spaces at the begining
for (i = 0; (i < len) && (str[i] == ' '); i ++);
if (i == len) return 0;
char sgn = str[i];
// check sign
if (sgn == '+') {
plus = true;
i ++;
} else if (sgn == '-') {
plus = false;
i ++;
} else if (!isDig(sgn)) {
return 0; // invalid number format
}
long long r = 0;
for (; (i < len) && (isDig(str[i])); i ++) {
r *= 10;
r += str[i] - 48;
if (r > 2147483648) break;
}
if (plus) {
if (r > 2147483647) return 2147483647;
return r;
} else {
if (-r < -2147483648) return -2147483648;
return -r;
}
}
};–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Python range and xrange
Next Post: Coding Exercise - Plus One C++ - Online Judge
