攻陷LeetCode算法区(C++) -------- LeetCode 6~10

2021/7/17 20:08:33

本文主要是介绍攻陷LeetCode算法区(C++) -------- LeetCode 6~10,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

LeetCode 6. Z 字形变换

算法:找规律

LeetCode 7. 整数反转

算法1:int 转字符串,再字符串转 int

算法2:模拟

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

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

算法2:正经的模拟

LeetCode 9. 回文数

算法1:整数转字符串

算法2:模拟

LeetCode 10. 正则表达式匹配

算法:动态规划


LeetCode 6. Z 字形变换

算法:找规律

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

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;
    }
};

时间复杂度都是O(1)

第七题完~~


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;
    }
};

时间复杂度都是O(n)

第八题完~~



LeetCode 9. 回文数

算法1:整数转字符串

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

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;
    }
};

时间复杂度都为O(1)

第九题完~~i


LeetCode 10. 正则表达式匹配

这是一道序列dp问题,很具有挑战性!( ̄▽ ̄)

算法:动态规划

基本思路:
状态表示:f[i][j] 表示 p 从 j 开始到结尾,是否能匹配 s 从 i 开始到结尾的二维布尔数组元素
状态转移:

1.如果 p[j+1] 不是通配符 '*' ,则f[i][j] 是真,当且仅当 s[i] 可以和 p[j] 匹配,且f[i+1][j+1] 是真;


2.如果p[j+1]是通配符 '*',则下面的情况只要有一种满足,f[i][j]就是真;
f[i][j+2] 是真;
s[i] 可以和 p[j] 匹配,且f[i+1][j] 是真;

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

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

 这样时间复杂度为 O(nm),代码如下:

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✿ฺ)



这篇关于攻陷LeetCode算法区(C++) -------- LeetCode 6~10的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程