数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学Python中定义支持区间和的数据结构的程序
假设我们想开发一种数据结构，它可以用整数列表构建，并且有一个函数可以在需要时高效地查找从索引i到索引j-1的元素之和。有两个函数。
- 构造函数：用整数数组构造一个新实例。
- get_sum(i, j)：返回从起始索引i到结束索引j-1的数组元素的整数之和。
因此，如果输入类似于 array = [5,2,3,6,4,7,8,9,3,2]，则构造一个对象 obj，并调用函数 obj.get_sum(1,5) 和 obj.get_sum(4,8)，则输出将分别为 15 和 28。因为第一个范围的元素是 [2,3,6,4]，所以和是 15；第二个范围的元素是 [4,7,8,9]，这里的和是 28。
为了解决这个问题，我们将遵循以下步骤：
- 定义构造函数。这将接收数组。
- sums := 这是一个列表，最初插入 0。
- 对于数组中的每个 x，执行：
- 在 sums 的末尾插入 (x + (sums 的最后一项))。
- 定义一个函数 get_sum()。这将接收 i, j。
- 返回 sums[j] - sums[i]
示例
让我们看下面的实现来更好地理解：
class RangeSum: def __init__(self, array): self.sums = [0] for x in array: self.sums.append(x + self.sums[-1]) def get_sum(self, i, j): return self.sums[j] - self.sums[i] array = [5,2,3,6,4,7,8,9,3,2] obj = RangeSum(array) print(obj.get_sum(1,5)) print(obj.get_sum(4,8))
输入
[5,2,3,6,4,7,8,9,3,2] obj.get_sum(1,5) obj.get_sum(4,8)
输出
15 28
更新于：2021年10月14日
浏览量：152
广告