×

Loading...
Ad by
  • 推荐 OXIO 加拿大高速网络,最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务
Ad by
  • 推荐 OXIO 加拿大高速网络,最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

...

char* ReverseWord(char* in)
{
    char *p, *q, *r;
    char c;
    for (p = q = in; ;p++)
    {
        if ((*p == ' ') || !*p)
        {
            for (r = p - 1; q < r; q++, r--)
            {
                c = *r;
                *r = *q;
                *q = c;
            }
            q = p + 1;
            if (!*p)
                break;
        }
    }
    for (q = in, p--; q < p; q++, p--)
    {
        c = *q;
        *q = *p;
        *p = c;
    }
    return in;
}
Report

Replies, comments and Discussions:

  • 工作学习 / 专业技术讨论 / 求解, 哪位C语言大侠给写一个。
    要求: 反转字符串中的单词。
    例如: 输入: “I am a student”
    输出:“student a am I”
    函数原型: char * ReverseWord(char * src)
    • strtok()
      • 不是, 要求在原地址空间内。 另外, strtok会把空格都虑掉的
    • ...
      char* ReverseWord(char* in)
      {
          char *p, *q, *r;
          char c;
          for (p = q = in; ;p++)
          {
              if ((*p == ' ') || !*p)
              {
                  for (r = p - 1; q < r; q++, r--)
                  {
                      c = *r;
                      *r = *q;
                      *q = c;
                  }
                  q = p + 1;
                  if (!*p)
                      break;
              }
          }
          for (q = in, p--; q < p; q++, p--)
          {
              c = *q;
              *q = *p;
              *p = c;
          }
          return in;
      }
      
      • 还有个更扯的
        不想累你, 还有个更扯的。
        bool TestStr(char *src1, char* src2)

        输入: 任意字母的组合, 返回true.
        例如: abc的组合有abc, acb, bca, cab等,任选2个作为输入,返回true.
        但如果有个输入是aab, 则返回false.
        • 分别排序再进行串比较就可以啊
          • 这是一道微软面试题,他们不要这种方法:(((
        • 排序,比较。
        • 可以用hashtable.
          • 你的code怎么丢了?
            • 写得太滥,不想贴了。
              • 你也太谦虚了吧?
              • 太谦虚了。
              • 写的不滥,有时这编程还挺有意思。
              • 也是,这东西没什么技术含量。 -frankwoo(柳五随风); 3.18 17:22 (#3560494@0)
        • ...
          bool TestStr(char *src1, char* src2)
          {
              int n[256], m[256];
              int i;
              for (i = 0; i < 256; i++)
              {
                  n[i] = m[i] = 0;
              }
              while (*src1)
              {
                  n[(unsigned char)*src1++]++;
              }
              while (*src2)
              {
                  m[(unsigned char)*src2++]++;
              }
              for (i = 0; i < 256; i++)
              {
                  if (n[i] != m[i])
                      return false;
              }
              return true;
          }
          
          • excellent
        • 这个比上边那道的简单多了。
      • 这应当是最优的了.
      • 妙,不过这种面试题有点耍赖,如果从来接触过,不太可能很短时间想到算法。
      • 这么复杂?应该在5行以内就搞定了啊
    • 分别从头和尾扫描 到最短的单词位置,交换内容,然后将长的单词的剩余部分移动,调整头尾位置继续递归。
    • Answer
      void ReverseSub(char *s, char *e) {
      // from billhao, thanks to billhao
      while (s < e) {
      char tmp = *--e;
      *e = *s;
      *s++ = tmp;
      }
      }

      char *ReverseWord(char *src) {
      if (src) {
      ReverseSub(src, src + strlen(src));
      char *s = src, *e;
      while (*s) {
      while (*s && *s == ' ') s++;
      if (!*s) break;
      e = s + 1;
      while (*e && *e != ' ') e++;
      ReverseSub(s, e);
      s = e;
      }
      }
      return src;
      }
    • 详细算法 (Frankwoo说过了)
      算法 (Frankwoo说过了)

      示例子串: ABCDE FG HIJ k LMO
      1. 分别从左右扫描,得到左ABCDE长度为5, 右LMO长度3,对较长者调整,如果等长,调过此步
      ABCDE调整成CDEAB, 即把长度为5-3=2的子串从头移到尾,这可以是一个O(1)的动作。笨了一点
      如下ABCDE -> ACBDE->ACDBE->ACDEB ->CADEB->CDAEB->CDEAB
      没办法,时间换空间了。我怀疑会有这样的现实需要,不过做题嘛,丁是丁卯是卯。
      如果给出来每个字的最大长度,允许用一个缓冲区的话,那就不用那么多循环咯,不过时间复杂度还是O(n) n为最大单词长度
      经此步,得到 CDEAB FG HIJ k LMO

      2. 首尾交换 得到 LMOAB FG HIJ k CDE
      3 对从A到C前面的那个空格开始的子串,重复1-2的动作,直到子串中剩下0或1个单词。

      需要注意的是空格的处理。如果两个单词间可以用不只一个空格隔开,那空格是前结合还是后结合会影响输出结果,如下例
      ABC__DEF_G (_表示空格)
      转换结果究竟是应该为G__DEF_ABC还是G_DEF__ABC, 这个需要规定好。

      上面的算法可以简单的用循环实现,无须用到递归。空间复杂度为O(1)或O(0) (如果用异或实现swap的话 :-)
      • 简单事情复杂化。而且需要重新学习一下Big O的定义。