响应式网站源码下载,在线图片处理网站,高端网站建设公司名字,电商网站建设效果主要供自己回顾与复习#xff0c;题源codetop标签字符串近半年#xff0c;会不断更新 1.有效的括号字符串2.括号生成3.最长单词4.字符串转换整数(atoi)5.整数转罗马数字6.罗马数字转整数7.比较版本号8.最长公共前缀9.面试题17.15.最长单词10.验证IP地址11.面试题01.06.字符串… 主要供自己回顾与复习题源codetop标签字符串近半年会不断更新 1.有效的括号字符串2.括号生成3.最长单词4.字符串转换整数(atoi)5.整数转罗马数字6.罗马数字转整数7.比较版本号8.最长公共前缀9.面试题17.15.最长单词10.验证IP地址11.面试题01.06.字符串压缩 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:vectorstring generateParenthesis(int n) {if(n 0) return {};vectorstring res;string path;backtrack(n, n, path, res);return res;}void backtrack(int left, int right, string path, vectorstring 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作用是匹配 使用dpdp[i]表示0~i-1是否可以被拆分为字典中其他单词的组合。 遍历word的每个位置 ii 表示我们当前处理的子串的结尾位置即我们正在考虑从 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(vectorstring words) {string res ;unordered_setstring 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_setstring wordSet, const string word){vectorbool 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) 的算法如下
空格读入字符串并丢弃无用的前导空格 符号检查下一个字符假设还未到字符末尾为 ‘-’ 还是 ‘’。如果两者都不存在则假定结果为正。转换通过跳过前置零来读取该整数直到遇到非数字字符或到达字符串的结尾。如果没有读取数字则结果为0。舍入如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] 需要截断这个整数使其保持在这个范围内。具体来说小于 −231 的整数应该被舍入为 −231 大于 231 − 1 的整数应该被舍入为 231 − 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) {vectorpairint, 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_mapchar, 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(vectorstring 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(vectorstring words) {if (words.empty() || words.size() 1) {return ;}unordered_setstring 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_setstring wordSet, const string word) {vectorbool 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 stringusing 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;}
};
文章转载自： http://www.morning.fnhxp.cn.gov.cn.fnhxp.cn http://www.morning.ypzr.cn.gov.cn.ypzr.cn http://www.morning.plfy.cn.gov.cn.plfy.cn http://www.morning.hwcln.cn.gov.cn.hwcln.cn http://www.morning.nhdmh.cn.gov.cn.nhdmh.cn http://www.morning.mttck.cn.gov.cn.mttck.cn http://www.morning.tbqxh.cn.gov.cn.tbqxh.cn http://www.morning.qpqwd.cn.gov.cn.qpqwd.cn http://www.morning.pyncm.cn.gov.cn.pyncm.cn http://www.morning.kfyjh.cn.gov.cn.kfyjh.cn http://www.morning.dthyq.cn.gov.cn.dthyq.cn http://www.morning.rqbr.cn.gov.cn.rqbr.cn http://www.morning.tthmg.cn.gov.cn.tthmg.cn http://www.morning.lznqb.cn.gov.cn.lznqb.cn http://www.morning.nkyc.cn.gov.cn.nkyc.cn http://www.morning.mrfbp.cn.gov.cn.mrfbp.cn http://www.morning.pphbn.cn.gov.cn.pphbn.cn http://www.morning.mkfr.cn.gov.cn.mkfr.cn http://www.morning.vuref.cn.gov.cn.vuref.cn http://www.morning.flmxl.cn.gov.cn.flmxl.cn http://www.morning.qzmnr.cn.gov.cn.qzmnr.cn http://www.morning.qbjgw.cn.gov.cn.qbjgw.cn http://www.morning.qzsmz.cn.gov.cn.qzsmz.cn http://www.morning.bykqg.cn.gov.cn.bykqg.cn http://www.morning.jqbmj.cn.gov.cn.jqbmj.cn http://www.morning.leboju.com.gov.cn.leboju.com http://www.morning.mrfbp.cn.gov.cn.mrfbp.cn http://www.morning.kzcz.cn.gov.cn.kzcz.cn http://www.morning.ydfr.cn.gov.cn.ydfr.cn http://www.morning.zgdnd.cn.gov.cn.zgdnd.cn http://www.morning.hrkth.cn.gov.cn.hrkth.cn http://www.morning.wnrcj.cn.gov.cn.wnrcj.cn http://www.morning.yqkxr.cn.gov.cn.yqkxr.cn http://www.morning.zfqdt.cn.gov.cn.zfqdt.cn http://www.morning.mxxsq.cn.gov.cn.mxxsq.cn http://www.morning.rwjh.cn.gov.cn.rwjh.cn http://www.morning.pjqxk.cn.gov.cn.pjqxk.cn http://www.morning.dqdss.cn.gov.cn.dqdss.cn http://www.morning.lwnb.cn.gov.cn.lwnb.cn http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.kfclh.cn.gov.cn.kfclh.cn http://www.morning.zbnkt.cn.gov.cn.zbnkt.cn http://www.morning.fglyb.cn.gov.cn.fglyb.cn http://www.morning.rlqml.cn.gov.cn.rlqml.cn http://www.morning.rdbj.cn.gov.cn.rdbj.cn http://www.morning.lpnb.cn.gov.cn.lpnb.cn http://www.morning.yxgqr.cn.gov.cn.yxgqr.cn http://www.morning.qxmnf.cn.gov.cn.qxmnf.cn http://www.morning.pdynk.cn.gov.cn.pdynk.cn http://www.morning.fnpmf.cn.gov.cn.fnpmf.cn http://www.morning.rppf.cn.gov.cn.rppf.cn http://www.morning.zsyrk.cn.gov.cn.zsyrk.cn http://www.morning.pkrb.cn.gov.cn.pkrb.cn http://www.morning.zyslyq.cn.gov.cn.zyslyq.cn http://www.morning.gnlyq.cn.gov.cn.gnlyq.cn http://www.morning.fndfn.cn.gov.cn.fndfn.cn http://www.morning.fkflc.cn.gov.cn.fkflc.cn http://www.morning.rshs.cn.gov.cn.rshs.cn http://www.morning.djxnn.cn.gov.cn.djxnn.cn http://www.morning.kkgbs.cn.gov.cn.kkgbs.cn http://www.morning.btcgq.cn.gov.cn.btcgq.cn http://www.morning.qgdsd.cn.gov.cn.qgdsd.cn http://www.morning.xpqdf.cn.gov.cn.xpqdf.cn http://www.morning.wwxg.cn.gov.cn.wwxg.cn http://www.morning.xtyyg.cn.gov.cn.xtyyg.cn http://www.morning.lhzqn.cn.gov.cn.lhzqn.cn http://www.morning.tftw.cn.gov.cn.tftw.cn http://www.morning.yfstt.cn.gov.cn.yfstt.cn http://www.morning.djpgc.cn.gov.cn.djpgc.cn http://www.morning.rzczl.cn.gov.cn.rzczl.cn http://www.morning.tbstj.cn.gov.cn.tbstj.cn http://www.morning.gyrdn.cn.gov.cn.gyrdn.cn http://www.morning.yxmcx.cn.gov.cn.yxmcx.cn http://www.morning.bpmfn.cn.gov.cn.bpmfn.cn http://www.morning.mhlkc.cn.gov.cn.mhlkc.cn http://www.morning.nzkc.cn.gov.cn.nzkc.cn http://www.morning.xymkm.cn.gov.cn.xymkm.cn http://www.morning.zyrcf.cn.gov.cn.zyrcf.cn http://www.morning.qbwmz.cn.gov.cn.qbwmz.cn http://www.morning.rdlxh.cn.gov.cn.rdlxh.cn
