反转字符串I

力扣题目链接

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

解题思路

1. 直接使用C++/Java库函数reverse()可以直接达到题目要求

2. 自定义函数实现相应功能

   • 使用双指针，分别从数组首地址开始和数组末尾开始，相向移动并进行互换

   • C++

     void reverseString(vector<char>& s) {
         for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
             // swap() 交换值，也可以使用位运算交换值
             swap(s[i],s[j]);
         }
     }
     

   • Java

     class Solution {
         public void reverseString(char[] s) {
             int l = 0;
             int r = s.length - 1;
             while (l < r) {
                 s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
                 s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
                 s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
                 l++;
                 r--;
             }
         }
     }
     

   ---

反转字符串II

力扣题目链接

题目描述

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

解题思路

1. 遍历字符串的过程中，让 i = i + (2 * k)，i 每次移动2 * k，然后判断是否需要有反转的区间。

   因为我们只需要找到每个2 * k 区间的起点

• C++

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

• Java

  class Solution {
      public String reverseStr(String s, int k) {
          char[] ch = s.toCharArray();
          // 1. 每隔 2k 个字符的前 k 个字符进行反转
          for (int i = 0; i< ch.length; i += 2 * k) {
              // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
              if (i + k <= ch.length) {
                  reverse(ch, i, i + k -1);
                  continue;
              }
              // 3. 剩余字符少于 k 个，则将剩余字符全部反转
              reverse(ch, i, ch.length - 1);
          }
          return  new String(ch);
      }
      // 定义翻转函数
      public void reverse(char[] ch, int i, int j) {
      for (; i < j; i++, j--) {
          char temp  = ch[i];
          ch[i] = ch[j];
          ch[j] = temp;
      }
  
      }
  }