n****r
发帖数: 120 | 1 Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
这道题咋解呢？每个节点DFS？ |
|
z********i
发帖数: 568 | 2 150有一题是finding all paths which sum up to a given value.
给出来的解法是O(nlogn)。可是感觉解法中的path没有考虑说有的path,只考虑了从上
到下的path.
For example,
5
3 6
4 9 7 8
3+5+6=14这样的path没有考虑进去。 |
|
c***a
发帖数: 32 | 3 比如lum sum payment是5000，是不是就是公司给5000，然后自己用这5000块搞定
relocation？
thx |
|
j*****o
发帖数: 394 | 4 我的理解就是一次性付你一张支票
与之相对应的是另一种：
你可以用搬家公司，报销上限是多少之类的的
比如你可以报销上限到1W
如果你选择lump sum payment,你可能能之前就收到一张7000块的check |
|
t*******e
发帖数: 274 | 5 有没有java solution么？下面的代码是combination sum的，怎么在这个基础上改呢？
public class Solution {
public ArrayList> combinationSum(int[] candidates,
int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> results = new ArrayList
Integer>>();
Arrays.sort(candidates);
addUp(candidates, 0, target, new ArrayList(), results);
return results;
}
private void addUp(i... 阅读全帖 |
|
a****x
发帖数: 89 | 6 网上搜到的都没有考虑negative的情况，比如一个tree只有一个node，这个node的值
是negative。
下面是我自己的答案，已经pass OJ：
class LocalResult
{
int localMaxPathSum; // local max path sum
int localSubPathSum; // either root, or root+left, or root+right
public LocalResult(int maxPathSum, int subPathSum)
{
this.localMaxPathSum = maxPathSum;
this.localSubPathSum = subPathSum;
}
}
public class binaryTreeMaxPathSum {
/**
* @param args
*/
public static void main(String[] args) {
/... 阅读全帖 |
|
f*****7
发帖数: 92 | 7 这才是divide-and-conquer啊
一条path，可能全在左子树，可能全在右子树，也可能跨过root
跨过root的path，就有四种情况。
我这么写，每个子树的sum都是一条从子树的root开始的path，这样和root相连成一条
path。
你这么后序递归走几步，就发现leftSum和rightSum是root的“两条腿” |
|
r*****e
发帖数: 146 | 8 Given n arrays, find n number such that sum of their differences is minimum.
For e.g. if there are three arrays
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here
the answer is a = 15, b = 13, and c = 14.
It seems an old question. Any idea would be appreciated. Thanks! :) |
|
r*****e
发帖数: 146 | 9 不会啊，上来请教一下。
Given an unsorted array, how to divide them into two equal arrays whose
difference of sum is minimum in O(n) time? |
|
c*****a
发帖数: 808 | 10 leetcode的Combination Sum?
cc150的硬币题? |
|
|
b******7
发帖数: 92 | 12 面试中有可能会问到啊，我就被问过merge-sort的非递归。
类似的有quick-sort,path sum, is balance tree。就这个感觉最难，很容易被里面的
逻辑搞晕
而且递归算法只能描述算法思想，实际工程中感觉不适用，还得用stack转非递归 |
|
c****m
发帖数: 179 | 13 楼上的没考虑key为负数的情况吧。应该判断sum是否比min(0, KEY)小？ |
|
|
h***i
发帖数: 1970 | 15 partition的时候可以顺便把两部分的sum算出来，如果后面的小于key，需要在前面再
找，否则就在后面找。 |
|
c*****a
发帖数: 808 | 16 dfs 啊
leetcode 的 combination sum 2啊 |
|
j********x
发帖数: 2330 | 17 双指针的窗口移动，考虑全是正数，这应该是最直观的解法
subarray和一类的题目可以考虑用prefix array sum的方法在常数时间内求得，这个方
法在很多跟array matrix有关的题目里都用得上
楼上几位能介绍一下dfs怎么做么？ |
|
r**h
发帖数: 1288 | 18 题目不要求subarray是连续的吧
DFS，就是根据每个节点（取或者不取）两种情况向后搜索并记录当前的解。由于题目
里面提到数组中所有元素都是正数，因此如果当前的和已经大于sum那么就可以直接剪枝
void findSubSetSum(int *pArr, int *pSub, int nSize, int nIndex, int curSum,
int nSum){
//剪枝
if(curSum+pArr[nIndex] > nSum)
return;
//找到解
if(curSum+pArr[nIndex] == nSum){
pSub[nIndex] = 1;
printResult(pArr, pSub, nIndex);
pSub[nIndex] = 0;
return;
}
//继续向后搜索，分两种情况
if(nIndex < nSize-1){
pSub[nIndex] = 1;
findSubSetSum(pArr, pSub, nSize, nIndex+1, curSum+pArr[nIndex... 阅读全帖 |
|
d**********x
发帖数: 4083 | 19 你就是被忽悠了
算法分析课上说了，我们至今不知道k-sum有没有优于O(n^(k-1))的解。。 |
|
|
a******3
发帖数: 113 | 21 楼主这个是不是时间超时？ two sum有O(n)的解法。 |
|
|
c********w
发帖数: 2438 | 23 leetcode上的combination sum I&II
dfs就行 |
|
n********r
发帖数: 719 | 24 哪个更划算些？
我个人具体情况是夫妻两人，从东岸到西岸，一直租房住，没什么大件家具，基本上是
衣服，杂物，书，一张床可要可不要，车不运，没宠物
如果选前者，我看了下有relocation allowance $2500,外加报销两个人的home
finding trip费用，30天的temporary housing费用，relocation时两个人的单程机票
费用
其他什么报销spouse $2500的settling-in费用，宠物运输费用以及运车费用好像都用
不到
搬家的时候公司找搬家公司所以费用也是自动cover了
如果选lump sum就是公司直接一次性付税后$5000，其它都不管了 |
|
s*******e
发帖数: 1630 | 25 公司给的offer中，relocation可以选择lump sum，说是给一张prepaid card，不用我
提供receipt，可是我搬家可能花不完这张卡，可以用来买家具厨具甚至电脑日用品吗
？会被认为和relocation无关吗？ |
|
m*******1
发帖数: 855 | 26 我LG也是lump sum,不过直接deposite到银行账户....怎么花都行,剩的是自己的 |
|
s*******i
发帖数: 698 | 27 lump sum就是你自己的钱了 跟sign-on一样 |
|
r******o
发帖数: 1851 | 28 lump sum 就是给你的，你随便怎么花都可以，花不完也是你的了 |
|
f****n
发帖数: 1 | 29 O(n^2)两两配对求和，对这些和再做two sum吧 |
|
d*******y
发帖数: 27 | 30 基本上2,3,4-sum都是一个思路吧，用hashmao做一个的索引。我之前做
的时候都是优化一个指数级别就可以过large set了。
import java.util.*;
public class Solution {
public ArrayList> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
HashSet> result = new HashSet>
();
HashMap map = new HashMap();
ArrayList> rtn = new ArrayLis... 阅读全帖 |
|
y*********0
发帖数: 406 | 31 /**
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.
**/
OJ上面的题目。
给的例子，为啥是结果6，而不是4？ 不是说path吗？ |
|
p****n
发帖数: 4 | 32 一道面试题 for a big company in java , the efficiency solution?
25 24 23 22 21
10 9 8 7 20
11 2 1 6 19
12 3 4 5 18
13 14 15 16 17
Starting with the number 1 and moving to the right in a counter-clockwise
direction a 5 by 5 螺旋 is as above, sum the 对角线:
for example 21 + 7 + 1 + 3 + 13 |
|
p****n
发帖数: 4 | 33 The answer(5X5) should be 45.
10 X 10 should be 340.
螺旋矩阵（由内向外, This question also check the way to generate a 螺旋矩阵
（由内向外), move the "point" in related directions and then calculate one
of the 对角线 sum. |
|
c*****t
发帖数: 48 | 34 先排序 O(n)
然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
bin |
|
a**********0
发帖数: 422 | 35 如果扩展到找三个数whose sum 已知 时间复杂度可以做到多少？ |
|
x*******i
发帖数: 26 | 36 有种极限情况，range很大，所有subarray sum都在里面，总数是n^2级别的
这应该是下限吧
★ 发自iPhone App: ChineseWeb 8.2.2 |
|
b****p
发帖数: 216 | 37 一个一个加起来，sum array排序，然后两个指针一个从头一个从屁股扫一下就好了。 |
|
s***5
发帖数: 2136 | 38 如果你算术好点，能吃点苦（不坐飞机自己把车开过去），lump sum还是能省不少钱的。 |
|
j**********m
发帖数: 51 | 39 A non-empty zero-indexed array A consisting of N integers is given.
A pair of integers (P, Q) is calledK-complementary in array A if 0 ≤ P, Q <
N and A[P] + A[Q] = K.
For example, consider array A such that:
A[0] = 1 A[1] = 8 A[2]= -3
A[3] = 0 A[4] = 1 A[5]= 3
A[6] = -2 A[7] = 4 A[8]= 5
The following pairs are 6-complementary in array A: (0,8), (1,6), (4,8), (5,
5), (6,1), (8,0), (8,4).
For instance, the pair (... 阅读全帖 |
|
|
g***j
发帖数: 1275 | 41 为啥不care重复的
比如 0 0 0 0 sum 是 0
你的算法返回哪个？
就行 |
|
o****s
发帖数: 143 | 42 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
- it does not have to start at the root.
这道题的答案有问题吧，没有考虑到过某个节点再回来的情况，比如
5
/
3 7
比如target=15，给出的答案找不到3，5，7这条path啊
还是我理解有问题？谢谢 |
|
|
b******g
发帖数: 3616 | 44 完全不懂java的人表示第一段code貌似是按C++的写法把返回结果放在输入参数的sum里
？但是似乎听说java是pass-by-value。。。。 |
|
z*******3
发帖数: 13709 | 45 list是对象，存的是reference
你这里sum是primitive type |
|
l******i
发帖数: 194 | 46 移动到不相等的呗。。。4 sum我也移动了。。。 |
|
i******t
发帖数: 798 | 47 那 k sum 如何避免duplicate 呢？ |
|
i******t
发帖数: 798 | 48 en多谢指点
假设2sum
是这个意思吗
prei =-10000;
for(int i =0; i
{
if(prei == A[i])
{
continue;
}
prei = a[i];
prej =-10000;
for(int j =i+1; j
{
if(prej == A[j])
{
continue;
}
prej = a[j];
// do sum test....
}
}
是这个意思吧 |
|
l********g
发帖数: 372 | 49 对于k sum, k>=3的，都先用nlogn排序后进行上头说的那样的跳跃法子来进行两指针的
2sum，复杂度应该都是O(n^(k-1))。 2sum本身因为要O(n)了所以无序的大家一般不会
先sort。 |
|
f*****u
发帖数: 308 | 50 k-sum: 给定一个数组A, A中无重复数字,且都是正整数,k,target是某两个给定数,求A
中所有可能的k个数,其和等于target.也就是2sum,3sum,4sum等等的通解. |
|
