(分类讨论, 情景模拟, 区间类型) lintcode 640. One Edit Distance, leetcode 388，intcode 645. 13. 12. 659. 660...

class Solution {
public:
    /**
     * @param s: a string
     * @param t: a string
     * @return: true if they are both one edit distance apart or false
     */
    bool isOneEditDistance(string &s, string &t) {
        // write your code here
        if(s.size() > t.size())
            swap(s, t);   //保证t比s长
        int diff = t.size() - s.size();
        if(diff > 1)
            return false;
        if(diff == 1){
            for(int i=0; i<s.size(); i++){
                if(t[i] != s[i])
                    return (s.substr(i) == t.substr(i+1));   //t去掉索引为i的字符之后剩余的子串和s是否相同
            }
            return true;
        }
        if(diff == 0){
            int cnt = 0;
            for(int i=0; i<s.size(); i++){
                if(s[i] != t[i])
                    cnt ++;
            }
            return (cnt==1);
        }
    }
};

// Forward declaration of the read4 API.
int read4(char *buf);  //return the actual number of characters read

class Solution {
public:
    /**
     * @param buf destination buffer
     * @param n maximum number of characters to read
     * @return the number of characters read
     */
    char buffer[4];
    int bufferPtr = 0, bufferCnt = 0;  //队列的头指针和尾指针 
    int read(char *buf, int n) {
        // Write your code here
        
        int ptr = 0;
        while(ptr < n){
            if(bufferPtr == bufferCnt){
                //队列为空,进队
                bufferCnt = read4(buffer);
                bufferPtr = 0;
            }
            if(bufferCnt == 0)  //没有数据读入就退出
                break;
            while(ptr < n && bufferPtr < bufferCnt){
                buf[ptr] = buffer[bufferPtr];
                ptr++;
                bufferPtr++;
            }
        }
        return ptr;
    }
};

class Solution {
public:
    /*
     * @param strs: a list of strings
     * @return: encodes a list of strings to a single string.
     */
    string encode(vector<string> &strs) {
        // write your code here
        string ans;
        for(int i=0; i<strs.size(); i++){
            string s = strs[i];
            for(int j = 0; j<s.size(); j++){
                if(s[j] == ':')
                    ans += "::";   //加一个转义符,把所有的：变为：：
                else
                    ans += s[j];
            }
            ans += ":;";    //一个字符串结束后加上分隔符
        }
        return ans;
    }

    /*
     * @param str: A string
     * @return: dcodes a single string to a list of strings
     */
    vector<string> decode(string &str) {
        // write your code here
        vector<string> ans;
        string item;
        int i = 0;
        while(i<str.size()){
            if(str[i] == ':'){
                if(str[i+1] == ';'){
                    // ; 为分隔符
                    ans.push_back(item);
                    item = "";
                    i += 2;
                }
                else{
                    // ：为转义符
                    item += str[i+1];
                    i += 2;
                }
            }
            else{
                item += str[i];
                i++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    
    vector<string> split(string& str, char c){
        char *cstr, *p;
        vector<string> ret;
        cstr = new char[str.size() + 1];
        strcpy(cstr, str.c_str());  //将str拷贝给cstr
        p = strtok(cstr, &c); //将cstr指向的字符数组以c来分割
        while(p!=NULL){
            ret.push_back(p);
            p = strtok(NULL, &c);
        }
        return ret;
    }
    
    int lengthLongestPath(string input) {
        int ans = 0;
        vector<string> lines = split(input, '\n');  //用\n来分隔字符串
        map<int, int> level_size;
        level_size[-1] = 0;  // 初始化在第0层
        
        for(int i=0; i<lines.size(); i++){
            string line = lines[i];
            int level = line.find_last_of('\t') + 1;   
            // 查找字符串中最后一个出现\t。有匹配，则返回匹配位置；否则返回-1.
            int len = (line.substr(level)).size();  //第level层字符串的长度
        
            if(line.find('.') != string::npos){   //if(s.find('.') != -1)
                //找到. 说明是文件
                ans = max(ans, level_size[level - 1] + len);
            }
            else{
                //每一行要加/ 故+1
                level_size[level] = level_size[level - 1] + len + 1;  //前缀和优化
            }
        }
        return ans;
    }
};

// Forward declaration of the knows API.
bool knows(int a, int b);  //return whether A knows B
//if true, A is not celebrity
//if false, B is not celebrity
class Solution {
public:
    /**
     * @param n a party with n people
     * @return the celebrity's label or -1
     */
    int findCelebrity(int n) {
        // Write your code here
        int ans = 0;
        for(int i=1; i<n; i++){
            if(knows(ans, i))
                //第0个人认识第i个人说明第0个人不是celebri
                ans = i;  //每次去掉一个人
                //最终得到一个人
        }
        
        //对上面最后剩下的人做一次名人检验
        for(int i=0; i<n; i++){
            if(ans!=i && knows(ans, i))
                return -1;
            if(ans != i && !knows(i, ans))
                return -1;
        }
        return ans;
    }
};

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> mp = {{'I',1}, {'V', 5},  {'X', 10}, {'L', 50},  {'C', 100}, {'D', 500}, {'M', 1000}};
        int r = mp[s[0]];
        for(int i=1; i<s.size(); i++){
            r += mp[s[i]];
            if(mp[s[i-1]] < mp[s[i]])
                r = r - 2*mp[s[i-1]];    
        }
        return r;
    }
};

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<string, int> mp = {{"I",1}, {"V", 5},  {"X", 10}, {"L", 50},  {"C", 100}, {"D", 500}, {"M", 1000}};
        int r = mp[s.substr(0, 1)];
        for(int i=1; i<s.size(); i++){
            r += mp[s.substr(i, 1)];
            if(mp[s.substr(i-1, 1)] < mp[s.substr(i, 1)])
                r -= 2*mp[s.substr(i-1, 1)];    
        }
        return r;
    }
};

class Solution {
public:
    string intToRoman(int num) {
        vector<int> value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5,4,1};
        vector<string> roman = {"M", "CM", "D","CD","C","XC","L","XL","X","IX","V","IV",
"I"};
        string str;
        int i = 0;
        while(i<value.size()){
            if(num >= value[i]){
                num -= value[i];
                str += roman[i];
            }
            else
                i++;
        }
        return str;
    }
};

class Solution {
public:
    /*
     * @param nums: a sorted integer array
     * @param lower: An integer
     * @param upper: An integer
     * @return: a list of its missing ranges
     */
    string getString(long long st, long long ed){
        //左端点st，右端点ed
        if(st > ed)
            return "";
        if(st == ed)
            return to_string(st);
        return to_string(st) + "->" + to_string(ed);
    }
    vector<string> findMissingRanges(vector<int> &nums, int lower, int upper) {
        // write your code here
        vector<string> ans;
        string tmp;
        
        vector<long long> nums2;
        for(int i=0; i<nums.size(); i++)
            nums2.push_back(nums[i]);
        
        if(nums2.empty()){
            tmp = getString(lower, upper);
            if(tmp != "")
                ans.push_back(tmp);
            return ans;
        }
        
        tmp = getString(lower, nums2[0]-1);
        if(tmp!="")
            ans.push_back(tmp);
        
        for(int i=1; i<nums2.size(); i++){
            tmp = getString(nums2[i-1]+1, nums2[i]-1);
            if(tmp != "")
                ans.push_back(tmp);
        }
        
        tmp = getString(nums2.back()+1, upper);
        if(tmp != "")
            ans.push_back(tmp);
        
        return ans;
    }
};

class Solution {
public:
    static bool cmp(const )
    
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if(intervals.empty())
            return res;
        sort(intervals.begin(), intervals.end());
        //sort(intervals.begin(), intervals.end(), cmp);
        int start = intervals[0][0], end = intervals[0][1];
        intervals.push_back({INT_MAX, INT_MAX});
        
        for(int i=1; i<intervals.size(); i++){
            vector<int> interval = intervals[i];
            if(interval[0] <= end){
                if(interval[1] > end)
                    end = interval[1];
            }
            else{
                res.push_back({start, end});
                start = interval[0];
                end = interval[1];
            }
            
        }
        return res;
    }
};

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        // write your code here
        vector<Interval> ans;
        int st;
        for(st=0; st<intervals.size() && intervals[st].start < newInterval.start; st++)    
            ans.push_back(intervals[st]);
        
        if(!ans.empty() && ans.back().end >= newInterval.start)
            ans.back().end = max(ans.back().end, newInterval.end);
        else
            ans.push_back(newInterval);
            
        for(int i=st; i<intervals.size(); i++){
            if(ans.back().end >= intervals[i].start)
                ans.back().end = max(ans.back().end, intervals[i].end);
            else
                ans.push_back(intervals[i]);
        }
        
        return ans;
    }
};