哪里买12 quart plastic container? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

哪里买12 quart plastic container?

哪里买12 quart plastic container?# Parenting - 为人父母

Z*Z2013-07-09 07:07

1 楼

Given an array, find the longest subarray which the sum of the subarray less
or equal then the given MaxSum.
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6}
感觉用两个指针一前一后扫一遍数组就行了？求证。。。
出处：
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
2821_2.C0/%C0%B4%B5%C0%C4%D1%D2%BB%B5%E3%B5%C4%CC%E2

o*a2013-07-09 07:07

2 楼

Preschool 要家长准备12 quart 的container, 11"x6"x13" , 我在target 和amazon
上没有看到完全符合标准的...请问在哪里可以买到？谢谢

p*22013-07-09 07:07

3 楼

你先说说你啥思路？

h*r2013-07-09 07:07

4 楼

差不多大就行了
可以去staples， lowes 看看

【在 o*********a 的大作中提到】

: Preschool 要家长准备12 quart 的container, 11"x6"x13" , 我在target 和amazon
: 上没有看到完全符合标准的...请问在哪里可以买到？谢谢

h*e2013-07-09 07:07

5 楼

你觉得可以给出线性的解法？数字可正可负的话，我觉得DP都
不一定能给得出正解。

less

【在 Z*****Z 的大作中提到】

: Given an array, find the longest subarray which the sum of the subarray less
: or equal then the given MaxSum.
: int[] FindMaxSumArray(int[] array, int maxsum)
: for example, given array: {1, -2, 4, -2, 6, 7}
: maxsum=7
: the result would be: {1,-2, 4, -2, 6}
: 感觉用两个指针一前一后扫一遍数组就行了？求证。。。
: 出处：
: http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
: 2821_2.C0/%C0%B4%B5%C0%C4%D1%D2%BB%B5%E3%B5%C4%CC%E2

B*12013-07-09 07:07

6 楼

是不是可以用这里的方法？
http://www.geeksforgeeks.org/archives/19267

h*e2013-07-09 07:07

7 楼

那个O(N)解法看来不行，甚至不能扩展到求最长子数列和为定值的
题目，尤其是有零和负数的时候，例如给定数列{1,1,1,1,-1}
和定值3。

【在 B*******1 的大作中提到】

: 是不是可以用这里的方法？
: http://www.geeksforgeeks.org/archives/19267

B*12013-07-09 07:07

8 楼

似乎可以吧，刚测试了一下，没有发现不对啊。
测了这几个例子
72 cout << "-----------------Test 1--------------------" << endl;
73 int test1[] = {1, -2, 4, -2, 6, 7};
74 getSubArray(test1, sizeof(test1)/sizeof(int), 7);
75
76 cout << "-----------------Test 2--------------------" << endl;
77 int test2[] = {1,1,1,1,-1};
78 getSubArray(test2, sizeof(test2)/sizeof(int), 3);
79
80
81 cout << "-----------------Test 3--------------------" << endl;
82 int test3[] = {1,1,1,1,0,-1,0,-1,1};
83 getSubArray(test3, sizeof(test3)/sizeof(int), 3);
84
85
86 cout << "-----------------Test 4--------------------" << endl;
87 int test4[] = {1,1,1,1,0,-1,0,1};
88 getSubArray(test4, sizeof(test4)/sizeof(int), 3);
输出为
-----------------Test 1--------------------
1 -2 4 -2 6
-----------------Test 2--------------------
1 1 1 -1
-----------------Test 3--------------------
1 1 1 0 -1 0 -1 1
-----------------Test 4--------------------
1 1 1 0 -1 0 1
楼主的例子也过了。你的例子输出 1 1 1 -1

【在 h****e 的大作中提到】

: 那个O(N)解法看来不行，甚至不能扩展到求最长子数列和为定值的
: 题目，尤其是有零和负数的时候，例如给定数列{1,1,1,1,-1}
: 和定值3。

s*52013-07-09 07:07

9 楼

那个例子是求和相等，完全不是一回事了
这个题目只能DP, try all n*(n+1)/2 combination

B*12013-07-09 07:07

10 楼

我是说参考，我把code改了套在这个问题上的。你可以给个反例我试验一下吗。
谢谢。

【在 s*********5 的大作中提到】

: 那个例子是求和相等，完全不是一回事了
: 这个题目只能DP, try all n*(n+1)/2 combination

v*c2013-07-09 07:07

11 楼

你的code怎么写的？
{1,1,100,-100,1}，定值是3的话怎么做？

【在 B*******1 的大作中提到】

: 我是说参考，我把code改了套在这个问题上的。你可以给个反例我试验一下吗。
: 谢谢。

B*12013-07-09 07:07

12 楼

多谢指点，这个case没有过看来的确不行。

【在 v****c 的大作中提到】

: 你的code怎么写的？
: {1,1,100,-100,1}，定值是3的话怎么做？

v*c2013-07-09 07:07

13 楼

大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,-1,10,
-7}

【在 B*******1 的大作中提到】

: 多谢指点，这个case没有过看来的确不行。

Z*Z2013-07-09 07:07

14 楼

谢谢回复，早晨去接人了，刚回来。
我发帖时的想法就就是keep一个current sum和两个指针，前面那个指针不停地走，更新
current sum，如果sum大于要找的target，就前进后面的指针，同时减少sum。这个对于
输入是正数和0的情况，并且寻找的解是<=target时应该是对的吧？
有了负数之后这个就不对了。
BT是穷举所有的可能，复杂度也不过O（N2）
然后还可以用二分，猜一个长度L，然后在O（N）的时间内verify。总复杂度NlogN，是
吧？
这就研究一下vimabc的算法。

【在 p*****2 的大作中提到】

: 你先说说你啥思路？

Z*Z2013-07-09 07:07

15 楼

对的！这个和找最大的i < j 使得 A[i] < A[j]是一样的。

【在 v****c 的大作中提到】

: 大概想了个linear的算法
: 假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
: 1. 计算partial sum：S={0,1,0,10,3,12,5}
: 方便起见，我在S最前面加了一个0
: 原问题转化为找离的最远的i: 2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
: 最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
: 因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
: 3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
: while(p)

C*U2013-07-09 07:07

16 楼

赞第二步～！

【在 v****c 的大作中提到】

C*U2013-07-09 07:07

17 楼

这里应该是递增
那个i

j*a2013-07-09 07:07

18 楼

n^2 DP

less

【在 Z*****Z 的大作中提到】

s*02013-07-09 07:07

19 楼

额后来想了下应该是递增然后我就删了呵呵

【在 C***U 的大作中提到】

: 这里应该是递增
: 那个i

j*e2013-07-09 07:07

20 楼

首先，partial sum你计算错了，最后一个数是4，不是5.
最好的结果是{-1, 10, -7, 9, -8}.
算法本身好像没有问题。

大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,-1,10,
-7}

【在 v****c 的大作中提到】

b*e2013-07-09 07:07

21 楼

100, -100000, 1, 1, 1, ... (100000 1s)..., 100, 100, 100
target 400

【在 C***U 的大作中提到】

: 赞第二步～！

v*c2013-07-09 07:07

22 楼

这个例子好像没啥问题啊
partial sum是{0,100,-99900,...,100,200,300,400}
递增序列是0->100->200->300->400

【在 b***e 的大作中提到】

: 100, -100000, 1, 1, 1, ... (100000 1s)..., 100, 100, 100
: target 400

b*e2013-07-09 07:07

23 楼

What is the result according to your algorithm?

【在 v****c 的大作中提到】

: 这个例子好像没啥问题啊
: partial sum是{0,100,-99900,...,100,200,300,400}
: 递增序列是0->100->200->300->400

v*c2013-07-09 07:07

24 楼

整个数组都是啊
一开始q指向最后一个，然后就不动了，p一直走到第一个

【在 b***e 的大作中提到】

: What is the result according to your algorithm?

g*u2013-07-09 07:07

25 楼

没弄明白,麻烦vimabc指点一下:
A={0,3,-2,2,2,1,-2}
target<=1
算出的 S={0,4,2,4,6,7,5}
算出L是 {0,4,6,7}
这样的得到的结果是什么呢?
期待的结果是:
{-2,2,2,1,-2}

【在 v****c 的大作中提到】

: 整个数组都是啊
: 一开始q指向最后一个，然后就不动了，p一直走到第一个

i*72013-07-09 07:07

26 楼

mark一下，最近没在啃算法，回头再看看大家讨论吧

v*c2013-07-09 07:07

27 楼

I think in your example A should be {0,4,-2,2,2,1,-2}.
S and L are correct for this A.
initially: p=7,q=5, it is valid because 5<=7+1
next: p=6,q=5, still valid
next: p=4,q=5, still valid
next: p=0, move q until q<=p+target, so in the end q=0
p=4,q=5, corresponding to {-2,2,2,1,-2}, is the best sequence found.

【在 g**u 的大作中提到】

:
: 没弄明白,麻烦vimabc指点一下:
: A={0,3,-2,2,2,1,-2}
: target<=1
: 算出的 S={0,4,2,4,6,7,5}
: 算出L是 {0,4,6,7}
: 这样的得到的结果是什么呢?
: 期待的结果是:
: {-2,2,2,1,-2}

i*72013-07-09 07:07

28 楼

int* findmaxsumarray(int *array, int length, int maxsum){
int *sum = new int[length + 1];
sum[0] = 0;
for(int i = 1; i <= length; i++)
sum[i] = sum[i - 1] + array[i - 1];
int *max = new int[length + 1];
int *min = new int[length + 1];
for(int i = 0;i<=length;i++)
cout<cout<max[0] = 0;
for(int i = 1; i < length + 1;i++)
{
max[i] = std::max(max[i - 1], sum[i]);
}
min[length] = sum[length];
for(int i = length - 1 ; i >= 0; i--){
min[i] = std::min(min[i + 1], sum[i]);
}
int prev = 0,next = 0;
int rightmost = 0,leftmost = 0;
while(prev != length + 1 && next != length + 1){
if(min[next] - max[prev] <= maxsum){
if(next != prev){
if(next - prev > rightmost - leftmost){
rightmost = next;
leftmost = prev;
}
}
next++;
}
else
prev++;
}
int *res = new int[rightmost - leftmost];
for(int i = leftmost; i < rightmost; i++){
cout<res[i - leftmost] = array[i];
}
cout<return res;
}
这是我关于这题的算法代码。
求测试，求轻拍

p*s2013-07-09 07:07

29 楼

呵呵我猜是对的。。
其实觉得也不用求和，楼上思路本质就是预处理把所有负数往左merge。因为如果a[i+1
]是负数的话选了a[i]肯定要再选a[i+1]，所以直接看成一个整体就行了。于是转化为
一串正数，求起来就直接了。

a*y2013-07-09 07:07

30 楼

这个longest increasing sequence当场都未必能写出来

【在 j********e 的大作中提到】

: 首先，partial sum你计算错了，最后一个数是4，不是5.
: 最好的结果是{-1, 10, -7, 9, -8}.
: 算法本身好像没有问题。
:
: 大概想了个linear的算法
: 假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
: 1. 计算partial sum：S={0,1,0,10,3,12,5}
: 方便起见，我在S最前面加了一个0
: 原问题转化为找离的最远的i: 2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12

s*y2013-07-09 07:07

31 楼

这个最长的序列不是{-1,10,-7,9,-8}吗？为什么是{1,-1,10,-7}？
另外为什么partial sum从第一个数开始找递增序列？S中可能有负数的，极端一点，A
全是负数，要求和小于一个负数，这个递增序列就找不到了。

大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,-1,10,
-7}

【在 v****c 的大作中提到】

w*g2013-07-09 07:07

32 楼

排序之后再做是nlogn吧