LeetCode 实践练习6-10

LeetCode—6

思路：通过从左向右迭代字符串，我们可以轻松地确定字符位于Z字形团中的哪一行。
算法：从左到右迭代s，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会改变。

C++解法：

class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1) return s;

        vector<string> rows(min(numRows, int(s.size())));
        int curRow = 0;//当前行
        bool goingDown = false;//方向

        for (char c : s) {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;//若是第一行或是最后一行
            curRow += goingDown ? 1 : -1;//判断方向向上-1向下+1
        }

        string ret;
        for (string row : rows) ret += row;
        return ret;
    }
};

LeetCode—7

为什么会存在溢出问题呢，我们知道int型的数值范围是 -2147483648～2147483647， 那么如果我们要翻转 1000000009 这个在范围内的数得到 9000000001，而翻转后的数就超过了范围。

C++解法：

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (abs(res) > INT_MAX / 10) return 0;//解决溢出问题
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};

LeetCode—8 字符串转换整数

C++解法：

class Solution {
public:
    int myAtoi(string str) {
        if (str.empty()) return 0;
        int sign = 1,base = 0,i = 0,n = str.size();
        while(i<n && str[i] == ' ') i++;
        if(str[i] == '+' || str[i] == '-') {
            sign = (str[i++] == '+') ? 1 : -1;
        }
        while(i<n && str[i] >= '0' && str[i] <= '9'){
            if(base > INT_MAX/10 || (base == INT_MAX/10 && str[i] - '0' > 7)){
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            base = base * 10 + (str[i++] - '0');
        }
        return (sign*base);
    }
};

LeetCode—9 回文数（关联第5题）

思路：不能为负数 不为的数字且最低位不可以为0 这两个条件就是不是回文。
再利用函数反转，溢出则一定不是回文 ，然后在判断反转后与原来数字相同与否。
C++代码：

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0 || (x % 10 == 0 && x != 0)) return false;
        return reverse(x)==x;
    }
    int reverse(int x){
        int res = 0 ;
        while(x != 0){
            if(res > INT_MAX/10) return -1;
            res = res * 10 + x%10;
            x /= 10;
        }
        return res;
    }
};

LeetCode—10 正则表达式匹配

思路：解法链接
C++解法：

class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p.size() == 1) {
            return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
        }
        if (p[1] != '*') {
            if (s.empty()) return false;
            return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
        while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
            if (isMatch(s, p.substr(2))) return true;
            s = s.substr(1);
        }
        return isMatch(s, p.substr(2));
    }
};