r********t
发帖数: 395 | 1 不过这个不适用于负数，因为这个方法的一个特性就是sum是递增的。 |
|
r********t
发帖数: 395 | 2 不过这个不适用于负数，因为这个方法的一个特性就是sum是递增的。 |
|
b********h
发帖数: 119 | 3 I see. Then how about find the smallest number in the array, add this number
to every element of the array and to the sum you are looking for. It is the
same problem as before. |
|
c**y
发帖数: 172 | 4 问题是找到一个binary tree中所有路径，对于每一条这样得路径，其成员节点的和等
于一个指定的值。附带的说明是符合条件的路径不是必须从root开始。下面是
CareerCup的问题说明和解答。
我的疑惑是这个solution给出的路径（们）确实可以不是从root开始，但是每一条路径
一定是沿着root到某一个叶子节点（即在较低level的端点一定是在一个以在较高level
端点为顶点的subtree里面），而不会出现路径的两端出现在两个不同的subtree中。
However，题的说明之中并没有指明路径的两端不可以出现在两个不同的subtree中。
如何修改下面的solution使得上面所说的路径可以被找到呢？Thanks
Problem:
You are given a binary tree in which each node contains a value. Design an
algorithm to print all paths which sum up to that value. Note that it can be
any path in the tree |
|
|
a***c
发帖数: 2443 | 6 it's called subset sum, look it up
also, hardness is hardness, complexity is complexity. |
|
|
j********x
发帖数: 2330 | 8 k is a fixed number... subset sum considers the case that k is not fixed,
which forces to explore all possible combinations.
I believe the complexity is n^(k-1) just guess |
|
e*****e
发帖数: 1275 | 9 是subarray 还是 subset.
subset 是个经典DP的题目。
subarray 就算i到n的sum好了~~然后用hash table |
|
a******7
发帖数: 106 | 10 kind of saw this before here, but with sum <= k |
|
j**y
发帖数: 462 | 11 detect if a sorted array contains two integer that sum up to 7. And then
improve your code so that the array is accessed with only one iteration
any solution for one iteration? |
|
|
e******s
发帖数: 38 | 13 Two reverse sorted arrays A and B have been given, such that size of A is m
and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B.
看了好多论坛上的答案，好像都不是很清楚。 有一个用max-heap做的，就是每次从
heap里pop出一个
pair(a[i]+b[j]),然后将 pair(a[i],b[j+1]) 和pair(a[i+1],b[j]) insert到heap里。
但好像需要check是不是重复的pair(a[i],b[j])已经在heap里了。 不知道有没有人有
更清楚的解
法，多谢。 |
|
|
S****a
发帖数: 330 | 15 Cartus的人发了一封邮件：“Relocation Lump Sum"
说：Please fill out your banking information. Your $X,000 will be requested.
It will be in your account within 7-10 business days.
但是在banking information form里面有说：this form will be used to send money
to you when you submit a expense report.
请教几个问题
1。这是实报实销还是给钱？
2.这个expense report 要写明搬家花了多少钱吗？
3。要是给钱的话，听说还要交税，怎么交法（Connecticut）？
请过来人指教！ |
|
l*********r
发帖数: 674 | 16 一般Lump Sum指的是一次性给多少钱，而不是实报实销，当然还要扣税（打到你帐上的
就已经是税后的）。 |
|
|
l*********r
发帖数: 674 | 18 我以前有lump sum，同时报销全家人机票，和以前租的房子break lease的罚款。 |
|
h*********1
发帖数: 279 | 19 给了lump sum，是不是就不再给租过去以后暂时住的房子了？或者报销房租？ |
|
a***a
发帖数: 739 | 20 有给lump sum，又给搬家，又给机票，又给allowance的。 |
|
S****a
发帖数: 330 | 21 Cartus的人发了一封邮件：“Relocation Lump Sum"
说：Please fill out your banking information. Your $X,000 will be requested.
It will be in your account within 7-10 business days.
但是在banking information form里面有说：this form will be used to send money
to you when you submit a expense report.
请教几个问题
1。这是实报实销还是给钱？
2.这个expense report 要写明搬家花了多少钱吗？
3。要是给钱的话，听说还要交税，怎么交法（Connecticut）？
请过来人指教！ |
|
l*********r
发帖数: 674 | 22 一般Lump Sum指的是一次性给多少钱，而不是实报实销，当然还要扣税（打到你帐上的
就已经是税后的）。 |
|
|
l*********r
发帖数: 674 | 24 我以前有lump sum，同时报销全家人机票，和以前租的房子break lease的罚款。 |
|
h*********1
发帖数: 279 | 25 给了lump sum，是不是就不再给租过去以后暂时住的房子了？或者报销房租？ |
|
a***a
发帖数: 739 | 26 有给lump sum，又给搬家，又给机票，又给allowance的。 |
|
h*********n
发帖数: 915 | 27 given array X and target t, find k elements in X such that sum {X[i]|i=1~k}
= t.
k = 2, 3 is classical
k = 4 sometimes is asked too
how about k = 5, and any given constant k? any general solution and what's
the complexity with respect to k? |
|
a***r
发帖数: 93 | 28 memory O(n)
time O(nlogn)
//~ Given a array,find out if there exist a subarray such its sum is zero
#include
#include
using namespace std;
static void swap(int *p, int i, int j) {
int t=p[i]; p[i]=p[j];p[j]=t;
}
static int partition(int *p,int left,int right) {
int j=left;
for(int i=left;i
if(p[i]
}
swap(p,j,right);
return j;
}
static void binary_sort(int *p, int left, int right) {
if(left>=r... 阅读全帖 |
|
j********x
发帖数: 2330 | 29 照你本来题目的描述，其实是个很简单的问题
这个题目的描述跟subset sum其实是不同的，你这里是subarray，而不是subset |
|
f****4
发帖数: 1359 | 30 原帖：http://www.mitbbs.com/article_t/Programming/31198701.html
Two reverse sorted arrays A and B have been given.such that size of A is m
and size of B is n You need to find the k th largest sum (a+b) where a is
taken from A and b is taken from B. such that k < m*n
有O(n)的解么？怎么转化成杨矩啊？
谢谢 |
|
f****4
发帖数: 1359 | 31 找到一个对的O(N)的解法
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
This is a pretty good puzzle. You can actually find the cutoff and a
description of exactly which pairs are in the solution in less than O(N)
time, but outputting all the solutions takes O(N) time, so it doesn't help
you overall. This won't be much of a hint, but finding the cutoff point can
be done in O(sqrt(N)*log2N) time. Forgive me for not writing code, but this
gets pretty nitty-gritty in spots.
I think of the pro... 阅读全帖 |
|
f****4
发帖数: 1359 | 32 原帖：http://www.mitbbs.com/article_t/Programming/31198701.html
Two reverse sorted arrays A and B have been given.such that size of A is m
and size of B is n You need to find the k th largest sum (a+b) where a is
taken from A and b is taken from B. such that k < m*n
有O(n)的解么？怎么转化成杨矩啊？
谢谢 |
|
f****4
发帖数: 1359 | 33 找到一个对的O(N)的解法
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
This is a pretty good puzzle. You can actually find the cutoff and a
description of exactly which pairs are in the solution in less than O(N)
time, but outputting all the solutions takes O(N) time, so it doesn't help
you overall. This won't be much of a hint, but finding the cutoff point can
be done in O(sqrt(N)*log2N) time. Forgive me for not writing code, but this
gets pretty nitty-gritty in spots.
I think of the pro... 阅读全帖 |
|
g**********y
发帖数: 14569 | 34 USACO的题是1~N的数字，换成int[] a也差不多。
就是把和/2， 就是目标值。然后用DP计算可以到达x的办法总数，存在dp[]里。
计算的时候，倒序计算，就不需要额外空间。
最后dp[sum/2]就是办法总数，因为对称性，所以除2. |
|
h****e
发帖数: 928 | 35 原题是Minimum Path Sum，只能向右向下走，求从左上角到
右下角的最小路径和。
更改以后的题目是上下左右移动都可以，还是求从左上角到
右下角的最小路径和。 |
|
e***s
发帖数: 799 | 36 Given a collection of candidate numbers (C) and a target number (T), find
all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … ,ak) must be in non-descending order.
(ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set i... 阅读全帖 |
|
y****u
发帖数: 11 | 37 add
if (l[i] > sum):
break;
to the loop. |
|
e***s
发帖数: 799 | 38 Given a collection of candidate numbers (C) and a target number (T), find
all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … ,ak) must be in non-descending order.
(ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set i... 阅读全帖 |
|
y****u
发帖数: 11 | 39 add
if (l[i] > sum):
break;
to the loop. |
|
t*****e
发帖数: 53 | 40 Can we design an algorithm that can find the triplet in an unsorted array (
including both positive and negative numbers) that sum up to a defined
number? Requirement: the runtime should be o(nlogn).
I can think about alot of O(n^2) way. Do you think this problem has a
solution with O(nlogn).
thanks in advance. |
|
j******2
发帖数: 362 | 41 又看了看好像重复调用的次数很少，sum越大越少，不知是否因此忽略考虑DP，直接用
递归。 |
|
d*********g
发帖数: 154 | 42 How to find maximum path sum in a binary tree.
The path need not be a top-bottom, can start and end nodes need not be root
or leaf, path can start in left/right subtree and end in right/left subtree
wrt any node.
Careercup上看到的，感觉里面没有正确的解答。求版里大神指教。题目里如果没有最
后一句话就好办了，加上最后那句话感觉好复杂。 |
|
l*********8
发帖数: 4642 | 43 我之前也问了这个问题。
Flexme的程序（和我修改的程序）在这种情况下返回empty path, sum为0.
如果不允许empty path, 那么程序要略作修改，要多加几句。 |
|
m*******1
发帖数: 77 | 44 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.
leetcode 上面的一道题，求大神们解释啊 |
|
D**f
发帖数: 439 | 45 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. |
|
b***m
发帖数: 5987 | 46 二爷的解法应该是对的，任何子树max为负就不计入。这题应该算是一维数组求最大sum
的变种吧？ |
|
r*****e
发帖数: 146 | 47 Given a binary tree, find a pair of nodes whose sum is the given target
value. Find all solutions.
Any idea to use as space as possible? thanks! :) |
|
p*****2
发帖数: 21240 | 48 two sum.
两个指针一个从前往后，一个从后往前。
实现两个函数，getnext和getprev |
|
h****n
发帖数: 1093 | 49 traverse之后不就变成2 sum problem了么
呵呵
如果是BST连sort这一步都不用了
题目有什么要求吗？空间时间方面？ |
|
|
