leetcode刷题记录21（2023-09-08）【罗马数字转整数(哈希表) | 最长公共前缀(集合求交) | 找出字符串中第一个匹配项的下标(KMP) | 整数转罗马数字(贪心)】

- 日理万妓 2024-03-04 05:46 26阅读 0赞

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

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格  
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。  
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。  
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。  
如果整数数超过 32 位有符号整数范围  \[ − 2 31 , 2 31 − 1 \] \[−2^\{31\}, 2^\{31\} − 1\] \[−231,231−1\] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于  − 2 31 −2^\{31\} −231 的整数应该被固定为  − 2 31 −2^\{31\} −231 ，大于  2 31 − 1 2^\{31\} − 1 231−1 的整数应该被固定为  2 31 − 1 2^\{31\} − 1 231−1 。  
返回整数作为最终结果。  
注意：

本题中的空白字符只包括空格字符 ’ ’ 。  
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：  
输入：s = “42”  
输出：42  
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。  
第 1 步：“42”（当前没有读入字符，因为没有前导空格）  
第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）  
第 3 步：“42”（读入 “42”）  
解析得到整数 42 。  
由于 “42” 在范围  \[ − 2 31 , 2 31 − 1 \] \[-2^\{31\}, 2^\{31\} - 1\] \[−231,231−1\] 内，最终结果为 42 。

示例 2：  
输入：s = " -42"  
输出：-42  
解释：  
第 1 步：" -42"（读入前导空格，但忽视掉）  
第 2 步：" -42"（读入 ‘-’ 字符，所以结果应该是负数）  
第 3 步：" -42"（读入 “42”）  
解析得到整数 -42 。  
由于 “-42” 在范围  \[ − 2 31 , 2 31 − 1 \] \[-2^\{31\}, 2^\{31\} - 1\] \[−231,231−1\] 内，最终结果为 -42 。

示例 3：

输入：s = “4193 with words”  
输出：4193  
解释：  
第 1 步：“4193 with words”（当前没有读入字符，因为没有前导空格）  
第 2 步：“4193 with words”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）  
第 3 步：“4193 with words”（读入 “4193”；由于下一个字符不是一个数字，所以读入停止）  
解析得到整数 4193 。  
由于 “4193” 在范围  \[ − 2 31 , 2 31 − 1 \] \[-2^\{31\}, 2^\{31\} - 1\] \[−231,231−1\] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200  
s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+‘、’-’ 和 ‘.’ 组成

这道题目需要把题目读明白，到底什么样的数算是合法的，“ -42”输出-42，而“0000-42”，输出的就是“0”。

#include <string>
    #include <iostream>
    #include <limits.h>
    
    using namespace std;
    
    class Solution
    {
        
    public:
        int myAtoi(string s)
        {
        
            int idx = 0;
            while (idx < s.size() && s[idx] == ' ')
            {
        
                idx++;
            }
    
            int res = 0;
            int times;
            if (s[idx] == '-')
            {
        
                times = -1;
                idx++;
            }
            else if (s[idx] == '+')
            {
        
                times = 1;
                idx++;
            }
            else if (s[idx] >= '0' && s[idx] <= '9')
            {
        
                times = 1;
            }
            else
            {
        
                return res;
            }
    
            int digit;
            while (idx < s.size() && s[idx] >= '0' && s[idx] <= '9')
            {
        
                digit = s[idx] - '0';
                if (times > 0 && res > (INT_MAX - digit) / 10)
                    return INT_MAX;
                if (times < 0 && res < (INT_MIN + digit) / 10)
                    return INT_MIN;
                res = res * 10 + times * digit;
                idx++;
            }
            return res;
        }
    };
    
    int main()
    {
        
        // 2147483647
        string s = "00000-42a1234";
        Solution sol;
        int res = sol.myAtoi(s);
        cout << res << endl;
        return 0;
    }

## 13. 罗马数字转整数 ##

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值  
I 1  
V 5  
X 10  
L 50  
C 100  
D 500  
M 1000  
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。  
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。  
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。  
给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = “III”  
输出: 3

示例 2:

输入: s = “IV”  
输出: 4

示例 3:

输入: s = “IX”  
输出: 9

示例 4:

输入: s = “LVIII”  
输出: 58  
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = “MCMXCIV”  
输出: 1994  
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= s.length <= 15  
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)  
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 \[1, 3999\] 内  
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。  
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。

主要做法就是遍历字符串，然后中间添加一个if-else分支判断。

#include <map>
    #include <string>
    using namespace std;
    
    class Solution
    {
        
    public:
        int romanToInt(string s)
        {
        
            map<char, int> mp;
            mp['I'] = 1;
            mp['V'] = 5;
            mp['X'] = 10;
            mp['L'] = 50;
            mp['C'] = 100;
            mp['D'] = 500;
            mp['M'] = 1000;
    
            int sum = 0;
            for (int i = 0; i < s.size(); i++)
            {
        
                if (i + 1 < s.size() && mp[s[i]] < mp[s[i + 1]])
                {
        
                    sum += mp[s[i + 1]] - mp[s[i]];
                    i++;
                }
                else
                {
        
                    sum += mp[s[i]];
                }
            }
            return sum;
        }
    };

## 14. 最长公共前缀 ##

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = \[“flower”,“flow”,“flight”\]  
输出：“fl”

示例 2：

输入：strs = \[“dog”,“racecar”,“car”\]  
输出：“”  
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200  
0 <= strs\[i\].length <= 200  
strs\[i\] 仅由小写英文字母组成

从第一个字符串的第一个元素开始枚举，一直循环到不满足条件为止。

#include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    class Solution
    {
        
    public:
        string longestCommonPrefix(vector<string> &strs)
        {
        
            int idx = 0;
            bool isCommon = true;
            for (int i = 0; i < strs[0].size(); i++)
            {
        
                idx = i;
                for (int j = 1; j < strs.size(); j++)
                {
        
                    if (idx < strs[0].size() && idx < strs[j].size())
                    {
        
                        if (strs[0][idx] != strs[j][idx])
                        {
        
                            isCommon = false;
                            break;
                        }
                    }
                    else
                    {
        
                        isCommon = false;
                        break;
                    }
                }
    
                if (isCommon == false)
                    break;
            }
    
            string res = strs[0];
            if (isCommon == false)
            {
        
                res = res.substr(0, idx);
            }
            else
            {
        
                res = res.substr(0, idx + 1);
            }
    
            return res;
        }
    };
    
    int main()
    {
        
        Solution sol;
        vector<string> vec = {
        "flower", "flow", "flight"};
        string res = sol.longestCommonPrefix(vec);
        cout << res;
        return 0;
    }

## 28. 找出字符串中第一个匹配项的下标 ##

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”  
输出：0  
解释：“sad” 在下标 0 和 6 处匹配。  
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = “leetcode”, needle = “leeto”  
输出：-1  
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

提示：

1 < = h a y s t a c k . l e n g t h , n e e d l e . l e n g t h < = 1 0 4 1 <= haystack.length, needle.length <= 10^4 1<=haystack.length,needle.length<=104

haystack 和 needle 仅由小写英文字符组成

KMP算法的板子题，这种题目最好还是算法背下来吧！

#include <string>
    #include <vector>
    #include<iostream>
    
    using namespace std;
    
    /// @brief 字符串匹配算法 KMP 模板
    class Solution
    {
        
        vector<int> getNext(string needle)
        {
        
            int j = 0, k = -1, lengthNeedle = needle.length();
            vector<int> next = vector<int>(lengthNeedle);
            next[0] = -1;
            while (j < lengthNeedle - 1)
            {
        
                if (k == -1 || needle[j] == needle[k])
                {
        
                    j++;
                    k++;
                    next[j] = k;
                }
                else
                    k = next[k];
            }
            return next;
        }
    
    public:
        int strStr(string haystack, string needle)
        {
        
            vector<int> next = getNext(needle);
            int posNeedle = 0, posHaystack = 0;
            int lengthNeedle = needle.length();
            int lengthHaystack = haystack.length();
            while (posNeedle < lengthNeedle && posHaystack < lengthHaystack)
            {
        
                if (posNeedle == -1 || haystack[posHaystack] == needle[posNeedle])
                {
        
                    posNeedle++;
                    posHaystack++;
                }
                else
                    posNeedle = next[posNeedle];
            }
            if (posNeedle < lengthNeedle)
                return -1;
            else
                return posHaystack - posNeedle;
        }
    };
    
    int main(){
        
        string haystack = "leetcode";
        string needle = "code";
        Solution sol;
        int res = sol.strStr(haystack, needle);
        cout << res;
        return 0;
    }

## 12. 整数转罗马数字 ##

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符 数值  
I 1  
V 5  
X 10  
L 50  
C 100  
D 500  
M 1000  
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。  
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。  
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。  
给你一个整数，将其转为罗马数字。

示例 1:

输入: num = 3  
输出: “III”

示例 2:

输入: num = 4  
输出: “IV”

示例 3:

输入: num = 9  
输出: “IX”

示例 4:

输入: num = 58  
输出: “LVIII”  
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994  
输出: “MCMXCIV”  
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

1 <= num <= 3999

主要思路就是，像换零钱一样，从大到小进行一个兑换。

#include <string>
    
    using namespace std;
    
    class Solution
    {
        
    public:
        string intToRoman(int num)
        {
        
            string res = "";
            if (num >= 1000)
            {
        
                int time = num / 1000;
                for (int i = 0; i < time; i++)
                {
        
                    res = res + "M";
                }
                num = num % 1000;
            }
    
            if (num >= 900)
            {
        
                res = res + "CM";
                num = num - 900;
            }
    
            if (num >= 500)
            {
        
                res = res + "D";
                num = num - 500;
            }
    
            if (num >= 400)
            {
        
                res = res + "CD";
                num = num - 400;
            }
    
            if (num >= 100)
            {
        
                int time = num / 100;
                for (int i = 0; i < time; i++)
                {
        
                    res = res + "C";
                }
                num = num % 100;
            }
    
            if (num >= 90)
            {
        
                res = res + "XC";
                num = num - 90;
            }
    
            if (num >= 50)
            {
        
                res = res + "L";
                num = num - 50;
            }
    
            if (num >= 40)
            {
        
                res = res + "XL";
                num = num - 40;
            }
    
            if (num >= 10)
            {
        
                int time = num / 10;
                for (int i = 0; i < time; i++)
                {
        
                    res = res + "X";
                }
                num = num % 10;
            }
    
            if (num >= 9)
            {
        
                res = res + "IX";
                num = num - 9;
            }
    
            if (num >= 5)
            {
        
                res = res + "V";
                num = num - 5;
            }
    
            if (num >= 4)
            {
        
                res = res + "IV";
                num = num - 4;
            }
    
            if (num >= 1)
            {
        
                for (int i = 0; i < num; i++)
                {
        
                    res = res + "I";
                }
            }
    
            return res;
        }
    };

力扣官方的解法：[https://leetcode.cn/problems/integer-to-roman/solutions/774611/zheng-shu-zhuan-luo-ma-shu-zi-by-leetcod-75rs/][https_leetcode.cn_problems_integer-to-roman_solutions_774611_zheng-shu-zhuan-luo-ma-shu-zi-by-leetcod-75rs]，感觉十分简洁：

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

[https_leetcode.cn_problems_integer-to-roman_solutions_774611_zheng-shu-zhuan-luo-ma-shu-zi-by-leetcod-75rs]: https://leetcode.cn/problems/integer-to-roman/solutions/774611/zheng-shu-zhuan-luo-ma-shu-zi-by-leetcod-75rs/