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

题目: 将字符串内容进行倒置,比如 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)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python中文社区

Python数组中求和问题

本专题主要介绍哈希表和指针两种方法来解决该类问题,从两个数之和引申到三个数之和,再从四个数之和的问题上思考如何构建出一种通用的代码(可以解决N个数之和)。本文主...

900
来自专栏King_3的技术专栏

leetcode-22-括号生成

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

762
来自专栏来自地球男人的部落格

[LeetCode] 216. Combination Sum III

【原题】 Find all possible combinations of k numbers that add up to a number n, giv...

1936
来自专栏有趣的Python

7-玩转数据结构-集合与映射

上一章我们详细的介绍了二分搜索树的底层实现。这章我们介绍两个高层的数据结构,集合和映射。这种高层的数据结构,更像是我们定义好了使用接口规则,但是具体的底层实现可...

1471
来自专栏尾尾部落

[剑指offer] 数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排...

772
来自专栏mathor

位与进制

 这里我假设读者有二进制的思维,知道(3)~10~=(011)~2~将十进制转换为二进制的方法

391
来自专栏LeetCode

LeetCode <dp>343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integ...

510
来自专栏赵俊的Java专栏

不用加减乘除做加法

1294
来自专栏智能算法

程序员必须了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

760
来自专栏用户2442861的专栏

异或的应用 及剑指offer 面试 40 数组中只出现一次的数字

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27568975

982

扫码关注云+社区