(leetcode)Reverse Words in a String的C代码实现

 

      最近想好好的补补基础,于是又开始搞起来C语言,做做题目去练练。在leetcode上遇到了一道巨简单的题目,我比较菜,用C做了半天才搞出来,有兴趣的可以看下。

 

     

1.题目:

 

     题目要求很简单(http://oj.leetcode.com/problems/reverse-words-in-a-string/):

         Given an input string, reverse the string word by word.

         For example,
        Givens = “the sky is blue“,
        return “blue is sky the“.

 

      非常直白、明了,我就没啥可翻译的了。

 

2.分析:

   

     要求很简单,但做的去做起来还有点麻烦。 最直接的就是直接把字符串中的每个单词给拿出来,然后仅仅简单的翻转所有的单词就ok了。

 

    这种的实现理由Py这种非常简单,先调用split去提取单词,然后使用reverse等进行翻转,再接着使用join去合并就完事了,几行代码就搞定了。但在C语言中没有现成的split、join这些函数去使用,所以我不得不考虑新的方法,当然你也可以自己去实现split、join这些函数。

 

3.我的另类思路:

 

      我在观察两个字符串的时候发现有一定的规律,所以考虑是直接按照这个规律进行拷贝就可以了。仔细看就可以知道,第二个字符串中:

 

     

"the sky is blue"

"blue is sky the"

        the的开始位置是字符串末尾的位置向前移动the单词长度的位置。同理,sky是字符串末尾的位置向前移动到”the sky”的长度的位置,即末尾位置减去the+sky的位置。所以我决定按照这个规律去翻转。

 

    

4.代码实现:

 

     具体的代码实现如下:

 

/* reverse.c: reverse the word in the string
* Write: furion
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int reverseWords(char *str)
{
        int i,j,k,word_len,len;
        /*
* use i to scan the whole string stop when it meet space(' ') or the end('\0')
* use j to store the postion where i stoped
* word_len to store the length to copy (i - j)
*/
        i=j=k=word_len=0;
        len=strlen(str);
        char *ret_str;
        ret_str =(char *)malloc(sizeof(*str));
        while(1) {
                if((*(str+i) == ' ') || (*(str+i) == '\0')) {
                     word_len = i -j;
                     int x,y;
                     //temp var used for loop copy
                     y=0;
                     for(x=word_len;x>0;x--) {
                         *(ret_str+ len -j - x ) = *(str+j+y);

                         y++;
                     }
                     *(ret_str+ len -j - 1 - word_len ) = ' ';
                     //reset the j postion to store new the postion of i
                     j=i+1;
                     if(*(str+i) =='\0')
                        break;
                }
                i++;

          }
        printf("%s",ret_str);
        printf("\n");
}

int main()
{
        char s[100];
        printf("please enter an string\n");
        fgets(s,sizeof(s),stdin);
        int i=0;
        //remove the '\n' char
        while(s[i] != '\0') {
                if(s[i] =='\n')
                        s[i] = '\0';
                i++;
        }

        reverseWords(s);
}

 

       稍微有点绕,大致举例说下:

 

"the sky is blue"

"blue is sky the"

i=0,j=0, word_len=0,

i=3,j=i'+1=0, word_len = i -j = 3

i=7,j=i'+1=3 ,word_len = i -j = 4

i=10,j=i'+1=8,word_len = i - j = 2

i=14,j=i'+1=10,word_len = i - j =4

 

              

   我使用了i,j两个变量,i用来扫描整个字符串中上次的空格或者结尾,用力拆分单词,然后j用来存储上次的i(i’代指上次的i的值。)位置,i – j 的长度是需要拷贝的字符串长度,而拷贝的位置,对于原始字符串来说就是从上次的单词分界出开始,这里我每次利用j+1来定位上次的单词的单词边界。

      

   而对已目的地址就困难了点,按照前面的规律,每次的拷贝的位置是字符串末尾位置减去已经拷贝的字符串的长度位置+需要拷贝的字符串的长度。同时对于每次的拷贝,原始字符串需要依次累加,这里我使用y进行累加,而对于目的字符串则需要依次进行递减操作,我使用了x。

 

  其他的就没什么了:

                 *(ret_str+ len -j – 1 – word_len ) = ‘ ‘;

 

    用来拷贝空格,前面没有拷贝这个。

 

代码地址:

       https://github.com/siashero/leetcode_C/blob/master/reverse.c

后续我有更好的思路会继续更新的,不过暂时就这样吧。

Leave a Reply

Your email address will not be published. Required fields are marked *


To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax