力扣151 反转字符串中的单词

问题描述

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意： 输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入： = "the sky is blue"
输出："blue is sky the"

示例 2：

输入： s = "  hello world  "
输出："world hello"
解释： 反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入： s = "a good   example"
输出："example good a"
解释： 如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

解题思路

套用题解的思路

  • 移除多余空格；
  • 将整个字符串反转

  • 将每个单词反转

    完整代码

    class Solution {
public:
  void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
      for (int i = start, j = end; i < j; i++, j--) {
          swap(s[i], s[j]);
      }
  }

  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的大小即为去除多余空格后的大小。
  }

  string reverseWords(string s) {
      removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
      reverse(s, 0, s.size() - 1);
      int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
      for (int i = 0; i <= s.size(); ++i) {
          if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
              reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
              start = i + 1; //更新下一个单词的开始下标start
          }
      }
      return s;
  }
};

卡码55: 右旋字符串

问题描述

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。 

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入描述

输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述

输出共一行，为进行了右旋转操作后的字符串。

输入示例

2
abcdefg

输出示例

fgabcde

提示信息

数据范围：
1 <= k < 10000,
1 <= s.length < 10000;

解题思路

  • 先定义一个字符反转函数 (使用现成的库函数reverse）
  • 调用反转函数，实现整体反转
  • 调用反转函数，实现局部反转
  • 完事

完整代码

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    //初始定义n和s
    int n;
    string s;
   
    //接收n和s
    cin >> n;
    cin >> s;

    reverse(s.begin(), s.end());//整体反转
    reverse(s.begin(), s.begin() + n);//反转前面n个；

    reverse(s.begin() + n, s.end());
    cout << s << endl;


}

本章小结

  • easy
  • algorithm

在C++中，algorithm库是标准模板库（STL）的重要组成部分，它提供了大量通用的算法，用于处理各种容器（如数组、向量、列表等）中的数据。这个库的设计目标是实现算法与数据结构的分离，使得同一算法可以应用于不同类型的容器。

algorithm库的主要功能

  1. 排序与搜索算法 - sort()：对容器元素进行排序（默认升序） - stable_sort()：稳定排序，保持相等元素的相对顺序 - partial_sort()：部分排序，只排序前n个元素 - binary_search()：二分查找（要求容器已排序） - lower_bound()和upper_bound()：查找第一个不小于/大于给定值的位置
  2. 元素操作算法 - find()和find_if()：查找元素 - count()和count_if()：统计元素出现次数 - replace()和replace_if()：替换元素 - remove()和remove_if()：移除元素（实际上是移到末尾） - unique()：移除连续重复元素
  3. 集合操作算法 - merge()：合并两个已排序的序列 - set_union()、set_intersection()：集合的并集、交集 - includes()：判断一个集合是否是另一个的子集
  4. 数值算法（部分在<numeric>中） - accumulate()：累加元素值 - iota()：用连续值填充容器
  5. 排列组合算法 - next_permutation()和prev_permutation()：生成下一个/上一个排列

  6. 比较与交换算法 - equal()：比较两个范围的元素是否相等 - swap()：交换两个元素的值 - min()和max()：返回较小/较大值

    为什么需要algorithm库？

  7. 提高代码复用性：无需重复编写常见算法，直接调用标准库函数。
  8. 性能优化：标准库的算法经过高度优化，通常比自己编写的代码更高效。
  9. 减少错误：使用经过充分测试的标准算法，降低了引入bug的风险。
  10. 统一接口：所有算法都遵循一致的设计模式，易于学习和使用。

示例用法

下面是一个使用algorithm库中sort和find的简单示例：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};
    
    // 使用sort排序
    std::sort(numbers.begin(), numbers.end());
    
    // 输出排序后的结果
    for (int num : numbers) {
        std::cout << num << " "; // 输出: 1 2 5 8 9
    }
    std::cout << std::endl;
    
    // 使用find查找元素
    auto it = std::find(numbers.begin(), numbers.end(), 5);
    if (it != numbers.end()) {
        std::cout << "找到了元素: " << *it << std::endl;
    } else {
        std::cout << "未找到元素" << std::endl;
    }
    
    return 0;
}

总结

algorithm库是C++标准库中最强大的组件之一，它提供了丰富的算法工具，可以大大简化日常编程工作，提高代码质量和开发效率。掌握这个库对于高效的C++编程至关重要。