l**********1
发帖数: 415 | 1 向大牛们求教：
1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
有求一条路的。那位牛人给个所有路径的code？
2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
max.
谢谢！ |
d****o
发帖数: 1055 | 2 第一题：
总的路径数是C(X+Y,X)
比如
X=3 Y=4
用0表示向左，1表示向下。下面就表示了一个路径
1110000
下面我们做的就是找出所有的combination
比如
输出 0 1 2就是表示1110000
输出 0 2 3表示 1011000
//XY中选X个
void combinationXY(int out[],int XYLen, int XLen,int lev,int start)
{
if(lev==XLen)
{
for(int i=0;i
cout<
cout<
return;
}
for(int i=start;i
{
out[lev]=i;
combinationXY(out,XYLen,XLen,lev+1,i+1);
}
}
the
【在 l**********1 的大作中提到】
: 向大牛们求教：
: 1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
: 有求一条路的。那位牛人给个所有路径的code？
: 2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
: max.
: 谢谢！
|
d****o
发帖数: 1055 | 3 第2题：
不知道对不对？
int maxSubTree(node* root,node** maxRoot, int& maxNum)
{
if(root==NULL) return 0;
else
{
int sum = root->data+maxSubTree(root->left)+maxSubTree(root->right);
if(sum>maxNum)
{
maxNum=sum;
(*maxRoot) = root;
}
return sum;
}
}
node* maxSub(node* root)
{
assert(root);
node* p = NULL;
int maxNum = root->data;
maxSubTree(root,&p,maxNum);
return p;
}
the
【在 l**********1 的大作中提到】
: 向大牛们求教：
: 1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
: 有求一条路的。那位牛人给个所有路径的code？
: 2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
: max.
: 谢谢！
|
r**********1
发帖数: 292 | |
q****x
发帖数: 7404 | 5
相当于在(x+y)个位置里选x个左。经典组合题。
the
递归。
【在 l**********1 的大作中提到】
: 向大牛们求教：
: 1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
: 有求一条路的。那位牛人给个所有路径的code？
: 2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
: max.
: 谢谢！
|
p*****2
发帖数: 21240 | 6 第二题
int maxSum=int.MinValue;
Node maxTree=null;
int Find(Node* node)
{
if(node==null)
return 0;
int l=Find(node.left);
int r=Find(node.right);
int sum=l+r+node.value;
if(sum>maxSum)
{
maxTree=node;
maxSum=sum;
}
return sum;
} |
q****x
发帖数: 7404 | 7 good
【在 p*****2 的大作中提到】
: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;
|
p*****2
发帖数: 21240 | |
r**********1
发帖数: 292 | 9 int maxSum(struct node* root, int* max)
{
if(root == NULL)
return 0;
if((root->left == NULL) && (root->right == NULL))
{
if(root->data > *max)
*max = root->data;
return root->data;
}
int sum = maxSum(root->left, max) + maxSum(root->right, max) + root->data;
if(sum > *max)
*max = sum;
return sum;
}
你是觉得哪里罗嗦了？ 我感觉和前面一个写的差不多啊。
【在 p*****2 的大作中提到】
:
: 是不是罗嗦点？
|
p*****2
发帖数: 21240 | 10 第一题这样可以吗？
public class Game
{
private void FindPath(int total, int x, int level, List path)
{
if (path.Count == x)
{
foreach (int i in path)
Console.Write("{0} ", i);
Console.WriteLine();
return;
}
for (int i = level; i < total; i++)
{
path.Add(i);
FindPath(total, x,i + 1, path);
path.RemoveAt(path.Count - 1);
}
}
public void AllPaths(int x, int y)
{
List path = new List();
FindPath(x+y, x, 0, path);
}
} |
|
|
p*****2
发帖数: 21240 | 11 这段有必要吗？
if((root->left == NULL) && (root->right == NULL))
{
if(root->data > *max)
*max = root->data;
return root->data;
}
【在 r**********1 的大作中提到】
: int maxSum(struct node* root, int* max)
: {
: if(root == NULL)
: return 0;
: if((root->left == NULL) && (root->right == NULL))
: {
: if(root->data > *max)
: *max = root->data;
: return root->data;
: }
|
r**********1
发帖数: 292 | 12 yeah, 你是对的。
【在 p*****2 的大作中提到】
: 这段有必要吗？
: if((root->left == NULL) && (root->right == NULL))
: {
: if(root->data > *max)
: *max = root->data;
: return root->data;
: }
|
b****y
发帖数: 257 | 13 That answer is wrong,
it should be
int left = maxSum(root->left, max);
int right = maxSum(root->right, max);
int sum = left + right + root->data;
int localMax = max(sum, max(left,right));
if(sum > *max)
*max = sum;
return max;
【在 r**********1 的大作中提到】
: 第二题：
: http://puddleofriddles.blogspot.com/2012/01/write-program-to-fi
: 包子啊。
|
j*****j
发帖数: 201 | 14 第一题，如果假设矩阵中有若干不能通过的点，怎么列出所有路径？
【在 d****o 的大作中提到】
: 第一题：
: 总的路径数是C(X+Y,X)
: 比如
: X=3 Y=4
: 用0表示向左，1表示向下。下面就表示了一个路径
: 1110000
: 下面我们做的就是找出所有的combination
: 比如
: 输出 0 1 2就是表示1110000
: 输出 0 2 3表示 1011000
|
e****r
发帖数: 581 | 15 search with backtracking, remember what you have been through
【在 j*****j 的大作中提到】
: 第一题，如果假设矩阵中有若干不能通过的点，怎么列出所有路径？
|
l*****a
发帖数: 14598 | 16 what language are you using now?
the combination of C and C#?
【在 p*****2 的大作中提到】
: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;
|
m*******l
发帖数: 12782 | 17 还好,你没有说smalltalk
【在 l*****a 的大作中提到】
: what language are you using now?
: the combination of C and C#?
|
l*****a
发帖数: 14598 | 18 what will happen if there is only one node and the value is negative number?
【在 p*****2 的大作中提到】
: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;
|
p*****2
发帖数: 21240 | 19
for interview, use C# now。feel much better than C， but it took me 2 months
to transition.
【在 l*****a 的大作中提到】
: what language are you using now?
: the combination of C and C#?
|
p*****2
发帖数: 21240 | 20
number?
好像没问题吧？
【在 l*****a 的大作中提到】
: what will happen if there is only one node and the value is negative number?
|
|
|
l*****a
发帖数: 14598 | |
l*****a
发帖数: 14598 | 22 i mean "node *" in your code
months
【在 p*****2 的大作中提到】
:
: number?
: 好像没问题吧？
|
p*****2
发帖数: 21240 | 23
typo. 现在有的时候还是有C的习惯。sigh。面试时候有时也会这样。
【在 l*****a 的大作中提到】
: i mean "node *" in your code
:
: months
|
l*****a
发帖数: 14598 | 24 u tried that?
真的没问题？
what is maxnode and maxnum with your code?
【在 p*****2 的大作中提到】
:
: typo. 现在有的时候还是有C的习惯。sigh。面试时候有时也会这样。
|
p*****2
发帖数: 21240 | 25
没问题呀。输出都是-5.
using System;
using System.Text;
using System.Collections.Generic;
public class Node
{
public int value;
public Node left;
public Node right;
public Node(int v, Node l, Node r)
{
value = v;
left = l;
right = r;
}
}
public class MaxSum
{
public int maxSum = int.MinValue;
public Node maxTree = null;
public int Find(Node node)
{
if(node==null)
return 0;
int l=Find(node.left);
int r=Find(node.right);
int sum=l+r+node.value;
if(sum>maxSum)
{
maxTree=node;
maxSum=sum;
}
return sum;
}
}
public class Test
{
static void Main(string[] args)
{
MaxSum test = new MaxSum();
Node node = new Node(-5, null, null);
test.Find(node);
Console.WriteLine(test.maxSum);
Console.WriteLine(test.maxTree.value);
Console.In.ReadLine();
}
}
【在 l*****a 的大作中提到】
: u tried that?
: 真的没问题？
: what is maxnode and maxnum with your code?
|
l*****a
发帖数: 14598 | 26 -5 works
how about one node with int.MinValue
【在 p*****2 的大作中提到】
:
: 没问题呀。输出都是-5.
: using System;
: using System.Text;
: using System.Collections.Generic;
: public class Node
: {
: public int value;
: public Node left;
: public Node right;
|
m*********e
发帖数: 13 | 27 Q1: left = 0, down = 1
#include
#include
using namespace std;
void pathes(int x, int y, string s){
if( x == 0 && y == 0){
cout<
return;
}
if(x > 0){
pathes(x-1, y, s+"0");
}
if(y > 0){
pathes(x, y-1, s+"1");
}
};
int main(int argc, char **argv){
pathes(3, 2, "");
}
If some points are not allowed, check it before move left or down. |
p*****2
发帖数: 21240 | 28
good catch. overflow的问题也没有考虑。
【在 l*****a 的大作中提到】
: -5 works
: how about one node with int.MinValue
|
p*****2
发帖数: 21240 | 29
这样的话。上边那个答案也有问题吧？上来把root.value给了maxvalue。
【在 l*****a 的大作中提到】
: -5 works
: how about one node with int.MinValue
|
d****o
发帖数: 1055 | 30 赞，这个recursion
【在 m*********e 的大作中提到】
: Q1: left = 0, down = 1
: #include
: #include
: using namespace std;
: void pathes(int x, int y, string s){
: if( x == 0 && y == 0){
: cout<: return;
: }
: if(x > 0){
|
|
|
H***e
发帖数: 476 | 31 第一题，
只需要加入一个path参数，每次保持处理一个新的点，push进去path,然后处理完再pop
出来就可以了。
java code如下:
import java.util.Stack;
public class PrintAllPathInMatrix {
private int[][] data;
public PrintAllPathInMatrix(int[][] data) {
this.data = data;
}
public void emumeratePath(int i, int j, Stack path) {
if (i > data.length - 1) {
return;
}
if (j > data[0].length - 1) {
return;
}
path.add(data[i][j]);
//found a path
if (i == data.length - 1 && j == data[0].length - 1) {
for (int p = 0; p < path.size(); p++) {
System.out.print(path.get(p) + "");
}
System.out.print("\n");
}
emumeratePath(i + 1, j, path);
emumeratePath(i, j + 1, path);
path.pop();
}
public void emumeratePath() {
if(data==null || data.length==0){
return;
}
Stack path = new Stack();
emumeratePath(0, 0, path);
}
public static void main(String[] args) {
int[][] data = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
PrintAllPathInMatrix printAllPathInMatrix = new PrintAllPathInMatrix(
data);
printAllPathInMatrix.emumeratePath();
}
}
the
【在 l**********1 的大作中提到】
: 向大牛们求教：
: 1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
: 有求一条路的。那位牛人给个所有路径的code？
: 2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
: max.
: 谢谢！
|
H***e
发帖数: 476 | 32 第二题，
用往上面反值的方法， 左右子树传值给parent node. 总复杂度为O(n).
inside a class:
BSTNode maxsumNode = null;
int maxValue = Integer.MIN_VALUE;
public void findMaxSumSubtree(BSTNode node, MutableInt sum) {
// base cases:
if (node == null) {
sum.setValue(0);
return;
}
// normal cases:
MutableInt leftSum = new MutableInt();
MutableInt rightSum = new MutableInt();
findMaxSumSubtree(node.left, leftSum);
findMaxSumSubtree(node.right, rightSum);
sum.setValue(leftSum.getValue() + rightSum.getValue() + node.key);
if (sum.getValue() > maxValue) {
maxValue = sum.getValue();
maxsumNode = node;
}
}
public BSTNode findMaxSumSubtree() {
MutableInt sum = new MutableInt();
findMaxSumSubtree(root, sum);
return maxsumNode;
}
the
【在 l**********1 的大作中提到】
: 向大牛们求教：
: 1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
: 有求一条路的。那位牛人给个所有路径的code？
: 2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
: max.
: 谢谢！
|
g***y
发帖数: 764 | 33 ur codes do not work for a tree like this:
1
/ \
-50 -30
/ \
100 20
【在 p*****2 的大作中提到】
: 第二题
: int maxSum=int.MinValue;
: Node maxTree=null;
: int Find(Node* node)
: {
: if(node==null)
: return 0;
: int l=Find(node.left);
: int r=Find(node.right);
: int sum=l+r+node.value;
|
p*****2
发帖数: 21240 | 34 我试了一下，返回100呀。这个值不对吗？
【在 g***y 的大作中提到】
: ur codes do not work for a tree like this:
: 1
: / \
: -50 -30
: / \
: 100 20
|
a********n
发帖数: 1287 | 35 #include
using namespace std;
// 0 means right, 1 means down
void AllPath(int N, int row, int col, int path[], int idx) {
if(row==N-1 && col==N-1) {
for(int i=0; i<2*N-2; i++) {
cout << path[i] << " ";
}
cout << endl;
}
// go down
if(row != N-1) {
path[idx] = 1;
AllPath(N, row+1, col, path, idx+1);
}
// go right
if(col != N-1) {
path[idx] = 0;
AllPath(N, row, col+1, path, idx+1);
}
}
int main() {
int path[4];
AllPath(3, 0, 0, path, 0);
} |
H***e
发帖数: 476 | 36 对的
【在 p*****2 的大作中提到】
: 我试了一下，返回100呀。这个值不对吗？
|
g***y
发帖数: 764 | 37 你对了 我看错了 我以为你的结果是find的return value。
my codes (C#):
public static int getMaxSum(Node root)
{
if (root == null)
return 0;
int max = 0;
getMaxSumHelper(root, ref max);
return max;
}
private static int getMaxSumHelper(Node root, ref int currMax
)
{
int leftSum = 0;
int rightSum = 0;
if (root.left != null)
{
leftSum = getMaxSumHelper(root.left, ref currMax);
}
if (root.right != null)
{
rightSum = getMaxSumHelper(root.right, ref currMax);
}
if (rightSum + leftSum + root.payLoad > currMax)
{
currMax = rightSum + leftSum + root.payLoad;
}
return rightSum + leftSum + root.payLoad;
}
【在 p*****2 的大作中提到】
: 我试了一下，返回100呀。这个值不对吗？
|
p*****2
发帖数: 21240 | 38 嗯。我没有好好写。用了两个全局变量。
【在 g***y 的大作中提到】
: 你对了 我看错了 我以为你的结果是find的return value。
: my codes (C#):
: public static int getMaxSum(Node root)
: {
: if (root == null)
: return 0;
: int max = 0;
: getMaxSumHelper(root, ref max);
: return max;
: }
|
H***e
发帖数: 476 | 39 喝喝，如果我需要全局变量来比较clean得话，我一般把他们wrap到一个 class里面。。
【在 p*****2 的大作中提到】
: 嗯。我没有好好写。用了两个全局变量。
|
p*****2
发帖数: 21240 | 40
。。
我在VS上是这么搞的。我当时就是在纸上写了一下就发上来了。只是表达一个算法。
【在 H***e 的大作中提到】
: 喝喝，如果我需要全局变量来比较clean得话，我一般把他们wrap到一个 class里面。。
|
|
|
r**********1
发帖数: 292 | 41 没有错。
你的这个比较，在原函数的recursive calls里面就比较过了。
【在 b****y 的大作中提到】
: That answer is wrong,
: it should be
: int left = maxSum(root->left, max);
: int right = maxSum(root->right, max);
: int sum = left + right + root->data;
: int localMax = max(sum, max(left,right));
: if(sum > *max)
: *max = sum;
: return max;
|
r**********1
发帖数: 292 | 42 如果你说这个函数没返回subtree的"root",是有这个问题。但是，对于sum值，是没问
题的。和peking2一样的啊。而且算法关键是recursive就行了啊。
对于包子，我也不在乎。但是我是前几个发帖子的，而且实现给了关键点了啊，怎么着
，我要个包子，我是理直气壮的吧。
【在 l*****a 的大作中提到】
: 不work
: why 包子
|
r**********1
发帖数: 292 | 43 我又看了一遍，这段就是对叶子节点的直接处理，避免了进一步的call。 我不觉的这
样有啥不妥的。
【在 p*****2 的大作中提到】
: 这段有必要吗？
: if((root->left == NULL) && (root->right == NULL))
: {
: if(root->data > *max)
: *max = root->data;
: return root->data;
: }
|
p*****2
发帖数: 21240 | 44
如果树大的话，每一个node都要进行判断，会影响performance.当然这不是关键，关键
就是代码看起来不简洁。
【在 r**********1 的大作中提到】
: 我又看了一遍，这段就是对叶子节点的直接处理，避免了进一步的call。 我不觉的这
: 样有啥不妥的。
|
S******t
发帖数: 151 | |
e***s
发帖数: 799 | 46 求教，第二题DP怎么写?
【在 S******t 的大作中提到】
: 第一题递归，第二题树形DP啊
|
h********w
发帖数: 221 | |
