一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 6599|回复: 35
收起左侧

[Leetcode] Count of Range Sum这道题都读不懂题……

[复制链接] |试试Instant~ |关注本帖
yuanb10 发表于 2016-1-10 11:52:09 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚刚放出来的这个题目,到底是什么意思啊,完全看不懂要哭了……
https://leetcode.com/problems/count-of-range-sum/

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.



dietpepsi 发表于 2016-1-15 05:36:50 | 显示全部楼层
楼主莫慌,题是我出的,可能是我英语太差了

题意很简单,就是给你一个数组,求数组的所有子数组和(sub array sum)在区间[lower, upper]之内的个数

题解我blog上有~,用的Merge Sort,边排序边数出来

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

163 发表于 2016-1-11 02:34:50 | 显示全部楼层
我感觉可以用Fenwick Tree做,或者线段树,或者带node count的BST。不知道有没有其他更巧妙的解法?
大概方法是这样:首先用dp计算 sum(0, i),这个是 O(n)
然后对于一个index j,关键就是想知道选择哪些 i 能够使得 sum(0,j) - sum(0, i-1)落在给定的range内
这等价于求之前的sum(0, i-1)落在某个range内的那些i,
可以用Fenwick Tree转化成求count的问题。最终复杂度就是 O(n log (n))了
回复 支持 1 反对 0

使用道具 举报

163 发表于 2016-1-11 06:31:06 | 显示全部楼层
关于 Fenwick Tree, 推荐大家看一下这篇介绍:
http://www.hrwhisper.me/binary-indexed-tree-fenwick-tree/

严格来说这不是个 “Tree”, 是一个树状的数组,index之间的移动的关系主要是根据最低位的1来定的,这个数据结构简洁巧妙。适合处理range类的问题。
回复 支持 1 反对 0

使用道具 举报

yiliaobailiao 发表于 2016-1-10 12:40:47 | 显示全部楼层
求有多少个连续区间,满足,区间内的数的和大于等于lower,并且小于等于upper
回复 支持 反对

使用道具 举报

samparly 发表于 2016-1-10 12:44:05 | 显示全部楼层
Let's see the example first:
[-2,5,-1], and its indices i, j should meet the requirement: i<= j, then we could get the following sequences:
[0,0],[0,1],[0,2],[1,1],[1,2],[2,2].
Notice that sum(i,j) is defined as the sum of the elements in the array between i and j, so write down each result in the above interval:
[0,0]=-2
[0,1]=3
[0,2]=2
[1,1]=5
[1,2]=4
[2,2]=-1
Then we should count the total numbers of range which should locate between lower and upper, here we use lower=-2 and upper=2, count the above numbers that meet this requirement, and we get 3 finally(-2, -1, 2)
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-1-11 01:44:38 | 显示全部楼层
I can understand the meaning of title, but I still can not work it out. What a shame
回复 支持 反对

使用道具 举报

163 发表于 2016-1-11 05:25:52 | 显示全部楼层
Fenwick Tree 已过。不过leetcode又来了一个恶心的test case,里面有 -2147483648 这种东西。。我用int的时候又over flow了。。改成long才pass的。
回复 支持 反对

使用道具 举报

yiliaobailiao 发表于 2016-1-11 06:04:43 | 显示全部楼层
163 发表于 2016-1-11 05:25
Fenwick Tree 已过。不过leetcode又来了一个恶心的test case,里面有 -2147483648 这种东西。。我用int的时 ...

厉害!厉害!学习了
回复 支持 反对

使用道具 举报

coolguy 发表于 2016-1-11 07:50:30 | 显示全部楼层
抛砖引玉

  1.     public class Solution {
  2.         SegmentTreeNode root = null;

  3.         public SegmentTreeNode buildTree(long[] nums, int left, int right) {
  4.             if (left > right) return null;

  5.             SegmentTreeNode p = new SegmentTreeNode(nums[left], nums[right]);
  6.             if (left == right) return p;

  7.             int mid = left + (right - left) / 2;
  8.             p.left = buildTree(nums, left, mid);
  9.             p.right = buildTree(nums, mid + 1, right);
  10.             return p;
  11.         }

  12.         public void update(SegmentTreeNode node, long key) {
  13.             if (node != null && node.start <= key && node.end >= key) {
  14.                 node.val++;
  15.                 update(node.left, key);
  16.                 update(node.right, key);
  17.             }
  18.         }

  19.         public int count(SegmentTreeNode node, long low, long high) {
  20.             if (node == null || node.start > high || node.end < low) return 0;
  21.             if (node.start >= low && node.end <= high) return node.val;
  22.             return count(node.left, low, high) + count(node.right, low, high);
  23.         }

  24.         public int countRangeSum(int[] nums, int lower, int upper) {
  25.             int rslt = 0;
  26.             int n = nums.length;
  27.             if (n <= 0) return rslt;

  28.             long[] sum_array = new long[n];
  29.             sum_array[0] = nums[0];
  30.             for (int i = 1; i < n; i++) {
  31.                 sum_array[i] = nums[i] + sum_array[i - 1];
  32.             }
  33.             long sum = sum_array[n - 1];
  34.             Arrays.sort(sum_array);
  35.             int unique = 1;
  36.             for (int j=1; j<n; j++ ) {
  37.                 if (sum_array[j] != sum_array[j-1]) {
  38.                     sum_array[unique] = sum_array[j];
  39.                     unique++;
  40.                 }
  41.             }
  42.             root = buildTree(sum_array, 0, unique - 1);

  43.             for (int i = n - 1; i >= 0; i--) {
  44.                 update(root, sum);
  45.                 sum -= nums[i];
  46.                 rslt += count(root, lower + sum, upper + sum);
  47.             }

  48.             return rslt;
  49.         }

  50.         public class SegmentTreeNode {
  51.             int val;
  52.             long start;
  53.             long end;
  54.             SegmentTreeNode left;
  55.             SegmentTreeNode right;

  56.             public SegmentTreeNode(long start, long end) {
  57.                 this.val = 0;
  58.                 this.start = start;
  59.                 this.end = end;
  60.                 this.left = null;
  61.                 this.right = null;
  62.             }
  63.         }
  64.     }
复制代码
回复 支持 反对

使用道具 举报

lrn0304 发表于 2016-1-11 08:30:15 | 显示全部楼层
就是求区间和, 然后最后和要在那个要求区间内.
回复 支持 反对

使用道具 举报

yanzigui 发表于 2016-1-11 09:02:22 | 显示全部楼层
本帖最后由 yanzigui 于 2016-1-11 09:04 编辑

hrwhisper.me/leetcode-count-of-range-sum/
google一下发现有题解了
回复 支持 反对

使用道具 举报

yanzigui 发表于 2016-1-11 22:27:18 | 显示全部楼层
yanzigui 发表于 2016-1-11 09:02
hrwhisper.me/leetcode-count-of-range-sum/
google一下发现有题解了

我也过了, lower ≤ sum[j] – sum[i – 1] ≤ upper得到 lower + sum[i – 1] ≤ sum[j] ≤ upper + sum[i – 1] ,然后用线段树或者Fenwick Tree查询。
代码和这个差不多
http://www.hrwhisper.me/leetcode-count-of-range-sum/
回复 支持 反对

使用道具 举报

haoxuango 发表于 2016-1-15 05:55:53 | 显示全部楼层
dietpepsi 发表于 2016-1-15 05:36
楼主莫慌,题是我出的,可能是我英语太差了

题意很简单,就是给你一个数组,求数组的所有子数 ...

发现你id和leetcode一样呢 你的blog用什么建的 感觉很整洁
回复 支持 反对

使用道具 举报

163 发表于 2016-1-15 06:06:35 | 显示全部楼层
dietpepsi 发表于 2016-1-15 05:36
楼主莫慌,题是我出的,可能是我英语太差了

题意很简单,就是给你一个数组,求数组的所有子数 ...

我擦。膜大神!!!
原来是个同胞,厉害呀!
我在leetcode上做了你好多题,感觉出的都蛮有档次的!
回复 支持 反对

使用道具 举报

163 发表于 2016-1-15 06:08:34 | 显示全部楼层
dietpepsi 发表于 2016-1-15 05:36
楼主莫慌,题是我出的,可能是我英语太差了

题意很简单,就是给你一个数组,求数组的所有子数 ...

另外你能回复一下你blog的地址吗?我还不知道这个题还能用merge sort做呢,学习一下!
回复 支持 反对

使用道具 举报

stellari 发表于 2016-1-15 09:25:22 | 显示全部楼层
dietpepsi 发表于 2016-1-15 05:36
楼主莫慌,题是我出的,可能是我英语太差了

题意很简单,就是给你一个数组,求数组的所有子数 ...

赞大神。出的题和提供的解法质量都相当高啊。
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-15 11:00:09 | 显示全部楼层
163 发表于 2016-1-15 06:08
另外你能回复一下你blog的地址吗?我还不知道这个题还能用merge sort做呢,学习一下!

等级不够不能发链接啊,你可以去看leetcode的discuss,最多投票那个帖子就是我的解法,里面也有我blog链接

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-15 11:04:18 | 显示全部楼层
stellari 发表于 2016-1-15 09:25
赞大神。出的题和提供的解法质量都相当高啊。

stellari才是大神!
最近少见你去LeetCode发解法了,原来在地里~
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-15 11:05:53 | 显示全部楼层
haoxuango 发表于 2016-1-15 05:55
发现你id和leetcode一样呢 你的blog用什么建的 感觉很整洁

blog是用wordpress啊
主题抄的hrwhisper,叫dazzling

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 06:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表