目录

LeetCode 6. Z 字形变换

算法：找规律

LeetCode 7. 整数反转

算法1：int 转字符串，再字符串转 int

算法2：模拟

LeetCode 8. 字符串转换整数 (atoi)

算法1 为什么不直接用库里的atoi呢(逃)

算法2：正经的模拟

LeetCode 9. 回文数

算法1：整数转字符串

算法2：模拟

LeetCode 10. 正则表达式匹配

算法：动态规划

LeetCode 6. Z 字形变换

算法：找规律

一道不太容易的找规律题
不过也挺水的，直接上代码吧( ﹁ ﹁ ) ，时间复杂度

class Solution {
public:
    string convert(string s, int numRows) {
        string res;
        if(numRows == 1) return s;  // 这里要特判，不然要超时
        for(int j = 0; j < numRows; j ++)
        {
            if(j == 0 || j == numRows - 1)//第一排和最后一排对应的下标是一个公差为(2*numRows-2)的等差数列
                for(int i = j; i < s.length(); i += 2 * numRows - 2) res += s[i];
            else 
                for(int k = j, i = 2 * numRows - 2 - j; 
                k < s.length() || i < s.length(); 
                k += 2 * numRows - 2, i += 2 * numRows - 2) //下面的每一排都是由两个公差为(2*numRows-2)的等差数列组合而成，填字符时注意边界
                {
                    if(k < s.length()) res += s[k];
                    if(i < s.length()) res += s[i];
                } 
        }
        return res;
    }
};

第六题完~~

LeetCode 7. 整数反转

算法1：int 转字符串，再字符串转 int

非常暴力要用到 int 转 string 的to_string()函数，字符串反转std::reverse()函数和 long long 转 string 的atoll()函数，上代码(ーー゛)

class Solution {
public:
    int reverse(int x) {
        string str;
        int flag = 1;       // 这种做法要判负
        if(x < 0) flag = 0;
        str = to_string(x);     // x 转成string
        std::reverse(str.begin(), str.end());   // 反转
        long long res = std::atoll(str.c_str());    // 反转后的字符串转成long long(防止数据溢出)
        if(res > INT_MAX) return 0;     // 判断数据是否溢出
        if(!flag) res = - res;
        return res;
    }
};

算法2：模拟

不是很难，直接上代码吧♪(^∇^*)

class Solution {
public:
    int reverse(int x) {
        long long res = 0;      // 这里用long long防止数据溢出
        while(x != 0)           // 手动反转
        {
            res *= 10;
            res += x % 10;      // 由于c++中取模运算的特性，不需要对负数特判
            x /= 10;
        }
        if(res < INT_MIN || res > INT_MAX) return 0;    // 越界了就返回0
        return res;
    }
};

时间复杂度都是

第七题完~~

LeetCode 8. 字符串转换整数 (atoi)

算法1 为什么不直接用库里的atoi呢(逃)

代码(＠_＠;)： （这么写可能会被面试官打）

class Solution {
public:
    int myAtoi(string s) {
        long long res = atoll(s.c_str());
        if(res > INT_MAX) return INT_MAX;    // 这里注意边界是否溢出
        if(res < INT_MIN) return INT_MIN;
        return res;
    }
};

算法2：正经的模拟

细节非常多啊，被坑了好几次o(一︿一+)o，代码：

class Solution {
public:
    int myAtoi(string str) {
        int res = 0;    // 保存结果
        int k = 0;      // 用来除去前导空格
        while (k < str.size() && str[k] == ' ') k ++ ;  // 边界判断(防止“    ”这种测试用例)
        if (k == str.size()) return 0;  // 全是空格直接返回0；

        int flag = 1;   //判断符号
        if (str[k] == '-') flag = -1, k ++ ;   
        if (str[k] == '+')  // 正号不能忘！
            if (flag == -1) return 0;   // 正负号一起出也不对
            else k ++ ;

        while (k < str.size() && str[k] >= '0' && str[k] <= '9') {      // 开始计算结果
            int x = str[k] - '0';   
            if (flag > 0 && res > (INT_MAX - x) / 10) return INT_MAX;  // 防止超出int边界，要在之前一步就判断好(直接long long也可)。如果结果为正且超出int类型的范围，就返回INT_MAX(题目要求)
            if (flag < 0 && -res < (INT_MIN + x) / 10) return INT_MIN; // 负数同理
            if (-res * 10 - x == INT_MIN) return INT_MIN;
            res = res * 10 + x;
            k ++ ;
        }

        res *= flag;
        return res;
    }
};

时间复杂度都是

第八题完~~

LeetCode 9. 回文数

算法1：整数转字符串

用to_string()将整数转换成字符串，再判断其是否为回文串即可
时间复杂度，代码如下：

class Solution {
public:
    bool isPalindrome(int x) {
        string str = to_string(x);
        for(int i = 0; i < str.length() / 2; i ++)
            if(str[i] != str[str.length() - i - 1])
                return false;
        return true;
    }
};

算法2：模拟

直接反转该数字，但要注意边界，上代码♪(^∇^*)：

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || x && x % 10 == 0) return false;
        int s = 0;
        while (s <= x)
        {
            s *= 10;
            s += x % 10;
            if (s == x || s == x / 10) return true; // 分别处理整数长度是奇数或者偶数的情况
            x /= 10;
        }
        return false;
    }
};

时间复杂度都为

第九题完~~

LeetCode 10. 正则表达式匹配

这是一道序列dp问题，很具有挑战性！(￣▽￣)

算法：动态规划

基本思路：
状态表示： 表示  从  开始到结尾，是否能匹配  从  开始到结尾的二维布尔数组元素
状态转移：

1.如果  不是通配符 '*' ，则 是真，当且仅当 可以和 匹配，且 是真；

---

2.如果是通配符 '*'，则下面的情况只要有一种满足，就是真；
 是真；
 可以和  匹配，且 是真；

 再对第二种情况的状态转移进行讨论：

最直观的转移方式是这样的：枚举通配符 '*' 可以匹配多少个 ，只要有一种情况可以匹配，则  就是真；
这样做的话，我们发现， 除了枚举0个  之外，其余的枚举操作都包含在中了，所以我们只需判断：
 是否为真，以及  是否可以和  匹配即可。

 这样时间复杂度为 ，代码如下：

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false)); // 定义一个(n+1)*(m+1)的二维可变长布尔数组
        f[0][0] = true;     // 空串相互匹配
        for(int i = 0; i <= n; i ++)
            for(int j = 1; j <= m; j ++)     // j = 0 时，空串与目标串匹配无意义
            {
               if (j + 1 <= m && p[j + 1] == '*') continue;   // 只考虑*或普通字符(后面不带*)
                if(i && p[j] != '*')    // i不为0且p[j]是普通字符
                {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.'); //状态转移
                }
                else if(p[j] == '*')    // p[j] 为 '*'
                {
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');//状态转移
                }
            }

        return f[n][m];
    }
};

第十题完~~

更多题解在主页哦~~(๑•̀ㅂ•́)و✧

如果觉得不错，可以⭐Star 和 Fork (u‿ฺu✿ฺ)