发信人: capcase (gotmail), 信区: JobHunting
标  题: 看看这2道题， 有没有什么捷径
发信站: BBS 未名空间站 (Mon Feb 16 01:25:08 2015, 美东)
From: http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid=32889531

Q1: S = power(2, p) * power(3, q);

A[0] = 1;
A[1] = 2;
A[2] = 3;
A[3] = 4;
A[4] = 6;
A[5] = 8;
A[6] = 9;
A[7] = 12;

求 A[N] , N >=0  && N <=200 in case of overflow

Q2. 类似于最大和的连续子数组。 但是有些不一样。
for array A[N],which can have negative values or positive values.
B[i][j] = Math.abs(A[i] + ... A[j]);

求 最小的 B[i][j];

Q1: 类似CC150 Q7.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7. O(n) solution.

Q2: 如果求最大的 B[i][j], 已有函数 maxSubArray() 找最大连续子数组和，对最大的 B[i][j]解法可以是：max( abs( maxSubArray(A) ), abs( maxSubArray( - A) ) ).  

Q2: 现在求最小的 B[i][j]。如果暴力解法，复杂度是O(n^2)。下面的方法可以做到O(nlog(n)) time, O(n) space: 先求部分和序列 S[i] = A[0] + A[1] + ... + A[i]，i = 0 to n-1。所有n^2部分和可以由S序列中两项相减得到。对S排序，找相差最小的两项S[i], S[j], B[i][j] 即得。解法来自[1]。


[1] http://stackoverflow.com/questions/25965939/finding-minimal-absolute-sum-of-a-subarray

If you compute the partial sums SUM_i Xi such as

2, 2 +(-4), 2 + (-4) + 6, 2 + (-4) + 6 + (-3)...

Then the sum of any contiguous subarray is the difference of two of the partial sums. So to find the contiguous subarray whose absolute value is minimal, I suggest that you sort the partial sums and then find the two values which are closest together, and use the positions of these two partial sums in the original sequence to find the start and end of the sub-array with smallest absolute value.

The expensive bit here is the sort, so I think this runs in time n log n.