Redian新闻
>
上来吐曹,中部农村工程男,受不了这破地方了
avatar
上来吐曹,中部农村工程男,受不了这破地方了# Working - 上班一族
i*r
1
一个unsorted数组包含n个int值, 需要分成m段(m中最大值最小. 能否找到mlog(n)
的算法?
avatar
f*7
2
工作还可以,刚刚升值,但是地方实在太差了,小镇1个,10万人口,同事都聊些养驴
养马之类的话题,实在太憋屈了。
但是客观来说,工作还可以,去其他地方不一定能找到这样的活
大家说要不要跳槽呢?
avatar
t*e
3
Is this the same as divide n elements into m group such that the group
average == the overall average?
If this is the case, then you can use DP.
avatar
C*d
4
跳!

【在 f********7 的大作中提到】
: 工作还可以,刚刚升值,但是地方实在太差了,小镇1个,10万人口,同事都聊些养驴
: 养马之类的话题,实在太憋屈了。
: 但是客观来说,工作还可以,去其他地方不一定能找到这样的活
: 大家说要不要跳槽呢?

avatar
g*y
5
mlogn也未免太科幻了吧?
假设m=2,试试log(n)做出来?
或者又是我题意没理解对?

【在 i********r 的大作中提到】
: 一个unsorted数组包含n个int值, 需要分成m段(m: 中最大值最小. 能否找到mlog(n)
: 的算法?

avatar
l*a
6

拿到offer有比较再看。

【在 f********7 的大作中提到】
: 工作还可以,刚刚升值,但是地方实在太差了,小镇1个,10万人口,同事都聊些养驴
: 养马之类的话题,实在太憋屈了。
: 但是客观来说,工作还可以,去其他地方不一定能找到这样的活
: 大家说要不要跳槽呢?

avatar
a*s
7
Consider if this is possible in O(m*lg(n)):
Given a sequence of n numbers, and we know that their sum is mS. Pick a
subset of them such that their sum is S?
avatar
T*u
8
跳吧。想趁早养老了吗。
avatar
i*r
9
说得是. 那还能找到比O(mn)优的么?

【在 g*******y 的大作中提到】
: mlogn也未免太科幻了吧?
: 假设m=2,试试log(n)做出来?
: 或者又是我题意没理解对?

avatar
s*s
10
换个思路想想, 人生折腾图个啥?再换个思路, 米帝这哪哪不是农村啊。

【在 f********7 的大作中提到】
: 工作还可以,刚刚升值,但是地方实在太差了,小镇1个,10万人口,同事都聊些养驴
: 养马之类的话题,实在太憋屈了。
: 但是客观来说,工作还可以,去其他地方不一定能找到这样的活
: 大家说要不要跳槽呢?

avatar
g*y
11
你能说说你的O(mn)方法么?

【在 i********r 的大作中提到】
: 说得是. 那还能找到比O(mn)优的么?
avatar
b*z
12
你养头双峰骆驼跟他们聊聊
avatar
k*k
13
把 N elements 分到 M 个 区。。

((M-1) + N)!
avatar
i*t
14
考 这么好的工作还不稀罕 真是!
avatar
g*y
15
整复杂了,这是标准的DP题。

【在 k*k 的大作中提到】
: 把 N elements 分到 M 个 区。。
: 有
: ((M-1) + N)!

avatar
s*8
16
没去过大城市的就跳,否则在农村呆呆也好

★ 发自iPhone App: ChineseWeb 7.8

【在 f********7 的大作中提到】
: 工作还可以,刚刚升值,但是地方实在太差了,小镇1个,10万人口,同事都聊些养驴
: 养马之类的话题,实在太憋屈了。
: 但是客观来说,工作还可以,去其他地方不一定能找到这样的活
: 大家说要不要跳槽呢?

avatar
t*t
17
O(mn)是什么算法呀?
怎么想都觉得要先排序。

【在 i********r 的大作中提到】
: 说得是. 那还能找到比O(mn)优的么?
avatar
l*s
18
我好想养匹马
avatar
a*r
19
m*n
m*log(n) is impossible. Think about m=2.
avatar
l*c
20
Kentucky? My ex-boss said he had 3 horses.
I got out of there 4 years ago.

【在 f********7 的大作中提到】
: 工作还可以,刚刚升值,但是地方实在太差了,小镇1个,10万人口,同事都聊些养驴
: 养马之类的话题,实在太憋屈了。
: 但是客观来说,工作还可以,去其他地方不一定能找到这样的活
: 大家说要不要跳槽呢?

avatar
a*r
21
O(m,n) = O(m-1, n) + O(m, n-1)
avatar
D*r
22
10万人口已经很多了。。。
avatar
i*r
23
bottom up,每次merge一个数, 使得和最小

【在 g*******y 的大作中提到】
: 你能说说你的O(mn)方法么?
avatar
j*k
24
别吐槽了,我31单身女屌丝马上就要被发配海岛两年了,10万人小镇,基本是白人,尼
玛还在岛上。等熬两年出来都33了,我看我这辈子是嫁不出去了。。。要不是因为工作
还可以,还有本人实在太屌工作没得选,否则鬼才去那种地方。我这几天快哭死了。唉
,怎么办呀。。。
avatar
r*o
25
what does element [i][j] mean?

【在 a*****r 的大作中提到】
: O(m,n) = O(m-1, n) + O(m, n-1)
avatar
B*a
26
找白男多好,大龄剩女国男都看不上,找个白男打发时间,有兴趣再往下发展

【在 j****k 的大作中提到】
: 别吐槽了,我31单身女屌丝马上就要被发配海岛两年了,10万人小镇,基本是白人,尼
: 玛还在岛上。等熬两年出来都33了,我看我这辈子是嫁不出去了。。。要不是因为工作
: 还可以,还有本人实在太屌工作没得选,否则鬼才去那种地方。我这几天快哭死了。唉
: ,怎么办呀。。。

avatar
r*o
27
每段的元素数目是否相同?

【在 i********r 的大作中提到】
: 一个unsorted数组包含n个int值, 需要分成m段(m: 中最大值最小. 能否找到mlog(n)
: 的算法?

avatar
f*r
28
这样贪心对么?

【在 i********r 的大作中提到】
: bottom up,每次merge一个数, 使得和最小
avatar
g*y
29
我觉得是有问题的。。。
至少我的状态方程算出来只能做到O(m*n^2),没找到优化的办法了。。。

【在 f*********r 的大作中提到】
: 这样贪心对么?
avatar
f*r
30
这题有很多解法.
DP可以优化到O(m*n*log(n)).
还可以用二分+贪心. 复杂度在某些情况下比DP要好!
面试的话O(m*n^2)的DP应付一下足以

【在 g*******y 的大作中提到】
: 我觉得是有问题的。。。
: 至少我的状态方程算出来只能做到O(m*n^2),没找到优化的办法了。。。

avatar
g*y
31
你能说说你的优化是什么思路吗?

【在 f*********r 的大作中提到】
: 这题有很多解法.
: DP可以优化到O(m*n*log(n)).
: 还可以用二分+贪心. 复杂度在某些情况下比DP要好!
: 面试的话O(m*n^2)的DP应付一下足以

avatar
k*e
32
放什么飞机?npc也搞出来了。
In computer science, the partition problem is an NP-complete problem. The
problem is to decide whether a given multiset of integers can be partitioned
into two "halves" that have the same sum. More precisely, given a multiset
S of integers, is there a way to partition S into two subsets S1 and S2 such
that the sum of the numbers in S1 equals the sum of the numbers in S2?
如果可以多项式时间解决楼主的问题,只要m取2,看得到的subset summation是否等于
sum/2,就可以回答该set是否能够partition的query?
麻烦大侠以后能贴点靠谱的题目。

【在 i********r 的大作中提到】
: 一个unsorted数组包含n个int值, 需要分成m段(m: 中最大值最小. 能否找到mlog(n)
: 的算法?

avatar
g*y
33
不是NPC,题目是分成m段(切m-1刀),不是m个subset

partitioned
multiset
such

【在 k***e 的大作中提到】
: 放什么飞机?npc也搞出来了。
: In computer science, the partition problem is an NP-complete problem. The
: problem is to decide whether a given multiset of integers can be partitioned
: into two "halves" that have the same sum. More precisely, given a multiset
: S of integers, is there a way to partition S into two subsets S1 and S2 such
: that the sum of the numbers in S1 equals the sum of the numbers in S2?
: 如果可以多项式时间解决楼主的问题,只要m取2,看得到的subset summation是否等于
: sum/2,就可以回答该set是否能够partition的query?
: 麻烦大侠以后能贴点靠谱的题目。

avatar
k*e
34
ft 原来是我土了。错怪楼主,sorry!
avatar
i*r
35
能具体说一下怎么二分+贪心么?

【在 f*********r 的大作中提到】
: 这题有很多解法.
: DP可以优化到O(m*n*log(n)).
: 还可以用二分+贪心. 复杂度在某些情况下比DP要好!
: 面试的话O(m*n^2)的DP应付一下足以

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。