一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 806|回复: 11
收起左侧

[Leetcode] LeetCode 392超时,但实在不觉得有小于O(n)的方法

[复制链接] |试试Instant~ |关注本帖
freeaccount 发表于 2016-10-23 06:14:48 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Is Subsequence,https://leetcode.com/problems/is-subsequence/
两个指针,如果指向元素相等则同时移动两个指针,否则只移动t的指针,如果过程中遍历完s,则返回true,否则,t遍历完时s还没遍历完,返回false。复杂度为O(n),其中n是t的大小,不是s的大小。

用C写的,代码如下,不好意思不知道怎么调格式。
bool isSubsequence(char* s, char* t)
{
    int index_s = 0;
   
    int len_s = strlen(s);
   
    if (!len_s)
    {
        return true;
    }
   
    int loop;
   
    for (loop = 0; loop < strlen(t); ++loop)
    {
        if (s[index_s] == t[loop])
        {
            ++index_s;
            
            if (index_s == len_s)
            {
                return true;
            }
        }
    }
   
    return false;
}

在t很长的一个case超时,但是实在想不出有什么 地方可以优化,多处搜索,都是一样的思路,虽然语言和代码有所差别。难道是因为用了C?


stellari 发表于 2016-10-23 06:53:41 | 显示全部楼层
难道是因为用了C?

某种意义上可以这么说,但不是因为C慢,而是你这里套用了其他语言的思维:在其他OO语言中,string.size()一般都是个O(1)操作,所以在循环结束条件处用t.size()这类的写法没问题;但你这里用的strlen(t)本身却是一个O(n)操作,所以最后的代码被拖慢成了O(n^2),自然无法通过大test case了。如果你想用t的长度的话,开一个变量暂存之即可。

更关键的一点是,C程序员压根就不会去先调用strlen,而是通常直接开始循环,直到检测到‘\0’为止。而且s [ i ] 这种用法其实是*(s+i),也就是说每次循环里还得多做一次+i操作,对于强调极致性能的C来说,也最好是能不这样用就不这样用。所以C程序员的代码可能会是这个样子的:

  1. bool isSubsequence(char* s, char* t)
  2. {
  3.     while (*s && *t)  // 若s和t都未扫描完
  4.     {
  5.         if (*s == *t++) s++;  // 若s[i]==t[j]则下次比较s[i+1]; 无论如何下次都比较t[j+1]
  6.     }
  7.     return !(*s);  // 若s扫描完,则返回真;否则返回假
  8. }
复制代码
关于C风格的问题你不妨去看看Kernighan and Ritchie的C Programming Language,相信会有不少帮助。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

飞仙公子 发表于 2016-10-23 06:51:07 | 显示全部楼层
关键在于那个for loop,同样都是O(n)的算法
我改写了一下,然后过了,可以参考下
bool isSubsequence(char* s, char* t){
   int index_t = 0;
   int len_s = strlen(s);
   int len_t = strlen(t);
   if (!len_s)
   {
      return true;
   }
   int loop;
   for(loop = 0; loop < len_s; loop++)
   {
      while (s[loop] != t[index_t]){
         index_t++;
         if (index_t >= len_t){
            return false;
         }
      }
      index_t++;
   }
   return true;
}
回复 支持 反对

使用道具 举报

jerryzhang 发表于 2016-10-23 06:54:37 | 显示全部楼层
算法复杂度都是O(m*n)。
这个时候需要优化。把短的循环放在外层是 O(n)。把长的循环放在外层,很可能就是O(m*n)了。
回复 支持 反对

使用道具 举报

jerryzhang 发表于 2016-10-23 06:59:44 | 显示全部楼层
stellari 发表于 2016-10-23 06:53
某种意义上可以这么说,但不是因为C慢,而是你这里套用了其他语言的思维:在其他OO语言中,string.size() ...

你这个解法太棒了。
不过在编译器里面会优化strlen(t)的操作,不会每个循环都做一次strlen(t)查长度。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-23 06:59:50 | 显示全部楼层
jerryzhang 发表于 2016-10-23 06:54
算法复杂度都是O(m*n)。
这个时候需要优化。把短的循环放在外层是 O(n)。把长的循环放在外层,很可能就是 ...

不,判断subsequence的复杂度就是O(n), 或者说是O(m+n):s和t上各一个指针,只加不减,s和t中每个元素最多只会被存取1次,最多只需O(m+n)次操作。substring的naive做法才是O(mn)
回复 支持 反对

使用道具 举报

jerryzhang 发表于 2016-10-23 07:22:11 | 显示全部楼层
stellari 发表于 2016-10-23 06:59
不,判断subsequence的复杂度就是O(n), 或者说是O(m+n):s和t上各一个指针,只加不减,s和t中每个元素最 ...

两个嵌套的loop复杂度是m*n呀。
eg. s = aa, t = (1000*b)aa。s loop放外层的话总比较次数1002,t loop放外层的话,总比较次数是2002.
m很小的时候没啥感觉,m比较大的时候,虽然worst case的big O是一样的,但是差别还是很大的。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-23 12:17:50 | 显示全部楼层
jerryzhang 发表于 2016-10-23 07:22
两个嵌套的loop复杂度是m*n呀。
eg. s = aa, t = (1000*b)aa。s loop放外层的话总比较次数1002,t loop ...

不是这样的。首先这题压根也不需要嵌套循环,楼主最开始的无嵌套循环的代码把strlen(t)改掉后就可以过。编译器确实可能将其优化,但是不能依赖于这一特性。LC上很可能就是没有优化的;其次是楼主改后的代码虽然看起来有二层循环,但是内层循环其实是个“伪循环”。因为它的特性是不管外层执行多少次,内层中的每句代码都总共会被执行t.size()(也就是n)次。证据是index_t只增不减,且一旦index_t超过len_t就会退出,换句话说,index_t++这句代码最多能被执行n次,而不是mn次. 因此最后的总时间复杂度还是O(n)。

你的意思我明白,但是你说的那种嵌套循环算法是在找substring问题中使用的。这里的subsequence不需要连续,所以并不需要二层循环。
回复 支持 反对

使用道具 举报

 楼主| freeaccount 发表于 2016-10-23 17:34:51 | 显示全部楼层
飞仙公子 发表于 2016-10-22 17:51
关键在于那个for loop,同样都是O(n)的算法
我改写了一下,然后过了,可以参考下
bool isSubsequence(cha ...

谢谢。已经确认原因是strlen(t)在作为循环判断条件时未被优化所以每次都被调用,导致实质复杂度为平方。
回复 支持 反对

使用道具 举报

 楼主| freeaccount 发表于 2016-10-23 17:44:32 | 显示全部楼层
stellari 发表于 2016-10-22 17:53
某种意义上可以这么说,但不是因为C慢,而是你这里套用了其他语言的思维:在其他OO语言中,string.size() ...
某种意义上可以这么说


其实我要表达的是,leetcode会不会因为C是编译成native executable所以会比其它语言快(虽然未必)导致为C的代码设置了更小的时间限制。

你这里套用了其他语言的思维


其实并没有,我很少用OO语言,因为我做的安全/内核之类的东西,只能用C和汇编。然后刷题的时候我追求写代码的速度,所以就按直白的思维写了,并没有考虑“美感”的问题。而且我经常会调试汇编,知道编译器的优化极其NB,所以以为strlen这个地方就默认会被优化了,大不了strlen是个O(n)循环再是个O(n)那O(2n)还是O(n)嘛。。。没想到被坑了

PS:插入代码怎么操作?我为啥只能插入引用。。。。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-24 02:59:16 | 显示全部楼层
freeaccount 发表于 2016-10-23 17:44
其实我要表达的是,leetcode会不会因为C是编译成native executable所以会比其它语言快(虽然未必)导 ...
大不了strlen是个O(n)循环再是个O(n)那O(2n)还是O(n)嘛


如果strlen每次循环都是O(n),那n次调用strlen的时间复杂度就是O(n^2),而非O(2n). 另外编译器确实能够可以优化掉,但是不能假设这点总成立,特别在刷题网站上,为了暴露出代码的实际复杂度,很可能会特意关闭优化。
回复 支持 反对

使用道具 举报

 楼主| freeaccount 发表于 2016-10-24 10:48:57 | 显示全部楼层
stellari 发表于 2016-10-23 13:59
如果strlen每次循环都是O(n),那n次调用strlen的时间复杂度就是O(n^2),而非O(2n). 另外编译器确实能 ...

我的意思是。。。我假设编译器会优化,这样我的for循环在进入时,会计算一次strlen,是O(n),之后不会再计算,然后循环本身是个O(n), 这样总的算法还是O(n),只是常数因子不同。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 16:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表