C++經典例題之字符串特定規(guī)則反轉問題的解法

更新時間：2025年03月20日 09:24:12 作者：倔強的石頭_

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

問題描述

在字符串處理的編程領域中，經常會遇到各種復雜的規(guī)則要求。

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

要求從字符串開頭算起，每計數(shù)至 2k 個字符，就反轉這 2k 字符中的前 k 個字符

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

原題鏈接

541. 反轉字符串 II - 力扣（LeetCode）

解題思路

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

代碼實現(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ù)量小于k，就全部反轉；剩下數(shù)量大于k，就反轉前k
            string::iterator rightend =(left + k)<s.end() ? (left + k) : s.end();

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

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