1. 字符串流的运用
字符串流stringstream
配合读写符>>可以轻松做到精确分割。分割的办法有两种
字符数字交替分割,可以分割
1.22.3
这样的数,但并不实用int num; char c; str>>c;str>>num;
另一种是以空格为标志的分割,非常好用。我们可以实现将原字符串某些部分转化为空格,以此作为分割的标志。
008 字符串转换整数(atoi)
请你来实现一个 atoi
函数,使其能将字符串转换成整数。
输入: "42"
输出: 42
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ,因为它的下一个字符不为数字。
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
解答:
int myAtoi(string str) {
stringstream s(str);
long val=0;
s >> val;
if (val > INT_MAX) return INT_MAX;
if (val < INT_MIN) return INT_MIN;
return val;
}
058 最后一个单词的长度
给定一个仅包含大小写字母和空格 ' '
的字符串,返回其最后一个单词的长度。如果不存在最后一个单词,请返回 0 。
输入: "Hello World"
输出: 5
解答:
在stringstream中判断是否为空的办法是s.rdbuf()->in_avail()
返回剩余字符串长度,如果为0就是为空。
int lengthOfLastWord(string s) {
stringstream str(s);
string word;
while (str.rdbuf()->in_avail())
{
str >> word;
}
return word.size();
}
071 简化路径
以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。
输入:"/home/"
输出:"/home"
解释:注意,最后一个目录名后面没有斜杠。
输入:"/../"
输出:"/"
解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。
输入:"/home//foo/"
输出:"/home/foo"
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。
解答:
第一步需要从/中切割出想要的成分。第二部开始分析,由于//
也是消灭的对象所以需要考虑part==""
。将/替换为空格,就可以利用流的特性进行分割读取。
注意:
- 在
s>>part
之前要先把垃圾清空 part == ".."
的判断一定要分两步走,防止/../
这种情况
string simplifyPath(string path) {
stack<string> stk;
auto lambda = [](auto& element) {
if (element == '/')
element = ' ';
};
for_each(path.begin(), path.end(), lambda);
stringstream s(path);
string part;
while (s.rdbuf()->in_avail())
{
part = "";
s >> part;
if (part == "." || part == "") continue;
else if (part == ".." )
{
if(!stk.empty())
stk.pop();
}
else stk.push("/" + part);
}
string res = "";
while (!stk.empty())
{
//注意顺序
res = stk.top() + res;
stk.pop();
}
if (res.size() == 0) res = "/";
return res;
}
125 验证回文串
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
输入: "A man, a plan, a canal: Panama"
输出: true
解答:
思路和上面一样,不过在lambda中需要先转化为小写,因为本题要求不考虑大小写。
bool isPalindrome(string s) {
auto lambda = [](auto& element) {
if (!isalnum(element))
element = ' ';
element = tolower(element);
};
for_each(s.begin(), s.end(), lambda);
stringstream str(s);
string ans = "";
while (str.rdbuf()->in_avail())
{
string tmp;
str >> tmp;
ans += tmp;
}
string rev_ans = ans;
reverse(rev_ans.begin(), rev_ans.end());
return ans == rev_ans;
}
165 比较版本号
比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1,如果 version1 < version2 返回 -1, 除此之外返回 0。
输入:version1 = "1.01", version2 = "1.001"
输出:0
解释:忽略前导零,“01” 和 “001” 表示相同的数字 “1”。
输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1
解答:
承接容器必须要int类型,如果用string来接会出现"001"
和"1"
不相等的情况。最后还要考虑长度问题解决version1 = "7.5.3.4", version2 = "7.5.3"
这一类长度不等的情况。
int compareVersion(string version1, string version2) {
auto lambda=[](auto& element){
if(!isdigit(element))
element=' ';
};
string str1=version1;
string str2 = version2;
for_each(str1.begin(),str1.end(),lambda);
for_each(str2.begin(),str2.end(),lambda);
stringstream s1(str1);
stringstream s2(str2);
while(s1.rdbuf()->in_avail()||s2.rdbuf()->in_avail())
{
int tmp1=0;
int tmp2=0;
s1>>tmp1;
s2>>tmp2;
if(tmp1>tmp2||(tmp2==0&&tmp1!=0)) return 1;
if(tmp1<tmp2||(tmp1==0&&tmp2!=0)) return -1;
}
return 0;
}
2. 其他
006 Z字变换
将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETCODEISHIRING"
行数为 3 时,排列如下:
L C I R
E T O E S I I G
E D H N
解答:
如果行数为3,就分成3个子串分别收集,依靠step进行指路。
string convert(string s, int numRows) {
if(s.empty()||numRows==1) return s;
int step=-1;
int dir=0;
vector<string> str(numRows);
for(int i=0;i<s.size();i++)
{
str[dir]+=s[i];
if(dir==numRows-1||dir==0)
step=-step;
dir+=step;
}
string res="";
for(auto x:str)
res=res+x;
return res;
}
014 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""
。
输入: ["flower","flow","flight"]
输出: "fl"
解答:
C++中字符串的大小比较是按照字典序排序的,利用这一性质我们可以找到最大和最小,只需要比较最大最小的前缀即可。
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()==0) return "";
string res="";
auto it_max = max_element(strs.begin(),strs.end());
auto it_min = min_element(strs.begin(),strs.end());
string max=*it_max;
string min=*it_min;
auto size = std::min(max.size(),min.size());
int i=0;
for(;i<size;i++)
{
if(max[i]!=min[i])
break;
}
return max.substr(0,i);
}