由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教这道题有没有比较efficient的方法
相关主题
求教一道软家面试题的最优解G一道题
发个fb的面经吧写个ServiceNow的面经吧
请教问题 三个整数之和为零的题目F家题请教
问一道精华帖的老题一道g家的几何题
programming pearl看不懂这个题这道题到底是应该怎么做的?
问个简单清楚的google题,但我不会...M家
an old problem on algorithmFind Peak Element这道题要考啥?
google phone interviewG家全部面经
相关话题的讨论汇总
话题: value话题: sum话题: key话题: int话题: node
进入JobHunting版参与讨论
1 (共1页)
v*******C
发帖数: 28
1
有N个数,初始值为0, 在M个操作之后,找出最大值。 每个操作(a, b, k)表示给第a
个到第b个数分别加k。
比如说,
N=5, M= 3, 三组(a,b,k)分别是
2, 3, 100;
1, 2, 200;
4, 5, 100;
返回最大值为300.
我只能想到很naive的方法,请教版上大神们有没有更好的方法?先谢谢啦!
n*******s
发帖数: 17267
2
直觉就是每次把index a->b的加K, 最后再选个最大数就可以了。
C****t
发帖数: 53
3
有点像最少会议室问题…不过现在不是按照起点时间排序,是所有的端点排序,左端点
正值,右端点正的相反数。从左到右,记录和的最大值…
v*******C
发帖数: 28
4
不好意思,刚没说清楚,K是大于0的不定的数。

【在 n*******s 的大作中提到】
: 直觉就是每次把index a->b的加K, 最后再选个最大数就可以了。
v*******C
发帖数: 28
5
大神,能展开说说吗?不是很理解。。。

【在 C****t 的大作中提到】
: 有点像最少会议室问题…不过现在不是按照起点时间排序,是所有的端点排序,左端点
: 正值,右端点正的相反数。从左到右,记录和的最大值…

n*******s
发帖数: 17267
6
改了, 呵呵, 其实就是问你怎么找最大数吧?
或许需要改进一下, 只需要搜索最小的a和最大的b之间就可以了, 还需要改善的话,
就已经不是年老色衰的人能想明白的了。

【在 v*******C 的大作中提到】
: 不好意思,刚没说清楚,K是大于0的不定的数。
n*******s
发帖数: 17267
7
好像是说把[a, b]排序, 纪录当前最大值, 然后向右滑, 最后返回最大值。

【在 v*******C 的大作中提到】
: 大神,能展开说说吗?不是很理解。。。
C****t
发帖数: 53
8
sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
according to keys(point). if two keys are identical, put ( , +) in front
of (, -). Scan the sorted array, record the sum of values, return the
maximum... M*log(M)

a

【在 v*******C 的大作中提到】
: 有N个数,初始值为0, 在M个操作之后,找出最大值。 每个操作(a, b, k)表示给第a
: 个到第b个数分别加k。
: 比如说,
: N=5, M= 3, 三组(a,b,k)分别是
: 2, 3, 100;
: 1, 2, 200;
: 4, 5, 100;
: 返回最大值为300.
: 我只能想到很naive的方法,请教版上大神们有没有更好的方法?先谢谢啦!

s****a
发帖数: 794
9
你的这个m可和输入个数没啥关系了。。。

【在 C****t 的大作中提到】
: sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
: according to keys(point). if two keys are identical, put ( , +) in front
: of (, -). Scan the sorted array, record the sum of values, return the
: maximum... M*log(M)
:
: a

s****a
发帖数: 794
10
naive的做法是插入O(N)查询O(N)
如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了
相关主题
问个简单清楚的google题,但我不会...G一道题
an old problem on algorithm写个ServiceNow的面经吧
google phone interviewF家题请教
进入JobHunting版参与讨论
v*******C
发帖数: 28
11
多谢大神解答,用正负来区分是否overlap,非常精妙!

【在 C****t 的大作中提到】
: sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
: according to keys(point). if two keys are identical, put ( , +) in front
: of (, -). Scan the sorted array, record the sum of values, return the
: maximum... M*log(M)
:
: a

C****t
发帖数: 53
12
What N = 100000000, M=1? I don't think it is related to N.

【在 s****a 的大作中提到】
: naive的做法是插入O(N)查询O(N)
: 如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了

v*******C
发帖数: 28
13
我想的naive 的做法是按个更新数组中的值,所以是O(sum_i (b_i - a_i +1)), i = 1
...M, 如果区间比较长的话,就比较慢了。
请问大神,这个O(N)是怎么做的?

【在 s****a 的大作中提到】
: naive的做法是插入O(N)查询O(N)
: 如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了

s****a
发帖数: 794
14
这个不好说的 如果N=10, M=100000000呢。。。
其实还是看实际应用的吧
那就再加一条排序M个操作 就是那个只和M有关的。
具体看哪个好就用什么吧。
另外笔误写错了:
naive的做法是插入O(N)查询*O(1)*
如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了

【在 C****t 的大作中提到】
: What N = 100000000, M=1? I don't think it is related to N.
s****a
发帖数: 794
15
呃 我说的插入是每次操作 总共m次就成m naive好处就是查询直接出结果就好了。

1

【在 v*******C 的大作中提到】
: 我想的naive 的做法是按个更新数组中的值,所以是O(sum_i (b_i - a_i +1)), i = 1
: ...M, 如果区间比较长的话,就比较慢了。
: 请问大神,这个O(N)是怎么做的?

C****t
发帖数: 53
16
If I was the interviewer, I will not give you N points, just M operations.
N is misleading.


1

【在 v*******C 的大作中提到】
: 我想的naive 的做法是按个更新数组中的值,所以是O(sum_i (b_i - a_i +1)), i = 1
: ...M, 如果区间比较长的话,就比较慢了。
: 请问大神,这个O(N)是怎么做的?

s****a
发帖数: 794
17
这个可没准 没准就是确定的一些资源 在上面刷访问数呢。。。总不能改题目来适合算
法吧。。。

.

【在 C****t 的大作中提到】
: If I was the interviewer, I will not give you N points, just M operations.
: N is misleading.
:
:
: 1

x***y
发帖数: 633
18
It's just merging different intervals so that each new interval after
merging has the same increased value; Then in each interval, find the max
value of that interval in the original array, get the sum of that value and
increased value; compare the sum of each interval, and then return the
largest sum.
l*****n
发帖数: 246
19
这个解法不对吧。。。

【在 C****t 的大作中提到】
: sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
: according to keys(point). if two keys are identical, put ( , +) in front
: of (, -). Scan the sorted array, record the sum of values, return the
: maximum... M*log(M)
:
: a

D*****r
发帖数: 133
20
Combine the ideas from Cagnet and shuiya:
For each operation (a, b, k), there are two key/value data to describe the
operation:(a, k) and (b+1, -k), which means all the location starting from
point a will increase the weight by k and all the locations starting from b+
1 will decrease the weight by k. Maintain a BST of all key/value data sorted
by the location (the key of the data). When insert a new key/value data, if
a node with the key exists, update the value of the node by summing up the
new value and the old value in the node.
Finally, traverse the BST in order and sum up the value in the nodes
cumulatively, the cumulative sum at each node is the final weight for that
location.

a

【在 v*******C 的大作中提到】
: 有N个数,初始值为0, 在M个操作之后,找出最大值。 每个操作(a, b, k)表示给第a
: 个到第b个数分别加k。
: 比如说,
: N=5, M= 3, 三组(a,b,k)分别是
: 2, 3, 100;
: 1, 2, 200;
: 4, 5, 100;
: 返回最大值为300.
: 我只能想到很naive的方法,请教版上大神们有没有更好的方法?先谢谢啦!

U***A
发帖数: 849
21
是不是直接用map做?
map的key就是index,value就是到现在为止的增加数木。
int result = INT_MIN;
map mp;
for(int i=0; i triple x = triples[i];
for(int j=x.first; j<=x.second; j++){
mp[j] += x.third;
result = result > mp[j] ? result:mp[j];
}
}
return result;
1 (共1页)
进入JobHunting版参与讨论
相关主题
G家全部面经programming pearl看不懂这个题
请教一个算法题问个简单清楚的google题,但我不会...
攒RP写面经an old problem on algorithm
这道题怎么做google phone interview
求教一道软家面试题的最优解G一道题
发个fb的面经吧写个ServiceNow的面经吧
请教问题 三个整数之和为零的题目F家题请教
问一道精华帖的老题一道g家的几何题
相关话题的讨论汇总
话题: value话题: sum话题: key话题: int话题: node