陈中正的网络日志

LeetCode: Reverse Words in a String

题目:

https://oj.leetcode.com/problems/reverse-words-in-a-string/

分析:

解法一:(相比较更麻烦点)

  1. 运用栈来解题, 先把s中的一个个单词解析出来压到栈里, 然后再出栈重组成s

  2. 有一些特殊的边界需要考虑, 比如连续出现两个空格, 单词的头尾部出现空格等等, 这些情况需要特殊处理一下。

解法二:(更巧妙, 推荐)

从后向前进行循环

    处理空格部分

    如果结果res非空, 插入一个空格

    处理非空格部分

代码:

解法一:

class Solution
{
public:
    void reverseWords(string &s)
    {
        if (s.empty())
            return;

        string word;
        stack<string> stk;
        s.push_back(' ');
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != ' ')
                word.push_back(s[i]);
            else if (i > 0 && s[i] == ' ' && s[i-1] != ' ')
            {
                stk.push(word);
                word.clear();
            }
        }

        s.clear();
        if (stk.empty())
            return;
        while (true)
        {
            s += stk.top();
            stk.pop();
            if (stk.empty())
                break;
            else
                s.push_back(' ');
        }
        return;
    }
};

解法二:

class Solution
{
public:
    void reverseWords(string &s)
    {
        string res;

        int i = s.size() - 1;
        while (true)
        {
            while (s[i] == ' ' && i >= 0) 
                i--;
            if (i < 0) break;

            if (!res.empty())
                res.push_back(' ');

            string temp;
            while (s[i] != ' ' && i >= 0) 
            {
                temp.push_back(s[i]);
                i--;
            }
            reverse(temp.begin(), temp.end());
            res += temp;
            if (i < 0) break;
        }
        s = res;
    }
};

参考:

http://blog.csdn.net/kenden23/article/details/20701069

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39138373

Categories:  OJ题解 

« 『转』LeetCode题目难度频率分布 LeetCode: Palindrome Partition »