本文着重介绍字符串流stringstream的妙用。

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