一个C++面试题[更新说明]

菜地一块

之前面试的时候遇到的一个题
把一个字符串以单词为单位，反序输出，如：
"I am a boy"，输出"boy a am I"。
字符串的开头和末尾都不会是空格。每个单词中间的空格只有一个。

如果您的算法使用的内存是O(1)，即不需要新分配内存的话，可以得到额外加分。
算法的效率，题目没有做要求。

增加说明：
0、函数的原型如下：
void f(char* pSZ)
{
}
1、只有15分钟时间，要把代码写出来
2、f里面当然可以分配几个变量什么的没问题，但是希望这里头分配的内存是O(1)的，即不会因为pSZ越长，要的内存就越多。当然如果您能首先实现功能，即使使用的内存比较多，也能获得一部分分数。
3、所谓的输出，指的是pSZ是一个输入输出参数，希望在进行完操作后，把处理完后的字符串通过pSZ传出来。不是要你把处理完毕后的字符串print出来。

[ 本帖最后由 菜地一块 于 2011-8-15 17:05 编辑 ]

bullying520

意思应该是不重新分配数组内存吧 临时变量总能分配吧 临时变量再不能分配 只能用异或了...

gooddong

使用一个寄存器变量，保存一个值，然后用指针互相倒过来就行了，这样就不用分配内存了。

混不到坑的萝卜

这个应该不难吧？Readify的面试题之一？

我的思路是：
用一个指针Head指向第一个不是空格的字符，然后另一个指针Tail顺着Array往前找到下一个空格的位置。然后你就可以从Tail倒着将这个选定的没有空格的部分输出到你的目的数组。然后重复这一过程直到Array的结尾。

这样，整个就是扫描整个array每个item两遍，算法复杂性O(n)，空间分配O(1)。

bullying520

原帖由 混不到坑的萝卜 于 2011-8-13 16:25 发表
这个应该不难吧？Readify的面试题之一？

我的思路是：
用一个指针Head指向第一个不是空格的字符，然后另一个指针Tail顺着Array往前找到下一个空格的位置。然后你就可以从Tail倒着将这个选定的没有空格的部分输出到你的目的数组。然后重复这一过程直到Array的结尾。

这样，整个就是扫描整个array每个item两遍，算法复杂性O(n)，空间分配O(1)。

两个指针 一头一尾 指向的内容互换 相向移动 碰头了不就行了

菜地一块

原帖由 混不到坑的萝卜 于 2011-8-13 16:25 发表
这个应该不难吧？Readify的面试题之一？

我的思路是：
用一个指针Head指向第一个不是空格的字符，然后另一个指针Tail顺着Array往前找到下一个空格的位置。然后你就可以从Tail倒着将这个选定的没有空格的部分输出到你的目的数组。然后重复这一过程直到Array的结尾。

这样，整个就是扫描整个array每个item两遍，算法复杂性O(n)，空间分配O(1)。

你的算法中都有“目的数组”了，空间分配怎么会是O(1)呢？
必然是输入字符串越大，你的目的数组越大啊。

飞翔翼

定义一个临时变量，按序头尾逐字符互换直到中间

netstat

这里玩c++的还是少呀

混不到坑的萝卜

原帖由 菜地一块 于 2011-8-13 17:28 发表

你的算法中都有“目的数组”了，空间分配怎么会是O(1)呢？
必然是输入字符串越大，你的目的数组越大啊。

看看题目，你不是只要输出就好了？那么的话不需要另存到另外一个数组，你只要输出不就好了？

混不到坑的萝卜

原帖由 飞翔翼 于 2011-8-13 17:48 发表
定义一个临时变量，按序头尾逐字符互换直到中间

你怎么找到字符串的尾巴？先遍历一次？再互换、再输出。每次元素你至少要访问三遍？

菜地一块

原帖由 混不到坑的萝卜 于 2011-8-13 18:01 发表

看看题目，你不是只要输出就好了？那么的话不需要另存到另外一个数组，你只要输出不就好了？

呵呵，题目是英文的，是我翻译成的中文，输出这个字可能容易引起歧义。

f函数的参数char* pSZ是一个输入输出参数，希望你把处理后的字符串再传回去。

混不到坑的萝卜

c++，十几年不用了，真生疏啊。

1. #include "stdafx.h"
   
2. #include <iostream>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. void f(char* s){
   
7.         int head = 0, tail = 0;
   
8.         char temp;
   
9. 
   
10.         do
    
11.         {
    
12.                 //found a space, end of word
    
13.                 if(s[tail] == 0x20)
    
14.                 {
    
15.                         if(head !=0) head++;
    
16.                         for(int i=tail-1; i>head; i--)
    
17.                         {
    
18.                                 //swap each char along the way
    
19.                                 temp = s[i];
    
20.                                 s[i] = s[head];
    
21.                                 s[head] = temp;
    
22.                                 head++;
    
23.                         }
    
24. 
    
25.                         head = tail;
    
26.                 }
    
27. 
    
28.                 tail ++;
    
29.         }
    
30.         while(s[tail]!=0x0);
    
31. 
    
32.         //last word
    
33.         head++;
    
34.         for(int i=tail-1; i>head; i--)
    
35.         {
    
36.                 //swap each char along the way
    
37.                 temp = s[i];
    
38.                 s[i] = s[head];
    
39.                 s[head] = temp;
    
40.                 head++;
    
41.         }
    
42. }
    
43. 
    
44. int _tmain(int argc, _TCHAR* argv[])
    
45. {
    
46.         string myString;
    
47.         cout<<"Please enter a string...\n\r";
    
48.         getline(cin, myString);
    
49. 
    
50.         char* cstr = new char[myString.size()+1];
    
51.         strcpy(cstr, myString.c_str());
    
52.         f(cstr);
    
53.        
    
54.         cout<<"Reversed text string:\n\r"<<cstr;
    
55.        
    
56.         cout << "\n\rPress ENTER key to exit.\n\r";
    
57.         getchar();
    
58.         return 0;
    
59. }

复制代码

[ 本帖最后由 混不到坑的萝卜 于 2011-8-13 20:53 编辑 ]

菜地一块

敢问兄弟贵庚？我毕业都没那么长时间，呵呵

混不到坑的萝卜

这些什么tchar tmain都是些虾米玩意儿？

混不到坑的萝卜

原帖由 菜地一块 于 2011-8-13 20:26 发表
敢问兄弟贵庚？我毕业都没那么长时间，呵呵

桑心，不提了。长江后浪拍前浪，前浪死在沙滩上……

bullying520

原帖由 混不到坑的萝卜 于 2011-8-13 20:27 发表
这些什么tchar tmain都是些虾米玩意儿？

TCHAR 是为了统一多语言编码而设计的。
ANSI 单字符编码
UNICODE 双字节字符编码
UTF－8  三字节字符编码

通过不同的编译选项，生成不同的支持不同编码的程序。
默认情况下的，ASCII，两者是互通的。

混不到坑的萝卜

今天看到一篇文章说谷歌的浏览器要推出native plugin了，9月后微软如果也宣布弄个native的C++的.net framework的替代，咱们又得学c++了。哭！！！！！！！！！！！

netstat

原帖由 混不到坑的萝卜 于 2011-8-13 20:22 发表
c++，十几年不用了，真生疏啊。#include "stdafx.h"
#include
#include
using namespace std;

void f(char* s){
        int head = 0, tail = 0;
        char temp;

        do
        {
                //found a space, end of word
                if(s[tail] == 0x20 ...

这样不是把：“I am a boy" 转换成了 "i ma a yob"

不合要求把

混不到坑的萝卜

原帖由 netstat 于 2011-8-13 22:13 发表
这样不是把：“I am a boy" 转换成了 "i ma a yob"

不合要求把

我觉得LZ似乎理解错了。原题并不是要求词序也反过来。

还是贴出原题吧，我拿到的版本是：


[ 本帖最后由 混不到坑的萝卜 于 2011-8-13 22:25 编辑 ]

菜地一块

呵呵其实编不过。不过能够一起思考就是好的。

混不到坑的萝卜

看来是我看错了。以为是一样的题目，所以就把我以前写的那个贴出来了。不过我以前写的是.net的，简单多了。写成C++就比较麻烦。因为C++既不知道串的长度，需要测试串的尾端。

[ 本帖最后由 混不到坑的萝卜 于 2011-8-13 22:30 编辑 ]

菜地一块

原帖由 混不到坑的萝卜 于 2011-8-13 22:24 发表

我觉得LZ似乎理解错了。原题并不是要求词序也反过来。

还是贴出原题吧，我拿到的版本是：

题目没有理解错。多举几个例子：
输入：i am a boy
输出：boy a am i
输入：abc def
输出：def abc
输入：ab c d ef
输出：ef d c ab

菜地一块

原帖由 混不到坑的萝卜 于 2011-8-13 22:27 发表
看来是我看错了。以为是一样的题目，所以就把我以前写的那个贴出来了。不过我以前写的是.net的，简单多了。写成C++就比较麻烦。因为C++既不知道串的长度，需要测试串的尾端。

C++有strlen函数可以获取字符串长度。
如果不熟悉C++语法和常用函数的话您说说算法就可以了，呵呵

混不到坑的萝卜

5楼的思路基本上是对的，照着那个做就对了。

bullying520

我也没仔细看题 面壁去了.........

混不到坑的萝卜

原帖由 菜地一块 于 2011-8-13 22:34 发表

C++有strlen函数可以获取字符串长度。
如果不熟悉C++语法和常用函数的话您说说算法就可以了，呵呵

用strlen的时候，其实函数内部也是遍历了一边那个串吧？反倒不如直接一个一个字符扫描过去快？

C.D.

你的例子和题里面的例子不一样啊

原帖由 菜地一块 于 2011-8-13 22:31 发表

题目没有理解错。多举几个例子：
输入：i am a boy
输出：boy a am i
输入：abc def
输出：def abc
输入：ab c d ef
输出：ef d c ab

混不到坑的萝卜

原帖由 C.D. 于 2011-8-13 22:39 发表
你的例子和题里面的例子不一样啊

大家都被我给弄晕了。其实是我错误理解楼主的题目了，以为是和Readify的题目一样的。其实楼主那个比较简单一点。

混不到坑的萝卜

楼主，如果这么一个输入，你那个题的结果应该是什么？
abc##def#ghi
这里我用#代替空格方便点算。

C.D.

c++ n年没有用过， 我做java, 如果做这样的题第一反应是stack,因为需要写的代码最少