1

最近我在一次讨论中被要求编写一个算法来实现一个句子的单词反转（不是整个句子的反转），而不使用除 ToCharArray 和 Length 之外的 Split/Replace/Reverse/Join 等字符串操作。以下是我可以在 5 分钟内设计的内容。尽管该算法运行良好，但它的实现方式似乎有点难看。有人可以通过完善代码来帮助我吗？

string ReverseWords(string s)
{
    string reverseString = string.Empty;
    string word = string.Empty;

    var chars = s.ToCharArray();
    List<ArrayList> words = new List<ArrayList>();
    ArrayList addedChars = new ArrayList();
    Char[] reversedChars = new Char[chars.Length];
    int i = 1;
    foreach (char c in chars)
    {
        if (c != ' ')
        {
            addedChars.Add(c);
        }
        else
        {
            words.Add(new ArrayList(addedChars));
            addedChars.Clear();
        }
        if (i == s.Length)
        {
            words.Add(new ArrayList(addedChars));
            addedChars.Clear();
        }
        i++;
    }
    foreach (ArrayList a in words)
    {
        for (int counter = a.Count - 1; counter >= 0; counter--)
        {
            reverseString += a[counter];
        }
        if(reverseString.Length < s.Length)
            reverseString += " ";
    }
    return reverseString;
}
4

10 回答 10

8

有一个相对优雅的解决方案，它使用 LIFO 堆栈。
然而，问题听起来像家庭作业，所以我只会提供伪代码。

currWord = new LIFO stack of characters
while (! end of string/array)
{
  c = next character in string/array
  if (c == some_white_space_character) {
     while (currWord not empty) {
       c2 = currWord.pop()
       print(c2)
     }
     print(c)
  }
  else
    currWord.push(c)
}
于 2012-12-24T06:46:14.363 回答
5

这有点简单：

string inp = "hai how are you?";
StringBuilder strb = new StringBuilder();
List<char> charlist = new List<char>();
for (int c = 0; c < inp.Length; c++ )
{

    if (inp[c] == ' ' || c == inp.Length - 1)
    {
        if (c == inp.Length - 1)
            charlist.Add(inp[c]);
        for (int i = charlist.Count - 1; i >= 0; i--)
            strb.Append(charlist[i]);

        strb.Append(' ');
        charlist = new List<char>();
    }
    else
        charlist.Add(inp[c]);
}
string output = strb.ToString();
于 2012-12-24T06:59:53.150 回答
2

一种抛光版本：-

string words = "hi! how are you!";
string reversedWords = "";

List<int> spaceEncounter = new List<int>();
spaceEncounter.Add(words.Length - 1);

for (int i = words.Length - 1; i > 0; i--)
{ 
    if(words[i].Equals(' '))
    {
        spaceEncounter.Add(i);

        for (int j = i+1; j < spaceEncounter[spaceEncounter.Count - 2]; j++)
            reversedWords += words[j];

        reversedWords += " ";
    }
}

for (int i = 0; i < spaceEncounter[spaceEncounter.Count - 1]; i++)
    reversedWords += words[i];
于 2012-12-24T17:43:52.617 回答
1

您的代码中有一个小错误。yo are how hi!因此，在给定输入字符串的情况下，输出字符串将显示为hi! how are you。它正在截断最后一个单词的最后一个字符。

改变这个：

spaceEncounter.Add(words.Length - 1);

至：

spaceEncounter.Add(words.Length);
于 2013-06-29T23:04:23.320 回答
1

最简单的答案之一如下所示，请仔细阅读，

public static string ReversewordString(string Name)
    {
        string output="";
        char[] str = Name.ToCharArray();
        for (int i = str.Length - 1; i >= 0; i--)
        {
            if (str[i] == ' ')
            {
                output = output + " ";
                for (int j = i + 1; j < str.Length; j++)
                {
                    if (str[j] == ' ')
                    {
                        break;
                    }
                    output=output+ str[j];
                }
            }
            if (i == 0)
            {
                output = output +" ";
                int k = 0;
                do
                {
                    output = output + str[k];
                    k++;
                } while (str[k] != ' ');
            }
        }
        return output;
    }
于 2018-03-01T11:57:57.780 回答
1

好吧，你没有说任何关于其他 LINQ 扩展方法的事情 :)

static string ReverseWordsWithoutSplit(string input)
{
    var n = 0;
    var words = input.GroupBy(curr => curr == ' ' ? n++ : n);

    return words.Reverse().Aggregate("", (total, curr) => total + string.Concat(curr.TakeWhile(c => c != ' ')) + ' ');
}
于 2016-08-23T22:38:31.677 回答
0 
        string temp = string.Empty;
        string reversedString = string.Empty;

        foreach (var currentCharacter in testSentence)
        {
            if (currentCharacter != ' ')
            {
                temp = temp + currentCharacter;
            }
            else
            {
                reversedString = temp + " " + reversedString;
                temp = string.Empty;
            }
        }
        reversedString = temp + " " + reversedString;
于 2016-02-01T00:11:21.730 回答
0

一个简单的递归函数如何检查“”然后相应地子字符串？

    private static string rev(string inSent) { 
        if(inSent.IndexOf(" ") != -1) 
        { 
            int space = inSent.IndexOf(" "); 
            System.Text.StringBuilder st = new System.Text.StringBuilder(inSent.Substring(space+1)); 
            return rev(st.ToString()) + " " + inSent.Substring(0, space); 
        } 
        else 
        { 
            return inSent; 
        } 
    }
于 2017-11-28T11:06:11.393 回答
0

这个版本就地工作，没有任何中间数据结构。首先，它反转每个单词中的字符。“我也是”=>“em oot”。然后它反转整个字符串：“em oot”=>“too me”。

    public static string ReverseWords(string s)
    {
        if (string.IsNullOrEmpty(s))
            return s;

        char[] chars = s.ToCharArray();
        int wordStartIndex = -1;

        for (int i = 0; i < chars.Length; i++)
        {
            if (!Char.IsWhiteSpace(chars[i]) && wordStartIndex < 0)
            {
                // Remember word start index
                wordStartIndex = i;
            }
            else
            if (wordStartIndex >= 0 && (i == chars.Length-1 || Char.IsWhiteSpace(chars[i + 1]))) {
                // End of word detected, reverse the chacacters in the word range
                ReverseRange(chars, wordStartIndex, i);

                // The current word is complete, reset the start index  
                wordStartIndex = -1;
            }
        }

        // Reverse all chars in the string
        ReverseRange(chars, 0, chars.Length - 1);

        return new string(chars);
    }

    // Helper
    private static void ReverseRange(char[] chars, int startIndex, int endIndex)
    {
        for(int i = 0; i <= (endIndex - startIndex) / 2; i++)
        {
            char tmp = chars[startIndex + i];
            chars[startIndex + i] = chars[endIndex - i];
            chars[endIndex - i] = tmp;
        }            
    }
于 2016-08-23T21:21:36.960 回答
0

在 C# 中使用堆栈

string str = "ABCDEFG";
Stack<char> stack=new Stack<char>();
foreach (var c in str)
{
    stack.Push(c);
}
char[] chars=new char[stack.Count];
for (int i = 0; i < chars.Length; i++)
{
    chars[i]=stack.Pop();
}
var result=new string(chars); //GFEDCBA
于 2018-07-31T09:24:56.397 回答