Leetcode 392（会） 20注意细节 * 12 151 6 71

12. Integer to Roman

1.

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

2.

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

151. Reverse Words in a String

class Solution {
private:
    void reverse(string& s, int start, int end){
        while(start <= end){
            swap(s[start], s[end]);
            start++;
            end--;
        }
    }
public:
    string reverseWords(string s) {
        //delete all the extra space in the old string
        string newString;
        for(int i=0; isize(); i++){
            if((i==0 && s[i]==' ') || (i!=0 && s[i]==s[i-1] && s[i] == ' ')){
                continue;
            }else{
                newString.push_back(s[i]);
            }
        }
 
        while(newString[newString.size()-1] == ' '){
            newString.resize(newString.size()-1);
        }
 
        reverse(newString, 0, newString.size()-1);
        int start = 0;
        for(int i=0; i<=newString.size(); i++){
            if(i==newString.size() || newString[i] == ' '){
                reverse(newString, start, i-1);
                start = i+1;
            }
        }
 
        return newString;
    }
};

1.这道题首先要把多余的空格去掉

2.出现的错误：

1）在写reverse函数的时候，要写string& s, 不要把&忘掉

2）每个单词进行翻转的时候，不要忘了判断最后一个词，因为最后一个词的后面没有空格，所以要加一个条件i==newString.size()

6. Zigzag Conversion

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        int dif = 2*(numRows-1);
        string res;
        int n = s.size();
 
        for(int currRow=0; currRow < numRows; currRow++){
            int index = currRow;
            while(index < n){
                res += s[index];
 
                if(currRow != 0 && currRow != numRows-1){
                    int charBewtween = dif - 2*currRow;
                    int secondIndex = index + charBewtween;
                    if(secondIndex < n)
                        res += s[secondIndex];
                }
 
                index += dif;
            }
        }
 
        return res;
 
    }
};

有基本思路：把每一组‘z'看成一个组，依次读取（像‘A-H’）

问题：

1.除了每组第一个数(如A， I)，其余每一行都会有两个这一组的数(如B和H)

要确定好函数关系

392. Is Subsequence

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i=0, j=0;
        while(isize() && jsize()){
            if(s[i] == t[j]){
                i++;
            }
            j++;
        }
        return i == s.size();
    }
};

20. Valid Parentheses

class Solution {
private:
    char leftOf(char ch){
        if(ch == ')') return '(';
        else if(ch == ']') return '[';
        else return '{';
    }
public:
    bool isValid(string s) {
        stack<char> stk;
        for(char ch:s){
            if(ch == '(' || ch=='[' || ch =='{'){
                stk.push(ch);
            }else{
                if(!stk.empty() && leftOf(ch) == stk.top()){
                    stk.pop();
                }else{
                    return false;
                }
            }
        }
        return stk.empty();
 
    }
};

71. Simplify Path

class Solution {
public:
    string simplifyPath(string path) {
        stack stk;
 
        for(int i=0; isize(); i++){
            if(path[i] == '/')
                continue;
            string tmp;
            while(isize() && path[i] != '/'){
                tmp += path[i];
                i++;
            }
            if(tmp == ".")
                continue;
            else if(tmp == ".."){
                if(!stk.empty()){
                    stk.pop();
                }
            }
            else stk.push(tmp);
        }
 
        string newPath;
        while(!stk.empty()){
            newPath = '/' + stk.top() + newPath;
            stk.pop();
        }
        if(newPath == "") return "/";
        return newPath;
    }
};

因为这里涉及到“..”, 所以正确的是stk存储的是string

c++要学会如何分割这些string

另一种方法，直接使用getline(a, b, c)

将a存储到b中，直到找到c

这里的a要是isstream,所以要加一步stringstream ss(path)