请教大拿们一个算法问题# JobHunting - 待字闺中
p*l
1 楼
一个长度为M非负整数的集合，劈成N个集合，要求这N个集合的和的最大值最小。
比如 （3，4，5，6），n=3， 结果应该是 （（3，4），（5），（6））
比如 （3，4，5，6），n=3， 结果应该是 （（3，4），（5），（6））
p*2
2 楼
int groups(int[] nums, int sum) {
int count = 1;
int s = 0;
for(int i : nums) {
s += i;
if(s > sum) {
count++;
s = i;
}
}
return count;
}
public int splitArray(int[] nums, int m) {
int x = 0;
int y = 0;
for(int i : nums) {
x = Math.max(x, i);
y += i;
}
while(x <= y) {
int mid = x+(y-x)/2;
int groups = groups(nums, mid);
if(groups <= m) {
y = mid-1;
}
else {
x = mid+1;
}
}
return x;
}
int count = 1;
int s = 0;
for(int i : nums) {
s += i;
if(s > sum) {
count++;
s = i;
}
}
return count;
}
public int splitArray(int[] nums, int m) {
int x = 0;
int y = 0;
for(int i : nums) {
x = Math.max(x, i);
y += i;
}
while(x <= y) {
int mid = x+(y-x)/2;
int groups = groups(nums, mid);
if(groups <= m) {
y = mid-1;
}
else {
x = mid+1;
}
}
return x;
}
p*l
3 楼
你这里是不是假设分割数组是连续的？ 这道题目没有这个假设。
比如 【2 ，5 ， 5， 8 】 n =2 , 可以分割成 【2，8】， 【5，5】
没有必要非得是 【2，5，5】， 【8】
【在 p*****2 的大作中提到】
: int groups(int[] nums, int sum) {
: int count = 1;
: int s = 0;
:
: for(int i : nums) {
: s += i;
: if(s > sum) {
: count++;
: s = i;
: }
比如 【2 ，5 ， 5， 8 】 n =2 , 可以分割成 【2，8】， 【5，5】
没有必要非得是 【2，5，5】， 【8】
【在 p*****2 的大作中提到】
: int groups(int[] nums, int sum) {
: int count = 1;
: int s = 0;
:
: for(int i : nums) {
: s += i;
: if(s > sum) {
: count++;
: s = i;
: }
s*z
4 楼
np-complete只能穷举
https://en.wikipedia.org/wiki/Partition_problem
https://en.wikipedia.org/wiki/Partition_problem
y*u
5 楼
大神 赞赞赞！
【在 p*****2 的大作中提到】
: int groups(int[] nums, int sum) {
: int count = 1;
: int s = 0;
:
: for(int i : nums) {
: s += i;
: if(s > sum) {
: count++;
: s = i;
: }
【在 p*****2 的大作中提到】
: int groups(int[] nums, int sum) {
: int count = 1;
: int s = 0;
:
: for(int i : nums) {
: s += i;
: if(s > sum) {
: count++;
: s = i;
: }
p*2
6 楼
做的不对也赞？
大神给我们来一个吧。
【在 y**********u 的大作中提到】
: 大神 赞赞赞！
T*e
7 楼
每次都敢直接贴码就说明你艺高人胆大。
而且楼主的第一个贴子和例子确实容易产生歧义，我只看第一帖也会以为是二分。
楼主澄清后，你的解法就算不是最优，也不完全作废。可以外面加一层全排列，
学习的价值并不比没有证明的greedy差。
【在 p*****2 的大作中提到】
:
: 做的不对也赞？
: 大神给我们来一个吧。
而且楼主的第一个贴子和例子确实容易产生歧义，我只看第一帖也会以为是二分。
楼主澄清后，你的解法就算不是最优，也不完全作废。可以外面加一层全排列，
学习的价值并不比没有证明的greedy差。
【在 p*****2 的大作中提到】
:
: 做的不对也赞？
: 大神给我们来一个吧。
p*2
8 楼
大牛总结的真好
【在 T*******e 的大作中提到】
: 每次都敢直接贴码就说明你艺高人胆大。
: 而且楼主的第一个贴子和例子确实容易产生歧义，我只看第一帖也会以为是二分。
: 楼主澄清后，你的解法就算不是最优，也不完全作废。可以外面加一层全排列，
: 学习的价值并不比没有证明的greedy差。
:
T*e
9 楼
惭愧。谈算法，我这个小虾米最多只能马后炮。
【在 p*****2 的大作中提到】
:
: 大牛总结的真好
【在 p*****2 的大作中提到】
:
: 大牛总结的真好
m*s
10 楼
leetcode原题
binary search
binary search
y*u
11 楼
我就看连续的，没问题啊
【在 p*****2 的大作中提到】
:
: 大牛总结的真好
【在 p*****2 的大作中提到】
:
: 大牛总结的真好
相关阅读
用哪些ccc可以办h-1b的，抽不中的话明年也多搞几分才行了欧洲被烙印侵袭的情况怎么样？Google选组大家等抽签结果时候不如去投票攒个运气Irvine,CA major financial招modeling manager III and director能否帮别人打sevis的电话查h1b绿卡这事儿真特么烦,请问版上有在General Motors上班的没?请进....打了三次sevis电话apple-Applied Machine Learning Java Engineering Teams 有人面過麽？面试报销一个月还没收到，正常吗。。。。。。。。。。。。。。。。。Miami求分析，花一年时间读个CS master值么？ （请帮忙转待字闺中版 (转载)Google 电面面经分享-H1B中签 PP-ADV 加州处理中心G家刚通知过了HC，请问现在还能team match上吗，顺带求refer！！！h1b 收到Receipt 多久后会有结果？请问OPT工作没跟学校说怎么办？已经工作大半年了，谢谢 (转载)IT职场印度人占上风背后一个根本原因是中国发展了问个BFS leetcode问一下有人面过soasta这个公司吗？