String

• Longest Substring Without Repeating Characters

  找出一个字符串中最长的 没有重复字符的字符串 要点就是这个begin的指针

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> wtf(256, -1);
        int max_len=0;
        int begin=-1;
        for (int i=0;i<s.length();i++){
            if (wtf[s[i]]>begin){
                begin=wtf[s[i]];
            }
            wtf[s[i]]=i;
            max_len=max(max_len,i-begin);
        }
        return max_len;
    }
};

• Roma to Integer (罗马人的智慧）

 int romanToInt(string s) {
    unordered_map<char, int> T = { { 'I' , 1 },
                                   { 'V' , 5 },
                                   { 'X' , 10 },
                                   { 'L' , 50 },
                                   { 'C' , 100 },
                                   { 'D' , 500 },
                                   { 'M' , 1000 } };                               
   int sum = T[s.back()];
   for (int i = s.length() - 2; i >= 0; --i) {
       if (T[s[i]] < T[s[i + 1]]){
           sum -= T[s[i]];
       }
       else{
           sum += T[s[i]];
       }
   } 
   return sum;
}

• Integer to Roma

string intToRoman(int num) {
        string M[] = {"", "M", "MM", "MMM"};
        string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    }

• ZigZag Convert https://leetcode.com/problems/zigzag-conversion/#/description

  so the gist of this question is how we made down when top and up at bottom, so someone use step, when you at top make step -1, when you at bottom make step 1.

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows<=1){
            return s;
        }
        string zigzag[numRows];
        int row=0,step=1;
        for(int i=0;i<s.size();i++){
            zigzag[row]+=s[i];
            if(row==0){
                step=1;
            }
            if(row==numRows-1){
                step=-1;
            }
            row+=step;
        }
        s.clear();
        for(int j=0;j<numRows;j++){
            s+=zigzag[j];
        }
        return s;
    }
};

• Reverse Words in a String https://leetcode.com/problems/reverse-words-in-a-string/#/description (reverse twice)

class Solution {
public:
    void reverseWords(string &s) {

        if(s.empty()){
            return;
        }
        //delete the lead and trail space

        while(s[0]==' ') s.erase(0,1);
        reverse(s.begin(),s.end());
        while(s[0]==' ') s.erase(0,1);

        int beg=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==' '){
                reverse(s.begin()+beg,s.begin()+i);
                while(s[i+1]==' ') s.erase(i+1,1);
                beg=i+1;
            }
        }
        //reverse the last you unable to reverse in for loop
        reverse(s.begin()+beg, s.end());
        return;
    }
};