S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 01:52:31 2011, 美东) 提到:
Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
nodes in the path from root to Y - sum of nodes in the common path from root
to first common ancestor of the Nodes X and Y
☆─────────────────────────────────────☆
SecretVest (Secret Vest) 于 (Tue Jun 21 04:01:30 2011, 美东) 提到:
not hard if someone is used... 阅读全帖 |
|
i**********e
发帖数: 1145 | 2 刚才写的，没有验证过。。。
typedef pair IntNode;
// precondition: binary tree must be complete. (eg, each node must have
either 0 or 2 children)
IntNode maxSumLeafNodes(Node *root, int sumFromRoot, Node *& leaf1, Node *&
leaf2, int &maxSum) {
assert(root);
// base case: leaf node (no children)
if (!root->left && !root->right) return IntNode(root->data, root);
// must have 2 children
assert(root->left && root->right);
IntNode fromLeft = maxSumLeafNodes(root->left, sumFromRoot + roo... 阅读全帖 |
|
p*****2
发帖数: 21240 | 3
没问题呀。输出都是-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=Fi... 阅读全帖 |
|
p******n
发帖数: 185 | 4 考虑起点和终点node为树中任意位置node(但满足相邻node不同时选），不止同一高度
最多选一个node的情况.代码如下
class Solver{
public:
int maxPathSumNoAdj(TreeNode* root){
int maxsumBelow=0, maxsum=0, maxPath=0;
maxPathSumNoAdj(root, maxsumBelow, maxsum, maxPath);
return maxPath;
}
void maxPathSumNoAdj(TreeNode* root, int& maxsumBelow, int& maxsum,
int& maxPath){
if(root->left==NULL && root->right==NULL){
maxsumBelow=0;
maxsum= (root->val>0)? root->val : 0;
... 阅读全帖 |
|
B*******1
发帖数: 2454 | 5 帮忙看看我的code能否处理一个孩子的情况？
测试树：
8
/ \
/ \
/ \
/ \
/ \
0 14
/ \ / \
/ \ / \
/ \ 11 5
17 24 \ \
\ / \ 12 45
34 / \
19 28
答案: 28 和 45
最大和124
typedef pair Item;
Item MaxpathSum(Tree *node, int &CurMaxSum, int SumToNow, Tree *&ln, Tree *&rn)
{
if (node->left && !node->right) {
Item leftPathMax = MaxpathSum(node->left, Cur... 阅读全帖 |
|
h****n
发帖数: 1093 | 6 贴一个通过OJ的版本，能处理全部负数的情况
楼主的版本很牛逼，不过有个大的bug，就是递归的结束条件没法达到，因为调用前判
断是不是指针为空了，不为空才调用，但是需要为空的时候才能达到递归结束条件
g才能正确的自底向上
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int res;
int g;
res = ... 阅读全帖 |
|
h****n
发帖数: 1093 | 7 面试写成这样子就挂了
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int res;
int g;
res = helper(root, g);
return res;
}
int helper(TreeNode * root, int & g)
{
if(!root)
{
g = 0;
return 0;
}
int leftG, rightG;
int maxSum = INT_MIN;
int leftMax = helper(root... 阅读全帖 |
|
h*********n
发帖数: 11319 | 8 这题比那题简单，因为都是正数
一遍scan就行了。
void scan(int A[], int n, int k){
int sum = 0;
int maxSum = 0;
int start = -1;
int end = -1;
int j=0;
while ((sum+A[j]) <= k && j
sum += A[j];
j++;
}
start = 0;
end = j-1;
maxSum = sum;
int i=0;
while(j
sum -= A[i];
while((sum+A[j]) <=k && j
sum+=A[j];
j... 阅读全帖 |
|
s*******f
发帖数: 1114 | 9 //1.Given an array, find the longest subarray which the sum of the subarray
//less or equal then the given MaxSum
//int[] FindMaxSumArray(int[] array, int maxsum)
//can only deal with all positive, or all negative
void FindMaxSumArray(int *in, int len, int *out, int maxsum){
if (!in || len < 1 || !out)
return 0;
int i = 0;
int j = 0;
int sum = 0;
int maxi = 0;
int maxj = 0;
while(j < len){
sum += in[j];
if (sum > maxsum){
if (j - i ... 阅读全帖 |
|
z*****n
发帖数: 447 | 10 最大的连续的数这题，如果考虑全负数的情况，应该把maxsum设为INT_MIN，而不是0，
就可以了
int getMaxSum(int A[], int N)
{
int maxsum = INT_MIN;
int sum = 0;
for(int i=0;i
sum+=A[i];
if(maxsum
maxsum = sum;
}
if(sum <0){
sum = 0;
}
}
return maxsum;
} |
|
d*******d
发帖数: 2050 | 11 我觉得没那么复杂,
没试验过
int maxsum(Node * root, int & maxpathsum, int sumtohere){
if( root== NULL){
maxpathsum = sumtohere;
return 0;
}
int left_maxpathsum = 0;
int left_maxsum = maxsum( root->left, left_maxpathsum, sumtohere+root->v);
int right_maxpathsum = 0;
int right_maxsum = maxsum root->right, right_maxpathsum, sumtohere+root->v
);
maxpathsum = max(left_maxpathsum, right_maxpathsum);
int curmaxsum = left_maxpathsum + right_maxpathsum - sumtohere - root->v;
return max(cur... 阅读全帖 |
|
A***M
发帖数: 18 | 12 我也没考虑complete binary tree的因素。
return的 maxsum 是有问题的， 正确的应该是
当前节点的MaxSum = max( CurSumFromRoot + LMaxSumToLeaf + RMaxSumToLeaf,
左节点的maxsum,
右节点的maxsum) |
|
d*******d
发帖数: 2050 | 13 这好办
int maxsum(Node * root, int & maxpathsum, Node * & maxpathNode,
int sumtohere, Node * & n1, Node * & n2){
if( root== NULL){
maxpathsum = sumtohere;
maxpathNode = NULL;
n1 = NULL;
n2 = NULL;
return 0;
}
int left_maxpathsum = 0;
Node * leftNode1;
Node * leftNode2;
Node * left_maxpathNode;
int left_maxsum = maxsum( root->left, left_maxpathsum, left_maxpathNode,
sumtohere+root->v, leftNode1, leftNode2);
int right_max... 阅读全帖 |
|
g*****i
发帖数: 2162 | 14 是个好思路,但是觉得有问题.前指针到了临界位时(再移动的话和后指针差距就超过
maxsum),前指针和它左边一直到后指针的每个位置都满足两者差<=MaxSum,但是你的方
法没有全部比较他们,因为后指针前进了一会可能前指针又前进了.
举例: 数组 3 -1 -1 3 1 1, MaxSum=3
b[]={(3,0),(2,1),(1,2),(4,3),(5,4),(6,5)} 前面是和,后面是i
排序后 b={(1,2),(2,1),(3,0),(4,3),(5,4),(6,5)}
第一次前指针到(5,4)就超过MaxSum了,用你的方法(3,0)和(5,4)不会比较,因为后指针
到(2,1)的时候前指针就继续前进了. |
|
T*****n
发帖数: 82 | 15 public class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxSum(root);
return max;
}
private int maxSum(TreeNode root){
if(root == null){
return 0;
}
int left = maxSum(root.left);
int right = maxSum(root.right);
max = Math.max(max, root.val + left + right);
int ret = Math.max(root.val + left, root.val + right);
return r... 阅读全帖 |
|
k***e
发帖数: 556 | 16 input: a circular array
output: a subvector of the array that has max sum
可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
我的想法是
1. take any element as the leader and break the circle into one dimensional
array a[1:n]. use the classical method to get the maxsum subvector
2. we did not consider the case that the maxsum subvector in the circle
passes a[1]. in the next step we will figure out the maxsum subvector that
passes a[1], suppose it is a[n - i:j].
3. claim: a[j+1:n-i-1] is the minsum subvector of a[1:n]. beca |
|
w********p
发帖数: 948 | 17 根据你提供的algorithm and feedback, 从写思路. one time scan
running time O(n) space O(1)
Please correct me, if logic error
//n is the array size
maxSum=-99999999;
if (k>n) return failed
for (int i=0; i
startIndex=i;
endIndex= (i+k-1)% n;
//get the sum of k number from startIndex to endIndex
sum=SumKMember(startIndex, endIndex， sum);
if (sum>maxSum ) { maxSum = sum; retrunIndex=startIndex }
}
//get sum only one time scan
int SumKMember(int startIndex, int endIndex, sum) {
|
|
w********p
发帖数: 948 | 18 俺嘬觉得O(1)space 还是可以的
1。 先说说普通non-circle array. 可以用非dynamic programing O(n)runing time,
O(1) space 。 关键是sum<0时，就drop, goto next
2. circle array, 向楼上说的在负数那段开，记住当前maxSum开始的 index,
计算到end of array 时继续，一直到one element before 当前maxSum开始的 index
ex1: -3, 5, 2, 1, 4, => 一只计算到5, 2, 1, 4, -3 got solution 5, 2, 1 , 4
ex2: −2, 1, −3, 4, −1, 2, 1, −2, 4 => 当前maxSum开始
4, −1, 2, 1, −2, 4, -2, 1, -3 got solution 4, -1, 2, 1, -2, 4 |
|
r**u
发帖数: 1567 | 19 Given an array, find the longest subarray which the sum of the subarray less
or equal then the given MaxSum.
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, 5, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6} |
|
p*********w
发帖数: 606 | 20 本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
1. atoi
当时写的程序很不细致，没有判断正负，字符串中字符不为数字，字符串过长越界等情
况。写完后想起来了，然后口头补充了一下，面试官说知道我的意思就直接到下一道题
了。
2. 用递归
bool Equal(Node* a, Node* b){
if(a == NULL && b != NULL) || (a != NULL && b == NULL)
return false;
if(a == NULL && b == NULL) return true;
return (Equal(a->left, b->left) && Equal(a->right, b->right)) || (Equal(a-
>left, b->right) && Equal(a->right == b->left))
}
因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
度这块比较弱，在他的提示下写出来的。
然后假如左右子树需要交换的情况下，用变量保存总共要交换几次... 阅读全帖 |
|
g*********s
发帖数: 1782 | 21 本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
2. 用递归
因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
度这块比较弱，在他的提示下写出来的。
how u know tree has lgN level? the worse case could be N.
然后假如左右子树需要交换的情况下，用变量保存总共要交换几次。我用一个引用来保
存，把代码最后一行加几个if语句，在需要交换左右子树的情况下变量自增。但他似乎
不满意，给我写了两个引用，我没懂他什么意思。
why u need a variable to keep the swap? confused here.
it seems this problem has an easy version and a complicated version.
easy version not considering left/right sub-tree swapping. in this case,
you can traverse each tree twice (i... 阅读全帖 |
|
A***M
发帖数: 18 | 22 我想到的一个办法是比较简单的递归：
int MaxSums(NODE* root, int SumFromRoot, int &MaxSumToLeaf)
{
if (NULL == root)
{
MaxSumToLeaf = 0;
return 0;
}
int CurSumFromRoot = SumFromRoot + root->value;
int LMaxSumToLeaf, RMaxSumToLeaf;
int LeftMax = MaxSums(root->left, CurSumFromRoot, LMaxSumToLeaf);
int RightMax = MaxSums(root->right, CurSumFromRoot, RMaxSumToLeaf);
int NewMaxSumToLeaf = (LMaxSumToLeaf >RMaxSumToLeaf)? LMaxSumToLeaf:
RMaxSumToLeaf... 阅读全帖 |
|
m**q
发帖数: 189 | 23 第一题可以用部分和的方法，先算出a[0]~a[i] (0<=i
放在数组b[]中，同时把对应的i值记录下来，就是说b数组每个元素是一个
结构，包含a[0]~a[i]的部分和以及对应的i值；然后根据部分和的值sort b数组，
用两个指针指向b数组开头，递增前指针直到前后指针指向的元素的部分和字段的
差值大于或等于MaxSum，然后递增后指针直到两指针指向元素的部分和字段的差
小于或等于MaxSum，在此过程中只要前后指针指向元素的部分和字段差值小于
等于MaxSum时就计算前后指针指向元素的i值字段的差值，并更新最大差值。
算部分和O(n), sort b数组 O(nlgn), 前后指针遍历数组b O(n)，总时间O(nlgn)。 |
|
r*******g
发帖数: 1335 | 24 hi
考古发现以前题似乎更难一些，不知道是不是错觉
1，从一个string 变到另一个，比如"study"->"world" （字数相等），要求
每次变一个字母，每次改变后的string必须是一个词典里面能查到的英语单词，比如你
不能把study变
成atudy
由于加了个条件，不知道最后讨论出来什么办法更好，似乎还是没有定论？
2， Given an integer, print the closest number to it that is a palindrome
input: 1224
return: 1221.
这个题仔细一想一点都不简单，关键是，最closet的数可能和原来的数完全不一样，怎
么弄？
3， In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of a... 阅读全帖 |
|
r*******g
发帖数: 1335 | 25 hi
考古发现以前题似乎更难一些，不知道是不是错觉
1，从一个string 变到另一个，比如"study"->"world" （字数相等），要求
每次变一个字母，每次改变后的string必须是一个词典里面能查到的英语单词，比如你
不能把study变
成atudy
由于加了个条件，不知道最后讨论出来什么办法更好，似乎还是没有定论？
2， Given an integer, print the closest number to it that is a palindrome
input: 1224
return: 1221.
这个题仔细一想一点都不简单，关键是，最closet的数可能和原来的数完全不一样，怎
么弄？
3， In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of a... 阅读全帖 |
|
p*****2
发帖数: 21240 | 26 第二题
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;
} |
|
r**********1
发帖数: 292 | 27 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;
}
你是觉得哪里罗嗦了？ 我感觉和前面一个写的差不多啊。 |
|
Z*****Z
发帖数: 723 | 28 Given an array, find the longest subarray which the sum of the subarray less
or equal then the given MaxSum.
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6}
感觉用两个指针一前一后扫一遍数组就行了？求证。。。
出处：
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
2821_2.C0/%C0%B4%B5%C0%C4%D1%D2%BB%B5%E3%B5%C4%CC%E2 |
|
D**f
发帖数: 439 | 29 MaxSum(pNode) = max {MaxSum(pNode->L), MaxSum(pNode->R), pNode->V +
MaxTopDown(pNode->L) + MaxTopDown(pNode->R) }
MaxTopDown(pNode) is the max sum of path from root to leaf in this tree. |
|
l*******0
发帖数: 95 | 30 这个就是求“路径和”最大值maxSum的问题，所需点数： maxSum >= 0 ? 0 : maxSum
* -1;
State: state[i][j] 表示从(0,0)到(i,j)的路径最大值，
init: state[0][0] = A[0][0],
state[0][i] = state[0][i-1] + A[0][i] for i = 1...n-1
state[i][0] = state[i-1][0] + A[i][0] for i = 1...n
DP function: state[i]j] = MAX(state[i-1][j], state[i][j-1]) + A[i][j]
result: state[n-1][n-1] >= 0 ? 0 : state[n-1][n-1] * -1; |
|
b***e
发帖数: 15201 | 31 恩 我转发答案吧 不一定对阿
发信人: philofellow (大智若愚), 信区: JobHunting
标 题: Re: 微软intern面经（一些解答）
发信站: BBS 未名空间站 (Wed Jan 19 22:22:13 2011, 美东)
本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
1. atoi
当时写的程序很不细致，没有判断正负，字符串中字符不为数字，字符串过长越界等情
况。写完后想起来了，然后口头补充了一下，面试官说知道我的意思就直接到下一道题
了。
2. 用递归
bool Equal(Node* a, Node* b){
if(a == NULL && b != NULL) || (a != NULL && b == NULL)
return false;
if(a == NULL && b == NULL) return true;
return (Equal(a->left, b->left) && Equal(a->right, b->right)) || (Equal(a-
>left, b->right) && ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 32 第二点我看错了，你的代码是对的，可以返回正确的 maxsum.
关于第一点，我一开始也是跟你一样，base case 判断为 NULL == root。这个如果只
是返回 maxsum 没有问题，但是如果要返回两个叶子节点的话就应该更改下 base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
g*****i
发帖数: 2162 | 33 1.Given an array, find the longest subarray which the sum of the subarray
less or equal then the given MaxSum
int[] FindMaxSumArray(int[] array, int maxsum)
2. Given an array of 'n' random integers. Given an integer k<=n. Find the k
numbers such that the minimum difference of all the possible pairs of k
numbers is maximum (maximum among other minimum differences for various
possible selections of k numbers ).
3.Given an array of integers(both positive and negative) divide the array
into two part... 阅读全帖 |
|
b****y
发帖数: 257 | 34 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; |
|
i*********7
发帖数: 348 | 35 int* findmaxsumarray(int *array, int length, int maxsum){
int *sum = new int[length + 1];
sum[0] = 0;
for(int i = 1; i <= length; i++)
sum[i] = sum[i - 1] + array[i - 1];
int *max = new int[length + 1];
int *min = new int[length + 1];
for(int i = 0;i<=length;i++)
cout<
cout<
max[0] = 0;
for(int i = 1; i < length + 1;i++)
{
max[i] = std::max(max[i - 1], sum[i]);
}
min[length] = sum[length];
for(int i = ... 阅读全帖 |
|
s*********3
发帖数: 25 | 36 facebook 那题的一个思路。
1. 先用一个MaxSum[i][j], 用来记录array中 i 到j的连续的最大和。是一个DP问题。
2. 再用maxSum[i][j]， 整个问题f(k, n) = max{f(k - 1, n - i), i<(n-i-k, n)}。 |
|
k***e
发帖数: 556 | 37 【 以下文字转载自 JobHunting 讨论区 】
发信人: krone (krone), 信区: JobHunting
标 题: 讨论个subarray sum的变种问题
发信站: BBS 未名空间站 (Sun Nov 29 09:27:08 2009, 美东)
input: a circular array
output: a subvector of the array that has max sum
可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
我的想法是
1. take any element as the leader and break the circle into one dimensional
array a[1:n]. use the classical method to get the maxsum subvector
2. we did not consider the case that the maxsum subvector in the circle
passes a[1]. in the next step we will fig |
|
w********p
发帖数: 948 | 38 额觉得， 这道题的关键不是array is circle or not. 因为我们只能用array来表达
circle array. circle array 只是多了几步边界问题。
搂主提到的“classical method to get the maxsum subvector“， 不知道running
time 是多少。
我的方法是 土土的将相临的K个数加起来。包括circle的情况。时间是 O(K*N)， 空间
是O（N)
不知道，有没有人更好的方法
dynamic 在这道题中应该用不着吧。 |
|
w********p
发帖数: 948 | 39 code is here, I run it simply, it looks good
O(n) for running time, and O(1) for space
#include
#include
#include
using namespace std;
int SumKMember(int iArray[],int startIndex, int endIndex, int sum);
int main (int argc, char *args[]) {
if (argc != 2) {
cout<<"comment line: a.exe number\n";
return 0;
}
int k=atoi(args[1]);
//n is the array size
int maxSum=-99999999;
int iArray[] = {1, 2 , 4 , -3, 5 ,2};
int n = sizeof( iArray) /sizeof |
|
l***i
发帖数: 632 | 40 enn... minsum(a1,...,an) = -maxsum(-a1,...,-an)...
This is just theoretical analysis (re-using an existing argument always
keeps proofs simple) -- One needn't implement it in this way though... |
|
j***n
发帖数: 301 | 41 这题很老了，貌似不是DP。
从最开始做累加，用一个sum变量记录累加结果。再用一个maxsum记录最大值。sum为负
的时候就清零。线性复杂度 |
|
P****i
发帖数: 1362 | 42 solution是从maxsum subsequence的第一个开始？ |
|
s*******f
发帖数: 1114 | 43 //3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
//子数字和最大。只能向右和下移动。时间复杂度，如何优化。
//well, no good way to express matrix parameter in c.
//i may always transfer to array next time
int MaxSum(int m[][3], int n){
if (!m || !*m || n < 1)
return 0;
int *tmp = new int[n * n];
tmp[0] = m[0][0];
for (int i = 1; i < n; ++i){
tmp[i] = m[0][i] + tmp[i - 1];
tmp[i * n] = m[i][0] + tmp[i * n - n];
}
for (int i = 1; i < n; ++i){
for (int j = 1; j < n; ++j){
... 阅读全帖 |
|
s*******f
发帖数: 1114 | 44 //3. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格
//子数字和最大。只能向右和下移动。时间复杂度，如何优化。
//well, no good way to express matrix parameter in c.
//i may always transfer to array next time
int MaxSum(int m[][3], int n){
if (!m || !*m || n < 1)
return 0;
int *tmp = new int[n * n];
tmp[0] = m[0][0];
for (int i = 1; i < n; ++i){
tmp[i] = m[0][i] + tmp[i - 1];
tmp[i * n] = m[i][0] + tmp[i * n - n];
}
for (int i = 1; i < n; ++i){
for (int j = 1; j < n; ++j){
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 45 你的基本思路是对的，但是：
1)问题要得到两个叶子节点，不单单只是 maxsum
2)你的代码 assume 所有节点值都是正数
稍微更改一下就好了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
d*******l
发帖数: 338 | 46 恩，居然大家都没注意到。上面想法一度有些混乱，总结一下，这题可以用递归做，每
个节点的maxsum依赖于3部分，一部分是根节点到它的sum，还有就是它左右子树向下的
最大path的sum，所以参数中要保存根节点到当前的sum，递归的过程中，在向下推的时
候是把这一部分求出来，向上收的时候是计算向下path的最大sum并且更新最大值。这
样应该没错了。 |
|
i**********e
发帖数: 1145 | 47 是的，你是对的。
只有单孩子节点的话，那其中一个 lChild or rChild 的 sum 会为０。
但是如果不只是要返回 maxsum，而也返回两个叶子节点的话就要额外判断了。
你的代码是很简洁，但是我说过了，没有达到题目的要求。
题目要求的是返回两个叶子节点，这个你代码不能轻易解决。不是简单地加入额外的两
个返回值就可以了。 |
|
g**********y
发帖数: 14569 | 48 第一个，brutal force:
public class MaxSum {
public int findMax(int x) {
int digits = ("" + x).length();
int max = 0;
for (int sum = 0; sum <= digits*9; sum++) {
max = Math.max(max, totalWaysUpto(x, sum));
}
return max;
}
private int totalWaysUpto(int x, int sum) {
if (sum < 0) return 0;
char[] c = ("" + x).toCharArray();
int N = c.length;
int count = 0;
if (N == 1) return sum<=x? 1 : 0;
... 阅读全帖 |
|
g***s
发帖数: 3811 | 49 we can preProcess using DP to save time;
time is O(logN×logN)
public class MaxSum {
private static final int MAX_DIGIT = 7;
static int dp[][] = new int[MAX_DIGIT+1][MAX_DIGIT*9+1];
public static int findMax(int x){
int digits = ("" + x).length();
int max = 0;
int t;
for (int sum = 0 ; sum <= 9*digits ; sum++){
max = Math.max(max, t = totalWaysUpto(x, sum));
}
return max;
}
private static int totalWaysUpt... 阅读全帖 |
|
g*****i
发帖数: 2162 | 50 第一题和经典题看上去像,但这里是求最长的子数组,还是有明显区别.而且bruteforce
只要O(N^2),dp复杂度肯定不会低于这个.我在想有没有nlogn的解法,但觉得挺难.O(N)
应该很难,举个例子吧.数组是: 1 2 3 4 5 100 -200. MaxSum=109. 用sliding window
的话到了-200还得往左扩张.
第二题你给我启发了,确实这个思路,dp其实复杂度还太高,可以用binary search更快的
找出如何分割,类似以前讨论过的paint问题,我怎么没想到呢,唉.
第四题看来只能brute force一个个尝试了?
element |
|
