审稿（EE方向） - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Immigration - 落地生根

审稿（EE方向）

审稿（EE方向）# Immigration - 落地生根

i*72011-10-10 07:10

1 楼

given an array of integers(positive or negative), and two integers x, y.
write a function that can find a subarray whose sum equals to x and product
equals to y
这题还有另一个变种：
Given an array with n positive and negative numbers, find the subarray with
one or more
consecutive numbers where the sum of the subarray is maximum.
看看大家有么有思路。。

d*y2011-10-10 07:10

2 楼

摘要如下。请有兴趣及方向相符的发站内信，附上简要介绍及联系方法
"Thermal Analysis of Nano Satellite Using Thermal Desktop 5.0"
Abstract
The analysis of nano satellites have been done for hot and cold case
orbital heating rates on material body as knowledgement and learning for
engineers especially thermal subsystem. This analysis has done intends for
calculating amount of temperature distribution from material body satellite
when happened heating rates in orbit. For prevented which happened of brutal
condition so we used material as MLI (Multilayer Insulation) based on
material body both kapton film, 2mil with ITO (indium tin oxide) and
painting material on solar arrays. The tools is used for analyzing, is
Thermal Desktop 5.0 software, which for calculating temperature distribution
we used Sinda/Fluint 5.0 software. The result that presenting as graphic
which show hot and cold case are happen on material body satellite and solar
arrays as long as in orbit.

l*82011-10-10 07:10

3 楼

sub-array 是要连续的吧？

product
with

【在 i*********7 的大作中提到】

: given an array of integers(positive or negative), and two integers x, y.
: write a function that can find a subarray whose sum equals to x and product
: equals to y
: 这题还有另一个变种：
: Given an array with n positive and negative numbers, find the subarray with
: one or more
: consecutive numbers where the sum of the subarray is maximum.
: 看看大家有么有思路。。

l*d2011-10-10 07:10

4 楼

谢谢这样的机会，吃个包子吧～

i*72011-10-10 07:10

5 楼

对，要连续的

【在 l*********8 的大作中提到】

: sub-array 是要连续的吧？
:
: product
: with

T*y2011-10-10 07:10

6 楼

docy, I often see that you send out review invitations, and in many
different areas. I am curious whether you are working for a publisher. It is
personal matter though. I don't need this, but thanks for sharing.

【在 d**y 的大作中提到】

: 摘要如下。请有兴趣及方向相符的发站内信，附上简要介绍及联系方法
: "Thermal Analysis of Nano Satellite Using Thermal Desktop 5.0"
: Abstract
: The analysis of nano satellites have been done for hot and cold case
: orbital heating rates on material body as knowledgement and learning for
: engineers especially thermal subsystem. This analysis has done intends for
: calculating amount of temperature distribution from material body satellite
: when happened heating rates in orbit. For prevented which happened of brutal
: condition so we used material as MLI (Multilayer Insulation) based on
: material body both kapton film, 2mil with ITO (indium tin oxide) and

w*x2011-10-10 07:10

7 楼

分配一个sum[n]: sum[i] = a[0] + a[1] + ... + a[i]
分配一个mul[n]: mul[i] = a[0]*a[1]...*a[i]
求i, j j > i 且 sum[j]-sum[i] == x && mul[j]/mul[i] == y
没考虑溢出. 要考虑的话用字符串乘除代替??

w*o2011-10-10 07:10

8 楼

有两个疑问：
1. 你的题目中的 x, y是任意给的吗？很有可能和是x, 乘积是y的subarray根本不存
在，对吧？！
2. 你说的那个变形题不就是著名的max sum subarray的题吗？难道有什么特别的吗？
不是有O(n)的算法吗？
谢谢！

product
with

【在 i*********7 的大作中提到】

c*p2011-10-10 07:10

9 楼

这两题不一样吧，，，后者是经典DP

product
with

【在 i*********7 的大作中提到】

c*p2011-10-10 07:10

10 楼

2 sum。。。。

f*22011-10-10 07:10

11 楼

如果subarray是指的位置连续的integer，正解。其实就是遍历所有可能，brute force？

【在 w****x 的大作中提到】

: 分配一个sum[n]: sum[i] = a[0] + a[1] + ... + a[i]
: 分配一个mul[n]: mul[i] = a[0]*a[1]...*a[i]
: 求i, j j > i 且 sum[j]-sum[i] == x && mul[j]/mul[i] == y
: 没考虑溢出. 要考虑的话用字符串乘除代替??

f*22011-10-10 07:10

12 楼

满足要求的不存在，就输出－1,退出。
就是max sum subarray，agree

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

: 有两个疑问：
: 1. 你的题目中的 x, y是任意给的吗？很有可能和是x, 乘积是y的subarray根本不存
: 在，对吧？！
: 2. 你说的那个变形题不就是著名的max sum subarray的题吗？难道有什么特别的吗？
: 不是有O(n)的算法吗？
: 谢谢！
:
: product
: with

l*82011-10-10 07:10

13 楼

先找sum等于给定数字的sub-array, 然后检查这个sub-array的product是否满足要求。
下面算法找sum等于给定数字的sub-array
input:
int a[]; // array
int n; // array size
Step 1, sort the input array a[] O(nlogn)
Step 2, 找到a[]中的第一个正数, 记下标为 indexP;
Step 3, 在 a[0 ... indexP-1] (负数和零部分）中寻找sum等于给定数字的sub-array
O(n)
Step 4，在 a[indexP ... n-1] (正数部分）中寻找sum等于给定数字的sub-array O
(n)
Step 5, 在整个a[] 中寻找sum等于给定数字的sub-array, 但是限定sub_array开始于
负数部分，结束于正数部分。 O(n)
检查sub_array 的product是否满足要求， O(l), where l is the length of the sub
-array. 因为sub-array的长度跟n是一个数量级的，所以O(l) = O(n).
对每一个满足sum条件的sub-array, 都要检查product是否满足要求。综合起来，算
法复杂度是O(n^2).

product
with

【在 i*********7 的大作中提到】

l*82011-10-10 07:10

14 楼

如果题目只要求返回一个sub-array，那么找到这样的sub-array后，程序就可以结束。
另外，一些简单的检查也可以避免无用的查找。
比如：如果要求的product为负，则不用step 4; 如果要求的sum为正，则不需要step
3. 如果要求的product为正，则在step3里面的sub-array size总是要偶数等等

array
O

【在 l*********8 的大作中提到】

: 先找sum等于给定数字的sub-array, 然后检查这个sub-array的product是否满足要求。
: 下面算法找sum等于给定数字的sub-array
: input:
: int a[]; // array
: int n; // array size
: Step 1, sort the input array a[] O(nlogn)
: Step 2, 找到a[]中的第一个正数, 记下标为 indexP;
: Step 3, 在 a[0 ... indexP-1] (负数和零部分）中寻找sum等于给定数字的sub-array
: O(n)
: Step 4，在 a[indexP ... n-1] (正数部分）中寻找sum等于给定数字的sub-array O

J*e2011-10-10 07:10

15 楼

If there is a 0 in the array, will this multiplication still work?

【在 w****x 的大作中提到】

m*g2011-10-10 07:10

16 楼

brute force, O(n^2)

p*22011-10-10 07:10

17 楼

brute force感觉要O(n^3)
这题如果能达到n^2应该就是最佳答案了吧？

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

: brute force, O(n^2)

m*k2011-10-10 07:10

18 楼

编了一下O(n)的maximum subarray问题：
int maxSubArray(int A[], int n) {
int max = A[0], max_neg = A[0], sum = 0;
bool flag = false; // test all negtive integers
for (int i = 0 ; i < n; i++)
{
if (A[i] >= 0)
flag = true;
else if (A[i] > max_neg)
max_neg = A[i];
sum += A[i];
if (sum < 0)
sum = 0;
else if (sum > max)
max = sum;

}

return flag?max:max_neg;
}
leetcode上测试通过