h****n
发帖数: 1093 | 1 给一个巨大的二维平面 横纵坐标无限 给定一个坐标点写一个add value函数 和求给定
一个四边形范围内的所有value的和 get sum 函数
不能用二维数组存因为是无限的平面 要求add value和get sum尽量高效 | j*****l
发帖数: 1624 | | h****n
发帖数: 1093 | 3 binary index tree我只知道二维数组的那种写法 怎么用hashmap来写？
面试那么短时间现想真的太难了
【在 j*****l 的大作中提到】
: 不是新题，2D range sum -- mutable.
: 用2D Binary indexed tree.
: https://www.topcoder.com/community/data-science/data-science-tutorials/
: binary-indexed-trees/
: https://www.youtube.com/watch?v=CWDQJGaN1gY
: https://leetcode.com/problems/range-sum-query-2d-mutable/
: https://leetcode.com/discuss/71169/java-2d-binary-indexed-tree-solution-
: clean-and-short-17ms
: 不许用2D数组那就用哈希表，key是坐标，value是值。
: 当然也有用quadtree的。但quadtree一般是考map的时候考吧。
| j*****l
发帖数: 1624 | 4 当然了，如果是有限的比如有个size，我喜欢把点(i,j)存成i*size+j什么的，转换成
整数。
但是如果非要是搞成无穷，那自己想个哈希函数就行了。用上个short url什么的的解
法。 | h****n
发帖数: 1093 | 5 大牛写一个看看 ...
没code不好理解你怎么用hashmap写索引树
【在 j*****l 的大作中提到】
: 当然了，如果是有限的比如有个size，我喜欢把点(i,j)存成i*size+j什么的，转换成
: 整数。
: 但是如果非要是搞成无穷，那自己想个哈希函数就行了。用上个short url什么的的解
: 法。
| j*****l
发帖数: 1624 | 6 你不是说给了坐标点和value?
他非说无穷，你就想，已经给了的坐标点怎么弄成无穷？
所以就记个当前最大值吧。maxRow, maxCol, 总能看成当前的极限吧。要是以后再新给
，咱在扩展就行了吧。
比如说
public void update(int row, int col, int val) {
if (maxRow == 0 || maxCol == 0) return;
hash_val=hash_func(row,col);
int delta = val - nums_hashtable[hash_val];
nums_hashtable[hash_val] = val;
for (int i = row + 1; i <= maxRow; i += i & (-i)) {
for (int j = col + 1; j <=maxCol; j += j & (-j)) {
ij_hash_val=hash_func(i,j);
tree_hashtable[ij_hash_val] += delta;
}
}
}
hash_func太复杂不写了。反正方法有很多种。 | h***d
发帖数: 6 | 7 row = -1, col = -1, 你这code怎么办？
【在 j*****l 的大作中提到】
: 你不是说给了坐标点和value?
: 他非说无穷，你就想，已经给了的坐标点怎么弄成无穷？
: 所以就记个当前最大值吧。maxRow, maxCol, 总能看成当前的极限吧。要是以后再新给
: ，咱在扩展就行了吧。
: 比如说
: public void update(int row, int col, int val) {
: if (maxRow == 0 || maxCol == 0) return;
: hash_val=hash_func(row,col);
: int delta = val - nums_hashtable[hash_val];
: nums_hashtable[hash_val] = val;
| l**g
发帖数: 133 | 8 我和楼主一样有一道类似题目，不过并不是计算给定区间，而是计算sum (0,0) -> (x,
y) 内所有点的value，而且对方没让我写代码，只是一个open ended discussion:
1. insertion > query
2. query > insertion
3. insertion = query
segmented tree现在看到才有点印象，当时一点也没想起来，我第一步就是直接按X排
序，然后按Y排序，然后可以query出来点，进行sum；后来多想了一个按照每个点预计
算总和，但没想到二分或者四分，对方也没有多问下去。。
后来又问了一道关于string的coding，给定string和一个整数m，计算最长的substring
里面包含最多m个字母：比如aabccdd, m=2 => ccdd
还是复习不到位，做题不够啊。。 | t**n
发帖数: 272 | | E********e
发帖数: 63 | 10
x,
substring
这个为什么会有insert？
{{1 ,1},
{1, 1}}
sum((0,0) -> (1,1)) = 4
是这个意思么
【在 l**g 的大作中提到】
: 我和楼主一样有一道类似题目，不过并不是计算给定区间，而是计算sum (0,0) -> (x,
: y) 内所有点的value，而且对方没让我写代码，只是一个open ended discussion:
: 1. insertion > query
: 2. query > insertion
: 3. insertion = query
: segmented tree现在看到才有点印象，当时一点也没想起来，我第一步就是直接按X排
: 序，然后按Y排序，然后可以query出来点，进行sum；后来多想了一个按照每个点预计
: 算总和，但没想到二分或者四分，对方也没有多问下去。。
: 后来又问了一道关于string的coding，给定string和一个整数m，计算最长的substring
: 里面包含最多m个字母：比如aabccdd, m=2 => ccdd
| l**g
发帖数: 133 | 11
每个点有一个value (1,1) = 2, (1,2) = 1, (3,3) =2, 那么sum(0,0 -> 2,2) => 3
【在 E********e 的大作中提到】
:
: x,
: substring
: 这个为什么会有insert？
: {{1 ,1},
: {1, 1}}
: sum((0,0) -> (1,1)) = 4
: 是这个意思么
| z*********n
发帖数: 1451 | 12
这题确实应该是kd tree一个典型应用，但是如果自己对如何实现kd tree不熟，不敢乱
说啊，万一让实现一个，搞不出来就挂了。
我以前有个同学就是面试时扯了一下平衡二叉树，然后人家就问你知道哪些平衡二叉树
，他就说了AVL和RBTree，然后对面说，那你随便实现一个我看看吧，然后。。就没有
然后了。。
【在 t**n 的大作中提到】
: 这难道不是kd tree?
| c******3
发帖数: 6509 | 13 有四边形坐标了，直接过滤范围内的数据，然后求和就行了吧 |
|
