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

菜地一块

原帖由 混不到坑的萝卜 于 2011-8-13 22:44 发表
楼主，如果这么一个输入，你那个题的结果应该是什么？
abc##def#ghi
这里我用#代替空格方便点算。

呵呵，特殊情况就不考虑了吧
输出
ghi#def#abc
ghi#def##abc
都算对吧。

混不到坑的萝卜

原帖由 C.D. 于 2011-8-13 22:46 发表
c++ n年没有用过， 我做java, 如果做这样的题第一反应是stack,因为需要写的代码最少

不许使用库函数啊……

C.D.

我指java不会从这个方向去问问题， 如果java的话就把stack得源代码搬过来也可以

混不到坑的萝卜

那是，如果允许用库函数，三行就解决了……
不用库函数，霸王硬上弓才是硬道理，呵呵

菜地一块

原帖由 混不到坑的萝卜 于 2011-8-13 22:55 发表
那是，如果允许用库函数，三行就解决了……
不用库函数，霸王硬上弓才是硬道理，呵呵

您说的是C++的库函数么？没有说不让用，可以使用。

bullying520

先把字符串全部反序 然后再重头扫描 把空格之前的作为一个单词再反序 然后依次下一个单词.......似乎有点麻烦 再想想怎么改进

菜地一块

原帖由 bullying520 于 2011-8-13 23:07 发表
先把字符串全部反序 然后再重头扫描 把空格之前的作为一个单词再反序 然后依次下一个单词.......似乎有点麻烦 再想想怎么改进

我想的也是这个办法。先全部反序，然后按照空格把每个单词再反序一次。
第一次反序的时间复杂度是O(n)。按单词反序也是O(n)。这样整个算法的复杂度也是O(n)的。
而且需要分配的内存是常量，与字符串的长度无关，是O(1)的。

如果可以分配内存的话，可以new一个字符串出来，与原字符串一样，然后扫描一次原字符串，拷贝到new出来的那个字符串里。然后把这个字符串拷贝回去到pSZ。
这样的话复杂度和内存都是O(n)的，不过很容易就想到了。

菜地一块

嗯上面说错了，“如果可以分配内存的话，可以new一个字符串出来，与原字符串一样，然后扫描一次原字符串，拷贝到new出来的那个字符串里。然后把这个字符串拷贝回去到pSZ。
这样的话复杂度和内存都是O(n)的，不过很容易就想到了。”
这样搞的话时间复杂度是O(n2)的，不是O(n)。

netstat

123 456 789
213 456 789
231 456 789
...............
23 456 7891
1到末尾后，得到字符串长途和单词数
再把2,3移到尾巴
遇到第一个字母是空格代表一个单词处理完毕，空额移到最后一个单词前（此单词长度和整个字母串长度都已知了

把字符串长度-已经完成移动的字母长度 所在位置作为尾部，重复上面的动作，直到重复了单词总数-1次结束

netstat

需要的临时变量
单词数
字符串长度
一个char
一个尾巴指针
一个当前操作字符指针

Xinjian

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

错了错了，这时候应该问“楼上的高寿？”。贵庚是问比自己小的人的，呵呵。

bullying520

刚又搜了下 应该没有很好的办法 不开空间的话 只能反序全句再反序单词

mmm2000

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int main(int argc, char** argv)
{
    vector<string> vec;
    vector<string>::iterator it;

    string str = "I am a boy";
    string sub;

    stringstream ss(stringstream::in | stringstream:: out);
    ss << str;
   
    while ( !ss.eof() )
    {
        ss >> sub;
        vec.push_back(sub);
    }

    for (it = vec.end() - 1; it >= vec.begin(); it--)
    {
        cout << *it << '\t';
    }
   
    return 0;
}

ingeer

輸入參數不可為const, 必需在stack或者heap上，要不然access violation


void f(char* pSZ)
{
  char* pEnd=pSZ;
  while (*pEnd != 0) pEnd ++;
  char *pEnd2=pEnd;
  while (pEnd >= pSZ)
  {
    while (*(pEnd-1) != ' ' && pEnd!=pSZ)  pEnd--;
    char chKeep=*pEnd2;
        *pEnd2= 0;
    printf("%s ", pEnd);
    *pEnd2 = chKeep;  
        pEnd2 = --pEnd;
  }
}

補： 另外，這是個很傳統的C題目。。。非C++。。

[ 本帖最后由 ingeer 于 2011-8-15 08:40 编辑 ]

xxmplus

按lz的描述，5楼是正解

mmm2000

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int main(int argc, char** argv)
{
    int length, pos;
    int strlen;
    vector<string> vec;
    char ch;


    string str = "I am a boy";
    string sub;

    length = 0;
    pos = 0;
    strlen = str.length();
    for (int i = strlen; i >= 0; i--)
    {
        length++;
        ch = str;
        if (ch == ' ')
        {
            pos = i;
            sub = str.substr(i, length);
            cout << sub;

            length = 0;
        }

        if (i == 0)
        {
            sub = str.substr(0, pos);
            cout << ' ' << sub;
        }
    }

    return 0;
}

mmm2000

for循环里的一句
ch = str [ i ] ;
新足迹把操作符当做特殊字符了

编译通过
看来还真不符合要求，再想想

[ 本帖最后由 mmm2000 于 2011-8-15 18:55 编辑 ]

mmm2000

#include <iostream>
#include <string>

using namespace std;

int main(int argc, char** argv)
{
    int length, pos;
    int strlen;
    char ch;

    string str = "I am a boy";
    string dest = "";
    string sub;
   
    length = 0;
    pos = 0;

    strlen = str.length();
    for (int i = strlen; i >= 0; i--)
    {
        length++;
        ch = str [ i ] ;
        if (ch == ' ')
        {
            pos = i;
            sub = str.substr(i, length);
            cout << sub << endl;
            str.resize(pos);
            cout << "string: " << str << endl;
            
            dest += sub;

            length = 0;
        }

        if (i == 0)
        {
            sub = str.substr(0, pos);
            str.clear();
            cout << ' ' << sub << endl;
            
            dest += ' ' + sub;
            str = dest;
            cout << "result = " << str << endl;
        }
    }

    return 0;
}

大概只能这样了，在源串中找出单词，删掉后加到另一个目的串中，都用动态分配内存的话，复杂度不变。但c++中的标准库是否是动态实现的，需要看它的源代码。程序只是示例，c语言实现可能更省空间

void f(string& str);

不知道理解的对不对?

[ 本帖最后由 mmm2000 于 2011-8-15 19:38 编辑 ]

菜地一块

LS请仔细看一下我的题目吧，我已经重新写了一下说明。

mmm2000

原帖由 菜地一块 于 2011-8-15 19:40 发表
LS请仔细看一下我的题目吧，我已经重新写了一下说明。

我仔细看了，你用c语言的char，我用string，只是为了方便。

一个删，一个加，都不会增加内存复杂度。因为在C++中函数调用是用引用，当退出函数时，程序自动销毁函数里的变量，似乎不会增加内存使用。

当然我瞎说的，不过似乎本题无解

菜地一块

呵呵，解在37楼。

你的内存占用不是O(1)的。因为你的dest跟str一样大。如果你把这段逻辑独立成一个函数，那么你在这个函数中所分配的内存将取决于你输入的sr的大小。
函数退出的时候，肯定会把栈上的内存释放。但是我们一般说讨论一种算法所需要消耗的内存资源，就是在进行运算时所占用的内存资源。不能因为函数退出时会释放掉栈上的内存，就认为内存占用是O(1)的。因为如果是这样的话，那么所有算法所占用的内存都将是O(1)的了。

cppbug

谈一点点看法，这道题time complexity最快应该也只能是O(n)，性能的提升应该也只可能是在constant上有所改进，
lz的反序再反序的算法复杂度的constant大概在6 （如果仅仅考虑value swap）。但这个constant是可以提升的，关键
在于你如何理解空间复杂度，如果你分配一个最长单词大小的buffer的话，就可以省去swap，只需要几个复制单词，而
且空间复杂度依然是O(1)，constant可以降到2-3差不多。

菜地一块

原帖由 cppbug 于 2011-8-15 20:01 发表
谈一点点看法，这道题time complexity最快应该也只能是O(n)，性能的提升应该也只可能是在constant上有所改进，
lz的反序再反序的算法复杂度的constant大概在6 （如果仅仅考虑value swap）。但这个constant是可以提升的，关键
在 ...

哦，这个题目对于效率没有做要求，您考虑找出最大单词的方法，也是一个思路；不过我们一般不考虑常数的大小。
你这个算法取决于最大单词到底有多长。那么在最差情形下（例如本身只有一个单词，或者最长单词的长度接近n）,消耗的内存就比较多了。同时我觉得你的算法可能更加好，但比较复杂。

15分钟之内，我没有那么多想法，呵呵。

cppbug

消耗的内存不会有多少，最长的单词也不会有多长，我只是想说的是从算法分析的角度，这种情况的空间复杂度也是O(1)，有了这个基础
思路就可以拓宽不少。像这种情况，你就可以头尾同时开始，读取单词，把长的放入buffer，短的直接copy到长单词的位置，这是基本思路。

不过在实际情况下，降低constant的效果是否明显很难说，这取决于计算机的cpu以及ram的model等很多因素。

菜地一块

原帖由 cppbug 于 2011-8-15 20:27 发表
消耗的内存不会有多少，最长的单词也不会有多长，我只是想说的是从算法分析的角度，这种情况的空间复杂度也是O(1)，有了这个基础
思路就可以拓宽不少。像这种情况，你就可以头尾同时开始，读取单词，把长的放入buffer，短的直接copy到长单词的位置，这是基本思路。

不过在实际情况下，降低constant的效果是否明显很难说，这取决于计算机的cpu以及ram的model等很多因素。

我觉得您的算法很复杂。能否把实际代码写出来？

cppbug

原帖由 菜地一块 于 2011-8-15 20:33 发表

我觉得您的算法很复杂。能否把实际代码写出来？

哈哈，行，不过今天算了，白天写了一天的代码，现在懒的写了。。。

菜地一块

原帖由 cppbug 于 2011-8-15 20:37 发表


哈哈，行，不过今天算了，白天写了一天的代码，现在懒的写了。。。

呵呵，好的，期待早日能够拜读到您的算法！

菜地一块

1. #include <iostream>
   
2. using namespace std;
   
3. void f(char* pSZ)
   
4. {
   
5.         char temp;
   
6.         const int iLen = strlen(pSZ);
   
7.         //整个字符串倒序
   
8.         for ( int iIndex = 0; iIndex < iLen/2; ++iIndex )
   
9.         {
   
10.                 temp = *(pSZ + iIndex);
    
11.                 *(pSZ + iIndex) = *(pSZ + iLen - 1 - iIndex);
    
12.                 *(pSZ + iLen - 1 - iIndex) = temp;
    
13.         }
    
14.         //按单词倒序
    
15.         int iBlank = 0;
    
16.         for ( int iIndex = 0; iIndex <= iLen; ++iIndex )
    
17.         {
    
18.                 if ( *(pSZ + iIndex) == ' ' || *(pSZ + iIndex) == '\n')
    
19.                 {
    
20.                         for ( int iIndex2 = iBlank; iIndex2 < iBlank + (iIndex - iBlank)/2; ++iIndex2 )
    
21.                         {
    
22.                                 temp = *(pSZ+iIndex2);
    
23.                                 *(pSZ+iIndex2) = *(pSZ + iBlank + iIndex - 1 - iIndex2);
    
24.                                 *(pSZ + iBlank + iIndex - 1 - iIndex2) = temp;
    
25.                         }
    
26.                         iBlank = iIndex + 1;
    
27.                 }
    
28.         }
    
29. }
    
30. 
    
31. int main(int argc, char** argv)
    
32. {
    
33.         char pSZ[] = "I am a big boy";
    
34.         cout << "before:\t" << pSZ << endl;
    
35.         f(pSZ);
    
36.         cout << "after:\t" << pSZ << endl;
    
37.         return 0;
    
38. }

复制代码

这里把我那个算法的代码贴一下，给有兴趣的同学做参考。
整个f函数的LOC为25行。

我现场写的代码肯定没有这么漂亮，而且可能功能都成问题；因为计算中央边界可能会有一些问题，不过现场是拿笔写的，主要关注逻辑，应该不会介意一点点瑕疵

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

混不到坑的萝卜

你忘记颠倒最后那个词了。嘿嘿。把你的第一段加上我的第二段就完美了。

菜地一块

原帖由 混不到坑的萝卜 于 2011-8-15 22:18 发表
你忘记颠倒最后那个词了。嘿嘿。把你的第一段加上我的第二段就完美了。

耶？没忘啊，我在单词倒序的时候用的iIndex <= iLen;而不是iIndex < iLen; 并且考虑了*(pSZ + iIndex) == '\n'，就是为了处理最后一个单词啊；
哈哈，不知道哪里搞错了一点，不管他了，就这样吧