请教大拿们一个算法问题# 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 的大作中提到】
:
: 大牛总结的真好
相关阅读
g家工资每年大概能涨多少？HireRight里residency history要写的多详细？单纯从技术角度讲，NASA排第一应该没什么可争议的拿到一个药厂offer -- 帮朋友转发，此人脸皮薄，轻拍 (转载)现在是不是必须进internet公司啊求解释丽寇儿的新题maximum gap题目到底啥意思？纽约现在找工作行情怎么样？请问EPIC的C#职位可以去吗？offer 反悔问题 求助refer eBay SDE 以及其他职位 针对新毕业生和想换工作的同学ETL QA-contractor向前辈请教一下Asana这个公司argue工资，是涨salary好还是多要点RSU？RSU是不是交税少？请问很多传统行业 有直接网站投录取的吗？这种情况我该选哪一个公司Rocket Fuel Data Platform组onsite 被问现在的薪水和预期的薪水 请问怎么回答？请教一道L的题FB面经从技术角度来看，google确实第一