S******t
发帖数: 151 | 1 +1
这个的实现复杂度秒杀一众AC自动机, 后缀xxx :) |
|
r**h
发帖数: 1288 | 2 请教一下这题的标准做法是什么？
我这种做法可以吗？
数字的下一个valid字符：右括号、操作符、数字
操作符的下一个valid字符：左括号、数字
左括号的下一个valid字符：左括号、数字
右括号的下一个valid字符：右括号、操作符
就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。 |
|
r**h
发帖数: 1288 | 3 请教一下这题的标准做法是什么？
我这种做法可以吗？
数字的下一个valid字符：右括号、操作符、数字
操作符的下一个valid字符：左括号、数字
左括号的下一个valid字符：左括号、数字
右括号的下一个valid字符：右括号、操作符
就和自动机一样检查下一个字符是否valid。同时兼顾检查左右括号的匹配。 |
|
h*****a
发帖数: 1718 | 4 regular expr 是比较难的题目，不过现实中的实现都是用自动机，这种问题在
interview的时候问比较扯淡，用递归应付大部分的时候都不会有问题。
recover bst中序遍历总是需要一个栈吧？
search in rotated sorted array II 最坏情况O(n)没错，但碰到相等直接线性扫瞄确
实不是最优的。
logn |
|
A******g
发帖数: 612 | 5 大牛，哥们我并不是不会写这题，只是觉得这题要一次bugfree或者几乎bugfree还是有
难度的, 背题不至于，上过编译原理或者自动机和形式语言课的看一眼就能写出这个表
达式，基本功而已 |
|
b*****g
发帖数: 145 | 6 我上过最难的课是数理逻辑，第一章是自动机什么的，巨难，班上一大半的人都听不懂
难。 |
|
n*****f
发帖数: 17 | 7 恭喜LZ！！！
题目不错，写些思路，如果有问题或者更好的思路，欢迎各位大牛指点
facebook
2. 先比较两个字符串的长度。如果相等，正向和反向分别求最长公共前缀，之和大于
等于串长-1就是similar；如果长度相差1，正向和反向分别求最长公共前缀，之和大于
等于短串的长度就是similar；否则不是similar。前两种情况可以合并一下，更简单，
O(n)
google
1. 维护两个指针从两头向中间扫
2. 每个function_name记录call的次数和总的duration time
3. parent -> child建边，入度为0的点是root，从root出发BFS或DFS
4. 同上
5. 同上
twitter
2. trie
ebay
1. 先git log找到相应时间段的commits，再用git diff找出时间段前后两次修改了哪
些file
3. ac自动机
walmartlab
1. 先看最大值能否正数，找最大的三个正数或绝对值最大的两负一正；如果不行，看
数组里有没有0；还不行就找绝对值最小的三个数
2. ^(https?:\/\/)?([\da-z\.... 阅读全帖 |
|
q****m
发帖数: 177 | 8 ebay 第三题ac自动机怎么搞？感觉对每个word,用一次kmp吗？ |
|
|
|
A*****i
发帖数: 3587 | 11 个人经验是
凡是要跑字典的东西，trie应该是首选
而且trie做自动机上面也有得天独厚的优势啊为什么不用trie？ |
|
A*****i
发帖数: 3587 | 12 这个用自动机就好了么，把那几个罗马数字pattern弄好然后一个字母一个字母扫么，
能跳到某一个的最后一个不就是valid么
DFA么 |
|
|
w*****j
发帖数: 226 | 14 补充一句，自动机另一种写法是用二维表格来记录状态转换，更简洁，但是可读性更差 |
|
|
w*****j
发帖数: 226 | 16 补充一句，自动机另一种写法是用二维表格来记录状态转换，更简洁，但是可读性更差 |
|
|
b***e
发帖数: 1419 | 18 我来给你试着解释一下。这个题说到底是一个有限自动机的问题。我们可以定义一下四
种状态：
0： 到目前为止A和B的字母都相同。
1： 到目前为止A和B的字母除了一个以外都相同。
2： 到目前为止A比B少一个字母，其他的都相同。
3： 到目前为止B比A少一个字母，其他的都相同。
初始状态设为S0 = {0}，因为A和B都是空，所以是相等的。下面是从S_n到S_{n+1}的转
换：
* Let S_{n+1} = {}
* If 0 is in S_n, then
- put 2 and 3 in S_{n+1}.
- If A[n] == B[n], then put 0 in S_{n+1}, otherwise put 1 in S_{n+1}
* If 1 is in S_n, then
- if A[n] == B[n], then put 1 in S_{n+1}
* If 2 is in S_n, then
- if A[n-1] == B[n], then put 2 in S_{n+1}
* If 3 is in S_n, then
- if A[n]... 阅读全帖 |
|
s******7
发帖数: 1758 | 19 应该是offer
BB据人都是hr自动机发而且不能回复 |
|
s**x
发帖数: 7506 | 20 会写递归的就差不多了。我觉的自动机的实现都比DP的好理解。 |
|
m******e
发帖数: 82 | 21 可以写一个isValidNum()的子函数，之后再转为数字。
子函数可以用自动机实现 |
|
r*****s
发帖数: 1815 | 22 edge case恶心的题注意用自动机！一个建议
: 这样几套拳法打下来 有套路的题目很长时间是不可能忘记了
: 剩下的要么是正则表达式那种难想通的dp
: 要么是strstr这种edgecase很恶心的题
: 我一般就看运气了 赌他不会考
|
|
d**********0
发帖数: 13081 | 23 俺的 LOWES 10% OFF CODE 是这么用的。。
先拷贝两张。 去 homedepot 用原版的， 要match.
去lowes 先去自动机checkout , 小二有时给你 10% off 的时候经常不 scan code.
再去lowes 买的时候还可以用一次。
这叫一变三。
包子。。。。 |
|
s******s
发帖数: 2721 | 24 【 以下文字转载自 Military 讨论区 】
发信人: Lurker (@Zerg), 信区: Military
标 题: 北京小学生创新比赛项目名单，跪了!
发信站: BBS 未名空间站 (Tue Dec 3 22:57:26 2013, 美东)
引自 http://www.acfun.tv/v/ac334765
第32届安捷伦北京青少年科技创新大赛学生科技创新项目公示名单(up节选)
小学组
论翼龙骨骼结构与灭绝原因的联系 魏博琨 洪瑞怡
负压式医用手套自动佩戴装置 米尔莉 张苏潼
双轴自稳云台 钱李潜馨 小学六年级
香烟浸出液对春羽介壳虫的防治实验 肖雨涵 小学四年级
北极斯瓦尔巴德群岛朗伊尔宾I号冰川不同海拔梯度环境对北极罂粟生长的影响
白宇辰 小学六年级
铬污染建筑粉碎颗粒大小对铬含量测定的影响 陈博伦 小学六年级
超声波汽车开门自动防刮蹭装置 王默涵 刘芃青
基于AVR单片机的中小... 阅读全帖 |
|
a**********e
发帖数: 5124 | 25 上周亲测买不了 自动机不能check out 人工小儿说早不让GC买GC了 |
|
c*******t
发帖数: 953 | 26 同意。大脑本来就不是multi-tasking的。小脑倒是，可以同时控制心跳、呼吸什么的
。这是因为小脑是自动机，机械地反应而已。人学习骑车，翻跟头，乒乓球等等这些需
要快速反应的技能，就是在训练小脑。这个作者说的可能就是训练小脑的multitasking
能力。游戏大概可以帮助训练保姆，一只手擦桌子，一只手擦地板。还有战士，一只手
开飞机，一只手发射火箭弹。
而进行思考的大脑是没法multi-tasking的。你不可能在思考个深奥的物理问题的同时
，思考个破案逻辑推理题。 |
|
t*******r
发帖数: 22634 | 27 恩，做平几证明题的时间不如拿来学形式逻辑和自动机。。。 |
|
t*******r
发帖数: 22634 | 28 我觉得说白了，就是 "符号系统的主人" vs "符号系统的奴隶" 的差别。。。或者说，
人肉符号自动机。。。 |
|
t*******r
发帖数: 22634 | 29 id 没有被盗。。。id 后面的有限状态自动机 flip 了一个 bit。。。 |
|
t*******r
发帖数: 22634 | 30 id 没有被盗。。。id 后面的有限状态自动机 flip 了一个 bit。。。 |
|
t*******r
发帖数: 22634 | 31 这其实就是一个 readiness 的问题。。。现在大数据时代的小学数学，
对于数理逻辑的要求，比三十年前要高太多了。。。导致刷熟练，要在
对理论有感觉以后，再刷熟练，才能对理论更熟练。。。否则娃可能会
被刷成有限状态自动机。。。 |
|
|
t******l
发帖数: 10908 | 33 对自然语言的理解，要看环境和上下文。不能按照上下文无关的计算机形式语言和自动
机课程来理解。
当然，一般把自然语言当计算机形式语言来理解的，如果不是自闭症患者，那形式语言
和自动机课程考试多半也是个不及格的主。原因不说了，基本概念的问题。 |
|
t*******r
发帖数: 22634 | 34 数学归纳法是 decision tree 的一种特殊形式。
decision tree 本身不需要归纳，跟归纳过程也无关。本质上就是无二义
的 record decision。或者说，更像有限状态自动机的概念。
从另一个角度说，数学归纳法是更反映肉算时代的概念，因为只有归纳后，
人肉才能实践上算出来。而 decision tree 更反映电算时代的概念，
先不管计算复杂度，反正不行就造个火星那么大的计算机，先能够无二义
地写下 decision tree，优化是第二步的事。
而 permutation / combination 问题，本质上就是搞一个 decision
tree 然后 count end leaf node 的数目（当然实践上是经常对 leaf
sub-tree 求和，本质上还是 counting）。但是因为问题只需要知道数目，
所以只要能知道 decision tree 的 topology 就可以了，根据 topology
算 leaf node 数，不需要真正计算每个节点。这样就把 permutation
/ combination 问题转化问 decision... 阅读全帖 |
|
t******l
发帖数: 10908 | 35 当然我现在已经养成新的习惯，就是左右不换，把 x 留在右边一直解到底再换有木有
！！！！！！
但是从形式语言自动机优化算法角度而言，这还真不算 sub-optimal 。。。
的 |
|
s******4
发帖数: 329 | 36 555，最近总是丢三落四的！
辉瑞的rebate，截止日期是30号，当天晚上想起来，只好在邮局自动机买的邮票，上面
写着sold on 3/30。。。可是我还没敢扔邮筒里，不知道邮寄的时候是不是还要加盖一
次邮戳呢？那样就是周一(4/2)了。。。这种情况怎么办呢？
献包子求教～ 多谢!!! |
|
o******6
发帖数: 9458 | 37 难怪我上周末两次用自动机结帐都出问题，还以为是个案哟。 |
|
k**i
发帖数: 10191 | 38 嗯,我们这儿的CVS自动机器用胖子的时候必须小二亲自帮扫. 所以还是去人工结帐的地
方吧. |
|
t****t
发帖数: 69 | 39 过去，一般2年左右也回去一次，一般回去也就1周不到10天，而且很少外出。但这次假
期允许，呆了近一个月，而且有很长一段是2-3天就换城市换地方，感觉和之前大不同
。这次去的都是2线及以下城市，一线高大上城市没去。
气候及环境：
大多是阴天，很难遇到大晴天，天，还是基本看不到美国那种很透亮的感觉。污染这几
年感觉比前几年略有改善，江河虽然还是脏，但比以前好点，而且老百姓的意识已经强
了不少，企业的情况不知道。
车：
基本家家都有车，高大上的家庭都进口车，50-200万不等。一般的家庭都合资或国产车
，10-20万就搞定，内饰比美国屌丝配置好。听说换一套皮座，6个人干一天才不到2000
块，大吃一惊，如果这价格拿到美国，美国的同款高配车，销售额估计得少卖至少1/3
到一半。出行高速路都修得非常好，但是收费太贵，随便走一段，收费动不动就是40-
60块，上100块也很正常，难怪高速路很好开，车相对少而且路新。有的路段高速出口
很少，错过一个出口得到下一个城市才能出去了。市区里面，车都是见缝插针，按美国
的开法是开不了车的，大家都当交规和道路分割线不存在，GPS导航会自动提醒你监控
路段事项。... 阅读全帖 |
|
b**********1
发帖数: 215 | 40 标 题: 2016年回国旅游
发信站: BBS 未名空间站 (Thu Jun 2 12:19:58 2016, 美东)
过去，一般2年左右也回去一次，一般回去也就1周不到10天，而且很少外出。但这次假
期允许，呆了近一个月，而且有很长一段是2-3天就换城市换地方，感觉和之前大不同
。这次去的都是2线及以下城市，一线高大上城市没去。
气候及环境：
大多是阴天，很难遇到大晴天，天，还是基本看不到美国那种很透亮的感觉。污染这几
年感觉比前几年略有改善，江河虽然还是脏，但比以前好点，而且老百姓的意识已经强
了不少，企业的情况不知道。
车：
基本家家都有车，高大上的家庭都进口车，50-200万不等。一般的家庭都合资或国产车
，10-20万就搞定，内饰比美国屌丝配置好。听说换一套皮座，6个人干一天才不到2000
块，大吃一惊，如果这价格拿到美国，美国的同款高配车，销售额估计得少卖至少1/3
到一半。出行高速路都修得非常好，但是收费太贵，随便走一段，收费动不动就是40-
60块，上100块也很正常，难怪高速路很好开，车相对少而且路新。有的路段高速出口
很少，错过一个出口得到下一个城市才能出去了。... 阅读全帖 |
|
b*******n
发帖数: 27 | 41 在加州一家自动化售货机工业应用的美国公司做产品经理，公司自主研发的软件，硬件
，有自己客服。公司已经做这个20年了，中间经历过收购别的公司和几轮风投进入，现
在盈利了。机器已经组装到四十几个个国家，近万的INSTALLATIONS.美国很多大的工厂
都有用我们的机器 我的职位很敏感，公司名字这就不说了，和CEO聊过很多行业战略
的东西和渠道的铺设，也做过软件features analysis，市场和客服类，所有的渠道商
和终端客户也都知道。不过我有签了份很详细的保密协议，所以不会和公司在美国同类
竞争，但刚看到网上有人提起这个，刚好这大半年我都在想把这个引入国内的可行性。
我简单调查过国内市场，工业应用这块还是绝对蓝海。我最近也有打算回国发展。
自动机现在应用很广泛，医疗和工业都在广泛应用。我们公司也是很大一部分是从医疗
的产品的改进应用 我之前就有想过在国内创新这个模式（绝不是照搬，国内情况不一
样）做这方面的创业。如果有做这行的有兴趣创业的我们可以聊聊 我本人不懂很深技
术，我是MBA出身，所以如果能有做这块技术的行家就最好了。
其实这个做的好是个很大的应用，加州有一个超级富豪... 阅读全帖 |
|
F****s
发帖数: 3761 | 42 发表一下感慨，没有任何冒犯楼主的意思，因为大家都一样。
在历史面前深深敬畏，虽然知道花街引人上绝路是必然，但是每次连心理变化过程都一
样，让人叹喟，人其实就是台机器，只不过是选择多一些的机器，再加上一点逆反心理
，但选择再多也不是无限的，所以还是等价于确定有限自动机的范畴。 |
|
F****s
发帖数: 3761 | 43 我们早知道人不比概率自动机更聪明。1970年代的文章就证明了。
机器发展到一个阶段，在思维上一定比人强，而且机器的能力是可扩展的，人这方面很
弱。 |
|
f*******a
发帖数: 2662 | 44 防空坚盾－－－76A37mm双管舰炮 [图]
76A37mm舰炮是望江机器厂开发的舰载防空武器系统。其作
战使命是在4000米以下，斜距4500米以内的空域里对空中威胁
实施有效防御，其主要 作战对象是歼击机，轰炸机，强击机，
武装直升机和各种飞行器，也可拦截各种导弹，必要时可用于对地面和海面目标交战。
系统组成
76A37mm舰炮由双37mm高炮，配用弹药，火控系统，电源，配套设备组成。
火炮 主要部件有自动机，炮架，火炮随动系统等。
弹药 目前可配用5种弹，即装有电子近炸引信的预制破片弹
，，爆破燃烧榴弹,洩光爆破燃烧弹，洩光穿甲爆破燃烧弹，洩
光训练弹，采用弹链供弹。
火控系统 根据用户需要，既可采用中国生产的火控系统，
如88C火控系统也可采用由用户指定的火控系统。
主要特点
76A37mm双管舰炮系统是一种全天候作战武器系统。其主要特点如下：
自动化程度高 火炮可全制动遥控操作，能在远距离实施遥控
启动，装填，击发和故障显示等自动控制功能。
初速高 由于火炮初速达1000米/ |
|
w********r
发帖数: 4193 | 45 这个说法正说明了dell重视你们，把你们看作活生生的人，而不是把你们当作开发、组
装、贩卖电脑的自动机。 |
|
m**k
发帖数: 18660 | 46 附近有walmart什么的么？都有自动付款。随便扔硬币。
或者
很多地方都有coinstar 自动机。
http://coinstar.com/ 可以找附近的location.
但是这东西需要手续费的。hehe.
不然就去超市买东西，自己把钱给他们。可以理解的。
hehe |
|
G****a
发帖数: 10208 | 47 【 以下文字转载自 JobHunting 讨论区 】
发信人: uglyduke (一苇居士), 信区: JobHunting
标 题: 绝对精华，offer＋面经
发信站: BBS 未名空间站 (Wed Mar 30 21:34:37 2011, 美东)
刚刚和amazon的recruiter通完电话，确认拿到offer，他正在发email
95k+15k
大概打算从了，希望板上有讨价还价经验的朋友可以给点经验争取最大利益^_^
另外，因为身份问题，我十月前要先去amazon北京，类似这期间的pay之类的问题有谁有
经验的？
鉴于NDA和某w同学，面经里问题我尽量只涉及方向不说具体内容。
先说下我的基本情况吧，应该有点励志效果：
学历只有国内大学cs的本科，还因为身体原因延毕了半年-_-之后在杭州找的一个小公司
的SDE工作了1年半，拿L1来了公司在美国的总部作PM。公司规模很小，不到20人，很多
东西是一团乱麻，工作不到2年后于去年12月跟老板吵翻，离职开始找工作。
L1签证到今年2月就过期了，所以算是黑着身份找的，想想也挺不容易的。
简历自己写的，然后托朋友改了一下（还不是cs... 阅读全帖 |
|
|
|
r*******t
发帖数: 8550 | 50 baggage claim 那一层有自动机，买杂志和汽水的小贩也有的卖
问问机场工作人员也可 |
|
