算法@LeetCode:ArithmeticSlices

Log

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

题目

Arithmetic Slices

【题目类型备注】

动态规划, 数学

提交

01

【语言】

Python

【时间】

170426

【思路】

首先明确定义：「算术序列」等价于一个长度不小于 3 的等差数列；当这个「算术数列」是一个更大的数列的子数列时，称该子数列为「算术子序列」。

目标是给定一个数列，在其中找到算术子序列的个数。

于是本题可以换一种表述：给定一个数列，找出其中有多少个子数列为等差数列，这些子数列的长度至少是 3。换句话说，若我们设一个数列 d[]，其中的元素为已知数列中相邻元素的差：

d = [0, d0, d0, d0, ..., d0, d1, d1, d1..., d1, ..., dn]

我们要求解的问题就成了：对 d[]，求出 [d0, d0, ..., d0] 中有多少个长度不小于 3 的子数列（也可能只有 [d0] 或 [d0, d0] 因此有 0 个这样的子数列；下同），求出 [d1, d1, ..., d1] 中有多少个长度不小于 3 的子数列，……，求出 [dn, dn, ..., dn] 中有多少个长度不小于 3 的子数列；然后把这些统计量相加，即为所求。

为了实现上述目标，我们需要一个变量 diff 来记录当前数列中元素间距；当 diff 发生变化时，意味着进入了下一个可能的等差数列，此时可以把上一个等差数列的统计量加入总统计量中。这里有 2 个细节需要处理：

1. 下标为 0 的位置对应的子数列统计量应该为 0
2. 我们有一个表来记录：对于每一个下标 k，A[k] 与它所在的等差数列的起点之间有多少个长度不小于 3 的等差子数列。在同一个等差数列中，每多发现一个新元素（该元素仍保持等差的特性），如何将 A[k] 与 A[k-1] 联系在一起，就是我们需要的状态方程。若我们令起点的坐标为 lastStart，那么答案就是 A[k] = A[k-1] + (k - lastStart - 2)，这个公式来自于 A[k] = A[k-1] + ((k - lastStart + 1) - 3 + 1)，而后面这个公式的意思是：

• 假设加入新元素后的等差数列长度为 n，那么相对原等差数列，n 长度的子数列个数 +1，n-1 长度的子数列个数 +1，n-2 长度的子数列个数 +1，……，4 长度的子数列个数 +1，3 长度的子数列个数 +1……
• 因此新等差数列比旧等差数列而言，增加的「算术序列」数量为 n - 3 + 1
• 但对于每个新的等差数列，n 都是不确定的，因此需要记录本等差数列的起点 lastStart，以便计算出 n
• 而对于任两个相邻的等差数列而言， 一旦从前一个数列转变到后一个数列，新数列中马上就有了 2 个元素，因此起点应该是新元素 A[k] 的前一个元素 A[k-1]

因此有下述代码。

【代码】

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        # When len(A) <= 3
        if len(A) < 3:
          return 0
        # When len(A) >= 3
        diff, lastStart, sumCount = 0, 0, 0
        ArithCount = [0]
        for i in range(1, len(A)):
          if A[i]-A[i-1] == diff:
            ArithCount.append(ArithCount[i-1] + (i - lastStart - 1))
          else:
            diff = A[i] - A[i-1]
            lastStart = i-1
            ArithCount.append(0)
            sumCount += ArithCount[i-1]
        # Return the result
        sumCount += ArithCount[-1]
        return sumCount

【结果】

运行时：39 ms

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

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

Your runtime beats 85.78 % of python submissions.

00

参考解法：

• Java
  • 1：用了漂亮的技巧（那句 sum += curr），使整个程序极其短小精悍！漂亮！
  • 2：和我的思路一样
• C++：DP 解法！非常棒地把 i 规模的问题转换成 i-1 规模的问题：
  • 初始化每个位置 i 的算数子序列数为 0：意思是，从上一个算数子序列的结尾开始，到位置 i 为止，增加了多少算数子序列
  • 每当遇到一个新数 A[i]，如果它能和 A[i-1]、A[i-2] 形成算数序列，那么新增到等差数列中的这个元素，为等差数列中算数子序列数目的贡献，恰好就是等差数列中前一个元素的贡献 +1
  • 若新数 A[i] 不能和 A[i-1]、A[i-2] 形成算数序列，那么意味着上一个等差数列结束，因此使用初始化量 0

自己实现一遍最优解：

• [language]。。。