C算法上一道题，请大家帮我看看有什么思路。 - 编程论坛

#2

a1511412013-02-18 18:11

有点抽象

#3

青春无限2013-02-18 18:19

看看

#4

zyy_hz2013-02-18 21:22

有一种思路就是一下：
比如说前面已经知道了最长为7个，如果后面的第13个不为空格，就可以直接跳到第14个判断了，因为8和12之间的都不需要判断。
不知道对你有没有用。
新手上路。多指教。

#5

zyy_hz2013-02-18 21:32

好像有点问题可以这样直接判断第15个，如果第15个不是则可以跳到16个重新开始，因为是要最长的长度。如果15个也是的话就看中间的，然后看后一段直至都是空格，如果其中有个不是空格就可以跳了。

#6

zl520k2013-02-20 15:13

网上有人说折半进行查找空格的，不知道对不对？

#7

fanpengpeng2013-02-20 15:31

用zyy_hz说的方法写了一个程序，不知道合不合要求

程序代码：

#include <stdio.h>
#include <string.h>

/***********************************

* 参数len: 字符串长度
            防止指针在间跳后越界

**********************************/
int max_blankarr(char *str, int len);

int main()
{
    char test[] = "The following string has 20 blankspaces:                    ";

    printf("The max blank arry length is %d.\n", max_blankarr(test, strlen(test)));

    return 0;
}

int max_blankarr(char *str, int len)
{
    int maxlen, index, i;

    for(maxlen = 0, index = 0; index+maxlen < len; index++){
        if(str[index] == ' ')
            if(str[index+maxlen] == ' '){
                i = 1;
                while(++index < len && str[index] == ' ') ++i;
                (i > maxlen)? maxlen = i : maxlen;
            }
            else index += maxlen;
    }

    return maxlen;
}

#8

fanpengpeng2013-02-20 16:38

上面的max_blankarr函数重新优化了一下，这样效率比刚才那个要高

程序代码：

int max_blankarr(char *str, int len)
{
    int maxlen, index, i;

    for(maxlen = 0, index = 0; index+maxlen < len; index++){
        if(str[index+maxlen] != ' ')
            index += maxlen;
        else
            if(str[index] == ' '){
                i = 1;
                while(++index < len && str[index] == ' ') ++i;
                (i > maxlen)? maxlen = i : maxlen;
            }
    }

    return maxlen;
}

#9

beyondyf2013-02-20 19:52

我不信能有比O(n)更高效的算法。要求尽量少检查串的字符，但每个字符至少得检查一次吧。提示更是莫名其妙。

程序代码：

int blank_len(char *s)
{
    int max, c;
    for(max = c = 0; *s; s++)
        if(*s == ' ') c++;
        else
        {
            if(max < c) max = c;
            c = 0;
        }
    return max > c ? max : c;
}

[ 本帖最后由 beyondyf 于 2013-2-20 19:54 编辑 ]

#10

fanpengpeng2013-02-20 20:41

楼上的回答欠考虑，关于这个问题每个字符都检查一遍是最低效的实现方法
其实存在许多不必要的比较可以优化掉的
当已经搜索到最长为n的连续空格时，继续搜索时如果当前位置后n+1处的字符不为空格，则这段字符至多为n个连续的空格
完全可以跳过不比较，当连续空格越长时这样的优势会更明显
举个例子来说：“a__b__f”,'_'表示空格
当我们检查到b的时候，就已经知道最大长度至少是2，那么接着只要直接看后面2+1处的字符，即f，不是空格，那么b后面到f这一段至多只有2个连续空格
就可以不用搜索，这里就有了优化的空间

#11

beyondyf2013-02-20 20:52

回复 10楼 fanpengpeng

楼上批评的对，确实欠考虑。呵呵，受教了，感谢指正！

#12

zl520k2013-02-21 11:02

楼上的回答，还有一个问题，就是如果加了n个空格数得到位置还是空格，那这个空格位置之前和字符之间的空格将没有计算。

#13

fanpengpeng2013-02-21 16:21

回复 12楼 zl520k

没明白你的意思
我举的例子只是说存在那样的情况可以做优化并没有说如果n+1位置是空格就不处理
只有在n+1位置不是空格的情况下才可以跳过不比较如果不管是不是空格都跳过那这样的算法还有什么意义
你仔细读一下我发的代码后面修正的那个函数看看是不是确实有没有考虑到的情况欢迎指正

#14

逆风而前2013-02-25 22:45

a$$$$$b$$$$$$$cvbgf$$$$ 字符串
_12345_1234567
5个 7个
$代表空格
当判后断完b最大空格为5个，会跳到第二个5处就是红色的$ 进行判断
按这样计算出为最大空格为5个，事实是7个。

[ 本帖最后由逆风而前于 2013-2-25 22:47 编辑 ]

#15

逆风而前2013-02-25 22:48

回复 8楼 fanpengpeng

a$$$$$b$$$$$$$cvbgf$$$$ 字符串
_12345_1234567
5个 7个
$代表空格
当判后断完b最大空格为5个，会跳到第二个5处就是红色的$ 进行判断
按这样计算出为最大空格为5个，事实是7个。

#16

逆风而前2013-02-25 22:50

回复 9楼 beyondyf

10楼的说法不一定对
a$$$$$b$$$$$$$cvbgf$$$$ 字符串
_12345_1234567
5个 7个
$代表空格
当判断完b后最大空格为5个，会跳到第二个5处就是红色的$ 进行判断
按这样计算出为最大空格为5个，事实是7个。

#17

azzbcc2013-02-25 23:13

好贴，仔细想了想，杨大哥的O(n)应该可以了吧，10楼的问题，会遇到14楼提到的情况，也就是说要再加一个判断，反而有可能增加判断次数，而且代码更复杂了。。。

前面还有提到二分法，貌似不可行，因为当前检测到的空格并不一定包含在最长序列中，还有其他的问题，也有些想不明白。。。

有时间试试吧，还得预习明天的课呢。。。

#18

fanpengpeng2013-02-25 23:32

回复 14楼逆风而前

哎吆喂我都不知道说什么好了
你至少应该先把代码运行一下再看结果是7还是5 是不是
就在上面刚刚回答了前面的人的疑问说不会因为出现空格就不处理继续往后跳
而是说在不是空格的情况下才可以省去不处理中间字符
你这儿又来了哎浮躁啊