c*****e
发帖数: 3226 | 1 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];
tnnd, 在有时间限定的情况下，我最后都是brute force 搞定的。Q2 应该可以一遍O(N
) 搞定。 |
e********2
发帖数: 495 | 2 第一题就用heap + flood sweep向右上扫。
第二题其实就是同时找最大正的连续和和最小负的连续和。
【在 c*****e 的大作中提到】
: 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
|
j********g
发帖数: 80 | 3 第一题就是用两个变量记录上一次乘二 和 乘三取到最小值时的index加一, 然后每次
用那
个index对应的数去乘二 和三, 取小的为下一个数, 然后更新index. o(n)可解
【在 c*****e 的大作中提到】
: 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
|
e****x
发帖数: 148 | 4 http://mathworld.wolfram.com/SmoothNumber.html
def smoothNumber(n):
A = [0]*201
A[0] = 1
j = 1
for k in range(1,201):
if 2*A[k-j] < 3**j:
A[k] = 2*A[k-j]
else:
A[k] = 3**j
j += 1
return A[n] |
b******i
发帖数: 914 | 5 你这个第二题的解感觉有问题
如果是求绝对值最大的连续数组，那么可以maintain一个最大的正的连续和和一个最小
的负的连续和，但是题目要求求绝对值最小的连续数组，这个有用吗？
【在 e********2 的大作中提到】
: 第一题就用heap + flood sweep向右上扫。
: 第二题其实就是同时找最大正的连续和和最小负的连续和。
|
I**********s
发帖数: 441 | 6 第一题类似CC150 问题 7.7 Design an algorithm to find the kth number such
that the only prime factors are 3, 5, and 7. |
I**********s
发帖数: 441 | 7 如果求最大的 B[i][j], 已有kadane函数 maxSubArray() 找最大连续子数组和，对最
大的 B[i][j]解法可以是：max( abs( maxSubArray(A) ), abs( maxSubArray( - A) )
).
现在求最小的 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] 即得。
【在 b******i 的大作中提到】
: 你这个第二题的解感觉有问题
: 如果是求绝对值最大的连续数组，那么可以maintain一个最大的正的连续和和一个最小
: 的负的连续和，但是题目要求求绝对值最小的连续数组，这个有用吗？
|
b******i
发帖数: 914 | 8 嗯，这个nlogn的方法靠谱，谢谢！
)
n
S
【在 I**********s 的大作中提到】
: 如果求最大的 B[i][j], 已有kadane函数 maxSubArray() 找最大连续子数组和，对最
: 大的 B[i][j]解法可以是：max( abs( maxSubArray(A) ), abs( maxSubArray( - A) )
: ).
: 现在求最小的 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] 即得。
|
c*****e
发帖数: 3226 | 9 神了！有几个人会这么做， 我是 brute force 解决的。
【在 e****x 的大作中提到】
: http://mathworld.wolfram.com/SmoothNumber.html
: def smoothNumber(n):
: A = [0]*201
: A[0] = 1
: j = 1
: for k in range(1,201):
: if 2*A[k-j] < 3**j:
: A[k] = 2*A[k-j]
: else:
: A[k] = 3**j
|
b*********e
发帖数: 26 | 10 第二题这个方法有可能吗？
先求sum，w/o loss of generality, assume sum>0
然后从两端加逼，如果两端有>0的数，去掉一个使得|sum|最小，然后继续
如果两端都小于0，就一起往里扫算subarray sum，直到碰到subarray sum>0的时候停
止，去掉subarray sum可以mininize |sum|的那个subarray
sum<0的情况同理
过程中记录|sum|最小的时候的subarray |
l*****n
发帖数: 246 | 11 我怎么觉得这个nlogn的方法不对啊。。。
【在 b******i 的大作中提到】
: 嗯，这个nlogn的方法靠谱，谢谢！
:
: )
: n
: S
|
x******s
发帖数: 398 | 12 这个方法是错的. 去掉两端>0的数只能使和最小,不能使得和的绝对值最小. 如果这个
时候和是负的比如-100, 两端都是大于0的, 比如7和10, 无法去掉一个继续下去.
【在 b*********e 的大作中提到】
: 第二题这个方法有可能吗？
: 先求sum，w/o loss of generality, assume sum>0
: 然后从两端加逼，如果两端有>0的数，去掉一个使得|sum|最小，然后继续
: 如果两端都小于0，就一起往里扫算subarray sum，直到碰到subarray sum>0的时候停
: 止，去掉subarray sum可以mininize |sum|的那个subarray
: sum<0的情况同理
: 过程中记录|sum|最小的时候的subarray
|
