h********g
发帖数: 155 | 1 把思路整理了一下，最终得到：
１ 当M和N都是偶数时，解总是存在的，列出的线性方程组可以通过MOD ２代数求解，
时间复杂度是O（M＊N）。
２ 当M和N中有一个是奇数时，问题的结构发生了变化，有的情况下可能不存在解， 但
可以通过动态编程来确定是否有解，并找到一个解，动态编程的时间复杂度是O（M＾３
N＾３），空间复杂度是O（M＾３N＾３）。
不知道情形２下面是否有更快的解法。 |
|
|
y***u
发帖数: 174 | 3 quick sort, 一半，一半，一半。。O(n)+O(n/2)+O(n/4)+.. |
|
f*****i
发帖数: 835 | 4 Like this? I can't open that link.
1. Calculate all 2 sum, create hash table, o(n^2) time and space.
2. 2 sum in o(n^2) space. Also o(n^2) time. |
|
f*****i
发帖数: 835 | 5 Like this? I can't open that link.
1. Calculate all 2 sum, create hash table, o(n^2) time and space.
2. 2 sum in o(n^2) space. Also o(n^2) time. |
|
C***U
发帖数: 2406 | 6 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
请牛人指点1 2 |
|
l***i
发帖数: 1309 | 7 Mine is O(n^2) and passed, how do you do O(n) time? |
|
C***U
发帖数: 2406 | 8 我能想到的就是O(n^2)时间 O(n)空间的
bool isInterleaveNew(string s1, string s2, string s3) {
vector possibleIndex;
vector tempIndex;
if(s1.empty()) {
return s2 == s3;
}
if(s2.empty()) {
return s1 == s3;
}
if(s1.size() + s2.size() != s3.size()) {
return false;
}
if(s1[0] != s3[0] && s2[0] != s3[0]) {
return false;
}
else {
if(s2[0] == s3[0]) {
possibleIndex.push_back(-1);
}
if(s1[0] == s3[... 阅读全帖 |
|
c********t
发帖数: 5706 | 9 用backtracking + recursion是O(n)时间，O(1)空间吗？
我的48个case都过了，但是judge large超时了！ |
|
C***U
发帖数: 2406 | 10 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
请牛人指点1 2 |
|
l***i
发帖数: 1309 | 11 Mine is O(n^2) and passed, how do you do O(n) time? |
|
C***U
发帖数: 2406 | 12 我能想到的就是O(n^2)时间 O(n)空间的
bool isInterleaveNew(string s1, string s2, string s3) {
vector possibleIndex;
vector tempIndex;
if(s1.empty()) {
return s2 == s3;
}
if(s2.empty()) {
return s1 == s3;
}
if(s1.size() + s2.size() != s3.size()) {
return false;
}
if(s1[0] != s3[0] && s2[0] != s3[0]) {
return false;
}
else {
if(s2[0] == s3[0]) {
possibleIndex.push_back(-1);
}
if(s1[0] == s3[... 阅读全帖 |
|
c********t
发帖数: 5706 | 13 用backtracking + recursion是O(n)时间，O(1)空间吗？
我的48个case都过了，但是judge large超时了！ |
|
h****n
发帖数: 1093 | 14 suppose the hash is implemented by chaining
Hash size is m, key number is n, the longest length of chain is L
Then we can do:
1. randomly select a bucket, suppose the length of chain is k (1<=k<=L)
2. for the list in bucket k, randomly generate a number l between 1 to L
if l is less than k, then we return the lth item in the list
It is just like a rejection sampling in a 2D array
Time complexity: The expected number per bucket is n/m
The probability that rejection sampling succeeds is n/m/L
The ... 阅读全帖 |
|
d**********x
发帖数: 4083 | 15 实际上是O(logn)的空间，但是既然长度为2^32的数列可以借助一个int来作为辅助空间
，这点overhead基本可以忽略不计了。欢迎找bug：
#include
#include
#include
using namespace std;
#include
static int get_index(int i) {
if (i == 0) {
return 1;
}
return (1 << i) + 1;
}
void rearrange(vector& vec) {
int bitmap = 0; //"O(1)" space for length < (1 << 32)
int k = vec.size() / 2;
int n = vec.size();
for (int i = 0; get_index(i) < k; ++i) {
int cur = get_index(i);
... 阅读全帖 |
|
M*********n
发帖数: 4839 | 16 虽然cut成很多块。
但每一块并不是占用O(n)的时间。
O( |
|
c***s
发帖数: 192 | 17 O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。 |
|
b****g
发帖数: 192 | 18 其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？ |
|
c***s
发帖数: 192 | 19 O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。 |
|
b****g
发帖数: 192 | 20 其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？ |
|
H******3
发帖数: 95 | 21 工资不够，考虑用这些title
http://www.flcdatacenter.com/OesQuickResults.aspx?code=19-4041&
O*Net™ JobZone: 3 such as
OES/SOC Title:Computer support specialist
GeoLevel:1
Level 1 Wage:$16.58 hour - $34,486 year
Level 2 Wage:$21.53 hour - $44,782 year
Level 3 Wage:$26.49 hour - $55,099 year
Level 4 Wage:$31.44 hour - $65,395 year
Mean Wage (H-2B):$26.49 hour - $55,099 year
This wage applies to the following O*Net occupations:
15-1151.00 Computer User Support Specialists
Provide technical assistance... 阅读全帖 |
|
b******7
发帖数: 92 | 22 算法思想：可以使用|L|大小的最小堆，同时维护堆的最大值，则range为(heap.top(),
max{heap}),最多迭代n-|L|次，得出最优range。
时间复杂度O(|L|) + O(n*log|L|) 由于|L|最多为128，故为O(n）
此算法前提为：D(c)从小到大排序
code：
typedef pair::iterator,vector::iterator> Itemtype;
struct ItemCompare{
bool operator()(const Itemtype & left, const Itemtype & right)
{
return *(left.first) > * (right.first);
}
};
pair minrange(unordered_map > & D, vector &
L)
{
pair result = make_pair(-1,-1);
v... 阅读全帖 |
|
w******j
发帖数: 185 | 23 http://discuss.leetcode.com/questions/49/binary-tree-level-orde
Complexity Analysis:
Although the DFS solution traverse the same node multiple times, it is not
another order slower than the BFS solution. Here is the proof that the DFS
solution above runs in O(N) time, where N is the number of nodes in the
binary tree and we assume that the binary tree is balanced.
We first compute the complexity of printLevel for the kth level:
T(k) = 2T(k-1) + c
= 2k-1 T(1) + c
= 2k-1 + c
Assuming it'... 阅读全帖 |
|
a********m
发帖数: 15480 | 24 估计应该是这样。不然O(n)/O(1)感觉不可能。 |
|
s********r
发帖数: 403 | 25 Quant 区转来的，还以为是要用 Quantum Computing, O(N)/O(1) 怎么这么高级啊 |
|
p***u
发帖数: 60 | 26 大家好，我的opt快到期了，急求化工OPT挂靠的机会， 请大家给我出出主意吧。
谢谢了O(∩_∩)O~ |
|
f*****2
发帖数: 141 | 27 2.1 Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
algorithm to change this array to a1, b1, a2, b2, ..., an, bn
答案给的是O（n*n）和O（nlgn）的解，分治法还得用recursion，这题并没有说不能用
额外的buffer空间，那不可以用最简单的方式弄个O（n）的解吗？
另外像这样的题没说数组类型，是不是面试的时候可以问是哪种类型？
假设是int型，这样写行不行：
int *rearrange(int *arr, int N)
{
if (arr == NULL)
return NULL;
int new_arr[2*N];
for (int i = 0; i < N; i++)
{
new_arr[2*i] = arr[i];
new_arr[2*i+1] = arr[N+i];
}
arr ... 阅读全帖 |
|
t**r
发帖数: 3428 | 28 class Solution {
public:
vector > fourSum(vector &num, int target) {
int n = num.size();
vector > ret;
sort(num.begin(), num.end());
for (int i = 0; i < n; ++i) {
if (i != 0 && num[i] == num[i - 1]) continue;
for (int j = n - 1; j > i; --j) {
if (j != n - 1 && num[j] == num[j + 1]) continue;
int L = i + 1, R = j - 1;
while (L < R) {
int sum ... 阅读全帖 |
|
i******s
发帖数: 301 | 29 枚举所有pair, 一共有n*(n-1) / 2个，然后转化为求2sum。重点是去重，可以在pair
里面记录在原来数组的index。所以最好是O(n^2)吧。你的解法应该是O(n^3) |
|
h*******e
发帖数: 6167 | 30 你见过哪个大妈每天躺沙发上看电视赚的钱还比谁都多的？
看看revenue就知道，某些公司的员工天天加班，狗一样的工作，最后revenue就那么一
点点。o的员工“很懒，什么都不干”结果公司revenue很多。这直接说明了公司存在的
必然性和价值。
说起来这些也都是浮云，最重要的还是个人发展。在某些公司绝大部分老中一辈子就是
个“技术骨干”，说难听点就是个小喽罗呗。而o我认识的不少中国人都做到了管理层
，就算是底层管理，也比小喽罗强吧。
o的东西是卖给大公司的，重要的不是普通马工每天挂在嘴上的技术价值，而是商业价
值。一个有商业价值的公司才是有前途的，只有伴随商业应用的技术才是能养活人的。 |
|
d********o
发帖数: 12 | 31 这种方法确实是O(h)
如果用Morris Traversal，空间复杂度O(1) |
|
s*********3
发帖数: 25 | 32 如果N是树的深度， 那么就是O(N).
如果N是节点的个数， 那么就看树是不是balance，如果是balance，那么就是O(logN). |
|
w*****d
发帖数: 105 | 33 From your statement, it seems all the odd and even position elements in the
output array are both sorted, so I think there is no O(N) solutions.
The best way I can figure out is sort the array first(O(NlogN)), and then do
O(N) swaps in one pass:
1 2 3 4 5 6 7 ...
to
1 3 2 5 4 7 6 ... |
|
D**0
发帖数: 84 | 34 再问：如果file O-1时还在原单位工作（而不是sponsor O-1的未来单位），O-1的推荐
信可不可以还以我在原单位上班的口吻写？ |
|
D**0
发帖数: 84 | 35 有什么特殊要求吗？最近在申EB1-A。推荐信提到我是某国家实验室的postdoc。我在提
交O-1申请时还
会是目前的postdoc职位而我的O-1雇主是industry。EB1-A推荐信可以继续用于O-1么？ |
|
q*****q
发帖数: 100 | 36 看来找之前得问一下。。。 O(∩_∩)O哈哈~ |
|
r****o
发帖数: 3918 | 37 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: romero (Pepe Romero), 信区: SanFrancisco
标 题: 哪种蚂蚁药好啊？。。。o(╯□╰)o
发信站: BBS 未名空间站 (Sat Dec 12 15:09:55 2009, 美东)
家里闹蚂蚁得厉害
天气冷了
蚂蚁都跑到家里来取暖
太郁闷了 |
|
p******y
发帖数: 3523 | 38 有问题，房主如果没有permit私自动工是拿不到C.O.的，需要去申请permit，然后去
township约inspection，OK之后才会给C.O.
lender见不到C.O.或smoke cert是不会给close的，两者都是有township发放的。
就算LZ不介意，cash deal，未来卖房也可能会遇到麻烦。
还是搞定的好。 |
|
l****i
发帖数: 1758 | 39 都是早恋的娃啊
啊！刚是你亲了我吗？
帽子好漂亮，潮翻了
你以为幸福很昂贵，其实幸福很简单
请允许我咬一口
真正的天使是不用外物修饰的，小PP好Q...?o^ ^o
嘘，你没看到我哦（发色很赞） |
|
x********i
发帖数: 1147 | 40 看到差不多日子的姐妹们都早早的做了大B超，我等的好着急啊。终于轮到我啦，周六
大B超，知道我们宝宝版的祝福很灵验，第一次求祝福，希望宝宝能健健康康，一切都
如我所愿吧o(^_^)o
先跑个题，允许新妈我忏悔下。从怀孕开始吃了不少不该吃的；也干了不少不该干的;
坐飞机，hiking，旅游一样没拉下。还有好多，不一一列举了，有的是还不知道怀孕的
时候干的，有的是已经知道怀孕了干的。自己还是个学医的，平时也是个挺cautious的
人，也不知道自己当时怎么想的就干了这么多让我后怕且后悔的事儿。希望小宝不要怪
妈妈，一定要健健康康的长大，顺顺利利的生下来！
好吧，列一下我的孕期反应，以供姐妹们参考（想了很久，应该很全了）：
1.孕期没什么反应，早期吐过两三次的样子（貌似都是空腹吃了孕酮的时候）。对food
不picky，什么都能吃。酸辣都爱（孕前也都爱）。
2.皮肤：貌似好一点，虽然偶尔还会有点小痘痘。可能作息比较好了，睡得多了些（以
前是个夜猫子）。
3.体重：增长不怎么明显，算下来长了5,6磅的样子吧。主要都是15，6周之后长的。尤
其是最近,老是饿，需要不停得吃东西.我倒是不吐，然后吃睡 |
|
t********y
发帖数: 2114 | 41 刚接到lab电话，100%确定我的血型是A。
在国内11岁时动过手术，在当时算是大手术，还是那个三级甲等医院唯一一个留学过美
国的医生给做的，所以我动手术那天，医院院长啥的都到手术台来看我，给我鼓气，其
实我那时倒一点也不害怕，还跟那些穿白大褂的在里面说笑话。手术做了快6个小时，
住院期间，我妈说她去问了我的血型，是O型，她也让人家给验了个血型，说她也是O型
。只是现在不知道这份手术资料在老家还能不能找到，反正那时候一直就认为自己是O
型了。后来学校捐血，结婚婚检，公司体检啥的都没对血型有过质疑。
现在要生娃了，才发现美国这边抽血出来的结果是A型。
到底是国内当年搞错了还是我的血型真的变了？ |
|
v*******e
发帖数: 415 | 42 我高中一次体检说我血型是B，直到来美签证体检时才发现是O，后来几次都是O型。恰
好我老爸老妈一个O型一个B型，我也不知道自己是血型变了呢还是高中查错了。呵呵。 |
|
t********y
发帖数: 2114 | 43 但是也有例外，如果AB型的基因出现过变异，可能表示为ABO三个基因，并且AB是作为
一个基因整体来遗传的，即AB+O
这种情况下，ABO的AB型与O型的人生下来的小孩就可能是A、B、AB、O里的任一种情 |
|
t********y
发帖数: 2114 | 44 国内老妈翻过我所有材料了，从小到大的各种医疗记录，还有到外地工作后的体检捐血
记录，均证明我是O型。
而且AB型和O型是有可能生下O型的孩子的，这种机率只是特别少而已。没有绝对一说。 |
|
f*******a
发帖数: 671 | 45 很可能是你自己说o型， 之前国内的n多单位就偷懒没有做检查，随便写上去的。
如果做检查，把o和a弄错的可能性非常小，一般疏忽的情况下容易把A看成B,或者把AB
看成o |
|
x**t
发帖数: 247 | 46 爸妈一个是AB，一个是O，你从前查出来是O不郁闷吗？是A就正常多了。忘了O那回事好
了，A挺好的。 |
|
s********a
发帖数: 1861 | 47 要不是go8 mm最近一直在post sfw 的好deal，我从来不去他家的， 更不知道o是他家
自己的牌子。。。
反正我只在wholefoods and trader joes买O家我需要的。
怎么就不能用在其他店了？只要卖O家牌子的店都可以吧，不过我是从来没用过胖子在
那2家店，总放错车，ft |
|
y**********u
发帖数: 2067 | 48 本周SFW的O Organics(TM) Salads可以用1OFF5和1OFF O家产品叠用吗？如果能用算DEAL吧。。想入一点呢。 |
|
s******i
发帖数: 32 | 49 本人已经提交了J-1豁免的申请。美国和中国两边都还在pending。公司准备为我提交O-
1申请，律师说如果提交的时候还没有拿到豁免，就需要离境申请O-1签证。想请教一下
已经提交J-1豁免申请对回国申请O-1签证有影响么？多谢。 |
|
s********m
发帖数: 17 | 50 请问有木有人用 O visa ？ 如果换工作，O visa 可以transfer么？ 如果lay off，O
visa有多长的grace period呢？
多谢～！ |
|
