【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 1869|回复: 11
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
freeaccount 发表于 2016-10-23 06:14:48 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (79)
 
 
9% (8)  踩

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

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

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?



上一篇:关于函数
下一篇:关于UML的使用
我的人缘0
stellari 发表于 2016-10-23 06:53:41 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
难道是因为用了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大米 +5 收起 理由
OO0OO + 5 感谢分享!逮住野生大神!

查看全部评分

回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
飞仙公子 发表于 2016-10-23 06:51:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
关键在于那个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;
}
回复

使用道具 举报

我的人缘0
jerryzhang 发表于 2016-10-23 06:54:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  50% (2)
 
 
50% (2)  踩
算法复杂度都是O(m*n)。
这个时候需要优化。把短的循环放在外层是 O(n)。把长的循环放在外层,很可能就是O(m*n)了。
回复

使用道具 举报

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

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

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
stellari 发表于 2016-10-23 06:59:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
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)
回复

使用道具 举报

我的人缘0
jerryzhang 发表于 2016-10-23 07:22:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  50% (2)
 
 
50% (2)  踩
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是一样的,但是差别还是很大的。
回复

使用道具 举报

我的人缘0
stellari 发表于 2016-10-23 12:17:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
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不需要连续,所以并不需要二层循环。

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| freeaccount 发表于 2016-10-23 17:44:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (79)
 
 
9% (8)  踩
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:插入代码怎么操作?我为啥只能插入引用。。。。
回复

使用道具 举报

我的人缘0
stellari 发表于 2016-10-24 02:59:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (366)
 
 
1% (4)  踩
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). 另外编译器确实能够可以优化掉,但是不能假设这点总成立,特别在刷题网站上,为了暴露出代码的实际复杂度,很可能会特意关闭优化。

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

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

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-20 03:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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