k****r
发帖数: 807 | 1 谢谢ls的回复，我确实应该再好好看看java书。
by value，
所以说，第一段代码里的 sum = sum + newone;就不可会把改变了的sum值带到调用这
次recursion之外了吗？
如果是这样，我记得之前自己写了一个List>为入参的一个例子，好像
用的 add（）可以带出来，不知道怎么回事。 |
|
|
H******7
发帖数: 1728 | 3 public List> fourSum(int[] num, int target) {
ArrayList> ans = new ArrayList<>();
if(num.length<4)return ans;
Arrays.sort(num);
for(int i=0; i
if(i>0&&num[i]==num[i-1])continue;
for(int j=i+1; j
if(j>i+1&&num[j]==num[j-1])continue;
int low=j+1, high=num.length-1;
while(low
int sum=num[i]+num[j]+n... 阅读全帖 |
|
发帖数: 1 | 4 https://leetcode.com/problems/combination-sum/description/
半路出家的遇到这种题目就搞不定时间空间复杂度分析了。
我的code:
class Solution(object):
def combinationSum(self, candidates, target):
if not candidates:
return []
res=[]
self.dfs(res,candidates,target,[])
return res
def dfs(self,res,candidates,target,curr):
if sum(curr)==target:
res.append(curr)
return
if sum(curr)>target:
return
for i in range(len(candida... 阅读全帖 |
|
d**4
发帖数: 217 | 5 Dragon Gourmet Buffet中南海
1091 S University Dr
Plantation, FL 33324
Weekend Brunch has some Dim Sum items and good value
Toa Toa Chinese Restaurant陶陶居
4145 NW 88th Ave
Sunrise, FL 33351
Dim Sums ordered from a menu on weekends
China Pavilion 新醉琼楼酒家
270 S Flamingo Rd
Pembroke Pines, FL 33027
personally if I have the urge I will go to
Kon Chau Restaurant广州酒家
8376 SW 40th St
Miami, FL 33155
Been to a more famous one below, but still I prefer Kon Chau.
Tropical Chinese Restaurant大利饭店
7991 Bird Rd
Mia... 阅读全帖 |
|
b****r
发帖数: 219 | 6 偶的DIM SUM是
玉米小馒头蘸辣酱,加小米稀饭.
或者葱花油饼加海鲜豆腐脑.
或者紫菜黄瓜疙瘩汤.
或者土豆丝饼加甜沫.
或者羊杂散袋加糊辣汤.
或者油炸糕加八宝粥.
或者水煎包加紫菜蛋花汤.
最不济也是油条豆浆.
还有,,,,,,,,,
嘿嘿,偶的山东DIM SUM.
在泰安的时候,学校后边的文化路上,早点铺子那就叫一个多,香味那就叫一个远.....早上
跑操绕着龙潭路到文化路到水专,然后回来到岱宗大街,然后回校园,学校以为累趴的我们
会在食堂吃早饭,NO,我们继续一路小跑,跑回文化路大吃一顿,一直吃到早读预备铃,HIAHI
A.....
豆子MM,你可以讲给你的CANADA小弟弟了.广东茶点之所以名扬四海,是因为香港人在海外
久居,而且喜欢开店.北方人故土情节SO重,很难在外落叶生根.在外的人也很少以开店营生
过活.
偶和偶BF已经讨论过N次说,要在学校门口开个包子铺,准比那些CHNIESE
TAKEAWAY挣钱,HIAHIA,还能把北方食品发扬光大.上回好像把广告口号都准备好了,是什么
,BETTER, TO BE BEST.....好像是老许的主意,嗯?
早
南
不
白 |
|
a****1
发帖数: 61 | 7 sum(logi) >= logn/2 + log(n/2 + 1) + .. + logn
>= n/2 * log(n/2) >= 0.5n * logn - 0.5n * log2
当n大到一定 sum(logi) >= C*n*logn
又有sum(logi) < nlogn (显然) |
|
S*********N
发帖数: 6151 | 8 why sometimes it is below the sum-symbol, sometime it is at right-low
corner of sum-symbol?
I want to put them all under the SUM.
2 baozis for first solution. |
|
|
m***7
发帖数: 4207 | 10 广东人花样繁多的dim sum不假，可那太不健康了。
另外羊肉饺子味道完胜dim sum |
|
a******e
发帖数: 36306 | 11 4400 N Larmar Blvd, Get Sum Dim Sum |
|
t*******1
发帖数: 4965 | 12 挖坑吧你～～，不知道Dim Sum是什么？！
想当初我刚来美国的时候，一句英文都不会，只知道Dim Sum～～～ |
|
m*****f
发帖数: 1243 | 13 常常见到的是给定sum, 找array中的pair, 现在变化一下
Given a list of numbers, A = {a0, a1, ..., an-1}, its pairwise sums P are
defined to be all numbers of the form ai + aj for 0 <= i < j < n. For
example, if
A = {1,2,3,4},
then
P = {1+2, 1+3, 1+4, 2+3, 2+4, 3+4} = {3, 4, 5, 5, 6, 7}.
Now give you P, design an algorithm to find all possible A. |
|
J*****u
发帖数: 30 | 14 用hashtable 的那个貌似是sum为0吧,但是这里sum不为0的,可正,可负. |
|
|
y**i
发帖数: 1112 | 16 我想的就是这样的，两个循环，外层循环是当前检测的subsequence的起始点，内层循
环是终结点，用一个变量max记录目前为止最大的sum，用另一个变量index记录上一个
检测的increasing subsequence的终结点，如果当前的内循环变量所指的元素大于变量
index所指元素，那么就更新increasing subsequence的终结点并把其于max的和跟max
比较及更新max。对这应该是DP思想，因为记录了检测过的increasing sequence的最大
和，而不是把所以的increasing subsequence先全部找出来再求和比较，那样确实是2^
n。
不过这个DP应该不需要额外O(n)空间，因为我们只要记录最大就可以了对吧，没必要记录所有的sum |
|
Z*****Z
发帖数: 723 | 17 问题是如果内循环变量所指元素小于index所指元素应该如何做呢？
我想的就是这样的，两个循环，外层循环是当前检测的subsequence的起始点，内层循
环是终结点，用一个变量max记录目前为止最大的sum，用另一个变量index记录上一个
检测的increasing subsequence的终结点，如果当前的内循环变量所指的元素大于变量
index所指元素，那么就更新increasing subsequence的终结点并把其于max的和跟max
比较及更新max。对这应该是DP思想，因为记录了检测过的increasing sequence的最大
和，而不是把所以的increasing subsequence先全部找出来再求和比较，那样确实是2^
n。
不过这个DP应该不需要额外O(n)空间，因为我们只要记录最大就可以了对吧，没必要记
录所有的sum |
|
y**i
发帖数: 1112 | 18 我知道了，我想错了，是要记录下所有之前的sum，然后每次从之前的sum中找出最大的
再记录
max
2^ |
|
|
s*****o
发帖数: 1540 | 20 一个经典问题：a vector x of n real numbers. find the max sum found in any
contiguous sub vector。
大家知道，programming pearl的解法是：
maxsofar = 0;
maxendinghere = 0;
for i = [0, n)
maxendinghere = max (maxendinghere + x[i], 0);
maxsofar = max (maxsofar, maxendinghere);
我改动一下，要输出究竟是那个sub vector，请大侠指教是不是正确。
public class MaxSubVector {
static public void findBigestSum(double[] x)
{
double maxsofar = 0;
double maxendinghere = 0;
int maxsofarlow = -1;
int maxso... 阅读全帖 |
|
J*****u
发帖数: 30 | 21 给定一个array,问minimum sub-array的和与sum value相等.array里可能有正数,负数
和0,sum value也有可能是正负和
0.谢谢! |
|
e*****e
发帖数: 1275 | 22 不是这样的。。。。
a1, a2, a3...an
先算 sum
a1, a1+a2,a1+a2+a3,....sum(an)
as
b1, b2, b3....bn
连续的和就是bi-bj = target
i-j 最小~~
然后把target + bj(j=0,...n) 放进hash
然后每个b,就在hash里面找~~~
所以应该是O(n)
不知道对不对~~请大牛指正~~~ |
|
j**y
发帖数: 462 | 23 Find a pair of numbers that sums up to zero (or any other number), then
find three (and then four) numbers that sum up to zero
有什么好的方法？ 多谢 |
|
f******n
发帖数: 279 | 24 问一道面试题：
int array a[n] with all element 0<=a[i]<=1000,find the subarray with
the largest sum that is <= max and output the starting and ending index of
this subarray and the sum. If there is more than one such subarray ,
output the one with smallest starting index.
请问这个算最快？ |
|
d***d
发帖数: 99 | 25 一道大公司诡异的complete binary tree max sum of 2 nodes 题
当场 40min white board 给出了O(N2) 的解法，对方表示赞许，但是没时间optimize
了。直觉告诉我应该有NlogN的解法。大牛指点下。
具体如下：
given one complete binary tree, with positive and identical values in all
nodes.
Find 2 nodes, such that:
sum of their path nodes to root (identical nodes will count only once) are maximum. |
|
j********x
发帖数: 2330 | 26 find all n(n-1)/2 combinations of two numbers, put them into a hash-table.
Now look for two number in this hash-table that sums equal to k.
We can always follow such pattern, if we are asked to find m numbers that
sum up equals to k, can be solved using hash-table with
O(n^ceil(m/2)) time and space complexity |
|
f****4
发帖数: 1359 | 27 没仔细看，不过你想维护2个索引来找第k大sum是不对的
楼上有说，第k大sum的可能对象是线性增加的
b |
|
s******o
发帖数: 2233 | 28 第四版的4.8：
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.
书上的解法貌似只考虑root左边或者右边subtree里的path，比如下面这个找sum=6的就
找不出来，
2
1 3
想确认一下我的理解对不对。如果需要考虑这种情况有什么简洁点的做法？ |
|
f*********m
发帖数: 726 | 29 题目如下，求code。非常感谢。
Combination Sum II
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 s... 阅读全帖 |
|
j********g
发帖数: 244 | 30 Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top
left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
就是这道题，用DP解很简单。但是要维持一个M*N矩阵.
被要求expected time O(M*N), space O(M+N)
请问这个space怎么做到啊。。。。谢啦 |
|
f****e
发帖数: 34 | 31 你的标题中BST有误... 这题是G家面我的题....
用f[i]表示根节点为i的子树种的max path sum.
那么
f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i])
其中w[i]表示i节点的权重，g[x]表示从节点x，只能往下走，能够走出的最大的path
sum.
代码也很好些
int solve(TreeNode *root, int &g) {
if (!root) {
g = 0;
return 0;
}
int f = 0;
int leftG = 0, rightG = 0;
if (root->left) f = max(f, solve(root->left, leftG));
if (root->right) f = max(f, solve(root->right, rightG);
f = max(f, leftG + rightG + root->val);
g = root->val +... 阅读全帖 |
|
l*********8
发帖数: 4642 | 32 如果每个node的值都是负数，maximum sum path是个empty path（sum是0）吗？ |
|
f****e
发帖数: 34 | 33 看这个式子：
f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i])
leftG就是g[left[i]], rightG就是g[right[i]]
思路就是当考虑根节点为i的子树的max path sum是，有3种情况：
1. path不经过根节点，那么它要么完全在左子树中，要么完全在右子树中
a。 如果完全在左子树中，那么就是f[left[i]]
b。如果完全在右子树中，那么就是f[right[i]]
2.如果path经过根结点，那么答案就是g[left[i]]+g[right[i]]+w[i]
g[left[i]]表示从i的左结点开始，一直往下走，能够达到的max sum
g[right[i]]类似 |
|
e******o
发帖数: 757 | 34 I think it is similar to combination sum I.
sort the array first.
in combination sum I, you can use a number unlimited times.
but in II, if a number appears n times, then you can use it at most n times
. |
|
e******o
发帖数: 757 | 35 I think it is similar to combination sum I.
sort the array first.
in combination sum I, you can use a number unlimited times.
but in II, if a number appears n times, then you can use it at most n times
. |
|
i******e
发帖数: 273 | 36 20
/ \
-3 -5
/ \
3 8
/ \ \
-2 -1 10
/ /
6 -7
这个test case的max path sum 应该是20-> -3 -> 8 -> 10 (sum = 35).
按照你的程序
在根节点 20： maxSum = max(max(helper(-3, leftG), helpfer(-5， rightG)， 20
+ leftG + rightG);
因为leftG包含了以结点3为子树根节点的一条路径（6 -> -1 -> 3 -> -3 -> 8 -> 10
）. 这条路径不能和根节点20一起构成一条新的路径. 所以得出的解是最大和（20 +
23 = 43）， 但是却不是一条有效路径。
请大家帮忙看一下是不是我哪算的有问题？ 谢谢。 |
|
c********t
发帖数: 5706 | 37 在int matrix上求最大submatrix sum。
我在想对一维arr, 求最大连续sum, 有linear解法。
为什么2D似乎只有O(N^3)的解法？ |
|
c*******r
发帖数: 309 | 38 给一个array 都是 positive， 给一个 sum， 输出所有的 subarray 加和是 sum
这题应该咋解？ 用recursion?准备了小半年发现水平依然是菜比。。 |
|
P*******y
发帖数: 168 | 39 w...lab
是three sum，不是two sum |
|
c********p
发帖数: 1969 | 40 以前在本版看过，这2天写sum的那几个题，2 sum , 3sum什么的想起来了。
就是说，一组数，给个target值，不管你用几个（1个也行），只要和等于这个数就可
以。好像元素不能重复利用？。。。
返回所有这样的subset。
怎么做阿？
当初我看到的时候就蒙了。。。现在还是不会。。。 |
|
H*****l
发帖数: 1257 | 41 我用类似3 sum的方法，是O（n^3)的复杂度，但是过不了large judge，超时；
看到帖子说可以用hash table做到O（n^2）的复杂度，能不能具体说下算法？
题目如下：
Given an array S of n integers, are there elements a, b, c, and d in S such
that a + b + c + d = target? Find all unique quadruplets in the array which
gives the sum of target.
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ?
b ? c ? d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A soluti... 阅读全帖 |
|
p****n
发帖数: 4 | 42 Get the Sum of 对角线 of 螺旋（线) in n X n
Starting with the number 1 and moving to the right in a counter-clockwise
direction a 5 by 5 .
The issue is that the 1 is in the middle.
Normally:
for example :螺旋（线) (3X3)
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
[leetcode]Spiral Matrix II
(2013-03-12 15:14:57)
转载▼
标签：
分类： leetcode
Given an integer n, generate a square matrix filled with elements from 1 to
n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8,... 阅读全帖 |
|
c***0
发帖数: 449 | 43 我一直不明白为什么要先全扫一遍再找，为什么不能先判断sum-a[i]存在不存在，如果
存在就找到了，如果不存在就是找不到，不就解决了？
for each i in a
{
if sum-a[i] exist in hash
found
else
not found
hash insert a[i]
}
这样不是边扫边找嘛。 |
|
x*******i
发帖数: 26 | 44 给一个array of int，以及一个range (low, high)，找出array中
所有的subarray使得这个subarray的和在range之中。array可以有负数
这个O(N^2),
for i= 0 to N,
for j= i to N
check sum(i, j) is in range. // add num[j] to previous sum(i, j-1)
有更好的方法吗？ |
|
b******g
发帖数: 3616 | 45 不必用set。
假设A[i] = A[i+1] = A[i+2] = x != A[i+3]。
在A[i]的时候解2 sum问题以后，已经把包含一个x，两个x和三个x的解都考察过了。所
以下一步移动时直接移动到A[i+3]来解2 sum问题就行了。 |
|
b*****n
发帖数: 618 | 46 又想了一下，其实是有O(N)的解的。
先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
，并且要j - i的值最大。
所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
举个例子，如果b = [5, 4, 2, 8, 3, 7]
那么i的可能其实只有index 0,1,2,
j的可能其实只有index 3,5
然后用两个pointer分别从这两个序列的尾部开始往前移动就可以了，时间复杂度整体
上是O(N)因为上面每一步都是O(N) |
|
|
a*w
发帖数: 4495 | 48 水从地面渗到sum pump那个孔里需要一段时间，连绵的小雨比短时间的
暴雨对sum pump影响更大。 |
|
s**o
发帖数: 256 | 49 可是我的同事家里,离我家不是很远，每几个小时就要手动把水勺出来，倒出去，差不
多的下雨强度。难道是不同sum pump的工作原理不同，有的sum pump会自动排水吗？我
对这个百思不得其解，望高手赐教！ |
|
g*****i
发帖数: 9630 | 50 不是啊，来人检查过，没问题，查过最近几年的bill，也不高。都很正常。
应该也不是其他家自来水，否则不会好几年都查不出来。
反正能查的都查了，我去把sum pump停了会，不下雨，水位也不会涨。所以我觉得是打
在泉眼上了。回头院子里修个瀑布吧，弄个过滤水的系统，呵呵，我家都不用买水了。
关键本地虽然不算缺水，但小区离河或者湖也都几十miles了，只有个小区的人工湖不
远，我估计我家的sum pump都能供得上小区人工湖的蒸发、渗漏了。 |
|
