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

题目: 将字符串内容进行倒置,比如 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 条评论
登录 后参与评论

相关文章

来自专栏Jack-Cui

第八天、直接插入排序

     插入排序是把一个记录插入到已排序的有序序列中,使整个序列在插入该记录后仍然有序。插入序列中较简单的一种方法是直接插入排序,其插入位置的确定方法是将待插...

1820
来自专栏文武兼修ing——机器学习与IC设计

调度队列的优先堆实现应用场景模拟应用分析代码实现

应用场景模拟 考虑优先堆的一种应用场景——按优先级的任务调度队列:每个任务有一个优先级和唯一标号,该调度队列需要具有以下功能: 添加任务:将任务添加进调度队列并...

32510
来自专栏mathor

线性表(一)

642
来自专栏编程之旅

线性表的顺序存储结构

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有50个座位,那蔺老师会把这10...

662
来自专栏杨熹的专栏

【LEETCODE】模拟面试-101-Symmetric Tree

图源:新生大学 题目: https://leetcode.com/problems/symmetric-tree/ ---- 分析: Input: ...

34512
来自专栏好好学java的技术栈

”365算法每日学计划”:02打卡-线性表(赠书活动第①期预告)

1023
来自专栏醒者呆

Knowledge_SPA——精研查找算法

首先保证这一篇分析查找算法的文章,气质与大部分搜索引擎搜索到的文章不同,主要体现在代码上面,会更加高级,会结合到很多之前研究过的内容,例如设计模式,泛型等。这...

2585
来自专栏Java爬坑系列

【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

2075
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(五)No.55

Hello哈,又好久没聊大数据相关的东西了,是不是又忘记了吖?这次聊聊B-树的升级版,B+树。前面的内容小伙伴可以回顾一下。 大数据计数原理1+0=1这你都不...

1819
来自专栏用户2442861的专栏

分页和分段的联系和区别

    用户程序的地址空间被划分成若干固定大小的区域,称为“页”,相应地,内存空间分成若干个物理块,页和块的大小相等。可将用户程序的任一页放在内存的任一块中,实...

551

扫码关注云+社区