c****9
发帖数: 164 | 1 这个牛逼，顺着思路写了下：
int maxProfit(vector &prices) {
vector left(prices.size(),0);
vector right = left;
int max= 0 ;
int min = INT_MAX;
for(int i=0;i
{
if(prices[i]
{
min = prices[i];
}
if(prices[i]-min>max)
{
max = prices[i]-min;
}
left[i]= max;
}
max = 0;
int rightmax = INT_MI... 阅读全帖 |
|
D*********S
发帖数: 21 | 2 其实还能再优化一点，只不过加的限制条件太怪了，“只能用两个不套在一起的
下面给的相当于就一个for loop, one pass time O(n), space O(1)
class Solution {
public:
int trap(const vector& h) {
const int sz=h.size();
if(sz<=2)
return 0;
int leftMax=h[0], rightMax=h[sz-1], left=1, right=sz-2, ret=0;
while(left<=right)
if(leftMax
{
if(h[left]
ret+=leftMax-h[left];
else
leftMax=h[left];... 阅读全帖 |
|
m******2
发帖数: 1007 | 3 写个为代码, currentMax 是地址
F(node n, currentMax)
if n == Null
return -MAX_INT
leftMax = F(n.left, currentMax )
rightMax = F(n.right, currentMax )
currentMax = max(n.value,
n.value+ leftMax,
n.value + rightMax,
n.value+ leftMax + rightMax,
currentMax , )
return max(0, n.value+ leftMax, n.value + rightMax,n.value ) |
|
T******7
发帖数: 1419 | 4 //==========================================================================
==
// Binary Tree Maximum Path Sum
// Given a binary tree, find the maximum path sum.
//
// The path may start and end at any node in the tree.
//
// For example:
// Given the below binary tree,
//
// " 1 "
// " / \ "
// " 2 3 "
//
// Return 6.
//
//==========================================================================
==
#include
using namespace std;
/**
* Definition for binary t... 阅读全帖 |
|
L*******e
发帖数: 114 | 5 我很弱，试着写了一下，大侠看一下。我怎么觉得一遍scan不行呢。
/**
* A[i] + A[j] + j - i ===> (A[i] - i) + (A[j] + j)
*
* @param a
* @return
*/
public static int maxDistance(int[] a){
if (a == null || a.length == 0) {
return 0;
}
// the right max of A[j] + j (including j)
int[] rightMax = new int[a.length];
int max = rightMax[a.length - 1] = a[a.length - 1] + a.length - 1;
for (int j = a.length - 2; j >= 0; j--){
if (a[j] + j > max){
max = a[j] + j;
}
rightM... 阅读全帖 |
|
L*******e
发帖数: 114 | 6 我很弱，试着写了一下，大侠看一下。我怎么觉得一遍scan不行呢。
/**
* A[i] + A[j] + j - i ===> (A[i] - i) + (A[j] + j)
*
* @param a
* @return
*/
public static int maxDistance(int[] a){
if (a == null || a.length == 0) {
return 0;
}
// the right max of A[j] + j (including j)
int[] rightMax = new int[a.length];
int max = rightMax[a.length - 1] = a[a.length - 1] + a.length - 1;
for (int j = a.length - 2; j >= 0; j--){
if (a[j] + j > max){
max = a[j] + j;
}
rightM... 阅读全帖 |
|
h****n
发帖数: 1093 | 7 贴一个通过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 = ... 阅读全帖 |
|
b*****u
发帖数: 648 | 8 递归，有点tricky的地方在于递归函数每次返回的是最大的单侧路径，但同时把两侧加
自己的和与记录的最大值比较，最终返回的是那个记录值
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int maxSoFar= root->val;
int tmp = maxContainRoot(root, maxSoFar);
return maxSoFar;
}
int maxContainRoot(TreeNode *root, int& maxSoFar)
{
if (root == NULL) return 0;
int leftMax = maxContainRoot(root->left,maxSoFar);
... 阅读全帖 |
|
h****n
发帖数: 1093 | 9 面试写成这样子就挂了
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... 阅读全帖 |
|
c********6
发帖数: 33 | 10 您看看我这个行吗，只用了您给的两个数据，
static int result = Integer.MIN_VALUE;
static int getMaxNum(TreeNode root)
{
if(root == null) return 0;
pathMax(root);
return result;
}
static int pathMax(TreeNode root)
{
if(root == null) return 0;
if(root.left == null) return pathMax(root.right) * 10 + root.val;
if(root.right == null) return pathMax(root.left) * 10 + root.val;
int leftMax = pathMax(root.left);
int rightMax = pathMax(roo... 阅读全帖 |
|
A***M
发帖数: 18 | 11 我想到的一个办法是比较简单的递归：
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... 阅读全帖 |
|
S**I
发帖数: 15689 | 12 ☆─────────────────────────────────────☆
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... 阅读全帖 |
|
z*****u
发帖数: 51 | 13 面试的是infrastructure的software engineer的职位，面试的全是印度人，不知道是
不是c3 energy已经被印度人霸占了
第一轮电面，印度人
1. Binary tree,判断两个node是不是cousins
按层traverse然后判断
2. 给定两个array，要求按照第二个array的顺序排列第一个array，如果第一个array
里面有不包含第二个array的元素，则按照顺序排列
hashmap的应用
第二轮电面，两轮skype。因为我不在加州，所以用Skype。如果在加州，就直接去他们
公司。本来要面三轮。面的不好，直接给挂了
<1> 给一个amount和一堆denomination，然后把所有的可能组成amount的denomination
的组合输出出来
这道题不难，我用的是dfs search。然后又有几个follow up: 能不能用cache加快；如
果amount非常大，list of denomination size很大该怎么办；如果给你很多机器，怎
么进行分布式计算。这一轮就这么一道题。聊的感觉还不错，各种hadoop mapre... 阅读全帖 |
|
c*******t
发帖数: 1095 | 14 用stack建left/right min/max 数组
follow 1：
原值建rightMax
平方值建rightMin
再 2 pointer
follow 2：
能从两个方向去掉唯一的好处就是去掉最后一个的时候可以选择从前去掉或者从后去掉
，两个取最优
再对称做一遍的，建leftMax和leftMin，2pointer
取最优 O(n) |
|
