Code: Reverse A Sentence in Place

简介:
  这好像是传说中微软的一道面试题,没事做来玩玩。第一个方法想的比较ft,从时间复杂度上来看太大了;刚开始想其实是想的第二个方法,只是被第二个方法中把每个word都搞反了而郁闷了一下,其实再reverse一下每个word就纠正过来了:)

//  ReverseInPlace.cpp : Defines the entry point for the console application.

#include  "stdafx.h"
#include  "string.h"

#define SPACE    32

void SwapInPlace( char * a,  char * b)
{
     if ( *a != *b )
     {
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

void ReverseInPlace( char* src)
{
    size_t len = strlen(src);
     for ( size_t i=0 ; i < len ; ++i )
     {
         if ( *(src+i) == SPACE )
         {
             for ( size_t m=0 ; m <= i-1 ; ++m )
             {
                 for ( size_t n=0 ; n < len-1 ; ++n )
                 {
                    SwapInPlace(src+n, src+(len+n+1)%len);
                }
            }
            len -= i;
             for ( size_t n=0 ; n < len-1 ; ++n )
             {
                SwapInPlace(src+n, src+(len+n+1)%len);
            }
            len--;
            i = -1;
        }
    }
}

void ReverseInPlace2( char* src)
{
    size_t i, start;
    size_t len = strlen(src);
     for ( i=0 ; i < len/2 ; ++i )
     {
        SwapInPlace(src+i, src+len-1-i);
    }
    start = 0;
     for ( i=0 ; i < len ; ++i )
     {
         if ( *(src+i) == SPACE || i == len-1 )
         {
             if ( i== len-1 ) i++;
             for ( size_t j=0 ; j < (i-start)/2 ; ++j )
             {
                SwapInPlace(src+start+j, src+i-1-j);
            }
            start = i+1;
        }
    }
}

int _tmain( int argc, _TCHAR* argv[])
{
     char str[] = "Reverse A Sentence In Place Absolutely a a";
    printf("SRC: %s\r\n", str);
    ReverseInPlace(str);
    printf("DES: %s\r\n", str);
    ReverseInPlace2(str);
    printf("SRC: %s", str);
    
    getchar();
}

output:
SRC: Reverse A Sentence In Place Absolutely a a
DES: a a Absolutely Place In Sentence A Reverse
SRC: Reverse A Sentence In Place Absolutely a a

本文转自博客园鸟食轩的博客,原文链接:http://www.cnblogs.com/birdshome/,如需转载请自行联系原博主。

目录
相关文章
|
编解码 算法 5G
信息论与编码期末复习——概念论述简答题(一)
信息论与编码期末复习——概念论述简答题(一)
433 0
信息论与编码期末复习——概念论述简答题(一)
|
测试技术 API Android开发
Airtest新手升级:一个相对完整的纯.py脚本是怎样子的
Airtest新手升级:一个相对完整的纯.py脚本是怎样子的
230 0
|
8月前
|
存储 人工智能 Serverless
《AI 剧本生成与动画创作》解决方案测评
这篇评测介绍了2025年首个AI剧本生成与动画创作解决方案。该方案结合阿里云的函数计算、对象存储OSS和百炼大模型服务,通过API调用实现剧本生成、语音合成及字幕生成等功能,适用于教育、短视频、游戏娱乐等领域。评测详细描述了部署流程,包括开通相关服务、准备物料、应用体验等环节,并对视频生成过程中的用户体验进行了总结和优化建议。整体而言,方案操作简便,但视频生成耗时较长且存在一些功能限制,如缺少进度条、多任务支持不足等。希望开发者们积极参与分享真实体验,共同推动技术进步。
395 4
|
Java 关系型数据库 MySQL
SonarQube——如何搭建SonarQube完整版
SonarQube——如何搭建SonarQube完整版
375 0
SonarQube——如何搭建SonarQube完整版
|
6月前
|
缓存 Linux
如何创建Linux交换文件?Linux交换文件最新创建方法
Swap是Linux中的虚拟内存空间,用于在物理内存不足时将非活动进程移至磁盘,从而优化活动进程的性能。通过创建交换文件(如1GB),可灵活调整交换空间而无需重新分区。步骤包括:使用`fallocate`或`dd`创建文件、设置权限 (`chmod 600`)、格式化 (`mkswap`)、启用交换 (`swapon`)、修改`/etc/fstab`以持久化配置,以及调整`vm.swappiness`值(默认60,建议从10开始)来平衡内存与交换的使用。最后通过`swapon -s`检查状态并重启生效。此方法适用于VPS和专用服务器,需以root用户操作。
164 2
|
8月前
|
SQL 关系型数据库 分布式数据库
利用 PolarDB PG 版向量化引擎,加速复杂 SQL 查询!完成任务领发财新年抱枕!
利用 PolarDB PG 版向量化引擎,加速复杂 SQL 查询!完成任务领发财新年抱枕!
207 14
|
8月前
|
机器学习/深度学习 存储 自动驾驶
《深度剖析:设计最优深度Q网络结构,精准逼近Q值函数》
深度Q网络(DQN)结合深度学习与Q学习,通过神经网络逼近Q值函数,指导智能体在不同状态下选择最优动作。其核心优势在于解决高维状态空间下的决策问题,利用经验回放机制和目标网络提高训练稳定性。设计高效DQN需考虑输入层、隐藏层及输出层结构,针对不同任务选择合适的网络架构,如CNN处理图像数据,MLP应对数值型状态。案例分析显示,在CartPole和Atari游戏中,DQN通过优化网络结构和策略,取得了显著效果。未来研究将聚焦于更智能的网络设计和跨领域技术融合,拓展DQN的应用范围。
643 14
|
10月前
|
监控 算法 JavaScript
基于 Node.js Socket 算法搭建局域网屏幕监控系统
在数字化办公环境中,局域网屏幕监控系统至关重要。基于Node.js的Socket算法实现高效、稳定的实时屏幕数据传输,助力企业保障信息安全、监督工作状态和远程技术支持。通过Socket建立监控端与被监控端的数据桥梁,确保实时画面呈现。实际部署需合理分配带宽并加密传输,确保信息安全。企业在使用时应权衡利弊,遵循法规,保障员工权益。
187 7
|
人工智能 容器
子数组的解释与专题
子数组的解释与专题
352 0