lc handbook

因为面试的事情耽搁以至好久没刷题，很是惭愧，感觉像是借着面试的幌子逃避，但几次面试直到onsite，毕竟第一次正式在美国面试，在等待过程中，心里也是百感交集，都没有办法静下心来刷题，虽然不应该，但也毕竟是经历，今天是周一，在上周五面完最后一轮后，心中惴惴不安，不知道这几天会不会有消息。。只能继续等待

String的题：
String是不可以改的，如果要进行inplace操作需要转为char array后进行
note: 这里的Character.isLetterOrDigit()这个函数的用法，这里字面意思，是非letter和digit时ignore

125. Valid Palindrome

int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < j && !Character.isLetterOrDigit(s.charAt(i))){
                i++;
            }
            while (i < j && !Character.isLetterOrDigit(s.charAt(j))){
                j--;
            }
            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                return false;
            }
            i++;
            j--;
        }

8. String to Integer (atoi)

对这些chararcter的api都不熟悉

Character.isWhitespace()
Character.isDigit()
Character.getNumericValue(); 当然也可以用 while (str[i] >= '0' && str[i] <= '9')这样来判断，用str[i] - '0'来取值

//version1
int i = 0, n = str.length();
        while (i < n && Character.isWhitespace(str.charAt(i))) {
            i++;
        }
        int sign = 1;
        if (i < n && str.charAt(i) == '+') {
            i++;
        } else if (i < n && str.charAt(i) == '-') {
            sign = -1;
            i++;
        }
        int num = 0;
        while (i < n && Character.isDigit(str.charAt(i))) {
            int digit = Character.getNumericValue(str.charAt(i));
            if (num > maxDiv10 || num == maxDiv10 && digit >= 8) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            num = num * 10 + digit;
            i++;
        }
        return sign * num;

//version2
int atoi(const char *str) {
    int sign = 1, base = 0, i = 0;
    while (str[i] == ' ') { i++; }
    if (str[i] == '-' || str[i] == '+') {
        sign = 1 - 2 * (str[i++] == '-'); 
    }
    while (str[i] >= '0' && str[i] <= '9') {
        if (base >  INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) {
            if (sign == 1) return INT_MAX;
            else return INT_MIN;
        }
        base  = 10 * base + (str[i++] - '0');
    }
    return base * sign;
}

65. Valid Number
    .trim() omit the leading and trailing whitespace
    在trim过后分4种case：
    1. decimal:前面没有'e' 和 '.'
    2. e:前面没有'e', & 前面必须有num
    3. num
    4. sign:只出现在第一位或者e的后一位

        s = s.trim();
        boolean pointSeen = false;
        boolean eSeen = false;
        boolean numberSeen = false;
        for(int i=0; i<s.length(); i++) {
            if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
                numberSeen = true;
            } else if(s.charAt(i) == '.') {
                if(eSeen || pointSeen)
                    return false;
                pointSeen = true;
            } else if(s.charAt(i) == 'e') {
                if(eSeen || !numberSeen)
                    return false;
                numberSeen = false;
                eSeen = true;
            } else if(s.charAt(i) == '-' || s.charAt(i) == '+') {
                if(i != 0 && s.charAt(i-1) != 'e')
                    return false;
            } else
                return false;
        }
        return numberSeen;

3. Longest Substring Without Repeating Characters
   two pointers
   hashset to record max substring

Set<Character> set = new HashSet<>();
        while (j < s.length()) {
            if (set.contains(s.charAt(j))) {
                set.remove(s.charAt(i));
                i++;
            } else {
                set.add(s.charAt(j));
                j++;
                max = Math.max(max, set.size());
            }
        }