算法-反转字符串与反转单词

﹏ヽ暗。殇╰゛Y 2022-06-10 08:45 309阅读 0赞

**题目：**  
将字符串内容进行倒置，比如 I like beijing. 经过函数后变为：.gnijied ekil I。

**解题思路：**  
首先题目说的很明确，就是反转字符串，不是打印，也不是创建一个新的字符串，而是**改变**原数据，最简单的思路就是将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环，函数可以返回一个标志位，也可以啥都不返回：  
指针作为函数形参和数组作为函数形参是一样的，而且假设我们知道字符串的长度，所以我们可以写出如下代码：

#include "iostream"    
    
    using namespace std;
    void  Reserve(char arr[],int length);
    int main()
    {   
      char str[16] = "I like beijing.";
      cout<<str<<endl;
      Reserve(str,15);
      cout<<str<<endl;
      getchar();
      return 0;
    }
    void  Reserve(char arr[],int length)
    {
        if(arr == NULL && length <= 1)
            return;
        int before = 0;
        int after = length-1;
        for(;before <after;before++,after--)
        {
            char temp = arr[before];
            arr[before] = arr[after];
            arr[after] = temp;
        }
    }

下面我们考虑下还能不能优化，讲真，这个这个代码没啥好优化的地方了，这个时间复杂度已经是O(n)了，而O(1)不可能啊。  
即便是使用栈或者递归，时间复杂度上也是一样的，而使用栈的话从后向前打印字符串会方便一些，但是这个题目要求我们改变原数据。剩下的我们可以考虑是不是可以不用中间变量temp，而是两个值直接做交换，在这里需要按位异或操作：  
假设有两个二进数A，B：  
A：01  
B：10  
XOR=A^B=B^A=11  
A^XOR=10=B  
B^XOR=01=A  
我们发现，如果用一个值按位异或它们的异或，那么结果是另一个值，于是只需要修改一部分代码：

void  Reserve(char arr[],int length)
    {
        if(arr == NULL && length <= 1)
            return;
        int before = 0;
        int after = length-1;
        for(;before <after;before++,after--)
        {
            arr[before] = arr[before]^arr[after];
            arr[after] = arr[before]^arr[after] ;
            arr[before] = arr[before]^arr[after];
        }
    }

反转字符串的问题还可以有一些变体，比如反转一句话中的单词：

**题目：**  
将字符串内容单词进行倒置，比如 I like beijing. 经过函数后变为：beijing. like I，这个题目**好未来**出过笔试题。

解题思路：  
单词的定义是认为有空格隔开的子串，在之前我们已经将字符串变成.gnijied ekil I，如果在这个基础上再把每个单词用同样的方法换过来，就实现了beijing. like I。  
所以我们需要在遍历字符串，交换的条件就是出现空格：

void  Reserve(char arr[],int length)
    {
        if(arr == NULL && length <= 0)
            return;
        int before = 0;
        int after = length-1;
        for(;before <after;before++,after--)
        {
            arr[before] = arr[before]^arr[after];
            arr[after] = arr[before]^arr[after] ;
            arr[before] = arr[before]^arr[after];
        }
        before =after =  0;
        int   num = 0;
        while (arr[num] != '\0')
        {
            if (arr[num] == ' ')
            {
    
                after =num -1;
                for(;before <after;before++,after--)
                {
                    arr[before] = arr[before]^arr[after];
                    arr[after] = arr[before]^arr[after] ;
                    arr[before] = arr[before]^arr[after];
                }
                before = num+1;
            }
            num++;
        }
    }

不过不幸的是，这个代码的时间复杂度是O(n^2)。