快捷導(dǎo)航

C++經(jīng)典例題之字符串特定規(guī)則反轉(zhuǎn)問(wèn)題的解法

更新時(shí)間：2025年03月20日 09:24:12 作者：倔強(qiáng)的石頭_

這篇文章主要介紹了如何解決字符串反轉(zhuǎn)問(wèn)題,通過(guò)將字符串按每2k個(gè)字符為一個(gè)區(qū)間進(jìn)行劃分,并使用雙指針?lè)椒▉?lái)確定實(shí)際反轉(zhuǎn)的邊界,最終實(shí)現(xiàn)字符串按特定規(guī)則進(jìn)行反轉(zhuǎn),文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下

問(wèn)題描述

在字符串處理的編程領(lǐng)域中，經(jīng)常會(huì)遇到各種復(fù)雜的規(guī)則要求。

本文將深入探討一個(gè)給定字符串 s 和整數(shù) k，按照特定規(guī)則反轉(zhuǎn)字符串的問(wèn)題。

要求從字符串開(kāi)頭算起，每計(jì)數(shù)至 2k 個(gè)字符，就反轉(zhuǎn)這 2k 字符中的前 k 個(gè)字符

如果剩余字符少于 k 個(gè)，則將剩余字符全部反轉(zhuǎn)；
如果剩余字符小于 2k 但大于或等于 k 個(gè)，則反轉(zhuǎn)前 k 個(gè)字符，其余字符保持原樣

原題鏈接

541. 反轉(zhuǎn)字符串 II - 力扣（LeetCode）

解題思路

區(qū)間劃分：解題的核心在于將字符串按照每 2k 個(gè)字符為一個(gè)區(qū)間進(jìn)行劃分。通過(guò)雙指針的方式，定義一個(gè)左指針 left 來(lái)標(biāo)記每個(gè)區(qū)間的起始位置，初始時(shí) left 指向字符串的開(kāi)頭 s.begin()。
確定右邊界：對(duì)于每個(gè) 2k 區(qū)間，需要確定其右邊界 right。如果當(dāng)前區(qū)間有足夠的字符，即 left + 2*k 小于字符串的末尾 s.end()，那么右邊界 right 就是 left + 2*k；否則，右邊界 right 就是字符串的末尾 s.end()。這一步是為了確定一個(gè)2k區(qū)間
確定實(shí)際反轉(zhuǎn)的右邊界：在每個(gè) 2k 區(qū)間內(nèi)，需要進(jìn)一步確定實(shí)際反轉(zhuǎn)的右邊界 rightend。如果從 left 開(kāi)始往后數(shù) k 個(gè)字符不超過(guò)字符串末尾，即 (left + k) < s.end()，那么實(shí)際反轉(zhuǎn)的右邊界 rightend 就是 left + k；否則，實(shí)際反轉(zhuǎn)的右邊界 rightend 就是字符串的末尾 s.end()。這一步是為了滿(mǎn)足題目中關(guān)于剩余字符數(shù)量不同時(shí)的反轉(zhuǎn)規(guī)則
反轉(zhuǎn)操作：確定了實(shí)際反轉(zhuǎn)的左右邊界后，使用 reverse 函數(shù)對(duì) [left, rightend) 區(qū)間內(nèi)的字符進(jìn)行反轉(zhuǎn)。
移動(dòng)指針：完成一個(gè)區(qū)間的處理后，將左指針 left 移動(dòng)到當(dāng)前右邊界 right 的位置，以便處理下一個(gè) 2k 區(qū)間。重復(fù)上述步驟，直到左指針 left 到達(dá)字符串的末尾。

代碼實(shí)現(xiàn)

class Solution {
public:
    string reverseStr(string s, int k) 
    {
        string::iterator left = s.begin();//初始左區(qū)間
        

        while(left < s.end())
        {
            //初始右區(qū)間
            string::iterator right = (left + 2*k )< s.end() ?  left+ 2*k : s.end();
            
            //確定右區(qū)間的實(shí)際值
            //剩余數(shù)量小于k，就全部反轉(zhuǎn)；剩下數(shù)量大于k，就反轉(zhuǎn)前k
            string::iterator rightend =(left + k)<s.end() ? (left + k) : s.end();

            reverse(left,rightend);
            
            //移動(dòng)
            left = right;
            
        }
        return s;
    }
};

初始化左指針：string::iterator left = s.begin(); 這行代碼初始化了左指針 left，使其指向字符串 s 的開(kāi)頭。
循環(huán)處理區(qū)間：while(left < s.end()) 循環(huán)用于遍歷整個(gè)字符串，只要左指針 left 還未到達(dá)字符串末尾，就繼續(xù)處理下一個(gè) 2k 區(qū)間。
確定右邊界：string::iterator right = (left + 2*k )< s.end()? left+ 2*k : s.end(); 這行代碼根據(jù)當(dāng)前 left 的位置和 2k 的長(zhǎng)度，確定了當(dāng)前 2k 區(qū)間的右邊界 right。
確定實(shí)際反轉(zhuǎn)的右邊界：string::iterator rightend =(left + k)<s.end()? (left + k) : s.end(); 這行代碼根據(jù)當(dāng)前 left 的位置和 k 的長(zhǎng)度，確定了實(shí)際需要反轉(zhuǎn)的右邊界 rightend。
反轉(zhuǎn)操作：reverse(left,rightend); 這行代碼調(diào)用 reverse 函數(shù)，對(duì) [left, rightend) 區(qū)間內(nèi)的字符進(jìn)行反轉(zhuǎn)。
移動(dòng)左指針：left = right; 這行代碼將左指針 left 移動(dòng)到當(dāng)前右邊界 right 的位置，為處理下一個(gè) 2k 區(qū)間做準(zhǔn)備。

復(fù)雜度分析

時(shí)間復(fù)雜度：由于每個(gè)字符最多被處理一次，所以時(shí)間復(fù)雜度為 O(n)，其中 n 是字符串的長(zhǎng)度
空間復(fù)雜度：代碼中只使用了常數(shù)級(jí)別的額外空間，如指針 left、right 和 rightend，所以空間復(fù)雜度為 O(1)

通過(guò)上述解題思路和代碼實(shí)現(xiàn)，我們可以高效地解決這個(gè)字符串特定規(guī)則反轉(zhuǎn)的問(wèn)題。這種方法不僅邏輯清晰，而且在時(shí)間和空間復(fù)雜度上都達(dá)到了較好的性能。

總結(jié)

到此這篇關(guān)于C++經(jīng)典例題之字符串特定規(guī)則反轉(zhuǎn)問(wèn)題解法的文章就介紹到這了,更多相關(guān)C++字符串特定規(guī)則反轉(zhuǎn)問(wèn)題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: