[Lintcode] 53. Reverse Words in a String

一看到題目, 直覺就是用 stack 去實作
class Solution {
public:
    /*
     * @param s: A string
     * @return: A string
     */
    string reverseWords(string &s) {
        // write your code here
        stack<string> strStack;
        string word;
       
        string::iterator iter;
        for (iter = s.begin(); iter != s.end(); iter++) {
            if (' ' == *iter) {
                if (0 != word.length()) {
                    strStack.push(word);
                    word.erase();
                }
            }
            else {
                word.push_back(*iter);
            }
        }
       
        if (0 != word.length()) {
            strStack.push(word);
        }
       
        string result;
       
        while(! strStack.empty()) {
            if (0 != result.length()) {
                result.push_back(' ');
            }
            result.append(strStack.top());
            strStack.pop();
        }
       
        return result;
    }
};

[Lintcode] 13. strStr

只想到用暴力解, 兩個迴圈去掃描字串

class Solution {
public:
    /*
     * @param source: source string to be scanned.
     * @param target: target string containing the sequence of characters to match
     * @return: a index to the first occurrence of target in source, or -1  if target is not part of source.
     */
    int strStr(const char *source, const char *target) {
        // write your code here
        if (NULL == source || NULL == target) {
            return -1;
        }
        
        if ('\0' == *source && '\0' == *target) {
            return 0;
        }
        
        int srcIdx = 0;
        
        while ('\0' != source[srcIdx]) {
            bool isMatch = true;
            int srcTestIdx = srcIdx, tgtIdx = 0;
            
            while ('\0' != target[tgtIdx]) {
                if (target[tgtIdx] != source[srcTestIdx]) {
                    isMatch = false;
                    break;
                }
                srcTestIdx++;
                tgtIdx++;
            }
            
            if (isMatch) {
                return srcIdx;
            }
            
            srcIdx++;
        }
        
        return -1;
    }
};

[Leetcode] 65. Valid Number

解法本身不難, 但是要想清楚數字的規則

{空格}{+/-}{整數或浮點數}{e}{+/-}{整數}{空格}

class Solution {
public:
    enum State {
        PRE_SPACE,
        SIGN,
        BEFORE_PT_NUM,
        POINT,
        AFTER_PT_NUM,
        EXP,
        AFTER_EXP_SIGN,
        AFTER_EXP_NUM,
        POST_SPACE
    };
    
    bool isNumber(string s) {
        bool flag[9] = {false};
        State state = PRE_SPACE;
        
        for (std::string::iterator iter = s.begin() ; iter != s.end() ; iter ++) {
            switch (state) {
                case PRE_SPACE:
                    if (' ' == *iter) {
                        state = PRE_SPACE;
                    }
                    else if ('+' == *iter || '-' == *iter) {
                        state = SIGN;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else if ('0' <= *iter && '9' >= *iter) {
                        state = BEFORE_PT_NUM;
                    }
                    else if ('.' == *iter) {
                        state = POINT;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else {
                        return false;
                    }
                    
                    flag[state] = true;
                    break;
                case SIGN:
                    if ('0' <= *iter && '9' >= *iter) {
                        state = BEFORE_PT_NUM;
                    }
                    else if ('.' == *iter) {
                        state = POINT;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else {
                        return false;
                    }
                    
                    flag[state] = true;
                    break;
                case BEFORE_PT_NUM:
                    if ('0' <= *iter && '9' >= *iter) {
                        state = BEFORE_PT_NUM;
                    }
                    else if ('.' == *iter) {
                        state = POINT;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else if ('e' == *iter) {
                        state = EXP;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else if (' ' == *iter) {
                        state = POST_SPACE;
                    }
                    else {
                        return false;
                    }
                    break;
                case POINT:
                    if ('0' <= *iter && '9' >= *iter) {
                        state = AFTER_PT_NUM;
                    }
                    else if ('e' == *iter) {
                        state = EXP;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else if (' ' == *iter) {
                        state = POST_SPACE;
                    }
                    else {
                        return false;
                    }
                    break;
                case AFTER_PT_NUM:
                    if ('0' <= *iter && '9' >= *iter) {
                        state = AFTER_PT_NUM;
                    }
                    else if ('e' == *iter) {
                        state = EXP;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else if (' ' == *iter) {
                        state = POST_SPACE;
                    }
                    else {
                        return false;
                    }
                    break;
                case EXP:
                    if ('+' == *iter || '-' == *iter) {
                        state = AFTER_EXP_SIGN;
                        if (flag[state]) {
                            return false;
                        }
                    }
                    else if ('0' <= *iter && '9' >= *iter) {
                        state = AFTER_EXP_NUM;
                    }
                    else {
                        return false;
                    }
                    break;
                case AFTER_EXP_SIGN:
                    if ('0' <= *iter && '9' >= *iter) {
                        state = AFTER_EXP_NUM;
                    }
                    else {
                        return false;
                    }
                    break;
                case AFTER_EXP_NUM:
                    if ('0' <= *iter && '9' >= *iter) {
                        state = AFTER_EXP_NUM;
                    }
                    else if (' ' == *iter) {
                        state = POST_SPACE;
                    }
                    else {
                        return false;
                    }
                    break;
                case POST_SPACE:
                    if (' ' == *iter) {
                        state = POST_SPACE;
                    }
                    else {
                        return false;
                    }
                    break;
                default:
                    return false;
            }
            
            flag[state] = true;
        }
        
        if ((BEFORE_PT_NUM == state || POINT == state || AFTER_PT_NUM == state || AFTER_EXP_NUM == state || POST_SPACE == state) &&
            (flag[BEFORE_PT_NUM] || flag[AFTER_PT_NUM])) {
            return true;
        }
        return false;
    }

};