论坛 › 【编程】编程圣殿 › 一道面试题(以单词为单位的反转)

powerwind 发表于 2006-6-16 19:30

一道面试题(以单词为单位的反转)

最近在考试，天天复习得无聊。今天上CSDN看到一道面试题，觉得自己可以做出来，就没有去看答案，结果做了很久才做出来。据说有四种方法，我还没有去看，如果你有兴趣，也做做，看我们这里的人可以做出多少种方法。

题目：

                以单词为最小单位翻转字符串
                Write the function String reverseStringWordByWord(String input)
                that reverses a string word by word.For instance,
                reverseStringWordByWord("The house is blue") --> "blue is house The"
                reverseStringWordByWord("Zed is dead") --> "dead is Zed"

iptton 发表于 2006-6-16 19:54

指向指针的指针……应该是一种办法

powerwind 发表于 2006-6-16 21:44

不太明,可以详细说明吗?

powerwind 发表于 2006-6-16 23:41

哎,没人做!我先贴出自己的做法!


void reverseWord(char*src,char*dest)
{
        int i,len;
        char*p;
        len=strlen(src);
        p=src+len-1; //指向最后一个字符
        *dest='\0'; //根据strcat()的特点,不得不如此
        for(i=0;i<len;i++)
                if((*(p-i))==' ')
                {
                        strcat(dest,(p-i+1));
                        strcat(dest," ");
                        if(i!=len-1)
                                *(p-i)='\0';
                }
                strcat(dest,p-len+1);
}
int main()
{
        char str[]="The house is blue";
        char a;
        reverseWord(str,a);
        printf("%s\n",a);
        system("pause");
        return 0;
}


[ 本帖最后由 powerwind 于 2006-6-17 17:34 编辑 ]

wool王 发表于 2006-6-17 10:42

/*
* 创建日期 2006-6-17
* @author Woden Wang
* power by Heatpixel.com
*/
package test;

public class StringReverse {

        public static String reverseStringWordByWord(String input){
                String[] words = input.trim().split(" ");
                StringBuffer newWord = new StringBuffer();
                for(int i=words.length-1;i>=0;i--){
                        newWord.append(words);
                        newWord.append(" ");
                }
                return newWord.toString().trim();
        }
       
        public static void main(String[] args) {
                String input = "how do you do";
                System.out.println(reverseStringWordByWord(input));

        }

}


[ 本帖最后由 wool王 于 2006-6-17 02:43 编辑 ]

hjack 发表于 2006-6-17 14:49

单词全部是用空格分开还是可以带其它标点的呢？？？

iptton 发表于 2006-6-17 16:25

#include<stdio.h>
#define DIVI ' '
/*分割符定义*/
main()
{
char *s="Welcome to GDUT!";
char *p;
char *tmp;
int i=0;
tmp=s;
while(*s!='\0')
{
    if(*s++==DIVI)
    {
      p=tmp;
      tmp=s;
    }
}
p=tmp;
for(;i>=0;i--)
{
    while(*p!=DIVI&&*p!='\0')
    {
      putch(*p);
      p++;
    }
    printf("\n");
}
getch();
return 0;
}

powerwind 发表于 2006-6-17 17:34

原帖由 hjack 于 2006-6-17 14:49 发表
单词全部是用空格分开还是可以带其它标点的呢？？？

只有空格就可以啦.
因为后院搬家的原因,我回的一个帖不见了.现在补充:


WOOL用JAVA不算,呵呵!

如果我出题,一定要加上"不得使用厍函数,输入输出的测试除外"

iptton 发表于 2006-6-17 18:35

楼上的……

strcat也是库函数的说……

powerwind 发表于 2006-6-17 22:01

既然楼上这样说,我就改一下!

//相当于strlen()
int getLength(char str[])
{
        int i=0;
        while(str!='\0')i++;
        return i;
}
//相当于strcat
void stringCat(char *a,char*b)
{
        int len,i=0;
        len=getLength(a);
        while (b!='\0')
        {
                a=b;
                i++;
        }
        a='\0';
}
//
void reverseWord(char*src,char*dest)
{
        int i,len;
        char*p;
        len=strlen(src);
        p=src+len-1;
        *dest='\0';
        for(i=0;i<len;i++)
                if((*(p-i))==' ')
                {
                        stringCat(dest,(p-i+1));
                        stringCat(dest," ");
                        if(i!=len-1)
                                *(p-i)='\0';
                }
                stringCat(dest,p-len+1);
}
int main()
{
        char str[]="The house is blue";
        char a;
        reverseWord(str,a);
        printf("%s\n",a);
        system("pause");
        return 0;
}

iptton 发表于 2006-6-18 00:10

我写的strcat
char * myStrcat(char *des,char *src)
{
/*
   The des's length MUST larger than
   the total number of new string
*/
char *tmp=des;
while(*des++);
des--;
while(*src)
{
    *des++=*src++;
}
*des='\0';
return tmp;
}

wool王 发表于 2006-6-18 16:08

hjack,如果用标点也可以分词的话，我写的那段可以改成正则表达式分词。

wool王 发表于 2006-6-18 16:09

原帖由 powerwind 于 2006/6/17 09:34 发表


只有空格就可以啦.
因为后院搬家的原因,我回的一个帖不见了.现在补充:


WOOL用JAVA不算,呵呵!

如果我出题,一定要加上"不得使用厍函数,输入输出的测试除外"

不用java的话我投降，哈哈。我已经被当时笔试的那些C++吓怕了。看到指针就头疼。

iptton 发表于 2006-6-18 16:45

原帖由 wool王 于 2006-6-18 16:08 发表
hjack,如果用标点也可以分词的话，我写的那段可以改成正则表达式分词。


正则表达式……

不明，深奥……    上网查了下，看起来就晕，就像WOOL看指针一样

如果是标点分词的话，我的只要改掉宏 DIVI 就行了#define DIVI ','

sasadong 发表于 2006-6-18 20:18

php实现



1,利用已有的函数

function reverseStringWordByWord( $sInput ) {
$aWords = explode( ' ', $sInput) ;
$aWordsReversed = array_reverse( $aWords ) ;
$sOutput = implode( ' ', $aWordsReversed ) ;
return $sOutput ;
}

2,老老实实的写算法

function reverseStringWordByWord( $sInput ) {
$sOutput = '' ;
$sWordTmp = '' ;
for( $i =strlen( $sInput ) - 1; $i >= 0; $i-- ) {
    if ( $sInput{ $i } == ' ' ) {
       $sOutput .= $sWordTmp . ' ' ;
       $sWordTmp = '' ;
    }
    else {
      $sWordTmp = $sInput{$i} . $sWordTmp ;
    }
}
$sOutput .= $sWordTmp ;//the first word in the origin string

return $sOutput ;
}

3,正则

function reverseStringWordByWord( $sInput ) {
$sInput .= ' ' ; //construct for the regex search
$sOutput = '' ;
$sPatten = '/(\w+)\s+/i' ;
if ( preg_match_all( $sPatten, $sInput, $aMatches ) === false ){
    return false ;
}
else {
    for( $i = count( $aMatches ) - 1; $i >= 0; $i-- ) {
      $sOutput .= ( $aMatches[$i] . ' ' ) ;
    }
    $sOutput = rtrim( $sOutput ) ;
}

return $sOutput ;
}

4,strtok的用法
function reverseStringWordByWord( $sInput ) {
$sOutput = '' ;
$sWord = strtok( $sInput, " " );

while ( $sWord !== false ) {
    $sOutput = $sWord . ' ' . $sOutput ;
    $sWord = strtok(" ");
}
$sOutput = rtrim( $sOutput ) ;

return $sOutput ;
}



[ 本帖最后由 sasadong 于 2006-6-18 21:12 编辑 ]

hjack 发表于 2006-6-22 00:16

shell实现


#/bin/bash

count=$#
while [ $count -gt 0 ]
do
cmd="echo ""$""$count"
eval $cmd
count=`expr $count -1`
done

查看完整版本: 一道面试题(以单词为单位的反转)