算法@LeetCode:RangeSumQuery-Immuta

Log

• 【170424】完成 01 版（Python）提交
• 【170501】研究参考答案，并补充笔记

题目

Range Sum Query - Immutable

【题目类型备注】

动态规划

提交

01

【语言】

Python

【时间】

170424

【思路】

不复杂的 DP 题。常规思路是每次从 i 遍历到 j 求得其和，但其实只要另外构造一个表，记录子问题的和，总问题就可以由这个表求得解。这就是 DP 解法的思路。

DP 的思路极其简单：要求 i 到 j 的和，只要先求出 0 到数组任意下标 k 的和 sumTo[k]，此后，所求答案就是 sumTo[j] - sumTo[i-1]。

特殊情况是：考虑输入数组过短时如何处理。

【代码】

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        if len(nums) <= 1:
            self.sumTo = nums
        else:
            self.sumTo = [nums[0]] # sumTo[k] means sum from 0 to k(inclusive, k >= 0)
        if len(nums) >= 2:
          for i in range(1, len(nums)):
            self.sumTo.append(self.sumTo[i-1] + nums[i])

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if 0 == i:
            result = self.sumTo[j]
        else:
            result = self.sumTo[j] - self.sumTo[i-1]
        return result


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

【结果】

运行时：76 ms

报告链接：https://leetcode.com/submissions/detail/101068540/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 82.88% of python submissions.

00

参考解法：

• Python
  • 最大的启发就是发现了类似以前类 C 语言中的三元运算符 : 的写法！对应就是：
    • 类 C 中：(statement)?true_answer:false_answer
    • Python 中：true_answer if (statemnt) else false_answer
• Java
  • 1
  • 2
• C++
  • 和 STL 中的 partial_sum 函数有关，见这里

自己实现一遍最优解：

• [language]。。。