[科普贴]如果遇到天价医疗账单该怎么办

一亩三分地论坛

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

最近看过此主题的会员

锦晖律师事务所
12月16日
H1B讲座通知
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2037|回复: 11
收起左侧

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

[复制链接] |试试Instant~
我的人缘0
freeaccount 发表于 2016-10-23 06:14:48 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (96)
 
 
7% (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% (407)
 
 
1% (5)  踩
难道是因为用了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)   【踩】
全局: 顶  75% (6)
 
 
25% (2)  踩
算法复杂度都是O(m*n)。
这个时候需要优化。把短的循环放在外层是 O(n)。把长的循环放在外层,很可能就是O(m*n)了。
回复

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

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

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

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


回复

使用道具 举报

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-11 02:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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