c*****r
发帖数: 214 | 1 来自主题: JobHunting版 - 问道面试题 假设5个数从小到大是x1...x5
假设10个和从小到大分别是s1，...s10
x1+...x5=(s1+...+s10)/4
另外可以知道s1=x1+x2,s10 = x4+x5
然后就可以得到x3
然后由s2 = x1+x3,
s9 = x3+x5
可解x1，x5
re |
|
s******c
发帖数: 99 | 2 aa from s1
dbbc from s2
bc from s1
a from s2
c from s1 |
|
s******c
发帖数: 99 | 3 import java.io.*;
public class Solution {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.
in));
String line = br.readLine();
int N = Integer.parseInt(line);
String []strs=new String[N];
for (int i = 0; i < N; i++) {
strs[i]=br.readLine();
}
for(int i=0;i
{
char start=strs[i].charAt(0);
int sumtotal=0... 阅读全帖 |
|
b*******d
发帖数: 750 | 4 1.
写一个stack。
api是:
Stack pop();
Stack push(int value);
int top();
s2 = s1.pop();
那么s2是个独立的stack，但其值等于s1的常规pop之后的结果。s1 pop之后，仍保持原
来的内容，只产生一个新stack。
优化pop 和 push。
这个题我答的不好。有会的告诉哥一下。
2. 两个sorted array，A和B，找其中值。证明复杂度。 |
|
C***U
发帖数: 2406 | 5 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false. |
|
C***U
发帖数: 2406 | 6 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false. |
|
w***o
发帖数: 109 | 7 对第一题的理解有点混乱，我想可能有三种情况：
1. dist = sum_i(s1[i] - s2[i]);
2. dist = sum_i(|s1[i] - s2[i]|);
3. dist = |sum_i(s1[i] - s2[i])|;
我觉得这题本意是要考第三种情况。 |
|
o****i
发帖数: 1706 | 8 Consider a straight highway in the plane which can be modelled by a
horizontal strip in the plane. A finite set T of targets are located on the
highway, and a finite set S of wireless sensors are located outside of the
highway. A sensor s can monitor a target t if and only if the Euclidean
distance between s and t is at most one. Suppose that each sensor s has a
positive cost c and each target t can be monitored by at least one sensor in
S. Consider a subset S1 of sensors in S. S1 is said to be ... 阅读全帖 |
|
p*****2
发帖数: 21240 | 9 dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble
string。
有三种情况需要考虑：
1. 如果两个substring相等的话，则为true
2. 如果两个substring中间某一个点，左边的substrings为scramble string，
同时右边的substrings也为scramble string，则为true
3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为
scramble
string, 同时s1右边substring和s2左边的substring也为scramble
string，则为true |
|
p*****2
发帖数: 21240 | 10 感觉罗嗦不少，你按照我的java代码改改试试？
public boolean isScramble(String s1, String s2)
{
int n=s1.length();
boolean[][][] dp=new boolean[n][n][n+1];
for(int i=n-1; i>=0; i--)
for(int j=n-1; j>=0; j--)
for(int k=1; k<=n-Math.max(i,j);k++)
{
if(s1.substring(i,i+k).equals(s2.substring(j,j+k)))
dp[i][j][k]=true;
else
{
for(in... 阅读全帖 |
|
g***9
发帖数: 159 | 11 写了个C++的， 果然没有python，ruby的简洁呀
void GenerateCombinationsImpl(string s, int index, vector &result) {
if (index >= s.size()) {
result.push_back(s);
return;
}
if (s[index] == '?') {
string s1 = s;
s1[index] = '0';
GenerateCombinationsImpl(s1, index+1, result);
string s2 = s;
s2[index] = '1';
GenerateCombinationsImpl(s2, index+1, result);
}
else {
GenerateCombinationsImpl(s, index+1, result);
... 阅读全帖 |
|
w*******e
发帖数: 395 | 12 一直没有弄明白为什么网上许多代码是基于以下assumption的：
“如果s1和s2是scramble的话，那么必然存在一个在s1上的长度l1，将s1分成s11和s12
两段，同样有s21和s22。那么要么s11和s21是scramble的并且s12和s22是scramble的；
要么s11和s22是scramble的并且s12和s21是scramble的。”
有谁能解释一下吗？多谢了 |
|
w*******e
发帖数: 395 | 13 一直没有弄明白为什么网上许多代码是基于以下assumption的：
“如果s1和s2是scramble的话，那么必然存在一个在s1上的长度l1，将s1分成s11和s12
两段，同样有s21和s22。那么要么s11和s21是scramble的并且s12和s22是scramble的；
要么s11和s22是scramble的并且s12和s21是scramble的。”
有谁能解释一下吗？多谢了 |
|
d***n
发帖数: 832 | 14 是这个贴子里发出的
http://www.mitbbs.com/article_t/JobHunting/32569901.html
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
看了帖子后还是不明白O(nlog(n))是怎么解决的
有真正明白而且写过code的牛人能不能解释一下 |
|
d***n
发帖数: 832 | 15 是这个贴子里发出的
http://www.mitbbs.com/article_t/JobHunting/32569901.html
第二题是这样的：
n个Speaker，S1, S2, ...Sn
每个Speaker在不同的时间段有不同的音量如：
S1: {[2,5], vol=10}, {[6,10], vol=2}, ...
S2: {[1,6], vol=1}, {[8,12], vol=8}, ...
...
请输出每个时间段及这个时间段内最大的音量
比如，只有S1和S2的话，输出就是
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
看了帖子后还是不明白O(nlog(n))是怎么解决的
有真正明白而且写过code的牛人能不能解释一下 |
|
Q*****a
发帖数: 33 | 16 没想到什么比O(n^2)好的方法，毕竟是partially order, 不是total order
但到不了O(n^2*l), 只是O(n^2 + nl).只需要过一遍string计算sign就可以了，另外将
数组按长度从大到小排列，提前剪枝也可以优化一些，但复杂度还是O(n^2)
const int INT_BITS = sizeof(int) * 8;
const int DATA_LEN = 256/INT_BITS;
class Int256 {
vector data;
public:
Int256(): data(DATA_LEN, 0) {
}
Int256(string s): data(DATA_LEN, 0) {
for (auto c: s) {
Set((unsigned char)c);
}
}
void Set(int l) {
data[l/INT_BITS] |= 1 << (l%INT_BITS);
}
... 阅读全帖 |
|
s******d
发帖数: 424 | 17 给两个字符串，判断第一个字符串能否用第二个字符串中的字符构成。先给一个int
ncount[256]的方案，提示可以节省空间，换成unordered_map，
这个inplace的办法， 时间复杂度O(MlogM + NlogN)
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
return s2.find(s1) != string::npos; |
|
t*****a
发帖数: 106 | 18 我认为这个题是count inversion的变形。假设有两个string, S1,S2。我的思路是先选
取一个string,比如S1,对字符编号，S1="abcd"，则a=1,b=2,c=3,d=4.然后再对S2编号
，比如S2="acdb",则S2的编号是1342. 这样就相当于对S2排序，计算count inversion
。但是因为可以把第一个元素换到最后一个元素，所以在经典的merge count时，需要
多考虑一种情况，即向右swap，取最小的inversion值，而且是考虑全长度的向右swap
，不是sub array的向右swap。应该可以在n*(logn)的时间里解决。一个大概思路，回
头写个code试验一下。 |
|
t*****a
发帖数: 106 | 19 我认为这个题是count inversion的变形。假设有两个string, S1,S2。我的思路是先选
取一个string,比如S1,对字符编号，S1="abcd"，则a=1,b=2,c=3,d=4.然后再对S2编号
，比如S2="acdb",则S2的编号是1342. 这样就相当于对S2排序，计算count inversion
。但是因为可以把第一个元素换到最后一个元素，所以在经典的merge count时，需要
多考虑一种情况，即向右swap，取最小的inversion值，而且是考虑全长度的向右swap
，不是sub array的向右swap。应该可以在n*(logn)的时间里解决。一个大概思路，回
头写个code试验一下。 |
|
y*******7
发帖数: 99 | 20 String s="abc";
String s1=s+"";
String s2="ab"+"c";
s==s1 false
s和s1为什么不等
s==s2 true
谢谢 |
|
U***A
发帖数: 849 | 21 只会C++
vector printDotStr(string s)
{
int len = s.length();
vector v;
for(int i=1; i<= len-1; i++)
{
for(int j=len-1; j>=i; j--)
{
int k = i;
string s1= s;
int jj = j;
while(k>0)
{
s1.insert(jj,1, '.');
jj = jj-1;
k--;
}
v.push_back(s1);
}
}
return v;
}
OUTPUT
012345678.9
01234567.89
0123456.789
0123... 阅读全帖 |
|
l******9
发帖数: 579 | 22 I am designing a SQL Server 2008 R2 query.
If I used string concatenation to insert into table, it does not work.
DECLARE @s1 varchar(MAX);
DECLARE @s2 varchar(MAX);
DECLARE @s3 varchar(MAX);
DECLARE @s4 varchar(MAX);
SET @s1 = 'SELECT a.id, b.name as new_name, a.value FROM ['
SET @s2 = '].[dbo].[table1] as a, '
SET @s3 = 'a_temp_table as b ' -- a_temp_table is a table variable. No
matter I put "@" or "#" in front of a_temp_table, it doe snot work.
SET @s4 = 'WHERE a.id = b.i... 阅读全帖 |
|
k***g
发帖数: 166 | 23 网上都是2维DP的，我半年前用一个一维数组做出来了，现在却怎么也想不起来是什么
思路，上代码请教一下大家：
int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
if (n1 + n2 != n3) return false;
deque M(n2+1); M[n2] = true;
for (int j=n2-1; j>=0; j--)
if (!(M[j] = s3[n1+j] == s2[j] && M[j+1]))
break;
for (int i=n1-1; i>=0; i--) {
for (int j=n2-1; j>=0; j--) {
if ( s3[i+j] == s1[i] && M[j] )
M[j] = true;
else if ( s3[i+j] == s2[j] && M[j+1] )
M[j] = true;
else
M[j] = fals... 阅读全帖 |
|
m*****k
发帖数: 731 | 24 猜想：
sort first,
then s[0],s[n-1] go to S1,
s[1],s[n-2] go to S2,
s[2],s[n-3] go to S1,
...
when n is odd,
s[n-1] go to S1, s[n] go to S2 |
|
U***A
发帖数: 849 | 25 暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, map
string> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}
for(int i=pos1+1; i
string s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.ins... 阅读全帖 |
|
U***A
发帖数: 849 | 26 暴力法行吗？
bool matchPatternHelper(string s, int pos1, string q, int pos2, map
string> &mp){
if(pos1 == s.length() && pos2 == q.length()){
return true;
}
else if((pos1 < s.length() && pos2 == q.length()) || (pos1 == s.
length() && pos2 < q.length())){
return false;
}
for(int i=pos1+1; i
string s1 = s.substr(pos1, i-pos1+1);
if(mp.find(q[pos2]) == mp.end()){
mp.ins... 阅读全帖 |
|
l*****n
发帖数: 246 | 27 String s1 = "
waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";
s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也
就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺
序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有
四个。 |
|
w**********h
发帖数: 31 | 28
Map里面存个list就行吧，把所有重复的index都存进去。不知道你说的遍历所有diff怎
么做，复杂度多少？
这是我的思路， time复杂度为O(L),L 为字符串长。
只考虑有difference的index,否则交换无意义。交换后最多可以使difference减少2，
最少是0.
1.遍历s1，构建一个Map>.key 是s1的字符，value是s1包
含该字符的所有index.
2.遍历s2,如果map.containsKey(s2.charAt(i))， 遍历map.get(s2.charAt(i)), 其中
每个index记为j. 尝试swap(i,j),看difference 减少多少（至少减少1）. 如果发现减
少2的，返回。 |
|
y*********e
发帖数: 518 | 29 想了下，这个题用greedy算法解。有点类似dijkstra算法求最短路径。
首先用一个priority queue来装已经发现的字符串，按照字典序排序。
比如输入是cbacdcbc，
scan到了第三个字符的时候，p_queue里面只有一个值 cba。
当scan到第四个字符c的时候，有了重复。这个时候有两个选择：
a. 把 c 从 cba 里面删除，变成 bac。
b. 不理会新遇到的 c，还是 cba。
把a选项和b选项再重新丢回p_queue。
如此重复一直到字符串结尾。返回p_queue的第一个值。因为p_queue是一个按照字典序
排好的priority queue，所以返回的结果一定就是答案。
伪代码如下：
let q = p_queue
for each c in string:
let s = q.empty() ? "" : q.dequeue()
if not c in s
s += c
q.push(s)
else:
s1 = del c in s
s1 += c
q.push(s)
q.push(s1... 阅读全帖 |
|
L*1
发帖数: 11537 | 30 普通短期探亲不需要亲属关系证明。见这里：
http://visa.ywpw.com/news/20120724gb.html
亲属关系证明（Q1，S1，S2）
以申请人为邀请人的亲属为由申请定居类签证（如家庭团聚Q1，长期私人访问S1），或
短期私人访问签证（S2）的，需要提供申请人与邀请人直接的亲属关系证明（配偶、父
母、子女、子女的配偶、兄弟姐妹、祖父母、外祖父母、孙子女、外孙子女以及配偶的
父母）。
常见的文件为结婚证、出生证、公安派出所出具的亲属关系证明或亲属关系公证书等复
印件。 如果没有直接文件证明，可以通过多个文件及第三人间接证明。
特别提醒：普通短期探亲不需要亲属关系证明。 不是以亲属关系为理由的S1或S2私人
访问签证也不需要亲属关系证明。 |
|
c*w
发帖数: 65 | 31 这是Java类型转换的一个细节问题了。
1在code里作为literal默认为int
s2 += 1; 编译能过是因为javac解释为s2=short(s2+1);
但是
s1 = s1 + 1;解释为一个short(s1)加一个int(1),由于short不会被隐式转换为int，所
以编译通不过 |
|
|
j********1
发帖数: 211 | 33 去年八月出了车祸，没保险，一直看中医了，腰疼，上周做了核磁共振，中医根本看不
懂我的报告，我只看懂了一点，应该是轻微的腰间盘凸出，部位在 L4-5；L5-S1 两处
关节。
求懂英语的人翻译： 多谢了！
impression:
1 L4-5 mild circumferential bulge, left subarticular through foraminal
protrusion with annular tear, and mild to moderate facet DJD contribute to
right mild /left moderate foraminal narrowing without exiting l4 root
impingement.---------------------------------------------------------------2
L5-S1 central minimal protrusion without exiting L5 or descending S1 root
impingement. |
|
j********1
发帖数: 211 | 34 去年八月出了车祸，没保险，一直看中医了，腰疼，上周做了核磁共振，中医根本看不
懂我的报告，我只看懂了一点，应该是轻微的腰间盘凸出，部位在 L4-5；L5-S1 两处
关节。
求懂英语的人翻译： 多谢了！
impression:
1 L4-5 mild circumferential bulge, left subarticular through foraminal
protrusion with annular tear, and mild to moderate facet DJD contribute to
right mild /left moderate foraminal narrowing without exiting l4 root
impingement.---------------------------------------------------------------2
L5-S1 central minimal protrusion without exiting L5 or descending S1 root
impingement. |
|
j****y
发帖数: 149 | 35 嗯 偶决定先从vichy thermal s1/s2试起
s1/s2啥区别啊？ s2说是for very dry skin
会不会水多油也多？
s1的够不够水润？？
toner到底有没必要？在fashion看得很困惑
只好回这里细问的
精华区为啥没有“购物在温哥华”的说？
在 rcf (~o~花心兔～不光吃素) 的大作中提到: 】 |
|
P****S
发帖数: 2457 | 36 正手用S1 Turbo绝对没问题的，这个我已经在正式比赛中检验过了，感觉很不错！
反手的话，若让我来选择，可能更倾向于T64而不是S1(非turbo的), 因为直板反手横打
在多数情况下还是借力多过发力的，T64的借力效率要比S1好不少，且更易透板，虽然
控制会稍逊一点。 |
|
P****S
发帖数: 2457 | 37 正手用S1 Turbo绝对没问题的，这个我已经在正式比赛中检验过了，感觉很不错！
反手的话，若让我来选择，可能更倾向于T64而不是S1(非turbo的), 因为直板反手横打
在多数情况下还是借力多过发力的，T64的借力效率要比S1好不少，且更易透板，虽然
控制会稍逊一点。 |
|
K****D
发帖数: 30533 | 38 Strongly aglee.
I feel rackets is No.1, technique is No.2, and your racket will
decide what type of technique you will develop.
At first I used Wilson Impact OS from Walmart. It's 10.8 oz and
head heavy. I never learned topspin with it, even after some
serious practice. The racket was just too heavy for me to swing.
After I switched to Head Ti-S1, I learn topspin in just a few
sessions.
This Head Ti-S1 was not a good choice either. It's about 10 oz,
107 sq in, 4pt head heavy and with S1 swing st |
|
r*****u
发帖数: 169 | 39 这里USTA playoff，Captain提前一个小时就到了，电话一直盯着每个人的位置，每个
来加油的都带着拍子(当然还有啤酒)..just in case. 见到活人后才把名字写上。
在playoff前，亲身经历对方S1到时不到，captain沮丧地宣布那个court弃权，我们当
然欣然接受，并且立刻把我们的S1安排到D2里，过了10分钟对方S1到，D2都上场warm
up了，想往回要？那是肯定没戏了。 |
|
|
s*******t
发帖数: 838 | 41 【 以下文字转载自 Military2 讨论区 】
发信人: Hetzer (乌衣蓝帽), 信区: Military2
标 题: 【转载】又有一个老太太……
发信站: BBS 未名空间站 (Tue Jan 11 10:49:10 2011, 美东)
围观归来（via: spyseikai@s1）
请允许我单独发一帖来表达到现在也无法平复的心情。
首先，我想先致歉，由于手机不方便以及反应不够迅速，我的直播有一些滞后。还有文
字错误和表达错误等问题。
其次，我想感谢S1帮我转发的朋友们。 然后，感谢上面给了132厂和611职工围观的机
会 他们才是真正的功臣， 他们才是美丽丝带的亲生父母。
作为亲自在现场见证这一历史时刻的人之一，我很自豪。也很骄傲，我们国家航空工业
的发展终于艰难的跨越了仿制的时期。开始走向自主研制的新未来。
至于图片之类的，很抱歉，为了配合安全保卫工作，我没有带相机拍照，也没有用手机
拍照（忙着发直播消息，后来看见被收的各种电子产品，我觉得黄田坝派出所可以搞一
个电子产品展销会&……）
一些细节
丝带离地准确时间是1248
丝带离地不是满推力，也没开加力
丝带离地和降... 阅读全帖 |
|
l********k
发帖数: 14844 | 42 假设洞口面积s1，容器上表面面积s2，洞口流速v，上表面液面下降速度v*s1/s2。s1/
s2可以任意小（或者s2可以任意大），这样任意有限时间内因为液面高度变化引入的修
正，和水柱重量、动量变化导致上下两个水杯里水的重量的变化相比，可以任意小，所
以忽略不计。
做题分几个境界。完全不会、胡说八道最低，其次是吹毛求疵，而高手能看出来题目问
的是什么，也不会去纠缠细节，直奔答案。 |
|
H****r
发帖数: 16240 | 43 【 以下文字转载自 Military2 讨论区 】
发信人: Hetzer (乌衣蓝帽), 信区: Military2
标 题: 【转载】又有一个老太太……
发信站: BBS 未名空间站 (Tue Jan 11 10:49:10 2011, 美东)
围观归来（via: spyseikai@s1）
请允许我单独发一帖来表达到现在也无法平复的心情。
首先，我想先致歉，由于手机不方便以及反应不够迅速，我的直播有一些滞后。还有文
字错误和表达错误等问题。
其次，我想感谢S1帮我转发的朋友们。 然后，感谢上面给了132厂和611职工围观的机
会 他们才是真正的功臣， 他们才是美丽丝带的亲生父母。
作为亲自在现场见证这一历史时刻的人之一，我很自豪。也很骄傲，我们国家航空工业
的发展终于艰难的跨越了仿制的时期。开始走向自主研制的新未来。
至于图片之类的，很抱歉，为了配合安全保卫工作，我没有带相机拍照，也没有用手机
拍照（忙着发直播消息，后来看见被收的各种电子产品，我觉得黄田坝派出所可以搞一
个电子产品展销会&……）
一些细节
丝带离地准确时间是1248
丝带离地不是满推力，也没开加力
丝带离地和降... 阅读全帖 |
|
k**l
发帖数: 2966 | 44 我仔细想了想，老师仍然是对的
用一个最简单的模型，假设瓶子是个顶端开口的凸字
瓶子粗细不同的两段自上而下高度h1 and h2,面积S1 and S2，忽略大气压因为他处处
相等
那两段接触面压强是P1 = rho*g*h1，压力P1*S1
所以不接触的地方（凸字两肩上)的压强也是P1，压力方向向上，但是这是瓶子外的压
强是零（忽略大气压），所以瓶子必须靠自身张力提供向下的压力与之平衡，压强是P1
,压力是P1(S2-S1)
复杂形状如斜面，张力方向垂直斜面，所以也有一个向下或上的分力提供多余水的重力
的压强 |
|
t*****g
发帖数: 1275 | 45 这都玩滥了
S1 = 1+1+1+... = 1+(1+1+1+...) = 1+S1
=》
S1 = 1/2 |
|
|
T*********n
发帖数: 1361 | 47 只知道怎么model一般问题成QP来进行优化，没写过
quadratic program and vector programs for
this constrained maximum cut problem
也许是这样做， 把 S1 ∩ S2 = ∅ , S1 ∪ S2 = S vectorize了写成constraint,
并且把 NetworkFlow(S1，S2) model出来，写成矩阵形式， maximize.
这个问题看起来像NP hard, 所以简单的approximation说不定也可以。。。
随便说说。。。
|
|
