×

Loading...
Ad by
  • 最优利率和cashback可以申请特批，好信用好收入offer更好。请点链接扫码加微信咨询，Scotiabank -- Nick Zhang 6478812600。
Ad by
  • 最优利率和cashback可以申请特批，好信用好收入offer更好。请点链接扫码加微信咨询，Scotiabank -- Nick Zhang 6478812600。

@Florida

详细算法 （Frankwoo说过了)

nick_name(Nick_name)
算法 （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的话 :-)
(#3558832@0)
Last Updated: 2007-3-17
This post has been archived. It cannot be replied.
Report

Replies, comments and Discussions:

  • 工作学习 / 专业技术讨论 / 求解， 哪位C语言大侠给写一个。 -billhao(bill); 2007-3-15 {142} (#3554923@0)
    要求： 反转字符串中的单词。
    例如： 输入: “I am a student”
    输出：“student a am I”
    函数原型： char * ReverseWord(char * src)
    • strtok() -flyingdagger(飞刀); 2007-3-15 (#3554927@0)
      • 不是， 要求在原地址空间内。 另外， strtok会把空格都虑掉的 -billhao(bill); 2007-3-15 (#3554932@0)
    • ... -niu1986(只吃草的牛); 2007-3-15 {556} (#3555057@0) 
      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;
}
      • 还有个更扯的 -billhao(bill); 2007-3-15 {203} (#3555151@0)
        不想累你， 还有个更扯的。
        bool TestStr(char *src1, char* src2)

        输入： 任意字母的组合， 返回true.
        例如： abc的组合有abc, acb, bca, cab等，任选2个作为输入，返回true.
        但如果有个输入是aab, 则返回false.
        • 分别排序再进行串比较就可以啊 -wangqingshui(忘情水); 2007-3-15 (#3555582@0)
          • 这是一道微软面试题，他们不要这种方法：（（（ -billhao(bill); 2007-3-16 (#3555945@0)
        • 排序，比较。 -frankwoo(柳五随风); 2007-3-15 (#3555666@0)
        • 可以用hashtable. -canadiantire(轮胎-pax et lux); 2007-3-16 (#3556142@0)
          • 你的code怎么丢了？ -billhao(bill); 2007-3-16 (#3557513@0)
            • 写得太滥，不想贴了。 -canadiantire(轮胎-pax et lux); 2007-3-16 (#3557741@0)
              • 你也太谦虚了吧? -iwantcar(恶疾,时日无多,戒网); 2007-3-16 (#3557893@0)
              • 太谦虚了。 -frankwoo(柳五随风); 2007-3-16 (#3557942@0)
              • 写的不滥，有时这编程还挺有意思。 -billhao(bill); 2007-3-16 (#3558021@0)
              • 也是，这东西没什么技术含量。 -frankwoo(柳五随风); 3.18 17:22 (#3560494@0) -iwantcar(恶疾,时日无多,戒网); 2007-3-21 (#3565979@0)
        • ... -niu1986(只吃草的牛); 2007-3-16 {424} (#3558064@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 -wangqingshui(忘情水); 2007-3-16 (#3558131@0)
        • 这个比上边那道的简单多了。 -baalinca(scarb); 2007-3-17 (#3559510@0)
      • 这应当是最优的了. -wangqingshui(忘情水); 2007-3-15 (#3555584@0)
      • 妙，不过这种面试题有点耍赖，如果从来接触过，不太可能很短时间想到算法。 -baalinca(scarb); 2007-3-17 (#3559504@0)
      • 这么复杂？应该在5行以内就搞定了啊 -googleabcd(古狗); 2007-3-18 (#3559820@0)
    • 分别从头和尾扫描 到最短的单词位置，交换内容，然后将长的单词的剩余部分移动，调整头尾位置继续递归。 -frankwoo(柳五随风); 2007-3-16 (#3555690@0)
    • Answer -tiro(新手上路); 2007-3-16 {476} (#3557803@0)
      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说过了) -nick_name(Nick_name); 2007-3-17 {953} (#3558832@0)
      算法 （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的定义。 -niu1986(只吃草的牛); 2007-3-17 (#3558850@0)

More Topics

  • 看大家讨论日语，俺也正在认真学习。其实语言问题应该是很快也很容易就解决的，可能比自动驾驶来的还快。TREK里面，全宇宙的人都在大脑里安装了UNIVERSAL TRANSLATOR，外星人之间相互交流无障碍。废话少说，看视频。。。加上个MIC和耳机，不同国家的人就可以无障碍交流。
  • 肉脸真有搞 IT 的？Linux 把俄国中国伊朗踢出去了好像肉脸 IT 没啥感觉似的
  • 请问web developer和software developer技术上有什么区别？
  • Elon Musk 带着川普总统奔向火星了。
  • 扔硬币的实验研究
    • 枫下论坛主坛 /  工作学习 /  专业技术讨论