y****n
发帖数: 15 | 1 题目描述 Q4.8：
You have two very large binary trees: T1, with millions of nodes, and T2,
with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of
T1.
书中的解法一：
If T2’s preorder traversal is a substring of T1’s preorder traversal, and
T2’s inorder traversal is a substring of T1’s inorder traversal, then T2
is a subtree of T1.
我感觉这个方法可能有问题。虽然通过preorder和inorder遍历，可以唯一的定义一棵
树。但是如果T2是T1的子树，遍历字符串S2是S1的子串，那么S2可能对应到S1的不同位
置。举例来说，下面两棵树就满足S2是S1的子串，但T2不是T1的子树。
请众位高手帮忙检查一下，是我的结果有问题，还是书中有错误，多谢！
... 阅读全帖 |
|
S**I
发帖数: 15689 | 2 littlebirds' answer is relevant but not 100% correct. To be exact, the
second parameter of overloaded operator << is a reference to str type, which
requires it to be a l-value. s1 + s2, or (s1 + s2) (parentheses or not doesn
't matter here), is a r-value, so compiler cannot find a match for std::cout
<< s1 + s2. If you change the parameter type to const reference to str, a r
-value is acceptable and std::cout << s1 + s2 works fine.
In fact, if you change the second parameter to pass by value (st... 阅读全帖 |
|
w***g
发帖数: 5958 | 3 不允许出现最左边的const确实不能解决所有问题。见下面的例子
const static int s1 = 1, s2 = 1;
const extern int e1 = 1, e2 = 1;
等价于
int static const s1 = 1, s2 = 1;
int extern const e1 = 1, e2 = 1;
第二种写法更容易混淆。static/extern作用于后面所有的变量(编译成.o后用nm看输出的
变量可以确定)，而const作用于int。作用对象交错了。
int const *const s1 = 0, s2 = 1;
第一个const作用于int，所以跟s1和s2都有关。第二个const作用于*只和s1有关。
这个确实比第一个const写前面更变态。
我扛不住了，大家赶紧转java吧。 |
|
r********r
发帖数: 11248 | 4 Now we want to prove if S \in PARITION <==> Q \in Half-3-CNF
Proof: ====>
if S \in PARITION, then there is a subset of S, let's say
S1 ={1, 2, 3}, the sum of S1 is equal to the sum of S-S1 = {6}.
Then we can assign: x100 and x200 to 0, and all the xi corresponding
to S1 as 1, all xi corresponding to S- S1 as 0. In this example, we
set x1, x2, x3 to 1, x4 to 0, we can see the resulted Q belongs to Half-3-CNF.
<====
If this Q is a Half-3-CNF problem, meaning we can find an assignment making
hal |
|
H***a
发帖数: 735 | 5 如果座位编号S1,S2,S3,S4
当Z=1时（叫P1吧），他面临两个选择：
(a) 在S1,S3,S4里面挑一个
(b) 挑S2。
注意这两个选择好比你面对两条分岔路，完全等几率。为什么这么分就是这道题的妙处。
如果Z选择了方案(a)，那么唯一能够实现题目要求的只能是选S1，因为是随机选，选中
几率为1/3。这种情况我叫做"Z消失"，因为座位Z0（也就是S1）被占了。
如果Z选择了方案(b)，那么P2进来的时候发现自己的座位被占了，同时发现自己已经莫
名其妙变成新的Z了。要满足条件只能去选S1，几
率还是为1/3。这个时候座位Z0被占了，"Z消失"。
于是你发现无论最早的Z怎么选择，最后的结果都是1/3的几率。现在扩展到50个座位，
方案2里面就有了S2,S3,...,S48，结论同样适用。
就4个人的情况，Z=2,3,4都非常简单了。 |
|
w**********y
发帖数: 1691 | 6 我是真不明白....
不是应该 (w/s1)*X1+((1-w)/s2))*X2么?
variance是 (w/s1)^2*0.2^2+((1-w)/s2))^2*0.3^2+(w/s1)((1-w)/s2))*0.2*0.3
你这里面有s1和s2啊..除非你给s1=s2.那结果就是6/7..
第一问是0,E(sin(W_t))=\int sin(x) f(x/sqrt(t))dx, where f(x) is guassian
density. f(x),sin(x)都是symmetrical的,所以积分是0.
第二问对的-不是martingale.
我猜想,他先问你第一问,就是为了迷惑你让你第二问回答是martingale吧?所以觉得这
个题稍微有意
思一些.. |
|
n******m
发帖数: 169 | 7 The same happen here
d(dc/dS1)S1+d(dc/dS2)S2=0
So, it was omitted.
To see why this is true, think about you have a linear combination of S1 and
S2, which combine to a fix total value: a(t) S1 +b(t) S2 =Total
Then d(a)S1+d(b)S2=d(total)=0.
As people pointed out above, this portfolio is self financing, because by
calculation, we see d( a(t)S1(t)+b(t)S2(t) )= a(t)dS1(t)+b(t)dS2(t).
S_
S_ |
|
o****o
发帖数: 8077 | 8 then wrap it into a macro:
%macro switch(type);
%global s1 s2;
%if %upcase(&type) eq HTML %then %do;
%let s1=html;
%let s2=xls;
%end;
%else %if %upcase(&type) eq PDF %then %do;
%let s1=pdf;
%let s2=pdf;
%end;
%mend;
%switch(pdf);
ods listing close;
ods &s1 file="&add.\table.&s2";
options orientation=landscape nodate
nonumber missing=" " papersize="letter";
ods &s1 close;
ods listing; |
|
e*******0
发帖数: 367 | 9 Floor trader pivots
Pivot(P) =(H + L + C)/3
Resistance level 1 (R1) =(2*P) - L
Support level 1 (S1) =(2*P) - H
Resistance level 2 (R2) =(P - S1) + R1
Support level 2 (S2) = P - (R1 - S1)
Resistance Level 3 (R3) =(P - S1) + R2
Support Level 3 (S3) = P - (R2 - S1) |
|
l****o
发帖数: 2909 | 10 本月5日，中国铁道科学研究院（以下简称铁科院）网站发布了一条公示，引起媒体及
公众关注。
这条《北京市轨道交通门头沟线（S1线）工程环境影响评价公众参与第一次公示》
公布了S1线的具体走向、长度、车站等情况。
《公示》特别提出，希望社会各界从环保角度出发，说明对该项目持何种态度及原
因。此次环评包括城市生态环境影响评价等15项内容，并以生态环境、声环境、电磁环
境及公众参与为重点专题进行评价。
这条贯穿海淀区、石景山区、门头沟区的轨道交通，曾备受门头沟人期待。这个本
市西部的郊区，冀望借S1线建立的交通便利，助力大发展。
7天后，意想不到的情况发生了。
《公示》在铁科院网站上被撤了下来，随后又挂上去，标题相同，但内容已变。曾
多次给市长信箱、铁科院发意见书的业主Cxfs(网名)分外高兴，认为这是一次小小的胜
利，促使他更有动力去推动磁悬浮“下马”。
让沿线居民感到高兴的改变是：更新后的《公示》注明，S1线“在西郊粮库专用线
前入地，下穿永定河引水渠、西四环”，地下线长度由此前公示的约0.455公里，变更
为2.969公里。
高洁说，地下线延长后，受影响的居住区将减少。但是，碧森里、中国 |
|
d*********o
发帖数: 6388 | 11 http://www.chinanews.com.cn/cj/2010/09-09/2523615.shtml
中新社北京9月9日电 (记者 杜燕)北京中低速磁悬浮交通示范线——门头沟线(S1线)将于10月份动工。据悉，S1线作为地铁6号线的西延，连接通州和门头沟，全线长近20公里，行车最高时速100公里左右，每公里投资超过6亿元人民币。
这是北京市门头沟区区长王洪钟在今天召开的第四届首都西南区域经济发展论坛上透露的。
自从S1线拟采用中低速磁浮以来，关于这条线路的环境影响和技术经济可行性就引发了较大争议，线路设计方案不断调整。
据悉，今年5月份，中国铁道科学研究院网站对S1线“环境影响评价”开始公示。一石激起千层浪，沿线小区居民担心电磁辐射、噪声等影响，联名反对，并将签名信寄往中国铁道科学研究院和北京市政府部门。支持和反对中低速磁悬浮项目的专家则各执一词。
原本征集意见后很快要出台的第二次环评公示亦迁延良久，在今年8月才出台。在第二次环评公示中，中国铁道科学研究院认为“从环境保护的角度出发，本项目建设是可行的”。
北京控股磁悬浮技术发展有限公司网站资料显示，中低速磁悬浮首要的技术特点 |
|
s*****e
发帖数: 506 | 12 ◢ 1 ◣ 8月31日联合国调查叙化学武器问题真相小组完成实地取证，打包离开大马士
革，同日稍晚，美国总统奥巴马发表声明，表示确定要对叙动武，但将在9月9日国会复
会后寻求获得国会授权动用武力。由此，美对叙动武窗口期延长。面对紧张局势，叙利
亚表态称，已经做好了报复准备，“手指已放到了扳机上”，他们“随时奉陪”。
如果要打，美国将怎么攻打叙利亚？叙利亚到时将如何“奉陪”？这些都是世界舆
论关注的焦点。美国ISW网站最近对美军执行摧毁叙利亚防空系统任务进行了深度分析
，据分析指出，美军要想完整的摧毁叙利亚的防空系统，至少需要320至360枚“战斧”
式巡航导弹。除此之外，即便美军彻底摧毁叙利亚的防空系统，也不可能对叙利亚自由
军与政府军的战时进行直接干预，美军对叙利亚的打击将比想象中的更困难。美国也许
可以瞬间将叙利亚撕得粉碎，但要想控制该国就不那么容易了。
◢ 2 ◣ 叙利亚的战事正一触即发。不久前，奥巴马已经在白宫玫瑰园宣布将对叙
动武，打与不打已不是悬念，人们的关注点转移到何时开打、怎样打上来。（图片为美
军想定的叙利亚防空系统的主要目标，包括机场、防空雷达、防空导弹阵地等等）
... 阅读全帖 |
|
n**e
发帖数: 1296 | 13 http://sh.sina.com.cn/news/m/2016-08-27/detail-ifxvixer7323920.shtml
晨报记者钟晖报道 记者日前获悉，苏州在建的轨道S1线和4号线将争取与上海11号线
、17号线接轨，未来市民或有望乘坐地铁前往苏州旅游。
昆山市规划局公布的《<苏州市轨道交通S1线昆山段工程预可行性研究>编制完成》
称，最近S1轨道的规划走向中，将在花桥设立站点，与上海11号线衔接。根据规划，苏
州市轨道交通S1线自苏州城市轨道交通3号线夷亭路引出，与上海轨道11号线花桥站换
乘。
而距苏州吴江区政府新发布的《“十三五”固定资产投资与重大项目建设规划》披
露，苏州将加快推进通苏嘉城际铁路、湖苏沪城际铁路等铁路工程； 积极协调苏州市
轨道4号线松陵大道站和上海轨道17号线延伸至汾湖枢纽站建设。
记者另悉，上海轨交1号、5号线莘庄站为有效提升客流通行效率，确保乘客出行安
全，今年初，莘庄站启动了“补短板”改造项目，新增的5部自动扶梯已通过市有关部
门的安全验收，昨已投入使用。 |
|
c*********d
发帖数: 9770 | 14 根据俄罗斯阿尔玛兹设计局2018年1月最新发布的消息，其最新的“铠甲”-ME型近
防系统研发工作已经接近尾声，将于在今年装舰进行测试。该系统是“铠甲”-S1型近
防系统的海基版本，在性能上获得了很大的提升。
一般认为，最新的“铠甲”-ME是“铠甲”-S1型近防系统和“卡什坦”近防系统的
混血，兼具两者的长处。该系统配备了“铠甲”系统的1RS2-1E型相控阵雷达，同时也
安装有光电/红外目标获取和识别系统。
“铠甲”-ME型近防系统在俄罗斯海军的大小舰艇上都可配备，比如“库兹涅佐夫
”号航母、“基洛夫”级巡洋舰和“卡尔库特”级轻型护卫舰都能装上。该系统配有两
门GSh-6-30K/AO-18KD型30毫米加特林炮，具备非常强大的瞬时火力。
单门GSh-6-30K/AO-18KD型30毫米加特林炮的射速为4000～6000发/分，而两门炮加
起来射速可以达到1.2万发/分。相比之下，早期的“铠甲”-S1系统仅仅装两门单管的
30毫米机关炮，单炮射速仅有2500发/分。因此，仅仅火炮的射速就提升了很多。
该系统的反应时间为3～5秒，可同时拦截4个目标。武器方面，GSh-6-30K/AO-18... 阅读全帖 |
|
x****6
发帖数: 4339 | 15
The occurrence of concentrated pneumonia cases in Wuhan city, Hubei province
of China was first reported on December 30, 2019 by the Wuhan Municipal
Health Commission (WHO, 2020). The pneumonia cases were found to be linked
to a large seafood and animal market in Wuhan, and measures for sanitation
and disinfection were taken swiftly by the local government agency. The
Centers for Disease Control and Prevention (CDC) and Chinese health
authorities later determined and announced that a novel coro... 阅读全帖 |
|
d*********o
发帖数: 6388 | 16 http://science.caixin.com/2020-03-10/101526576.html?originReferrer=weibo_caixinwang
bioRxiv论文的通讯作者之一、中国科学院西双版纳热带植物园副研究员Alice
Catherine Hughes对财新记者表示，“人工干预没有任何证据，这种病毒显然（
clearly）是从野生动物起源和进化而来的。”
研究认为，来自蝙蝠的冠状病毒可能提供了新冠病毒的基因骨架，与蝙蝠或其他野生动
物的进一步重组事件，则使它获得了S蛋白、RBD和多碱基剪切位点
【财新网】（实习记者 黄晏浩 记者 徐路易）新冠病毒又一项“特殊性”在自然界中
找到了类似物。3月6日，一篇发表在bioRxiv预印本网站的论文称，S蛋白两个亚基S1和
S2间的蛋白酶切位点有多个氨基酸插入，并非新冠病毒独有，一种新的蝙蝠冠状病毒
RmYN02的S蛋白同样存在类似插入。研究团队认为，这一结果有力证明了类似插入可以
自然发生，新冠病毒起源于蝙蝠和其他野生动物中存在病毒之间的多重自然重组。论文
尚未经过同行评议。
该论文题目为《一种新的蝙蝠冠状病毒揭示了... 阅读全帖 |
|
z*****d
发帖数: 672 | 17 I did consider S1.4, which is only 500 more than the Focus S160, but since I
am buying used, I didn't find any S1.4 for sale. I was considering to have
a pair of $3k class bookshelf, I was waiting for 160, S1.4 and Cremona
Auditor M, but the last two are either so rare or so expensive even as used.
I went to a Dynaudio dealer, he says the S1.4 is not much different from
focus 160, he doesn't even advise me to consider it as an upgrade. The C1
will be on my list of potential replacement.
hundred |
|
z****e
发帖数: 2024 | 18 来自主题: JobHunting版 - 一道面试题 two regular stack S1, S2.
for the special stack:
push(a){
S1.push(a);
max=S2.top();
S2.push(a>max?a:max);
}
pop(){
S1.pop();
S2.pop();
}
max(){
return S2.top();
}
top(){
return S1.top();
} |
|
s*******e
发帖数: 174 | 19 【 以下文字转载自 Java 讨论区 】
发信人: shrubRose (喵喵喵), 信区: Java
标 题: 一道 JAVA Stack vs Heap 题
发信站: BBS 未名空间站 (Mon Nov 9 13:59:15 2009, 美东)
String s1 = "grapefruit";
String s2 = "grapefruit";
请问 s1 and s2 是在 stack 还是 heap 上呢？ Does s1 and s2 point to same
address?
String s3 = "grape"+"fruit";
Does s3 point to same address as s1 and s2?
String s4 = new String("grapefruit");
String s5 = new String("grapefruit");
s4 and s5 should be in heap, s4 and s5 should point to different addresses,
right?
System.out.print |
|
I**A
发帖数: 2345 | 20 huh?不是来回折腾？
Stack s1
Stack s2
比如add item in 的时候, s1.push
需要remove one item的时候，s1统统pop到s1，取最后一个？然后再pop回去？
我不sure是因为觉得这个法子太笨了些 |
|
I**A
发帖数: 2345 | 21 pushstack: s1
popstack: s2
enqueue(0)
enqueue(1)
enqueue(2)
now s1 has 0,1,2
now. dequeue
我需要0对吧？
if s2 empty..
{
s2.push(s1.pop()); //2 in
s2.push(s1.pop()); //1 in
}
最后pop出我要的0
咦，好像是不用。。。 |
|
i**********e
发帖数: 1145 | 22 怎样判断“满足都包含的条件”以及“不破坏条件”？
>> 判断“满足都包含的条件”就是利用一个counter。当满足了包含的条件之后，就可
以确保“不破坏条件”了。
不用一个counter的话，每次判断都要O(M)。
>>对的。
用counter的话，对应的hasFound超过了needToFind的时候怎么处理？
>>hasFound 超过了 needToFind counter 就不要加一，否则应该加一。
假设S1=ABAAAACAB，S2=AABC，当你遇到两个 A 的时候就 hasFound['a'] 加两次，值
为二。但是第三次你遇到 A 的时候就不必加了，因为这不帮助于满足条件。当
counter 为四的时候就满足条件了。
算下面这个test case时，
当end分别到了C和最后一个B的时候，什么时候begin该停？
S1=ABAAAACAB
S2=AABC
有人解释一下吗？
>>当end到了 C 的时候，就意味着刚满足条件，因为那时候 counter = 4.这时候就应
该开始移动 begin 指针，往右边挪。这时候 hasFound['a']=5, hasFound['... 阅读全帖 |
|
h**6
发帖数: 4160 | 23
别处看来的算法，稍加修改。
关于背包问题的另一思考：
有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M>W，f(M) = f(M-wi)+vi
这里的 W，也就是贪婪算法起点的上限。前面求出 W = [sum(w)-wi]*(wi-1)
具体到这题，也就是 W = (4+5+7+8+9)*(6-1) = 165
blaze 给出一个更小的 W 值，但用到了这些数字的特殊性，不能成为通解。我思考了一下，可以给出更小的 W 的通解形式：
不失一般性，设 w1
除了包裹 i 之外所有包裹总数不得大于等于 wi
设选取的包裹为 p1, p2, ... pk
另 S1=w[p1], S2=w[p1]+w[p2], ..., Sk=w[p1]+w[p2]+...+w[pk]
如果 k≥wi，根据鸽巢原理，则S1, S2, ..., Sk必有一项被wi整除，或者两项除以wi余数相等。
如果S1, S... 阅读全帖 |
|
g******0
发帖数: 221 | 24 Given two strings: s1(length n),s2(length m).
Building the suffix tree of s1 takes O(n) time. To search s2 in the suffix
tree of s1 takes O(m). Why?
For example: s1: abcde, s2: e. The tree is shown below. Shouldn't the search
time be O(n)? 弱问，what did i miss? Maybe I should ask what is data
structure of the children of a node in a suffix tree? many thanks!
|(1:abcde)|leaf
tree:|
|(2:bcde)|leaf
|
|(3:cde)|leaf
|
|(4:de)|leaf
|
|(5:e)|leaf |
|
g**********y
发帖数: 14569 | 25 再换了种结构，这个快一些，100000人，每个人accuse 1~3个，1.3秒左右算出来。
public class LiarLiar {
public int[] divide(String[] line) {
int N = Integer.parseInt(line[0].trim());
HashMap map = new HashMap();
for (int i=0, j=1; i
String[] s = line[j].split(" ");
String name = s[0].trim();
int n = Integer.parseInt(s[1].trim());
j++;
for (int k=0; k
add(map, name, line[j].trim());
add(map, line[j].trim(), name);
}
}
HashSet a = new HashSet();
HashSet阅读全帖 |
|
d********y
发帖数: 2114 | 26 sql新手写得比较复杂。
MySQL测试通过。
select p1.personId, p1.region, p1.age, s1.volume, champion.maximum from (
select p.region, max(s.volume) as maximum from Person p JOIN Sales s on p.
personId=s.personId group by p.region) as champion join Person p1 on p1.
region=champion.region join Sales s1 on s1.personId=p1.personId where s1.
volume=champion.maximum order by p1.age ASC limit 2; |
|
l*****a
发帖数: 14598 | 27 4:
root is fixed,
next is the root of left sub-tree or right sub-tree
do recursion for each sub-tree.
具体写出来还要花点功夫
5：
咋玩？介绍一下你的玩法
2：
根据输入pattern,构造一个状态表与输入字符的数组/map
initial state is s0, end state is sn
for example, pattern is ab+d
(s0,a)->s1
(s1,b)->s1
(s1,d)->s2
s2 is end state,once your input can goto s2,that is correct |
|
q****x
发帖数: 7404 | 28 string add(const string& s1, const string& s2)
{
string s = s1 + s2;
return s;
}
string add2(const string& s1, const string& s2)
{
return (s1 + s2);
}
记得有参考书说add2()会比add()快，因为编译器直接生成一个临时变量云云。谁能详
细解释一下细节？ |
|
m*******m
发帖数: 82 | 29 Interview Questions：
Redefine a function (signature given) to write data to a new replacement for
an antiquated database (which you previously designed)
Answer Question：
Write a function to return the longest common prefix between two strings.
//java code
String GetCommonPrefix(String a, String b)
{
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
int startIndex = 0;
//choose short length as the end index
int needLength= aChar.length>bChar.length?bChar.length:aChar.lengt... 阅读全帖 |
|
P***t
发帖数: 1006 | 30 可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length of A)
for LenC = X[i][j] to 1 // LenC as the length of segment C
&& (i+LenC >= Leng... 阅读全帖 |
|
P***t
发帖数: 1006 | 31 可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length of A)
for LenC = X[i][j] to 1 // LenC as the length of segment C
&& (i+LenC >= Leng... 阅读全帖 |
|
p*****2
发帖数: 21240 | 32 做了recursion的，道理不难。想研究一下bottom up的解法。
http://www.mitbbs.com/article_t/JobHunting/32132145.html
可以把两个字符串拆成四段来看。假如原字符串是：A B C D
中间交换 B C，应该得到：A C B D
(每次个大写字母代表一段字符，A D 可以是空).
用一个二维数组 X[i][j] 记录 S1从ｉ开始，S2从ｊ开始的相同字符的最大长度。譬如：
S1＝abcd
S2=cdab
then
X[0][0]=0
X[0][1]=0
X[0][2]=2 (ab -> ab)
X[0][2]=0
...
同时记录两头最大相同字串的长度。譬如：
S1=abxyz
S2=abyxz
那么 A 最大长度是2, D 最大长度是１.
Now,
for i = 1 to Length-1 // i is start of segment C in S1
for j = 0 to CommonPrefixLength // j is start of segment of C in S2 (
length o... 阅读全帖 |
|
a*******8
发帖数: 110 | 33 O(k^2)的brute force算法附上：
String getCommon(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int maxLength = Math.min(m, n);
while (maxLength > 0) {
if (s1.substring(m - maxLength).compareTo(s2.substring(0,
maxLength)) == 0) {
return s1.substring(m - maxLength);
}
--maxLength;
}
return "";
} |
|
E*******0
发帖数: 465 | 34 vector* GetAbsentPositions(string s1, string s2)
{
vector* rst=new vector();
int i=0,j=0;
while (j
while (i
if (s1[i]!=s2[j])
{
(*rst).push_back(i);
++i;
}
else
{
++j;
++i;
break;
}
while (i
(*rst).push_back(i++);
return rst;
} |
|
E*******0
发帖数: 465 | 35 vector* GetAbsentPositions(string s1, string s2)
{
vector* rst=new vector();
int i=0,j=0;
while (j
while (i
if (s1[i]!=s2[j])
{
(*rst).push_back(i);
++i;
}
else
{
++j;
++i;
break;
}
while (i
(*rst).push_back(i++);
return rst;
} |
|
i**********e
发帖数: 1145 | 36 这题可以优化用dp，通常看到递归用 i+1,j，要不然递归 i,j+1，这就是很明显的可以
转换非递归dp。
dp[i,j] = whether s3[i+j] can be formed as interleaving of substrings s1(0,i
) and s2(0,j).
eg, s1 = "hello", s1(0,1) = "h".
Then,
dp[i,j] = dp[i-1,j] && s1[i-1] == s3[i+j-1]
|| dp[i, j-1] && s2[j-1] == s3[i+j-1]
总复杂度 O(m*n). |
|
p*****2
发帖数: 21240 | 37 写了一个dp的。
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1==null || s2==null || s3==null)
return false;
int l1=s1.length();
int l2=s2.length();
int l3=s3.length();
if(l1+l2!=l3)
return false;
boolean[][] dp=new boolean[l1+1][l2+1];
dp[l1][l2]=true;
for(int i=l1;i>=0;i--)
for(int j=l2;j>=0;j--)
{
if(i阅读全帖 |
|
p*****2
发帖数: 21240 | 38
代码要麻烦一些。
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1==null || s2==null || s3==null)
return false;
int l1=s1.length();
int l2=s2.length();
int l3=s3.length();
if(l1+l2!=l3)
return false;
boolean[][] dp=new boolean[2][l2+1];
for(int i=l1;i>=0;i--)
{
int id=i%2;
Arrays.fill(dp[id],false);
for(int j=l... 阅读全帖 |
|
l****c
发帖数: 782 | 39 换了DP,觉得和你第二页做的很像，应该是n^2了。
可过了小测试，过不了大测试啊。
您的那个代码也是只能过小测试。。。。。。
boolean isInterleave(string s, string s1, string s2)
{
if (s.length()!=(s1.length()+s2.length())) return false;
int l1 = s1.length()+1;
int l2 = s2.length()+1;
bool **dpt = (bool**)malloc(sizeof(bool*)*l1);
for (int i = 0; i < l1; i++)
dpt[i] = (bool*)malloc(sizeof(bool)*l1);
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (i==0&&j==0)
dpt[i][j] = tr... 阅读全帖 |
|
l***i
发帖数: 1309 | 40 一个新想法，假设每个token的长度都不大，double类型的精度足够，不停的比两个
double，这样可以避免很多问题。
vector vs1, vs2;
// assume s has only 0-9 and .
// and begin with digit
vector split(string s)
{
vector ans;
int i;
for(i=0; i
int p=i;
for(; i
;
ans.push_back(s.substr(p, i-p));
return ans;
}
}
vs1 = split(s1);
vs2 = split(s2);
for(int i=0; i
string s1, s2;
s1 = "0." + vs1[i];
s2 = "0." + vs2[i]... 阅读全帖 |
|
l***i
发帖数: 1309 | 41 struct Node {
Node *left, *right;
int val;
};
// returns true if subtree at root is BST
// the pair is minval and maxval of this subtree
typedef pair pii;
pair isBST(Node *root)
{
if (root == NULL) return make_pair(true, pii(0,0));
if (root->left == NULL && root->right == NULL)
return make_pair(true, pii(root->val, root->val));
pair p1, p2;
bool b1, b2, ans;
int s1, s2, t1, t2, vmin, vmax;
p1 = isBST(root->left);
p2 = isBST(root->righ... 阅读全帖 |
|
l***i
发帖数: 1309 | 42 暴力法不行吧。
不用那个s1 s1的技术，直接简单暴力，try rotation length 1 to n, for each try
of length i, check s1[i+1..n] concat s1[1..i] is equal to s2 or not.
Time O(n*n) = O(n^2)
check s2 in s1s1 using naive string matching is O(n^2) as well. |
|
t****a
发帖数: 1212 | 43 f(s1, s2, (x & xs)) = f(s1-x, s2, xs) or f(s1, s2-x, xs) or f(s1, s2, xs)
f(0, 0, (x & xs)) 时候成功
话说楼主的3进制是什么意思啊？ |
|
p*****2
发帖数: 21240 | 44 def lcs s1,s2
m=s1.length
n=s2.length
dp=Array.new(m+1) {Array.new(n+1,0)}
ans=''
(m-1).downto(0) do |i|
(n-1).downto(0) do |j|
if s1[i]==s2[j]
dp[i][j]=dp[i+1][j+1]+1
ans=s1[i,dp[i][j]] if dp[i][j]>ans.length
end
end
end
ans
end
p lcs 'ABABCD', 'BABDC' |
|
n****r
发帖数: 471 | 45 用的方法就是最简单的逆序+ longest common substring （DP）
judge small能过
judge large就提示说memory limit exceeded。
我DP的table是用vector存的， code如下，请大侠们给点儿建议。 提前谢谢啦！
string longestPalindrome(string s) {
string ret;
if(s.empty())
return ret;
string s_copy = s;
reverse(s_copy.begin(), s_copy.end());
return findLongestCommonSubsequence(s, s_copy);
}
string findLongestCommonSubsequence(string s1, string s2){
int m = (int) s1.length();
int n = (int)... 阅读全帖 |
|
p*****p
发帖数: 379 | 46 large TLE了
不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list queue;
set visited;
map stepMap;
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string... 阅读全帖 |
|
p****e
发帖数: 3548 | 47 发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// St... 阅读全帖 |
|
p*****p
发帖数: 379 | 48 large TLE了
不过ladder 1判断比较奇葩：hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list queue;
set visited;
map stepMap;
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string... 阅读全帖 |
|
p****e
发帖数: 3548 | 49 发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// St... 阅读全帖 |
|
x******a
发帖数: 6336 | 50 【 以下文字转载自 Programming 讨论区 】
发信人: xiaojiya (xiaojiya), 信区: Programming
标 题: 请问关于overloading <<
发信站: BBS 未名空间站 (Wed Feb 27 11:59:50 2013, 美东)
I am working on the example in accelerated C++.
I have overloaded operator+= , operator+ , and operator<<.
the following code does not work.
I got "invalid operands to binary expression('ostream'(aka 'basic_ostream<
char>') and 'myString') when compiling the code.
myString s1="hello";
myString s2="world";
std::cout<< s1+s2 <
it worked in the foll... 阅读全帖 |
|
