unicorn0927

unicorn0927

关注
发信
关注(28)粉丝(399)

代码随想录算法训练营第七天|344.反转字符串，541.反转字符串2，卡码网54.替换数字，151.反转字符串中的单词，卡码网55.右旋转字符串

 字符串part01

 344.反转字符串

比较简单，使用双指针法

一个指针从前往后移动，另一个指针从后往前移动，在遍历列表的一半长度的过程中交换元素，达到了逆序的目的。 

python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        j = len(s)-1
        for i in range(len(s)//2):
            s[i], s[j] = s[j], s[i]
            j -= 1
  • j = len(s)-1: 首先，方法计算列表 s 的最后一个元素的索引，并将其赋值给变量 j。这个索引将用于在逆序过程中从列表的末尾开始访问元素。
  • for i in range(len(s)//2): 接下来，通过迭代列表的前半部分来逐步交换元素。这是因为当逐个交换前半部分和后半部分的对应元素时，到达列表的中间即完成了整个列表的逆序。不需要交换中间之后的元素，因为它们在前半部分的循环中已经被交换了。
  • s[i], s[j] = s[j], s[i]: 在每次迭代中，当前位置 i 的元素和位置 j 的元素被交换。i 从列表的开始位置递增，而 j 从列表的结束位置递减。
  • j -= 1: 在每次循环结束时，将 j 减一，以便在下一次迭代中将其与前一个元素进行交换。
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

C++

class Solution {
public:
    void reverseString(vector<char>& s) {
        int len = s.size();
        for(int i=0, j=len-1; i<len/2 ; i++,j--){
            swap(s[i],s[j]);
        }
    }
};

 541.反转字符串2

循环遍历字符串:

for(int i=0; i<s.size(); i+=2*k): 循环从字符串的开始位置遍历到结束，每次增加2*k的步长。这样做是为了按照题目要求，每2*k个字符中的前k个字符进行反转，然后跳过k个字符。

反转逻辑:

if(i+k<=s.size()): 判断当前位置i加上k是否超过了字符串的长度。如果没有超过，意味着从i到i+k的子字符串可以完整地进行反转。

reverse(s.begin()+i, s.begin()+i+k): 使用std::reverse函数反转从i到i+k的子字符串。

如果i+k超过了字符串的长度，表示剩下的字符不足k个：

reverse(s.begin()+i, s.end()): 直接反转从i到字符串末尾的所有字符。

std::reverse函数接受两个参数：要反转的范围的开始和结束迭代器。

std::string，我们可以使用其成员函数begin()和end()来获取这些迭代器。

 C++

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i=0;i<s.size();i+=2*k){
            if(i+k<=s.size()){
                reverse(s.begin()+i,s.begin()+i+k);
                continue;
            }
            reverse(s.begin()+i,s.end());
        }
        return s;
    }
};
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

python

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        # 将字符串转换为列表，便于就地修改字符
        s_list = list(s)
        
        for i in range(0, len(s), 2*k):
            if i + k <= len(s):
                s_list[i:i+k] = reversed(s_list[i:i+k])
            else:
                s_list[i:] = reversed(s_list[i:])
        
        # 将修改后的字符列表转换回字符串并返回
        return ''.join(s_list)

首先将输入的字符串转换成列表，因为Python中的字符串是不可变的，而列表允许我们进行就地修改。然后，我们遍历字符串，每次增加2*k的步长，根据剩余字符的数量决定是反转前k个字符还是反转所有剩余字符。最后，我们使用''.join()方法将字符列表转换回字符串并返回。

卡码网54.替换数字

输入处理

  • 使用while (cin >> s)循环从标准输入读取字符串，直到没有更多的输入（例如，遇到文件结束符EOF）。

统计数字字符

  • 初始化计数器count为0，用于统计字符串s中数字字符的个数。
  • 遍历字符串s，使用条件if (s[i] >= '0' && s[i] <= '9')检查每个字符是否为数字，如果是，则count增加1。

扩充字符串

  • 计算并调整字符串s的大小，为每个数字字符替换成"number"留出足够的空间。由于"number"有6个字符，而数字本身占用1个字符，所以对于每个数字字符，字符串长度需要额外增加5个字符，即count * 5。
  • s.resize(s.size() + count * 5);确保了有足够的空间来替换数字字符。

替换数字字符

  • 从字符串的末尾开始，逐个字符向前遍历，将数字字符替换为"number"。
  • 使用两个索引i（指向扩充后的字符串的末尾）和j（指向原始字符串的末尾），当j < i时进行字符的替换。
  • 如果当前字符是数字（s[j] >= '0' && s[j] <= '9'），则将i位置的字符设置为'r'，并按顺序向前填充"number"的其余字符。之后，将i向前移动5位，因为"number"占了6位空间（包括数字本身的位置）。
  • 如果当前字符不是数字，则将其直接复制到新位置，i和j都向前移动一位。

输出处理后的字符串

  • 使用cout << s << endl;输出处理后的字符串

C++

#include<iostream>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        int count = 0; // 统计数字的个数
        int sOldSize = s.size();
        for (int i = 0; i < sOldSize; i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                count++;
            }
        }
        // 扩充字符串s的大小，也就是每个数字替换成"number"之后的大小
        s.resize(sOldSize + count * 5);
        int sNewSize = s.size();
        // 从后向前将数字替换为"number"
        for (int i = sNewSize - 1, j = sOldSize - 1; j >= 0; j--, i--) {
            if (s[j] >= '0' && s[j] <= '9') {
                s[i] = 'r';
                s[i - 1] = 'e';
                s[i - 2] = 'b';
                s[i - 3] = 'm';
                s[i - 4] = 'u';
                s[i - 5] = 'n';
                i -= 5; // 因为前面已经有i--了，所以这里减5而不是6
            } else {
                s[i] = s[j];
            }
        }
        cout << s << endl;
    }
    return 0;
}

python

def replace_digits_with_word(s):
    # 使用列表推导式和条件表达式来替换数字为'number'
    return ''.join(['number' if ch.isdigit() else ch for ch in s])

def main():
    try:
        while True:
            s = input("请输入字符串（按Ctrl+D结束输入）: ")
            replaced_s = replace_digits_with_word(s)
            print(replaced_s)
    except EOFError:  # 捕获EOF，通常是Ctrl+D（在Windows上是Ctrl+Z然后回车）
        print("\n输入结束。")

if __name__ == "__main__":
    main()
  • 定义了replace_digits_with_word函数，该函数遍历输入字符串s，使用列表推导式检查每个字符。如果字符是数字（使用str.isdigit()方法检查），则将其替换为字符串"number"；否则，保持字符不变。最后，使用''.join()方法将修改后的字符列表合并回一个新的字符串。
  • 在main函数中，使用input函数在循环中从标准输入读取字符串，直到遇到EOF错误（这通常通过按Ctrl+D产生，或在Windows上是Ctrl+Z后按回车）。对于每个输入的字符串，调用replace_digits_with_word函数进行处理，并打印处理后的字符串。

151.反转字符串中的单词

C++


class Solution {
public:
    void removeExtraSpaces(string& s) {
        int n = s.length();
        int index = 0; // 用于更新字符串
        bool spaceFound = false;
        for (int i = 0; i < n; ++i) {
            if (s[i] != ' ') {
                if (spaceFound) {
                    s[index++] = ' ';
                    spaceFound = false;
                }
                s[index++] = s[i];
            } else if (!spaceFound) {
                spaceFound = true;
            }
        }
        // 处理尾部空格
        if (index > 0 && s[index - 1] == ' ') {
            s.resize(index - 1);
        } else {
            s.resize(index);
        }
        if (!s.empty() && s[0] == ' ') {
            s.erase(0, 1); // 从位置0开始，删除1个字符
        }

    }

    // 反转字符串的一部分
    void reverseString(string& s, int start, int end) {
        while (start < end) {
            swap(s[start++], s[end--]);
        }
    }
    string reverseWords(string s) {
        // 去除多余空格
        removeExtraSpaces(s);
        
        // 反转整个字符串
        reverseString(s, 0, s.length() - 1);
        
        // 反转每个单词
        int start = 0; // 单词的开始位置
        int end = 0; // 单词的结束位置
        int n = s.length();
        while (start < n) {
            while (end < n && s[end] != ' ') end++; // 查找单词的结束位置
            reverseString(s, start, end - 1); // 反转单词
            start = end + 1; // 更新下一个单词的开始位置
            end = start;
        }
        return s;
    }
};

定义函数removeExtraSpace（）用于去除头部空格，单词间多余空格，尾部空格

这个地方debug了挺久的

以下是代码随想录中的方法，用了双指针法

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

定义函数reverseString（）用于反转规定区域的字符串

思路：

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

python

class Solution:
    def removeExtraSpaces(self, s: str) -> str:
        # 使用split分割字符串，然后用join去除多余空格
        parts = s.split()
        return ' '.join(parts)
    
    def reverseString(self, s: list, start: int, end: int) -> None:
        # 反转字符串的一部分
        while start < end:
            s[start], s[end] = s[end], s[start]
            start, end = start + 1, end - 1
    def reverseWords(self, s: str) -> str:
        # 去除多余空格
        trimmed_s = self.removeExtraSpaces(s)
        
        # 将字符串转换为字符列表以便就地修改
        s_list = list(trimmed_s)
        
        # 反转整个字符串
        self.reverseString(s_list, 0, len(s_list) - 1)
        
        # 反转每个单词
        start = end = 0
        while start < len(s_list):
            # 查找单词的结束位置
            while end < len(s_list) and s_list[end] != ' ':
                end += 1
            # 反转单词
            self.reverseString(s_list, start, end - 1)
            # 更新下一个单词的开始位置
            start = end + 1
            end = start
        
        # 将字符列表转换回字符串
        return ''.join(s_list)

利用了Python语言的特性简化了代码

去除字符串中的多余空格时，直接使用了split和join方法，这使得代码更加简洁易读。

整体逻辑保持不变

python中有更加简便的方法，如下：

class Solution:
    def reverseWords(self, s: str) -> str:
         # 分割字符串为单词列表，然后反转列表，最后用空格连接每个单词
        return ' '.join(s.split()[::-1])

  1. s.split()：首先，使用split方法分割字符串s。默认情况下，split会以一个或多个连续的空格作为分隔符，这自动去除了字符串头部和尾部的空格，以及单词间多余的空格。

  2. [::-1]：然后，使用切片操作[::-1]来反转单词列表。这个操作创建了列表的一个反向副本。

  3. ' '.join(...)：最后，使用join方法将反转后的单词列表重新组合成一个字符串，单词之间用一个空格分隔。

卡码网55.右旋转字符串

 代码随想录算法训练营第七天|344.反转字符串，541.反转字符串2，卡码网54.替换数字，151.反转字符串中的单词，卡码网55.右旋转字符串-LMLPHP

  1. 按照输入分段
  2. 倒序
  3. 子串倒序 

C++

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); //获取长度

    reverse(s.begin(), s.end()); // 整体反转
    reverse(s.begin(), s.begin() + n); // 先反转前一段，长度n
    reverse(s.begin() + n, s.end()); // 再反转后一段

    cout << s << endl;

}

python

def special_reverse(n: int, s: str) -> str:
    # 整体反转字符串
    s = s[::-1]
    # 先反转前一段（实际上是最初的后一段），再反转后一段（实际上是最初的前一段）
    s = s[:n][::-1] + s[n:][::-1]
    return s

# 示例输入
n = int(input("请输入整数n: "))
s = input("请输入字符串s: ")

# 输出结果
print(special_reverse(n, s))
02-06 19:20
Powered by LMLPHP ©2024 unicorn0927 0.005561