每日一題

反轉(zhuǎn)字符串中的單詞

題目鏈接

思路（進(jìn)階）

• 我們首先不考慮太多限制因素，先看如何實現(xiàn)字符串中單詞的反轉(zhuǎn)

  • 舉個例子：我們要反轉(zhuǎn)字符串“the sky is blue”中的單詞，我們可以先將字符串中的每個字符反轉(zhuǎn)“eht yks si eulb”，然后我們可以發(fā)現(xiàn)，從右到左看字符串正好就是我們想要的結(jié)果“blue is sky the”，所以再將整個字符串反轉(zhuǎn)不就行了嗎?
  • 而具體方法我們已經(jīng)在反轉(zhuǎn)整個字符串，分區(qū)域反轉(zhuǎn)字符串分析清楚。

• 接下來就是要考慮題目最惱火的限制條件：不允許多余空格的出現(xiàn)，即只允許單詞之間出現(xiàn)一個空格，多余的空格須全部刪除。

  • 當(dāng)然，最容易想到的還是暴力解法，即碰到字符串串首空格（字符串開頭就是空格）和單詞之間的重復(fù)空格，就不斷將字符串的元素前移，直至覆蓋多余空格，但可想而知，這樣做的效率不高。

  • 其實比較好的做法其實我們已經(jīng)在移除元素中講過，只不過上一次我們處理的是數(shù)組，而這一次處理的時字符串（實際上字符串也是數(shù)組）文章來源地址http://www.zghlxwxcb.cn/news/detail-434584.html

    • 如果不對移除元素中的代碼進(jìn)行改進(jìn)（如下代碼），那么我們實現(xiàn)的就是將整個字符串中的空格刪除，這顯然不是我們想要的結(jié)果，我們應(yīng)該讓每個單詞之間留有一個空格

    int slow = 0;
    for(int fast = 0; fast <= strlen(s); fast++)
    {
        if(s[fast] != ' ')
            s[slow++] = s[fast];
    }
    

    • 因此我們就要對上述代碼進(jìn)行改進(jìn):

    int slow = 0;
    for(int fast = 0; fast <= strlen(s); fast++)
    {
        if(s[fast] != ' ')
        {
            //只要slow不位于第一個字符（不是第一個單詞），就需要手動插入空格，即確保每個單詞之間有一個空格
            if(slow != 0)
                s[slow++] = ' ';
            //如果while仍是if，那么上述插入空格的語句就會對一個單詞重復(fù)執(zhí)行
            //因此要用循環(huán)對每個單詞進(jìn)行整理
            while(s[fast] != ' ' && s[fast] != '\0')
                s[slow++] = s[fast++];
    	}
    }
    

實現(xiàn)代碼

void Part_reverseWords(char* s, int left, int right)	//反轉(zhuǎn)指定區(qū)域的字符串
{
    while (left <= right)
    {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}
void ReplaceSpaces(char *s)		//刪除多余空格
{
   int slow = 0;
    for(int fast = 0; fast < strlen(s); fast++)
    {
        if(s[fast] != ' ')
        {
            //只要slow不位于第一個字符（不是第一個單詞），就需要手動插入空格，即確保每個單詞之間有一個空格
            if(slow != 0)
                s[slow++] = ' ';
            //如果while仍是if，那么上述插入空格的語句就會對一個單詞重復(fù)執(zhí)行
            //因此要用循環(huán)對每個單詞進(jìn)行整理
            while(s[fast] != ' ' && s[fast] != '\0')
                s[slow++] = s[fast++];
        }
    }
    s[slow ] = '\0';	//在新的字符串末尾添加結(jié)束符
}
char* reverseWords(char* s) {
    ReplaceSpaces(s);
    int i = 0;
    //對每個單詞進(jìn)行反轉(zhuǎn)
    for (int j = i + 1; j <= strlen(s); j++)
    {
        if (s[j] == ' ' || j == strlen(s))
        {
            Part_reverseWords(s, i, j - 1);
            i = j + 1;
        }
    }
    //對整個字符串反轉(zhuǎn)
    Part_reverseWords(s,0,strlen(s) - 1);
    return s;
}

到了這里，關(guān)于每日一題——反轉(zhuǎn)字符串中的單詞的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！