codetop字符串刷题，刷穿地心！！不再畏惧！！暴打面试官！！

1.有效的括号字符串

给你一个只包含三种字符的字符串，支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回 true 。

‘*’ 可以被视为单个右括号 ‘)’ ，或单个左括号 ‘(’ ，或一个空字符串 “”。

与用栈判断有效括号字符串的区别在于，这里的*很灵活，可以被当做左括号也可以被当做右括号，甚至可以被当做空，所以(*))也是true的，因为*被当做左括号了。

这题的解法也比较特别，不需要栈，只需要遍历一遍，记录左括号最大和最小的可能性：
如果遇到的是(，那么左括号无论最大还是最小都要+1
如果遇到的是)，那么左括号最小的情况，是要-1，抵消一个，最大的情况，也要-1，因为不管怎么样，)始终是要抵消掉一个左括号的，即便是*当作左括号的情况
如果遇到的是*，那么左括号最小就是*抵消掉他一个左括号，减一个，左括号最大，就是*没有抵消他，而是算在他这边，+1个。

最后，lo表示到当前字符为止最小可能的左括号数，如果最终 lo <= 0，表示所有的左括号都有匹配的右括号，或者多余的 ‘*’ 被当作空字符处理，因此返回 true。

class Solution {
public:bool checkValidString(string s) {int lo = 0, hi = 0;//表示最低可能的左括号数和最高可能的左括号数for(auto c : s){if(c == '('){lo++;hi++;}else if(c == ')'){lo = max(0, lo - 1);hi--;if(hi < 0) return false;}else{hi++;lo = max(0, lo - 1);//遇到*的时候,左括号最小的情况是有一个左括号被*抵消掉了}}return lo <= 0;}
};

2.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
eg：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

题目转换一下就是：现在有2n个位置，每个位置可以放置字符(或者)，组成的所有括号组合中，由多少是合法的，这样听起来就很像回溯了，暴力穷举就可以了，合法的穷举需要满足以下两点：

• 对于一个合法的括号组合的左括号数量一定等于右括号数量
• 对于一个合法的括号字符串组合p，必然对于任何 0 <= i < size§ 都有：子串 p[0…i] 中左括号的数量都大于或等于右括号的数量。

因为从左往右计算的话肯定是左括号数量多，右括号逐步加多，最后相等，才能得到合法的括号组合嘛
用left记录还剩多少左括号，right记录还剩多少右括号

class Solution {
public:vector<string> generateParenthesis(int n) {if(n == 0) return {};vector<string> res;string path;backtrack(n, n, path, res);return res;}void backtrack(int left, int right, string& path, vector<string>& res){if(left > right) return;//不合法if(left < 0 || right < 0) return;//不合法if(left == 0 && right == 0){res.push_back(path);return;}path.push_back('(');backtrack(left - 1, right, path, res);path.pop_back();path.push_back(')');backtrack(left, right - 1, path, res);path.pop_back();}
};

3.最长单词

给定一个单词列表 words，要求找到其中的 最长单词，该单词可以由其他单词（也在 words 中）组合而成。如果有多个符合条件的单词，返回字典序最小的那个。如果没有符合要求的单词，返回空字符串。

和动态规划刷题那篇blog传送中的单词拆分很像，可以一起学。

主函数longestWord作用是匹配之后如果当前单词符合组合条件，我们需要和当前结果比较其长度；如果长度相同，还要判断字典序。
辅助函数isMatch作用是匹配
使用dp，dp[i]表示0~i-1是否可以被拆分为字典中其他单词的组合。
遍历word的每个位置 i：i 表示我们当前处理的子串的结尾位置，即我们正在考虑从 word 的第一个字如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

要注意2点：

• 第1点，单词拆分那一题没有newWord != word这个判断，因为两个题目的目的不一样，这个题目的word是从wordSet中拆出来的，单词拆分是给的另外一个词。
• 第2点，j如果从1开始，那么substr就是(j - 1, i - (j - 1))，j如果从0开始，那么substr就是(j , i - j)，总而言之j必须从1开始，这是为的dp的完整性

class Solution {
public:string longestWord(vector<string>& words) {string res = "";unordered_set<string> wordSet(words.begin(), words.end());for(const string& word : wordSet){if(isMatch(wordSet, word)){if(word.size() > res.size()) res = word;else if(word.size() == res.size() && word < res) res = word;}}return res;}bool isMatch(unordered_set<string>& wordSet, const string word){vector<bool> dp(word.size() + 1, false);dp[0] = true;for(int i = 1; i <= word.size(); i ++){for(int j = 0; j < i; j ++){string newWord = word.substr(j, i - j);if(newWord != word && wordSet.count(newWord) && dp[j]){dp[i] = true;break;}}}return dp[word.size()];}
};

4.字符串转换整数(atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

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

1. 空格：读入字符串并丢弃无用的前导空格（" "）
2. 符号：检查下一个字符（假设还未到字符末尾）为 ‘-’ 还是 ‘+’。如果两者都不存在，则假定结果为正。
3. 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
4. 舍入：如果整数数超过 32 位有符号整数范围 [−2³¹, 2³¹ − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2³¹ 的整数应该被舍入为 −2³¹ ，大于 2³¹ − 1 的整数应该被舍入为 2³¹ − 1 。
   返回整数作为最终结果。

class Solution {
public:int myAtoi(string s) {int res = 0;int index = 0, sign = 1;//丢弃前导空格while(index < s.size() && s[index] == ' ') index++;//检查符号if(index < s.size()){if(s[index] == '-'){sign = -1;index ++;}else if(s[index] == '+') index++;}//转换数字while(index < s.size() && isdigit(s[index])){int digit = s[index] - '0';//舍入计算if(res > (INT_MAX - digit) / 10){return (sign == 1) ? INT_MAX : INT_MIN;}//res * 10 + digit > int_max -> res > (int_max - digit) / 10res = res * 10 + digit;index++;}return res * sign;}
};

5.整数转罗马数字

七个不同的符号代表罗马数字：
符号 值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

• 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
• 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
• 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

900,400,90,40单领出来是有必要的，因为900不是DCCCC，而是CM

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

6.罗马数字转整数

4和9的特例用算法逻辑解决了，以IX为例，遍历到I的时候，发现 I 为 1，小于后续的 X 值为 10，所以执行减法，接下来遍历至X没有发现后续字符，或者X大于等于任何可能的后序字符，所以加上 X 的值。

class Solution {
public:int romanToInt(string s) {unordered_map<char, int> symbolTovalue{{'M', 1000}, {'D', 500}, {'C', 100}, {'L', 50}, {'X', 10}, {'V', 5},{'I', 1}};int res = 0;for(int i = 0; i < s.size(); i ++){int value = symbolTovalue[s[i]];if(i + 1 < s.size() && value < symbolTovalue[s[i + 1]]){res -= value;}else{res += value;}}return res;}
};

7.比较版本号

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 ‘.’ 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。
返回规则如下：

• 如果 version1 < version2 返回 -1，
• 如果 version1 > version2 返回 1，
• 除此之外返回 0。

eg1：
输入：version1 = “1.01”, version2 = “1.001”
输出：0
解释：忽略前导零，“01” 和 “001” 都代表相同的整数 “1”。
eg2：
输入：version1 = “1.0”, version2 = “1.0.0.0”
输出：0
解释：version1 有更少的修订号，每个缺失的修订号按 “0” 处理。

双指针做法，将两个字符串转换成整数

class Solution {
public:int compareVersion(std::string version1, std::string version2) {int i = 0, j = 0;int len1 = version1.size(), len2 = version2.size();while (i < len1 || j < len2) {// 获取 version1 中的下一个修订号int num1 = 0;while (i < len1 && version1[i] != '.') {num1 = num1 * 10 + (version1[i] - '0');i++;}i++; // 获取 version2 中的下一个修订号int num2 = 0;while (j < len2 && version2[j] != '.') {num2 = num2 * 10 + (version2[j] - '0');j++;}j++; // Skip the dot in version2// 比较两个修订号if (num1 > num2) return 1;if (num1 < num2) return -1;}return 0;}
};

8.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

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

把字符串列表看成一个二维数组，然后用一个嵌套 for 循环计算这个二维数组前面有多少列的元素完全相同即可。

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int minLen = strs[0].size();for(string str : strs){if(str.size() < minLen) minLen = str.size();}int n = strs.size();//行string res = "";for(int i = 0; i < minLen; i ++){char curStr = strs[0][i];for(int j = 1; j < n; j ++){if(strs[j][i] != curStr) return res;}res += curStr;}return res;}
};

9.面试题17.15.最长单词

给定一组单词words，编写一个程序，**找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。**若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

输入： [“cat”,“banana”,“dog”,“nana”,“walk”,“walker”,“dogwalker”]
输出： “dogwalker”
解释： "dogwalker"可由"dog"和"walker"组成。

class Solution {
public:string longestWord(vector<string>& words) {if (words.empty() || words.size() <= 1) {return "";}unordered_set<string> wordSet(words.begin(), words.end());string res = "";for (const string& word : wordSet) {if (isMatch(wordSet, word)) {if (word.length() > res.length()) {res = word;} else if (word.length() == res.length() && word < res) {res = word;}}}return res;}private:bool isMatch(const unordered_set<string>& wordSet, const string& word) {vector<bool> dp(word.length() + 1, false);dp[0] = true;for (int i = 1; i <= word.length(); ++i) {for (int j = 1; j <= i; ++j) {string cur = word.substr(j - 1, i - (j - 1));if (cur != word && wordSet.count(cur) && dp[j - 1]) {dp[i] = true;break;  // 找到一个有效的组合即可退出当前循环}}}return dp[word.length()];}
};

10.验证IP地址

正则表达式

#include <regex>
#include <string>using namespace std;class Solution {
public:bool ipv4(const string& ip) {regex pattern("(^((25[0-5]|2[0-4][0-9]|1\\d\\d|[1-9][0-9]|[0-9])\.){3}(25[0-5]|2[0-4][0-9]|1\\d\\d|[1-9][0-9]|[0-9])$)");return regex_match(ip, pattern);}bool ipv6(const string& ip) {regex pattern("(^([0-9A-Fa-f]{1,4}:){7}[0-9A-Fa-f]{1,4}$)");return regex_match(ip, pattern);}string validIPAddress(const string& queryIP) {if (ipv4(queryIP)) return "IPv4";else if (ipv6(queryIP)) return "IPv6";else return "Neither";}
};

11.面试题01.06.字符串压缩

利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。

• 遍历字符串，使用计数器记录每个连续字符的出现次数。
• 当遇到不同字符时，将之前的字符以及计数拼接到结果字符串中。
• 如果遍历到最后一个字符，将最后的字符及其计数添加到结果。
• 最后，比较压缩后的字符串长度和原始字符串长度，返回长度短的那个。

class Solution {
public:string compressString(string s) {if(s.empty()) return s;  // 空字符串的处理int count = 1;string res = "";for(int i = 1; i < s.size(); i ++){if(s[i] == s[i - 1]){// 当前字符和前一个字符相同，计数加1count ++;}else{// 当前字符和前一个字符不同，将前一个字符及其计数添加到结果res += s[i - 1];// 添加字符res += to_string(count);// 添加计数count = 1;// 重置计数}}//处理最后一个字符串res += s[s.size() - 1];// 添加最后一个字符res += to_string(count);// 添加最后一个字符的计数// 如果压缩后的字符串长度不小于原字符串长度，返回原字符串return res.size() < s.size() ? res : s;}
};