d******a
发帖数: 238 | 1 1. 一个整数数组，可以有负数，0，正数，求连续子数组的最大乘积。
2. 打印二叉树的所有从root到叶节点的所有路径，不能用递归。
当时写bug-free的代码还是有些困难的，欢迎讨论并贴代码。 |
C***U
发帖数: 2406 | 2 1 首先把整个数组都变成正的 然后把数组根据0的位置分成若干个小数组 对每个数组
进行查找 查找是这样的 对每个数取log 那么这个问题就变成查找连续子数组和最大
这个问题前段时间刚好有人讨论过 应该是O(n)能解决的
2 dfs就可以了吧 判断是不是leaf 如果是leaf就打印
【在 d******a 的大作中提到】
: 1. 一个整数数组，可以有负数，0，正数，求连续子数组的最大乘积。
: 2. 打印二叉树的所有从root到叶节点的所有路径，不能用递归。
: 当时写bug-free的代码还是有些困难的，欢迎讨论并贴代码。
|
r********g
发帖数: 1351 | 3 第一题记得是用两个list来记录正的最大值和负的最大值。但是corner case不是很清
楚：
比如：如果只有一个元素，是负数，那返回这个负数，还是返回0呢？（0的意思可以理
解成0个连续元素）。
int maxSubArray(int A[], int n) {
if(n == 0) return 0;
//init
int *minList = new int[n];
int *maxList = new int[n];
memset(minList, 0, sizeof(int)*n);
memset(maxList, 0, sizeof(int)*n);
int maxP = 0;
if(A[0] > 0) {
maxList[0] = A[0];
maxP = A[0];
}
else minList[0] = A[0];
//compute
for(int i = 1; i < n; i++){
if(A[i] == 0) {
minList[i] = 0;
maxList[i] = 0;
}
else if(A[i] > 0) {
if(maxList[i-1] > 0)
maxList[i] = maxList[i-1]*A[i];
else maxList[i] = A[i];
if(minList[i-1] < 0)
minList[i] = minList[i-1]*A[i];
else minList[i] = 0;
}
else {
if(maxList[i-1] > 0)
minList[i] = maxList[i-1]*A[i];
else minList[i] = A[i];
if(minList[i-1] < 0) {
maxList[i] = minList[i-1]*A[i];
}
else maxList[i] = 0;
}
//
if(maxList[i] > maxP) maxP = maxList[i];
}
return maxP;
} |
r********g
发帖数: 1351 | 4 第二题如果不用递归，就是iterative的post order遍历？
另外，打印也很麻烦，是不是用一个辅助stack？这样复杂度是O(nlgn)吗？
void printStack(stack S){
stack T;
while(!S.empty()){
T.push(S.top());
S.pop();
}
while(!T.empty()){
cout << T.top()->value << ' ';
T.pop();
}
cout << endl;
}
// post order traverse
void printAllPath(Node* root) {
if(!root) return;
stack S;
Node* prev = NULL;
S.push(root);
while(!S.empty()){
Node* p = S.top();
if(!prev || p == prev->left || p==prev->right){
//down
if(p->left) {
S.push(p->left);
}
else if(p->right){
S.push(p->right);
}
else {
printStack(S);
S.pop();
}
}
else if(prev == p->left){
// tranverse up from left
if(p->right){
S.push(p->right);
}
else {
printStack(S);
S.pop();
}
}
else{
//tranverse up from right
S.pop();
}
prev = p;
}
} |
n****r
发帖数: 120 | 5 写个第一题
public static int subarrayMaxMultiply(int[] a){
if (a == null || a.length == 0) return 0;
int max = Integer.MIN_VALUE, multiply = 1;
for (int i=0; i
multiply *= a[i];
if (multiply > max)
max = multiply;
if (multiply <= 0)
multiply = 1;
}
return max;
} |
s********0
发帖数: 34 | 6 第一题:
维护之前的最小值和最大值，每步更新当前可取的最大值
l = map(int, raw_input().split())
min_v = 1
max_v = 1
ans = -sys.maxint
for x in l:
ans = max(ans, max(min_v*x, max(max_v*x, x)))
t = min_v
min_v = min(min_v*x, min(max_v*x, x))
max_v = max(t*x, max(max_v*x, x))
print ans |
C***U
发帖数: 2406 | 7 第一题没看见是整数 如果只是整数就容易多了
【在 d******a 的大作中提到】
: 1. 一个整数数组，可以有负数，0，正数，求连续子数组的最大乘积。
: 2. 打印二叉树的所有从root到叶节点的所有路径，不能用递归。
: 当时写bug-free的代码还是有些困难的，欢迎讨论并贴代码。
|
d******a
发帖数: 238 | 8 举2个例子
-1 返回0
-1 0 -1 0 返回0
第二题我用的也是postorder的方式写的，不知道有没有其他好的idea.
【在 r********g 的大作中提到】
: 第一题记得是用两个list来记录正的最大值和负的最大值。但是corner case不是很清
: 楚：
: 比如：如果只有一个元素，是负数，那返回这个负数，还是返回0呢？（0的意思可以理
: 解成0个连续元素）。
: int maxSubArray(int A[], int n) {
: if(n == 0) return 0;
: //init
: int *minList = new int[n];
: int *maxList = new int[n];
: memset(minList, 0, sizeof(int)*n);
|
s******k
发帖数: 3716 | 9 首先，最大乘积不包括0。其次，最大乘积要保证正的情况下尽量多乘。
所以，如果用0把数组分段，这个所求连续数组要么是某个段的所有数
乘积，要么是去掉第一个（或者最后一个负数）之后的乘积。
举例：
1 -2 3 0 2 1 -1 3 4 -1 -4 -2 2 3 -2 5 0 。。。。
分成两段：
1 -2 3
2 1 -1 3 4 -1 -4 -2 2 3 -2 5
第一段要看：[1 -2 3]，[1]，[3]
第二段要看：[2 1 -1 3 4 -1 -4 -2 2 3 -2 5]
[3 4 -1 -4 -2 2 3 -2 5] （去掉第一个负数）
[2 1 -1 3 4 -1 -4 -2 2 3] （去掉最后一个负数）
选个最大的正数就好了。
【在 d******a 的大作中提到】
: 1. 一个整数数组，可以有负数，0，正数，求连续子数组的最大乘积。
: 2. 打印二叉树的所有从root到叶节点的所有路径，不能用递归。
: 当时写bug-free的代码还是有些困难的，欢迎讨论并贴代码。
|
g***s
发帖数: 3811 | 10 i think maybe it is lz's typo. it should be number instead of integer
【在 C***U 的大作中提到】
: 第一题没看见是整数 如果只是整数就容易多了
|
|
|
g***s
发帖数: 3811 | 11 这个过程也可以看做是一个一维的DP。然后为节约空间，只用O（１）的空间。
【在 s********0 的大作中提到】
: 第一题:
: 维护之前的最小值和最大值，每步更新当前可取的最大值
: l = map(int, raw_input().split())
: min_v = 1
: max_v = 1
: ans = -sys.maxint
: for x in l:
: ans = max(ans, max(min_v*x, max(max_v*x, x)))
: t = min_v
: min_v = min(min_v*x, min(max_v*x, x))
|
Z*****Z
发帖数: 723 | 12 这个方法应该也适用于非整数的情况。
btw，python里面的max好像能够接收任意多个参数。
【在 s********0 的大作中提到】
: 第一题:
: 维护之前的最小值和最大值，每步更新当前可取的最大值
: l = map(int, raw_input().split())
: min_v = 1
: max_v = 1
: ans = -sys.maxint
: for x in l:
: ans = max(ans, max(min_v*x, max(max_v*x, x)))
: t = min_v
: min_v = min(min_v*x, min(max_v*x, x))
|
s**********o
发帖数: 105 | 13 第二个printStack不需要了吧，因为并非叶子节点
【在 r********g 的大作中提到】
: 第二题如果不用递归，就是iterative的post order遍历？
: 另外，打印也很麻烦，是不是用一个辅助stack？这样复杂度是O(nlgn)吗？
: void printStack(stack S){
: stack T;
: while(!S.empty()){
: T.push(S.top());
: S.pop();
: }
: while(!T.empty()){
: cout << T.top()->value << ' ';
|
s**********o
发帖数: 105 | 14
但这是基于数组为正的结果啊
【在 C***U 的大作中提到】
: 1 首先把整个数组都变成正的 然后把数组根据0的位置分成若干个小数组 对每个数组
: 进行查找 查找是这样的 对每个数取log 那么这个问题就变成查找连续子数组和最大
: 这个问题前段时间刚好有人讨论过 应该是O(n)能解决的
: 2 dfs就可以了吧 判断是不是leaf 如果是leaf就打印
|
r********g
发帖数: 1351 | 15 nice catch！
【在 s**********o 的大作中提到】
: 第二个printStack不需要了吧，因为并非叶子节点
|
s********0
发帖数: 34 | 16 土了， 刚开始学python 还是用c++的习惯在写，以为只能两个。。
PS：如果只是整数 可以用前面的方法 不过写起来不够clean
并且也扩展不到real number
【在 Z*****Z 的大作中提到】
: 这个方法应该也适用于非整数的情况。
: btw，python里面的max好像能够接收任意多个参数。
|
l******9
发帖数: 26 | 17 做了第一道题，然后才看到那个python 版本的 比较max_so_far, min_ending_her 和
max_ending_her
http://ideone.com/BiLUP
public int search(int A[]) {
int max = 0;
int i = 0;
int count = 0; // the count of negative numbers between
zeros
int p = 1; // the product of all number between zeros
int first = 0; // the product of positive numbers before the
first negative number between zeros
int firstNegative = 0; // the value of the first negative
number between zeros
int last = 0; // the product of positive numbers after last
negative number between zeros
int lastNegative = 0; // the value of the last negative
number
while(i <= A.length) {
if(i == A.length || A[i] == 0) {
// calculate the max product at zero or the
end of array
if (count == 1) {
p = (first > last) ? first : last;
} else if (count % 2 == 1) {
int t1 = (first == 0 ? 1 : first) *
firstNegative;
int t2 = (last == 0 ? 1 : last) *
lastNegative;
if (t1 > t2) p = p / t1; else p = p
/ t2;
}
if (p > max) max = p;
count = 0;
p = 1;
first = 0;
firstNegative = 0;
last = 0;
lastNegative = 0;
} else if (A[i] > 0) {
p = p * A[i];
if (count == 0) first = (first == 0 ? 1 :
first) * A[i];
else last = (last == 0 ? 1 : last) * A[i];
} else {
p = A[i] * p;
if (count == 0) {
firstNegative = A[i];
} else {
lastNegative = A[i];
last = 0;
}
count++;
}
i++;
}
return max;
} |
m*****k
发帖数: 731 | |
r**d
发帖数: 316 | 19 public void printEveryLeaf(Tree root) {
Stack backTrackStack = new Stack ();
Set visited = new HashSet ();
backTrackStack.push(root);
while (!backTrackStack.empty()) {
Tree n = backTrackStack.peek();
if ((n.left != null) && (!visited.contains(n.left))) {
backTrackStack.push(n.left);
visited.add(n.left);
continue;
}
if ((n.right != null) && (!visited.contains(n.right))) {
backTrackStack.push(n.right);
visited.add(n.right);
continue;
}
//only if the node did not expand
if ((n.left == null) && (n.right == null)) {
for (int i = 0; i
System.out.print(backTrackStack.get(i).node);
System.out.print(" ");
}
System.out.println(" ");
}
backTrackStack.pop();
}
【在 r********g 的大作中提到】
: 第二题如果不用递归，就是iterative的post order遍历？
: 另外，打印也很麻烦，是不是用一个辅助stack？这样复杂度是O(nlgn)吗？
: void printStack(stack S){
: stack T;
: while(!S.empty()){
: T.push(S.top());
: S.pop();
: }
: while(!T.empty()){
: cout << T.top()->value << ' ';
|
Z*****Z
发帖数: 723 | 20 这个实现的最坏空间复杂度和平均空间复杂度是一样的，都是树的size。对非退化的树
来说，应该有更好的实现方法。
【在 r**d 的大作中提到】
: public void printEveryLeaf(Tree root) {
: Stack backTrackStack = new Stack ();
: Set visited = new HashSet ();
: backTrackStack.push(root);
: while (!backTrackStack.empty()) {
: Tree n = backTrackStack.peek();
: if ((n.left != null) && (!visited.contains(n.left))) {
: backTrackStack.push(n.left);
: visited.add(n.left);
: continue;
|
|
|
r**d
发帖数: 316 | 21 backTrackStack大小是树的深度，应该不能再改进了，
visited set可以优化一点，循环内pop stack后从set删除即可，因为子树都已经访问
过，不会再次进入栈了
这样set的空间也是树深度级别的。
【在 Z*****Z 的大作中提到】
: 这个实现的最坏空间复杂度和平均空间复杂度是一样的，都是树的size。对非退化的树
: 来说，应该有更好的实现方法。
|
Z*****Z
发帖数: 723 | 22 我指的就是visited set。
应该可以被优化到树的深度级别。
但是好像不是“在pop stack之后删除即可”。例子：
1
2 3
如果在pop 2之后将其从visisted set中删除，那么下次循环的时候还会来到2.
【在 r**d 的大作中提到】
: backTrackStack大小是树的深度，应该不能再改进了，
: visited set可以优化一点，循环内pop stack后从set删除即可，因为子树都已经访问
: 过，不会再次进入栈了
: 这样set的空间也是树深度级别的。
|
r**d
发帖数: 316 | 23 你说的对，只能删除pop出来的元素的左右child
【在 Z*****Z 的大作中提到】
: 我指的就是visited set。
: 应该可以被优化到树的深度级别。
: 但是好像不是“在pop stack之后删除即可”。例子：
: 1
: 2 3
: 如果在pop 2之后将其从visisted set中删除，那么下次循环的时候还会来到2.
|
