all articles

leetcode war 8 - String to Integer (atoi)

2016-10-10 @sunderls

leetCode

https://leetcode.com/problems/string-to-integer-atoi/

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

analysis

Firstly we have to list up all the possible forms of an integer(in C), what I can think of is:

example desc
"120", "+120" decimal integer
"-120" negative integer
"0x120" "0X120" hexadecimal integer
"0120" octal integer

and there are also postfix that needs attention.

post fix desc
u, U unsigned number,
l, L long int, which use 4 bytes, without l , integers use only 2 bytes.

based on the postfix above, numbers maybe overflowed, we should return what ? 0 ?

For those strings that cannot be converted, we return 0;

We just traverse the string, and do the calculation at the same time.

Coding

var myAtoi = function(str) {
    var result = 0;
    var sign  = 1;
    var countOfSign = 0;
    var i = 0;
    var char = null;
    var base = 10;

    char = str[i];
    if (char === '+' || char === '-'){
        countOfSign++;
        if (char === '-'){
            sign = -1;
        }
    } else if (char >= '0' || char <= '9'){
        if (char === '0'){
            base = 8;
        }
        result = result * base + (char - '0');
    } else {
        return result;
    }

    i++;

    while (i < str.length){
        char = str[i];
        if (i - countOfSign === 0 && char === '0'){
            base = 8;
        } else if (i - countOfSign === 1 && (char === 'x' || char === 'X')){
            base = 16;
        } else if (char >= '0' || char <= '9'){
            result = result * base + (char - '0');
        } else {
            break;
        }
        i++;
    }
    return result * sign;
};

Above one get right result but misses handling of postfix-l, and u, let's fix that.

When l or u are encountered, update the max & min;

/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
    var result = 0;
    var sign  = 1;
    var countOfSign = 0;
    var i = 0;
    var char = null;
    var base = 10;
    var isUnsigned = false;
    var isLong = false;

    var MAX_INT = Math.pow(2, 15) - 1;
    var MIN_INT = -Math.pow(2, 15);

    char = str[i];
    if (char === '+' || char === '-'){
        countOfSign++;
        if (char === '-'){
            sign = -1;
        }
    } else if (char >= '0' && char <= '9'){
        if (char === '0'){
            base = 8;
        }
        result = result * base + (char - '0');
    } else {
        return result;
    }

    i++;

    while (i < str.length){
        char = str[i];
        if (i - countOfSign === 0 && char === '0'){
            base = 8;
        } else if (i - countOfSign === 1 && (char === 'x' || char === 'X')){
            base = 16;
        } else if (char >= '0' && char <= '9'){
            result = result * base + (char - '0');
        } else if ((char === 'u' || char === 'U') && !isUnsigned){
            isUnsigned = true;
        } else if ((char === 'l' || char === 'L') && !isLong){
            isLong = true;
        } else {
            break;
        }
        i++;
    }

    if (isLong){
        MAX_INT = Math.pow(2, 31) - 1;
        MIN_INT = -Math.pow(2, 31);
    }

    if (isUnsigned){
        if (sign === -1){
            return 0;
        }

        MAX_INT = MAX_INT - MIN_INT;
        MIN_INT = 0;
    }

    result = result * sign;
    if (result < MIN_INT || result > MAX_INT){
        return 0;
    } else {
        return result;
    }
};

console.assert(myAtoi("011") === 9);
console.assert(myAtoi("-011") === -9);
console.assert(myAtoi("0") === 0);
console.assert(myAtoi("11") === 11);
console.assert(myAtoi("-11") === -11);
console.assert(myAtoi("0x11") === 17);
console.assert(myAtoi("-0x11") === -17);
console.assert(myAtoi("32767") === 32767);
console.assert(myAtoi("32768") === 0);
console.assert(myAtoi("32768u") === 32768);
console.assert(myAtoi("32768l") === 32768);
console.assert(myAtoi("32768l") === 32768);

But it failed passing leetcode, seems that my understanding of the problem is wrong.

Case By Case debugging

  1. for "010", 10 is expected, by we offer think it as octal 8. which means we don't consider octal thing.
  2. for " 010", 10 is expected, so we needs to skip white space;
  3. for "+-2", 0 is expected.
  4. for "2147483648" , 2147483647 is expected, so return MAX/MIN when overflowed rather than 0.
var myAtoi = function(str) {
    var result = 0;
    var sign  = 1;
    var i = 0;
    var char = null;
    var base = 10;
    var isStarted = false;

    var MAX_INT = Math.pow(2, 31) - 1;
    var MIN_INT = -Math.pow(2, 31);

    while (i < str.length){
        char = str[i];
        if ((char >= '0' && char <= '9')){
            isStarted = true;
            result = result * base + (char - '0');
        } else if ((char === '+' || char === '-') && !isStarted){
            isStarted = true;
            if (char === '-'){
                sign = -1;
            }
        } else if (!(char === ' ' && !isStarted)){
            break;
        }
        i++;
    }

    return Math.min(Math.max(result * sign, MIN_INT), MAX_INT);
};

It passed at 135ms, top 40% out of javascript submission.

Honestly, this is not a very much algorithm problem I think.