ArithmeticSlices [source code]
public class ArithmeticSlices {
static
/******************************************************************************/
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int res = 0, n = A.length, i = 0;
if (n < 3)
return 0;
while (i < n) {
int end = extendRun(A, i);
int length = end - i + 1;
i = end;
res += betterCount(length);
}
return res;
}
public int extendRun(int[] A, int start) {
int n = A.length;
if (start + 2 >= n)
return start + 1;
int diff = A[start + 1] - A[start];
int curr = start + 1;
while (curr + 1 < n && A[curr + 1] - A[curr] == diff)
curr++;
return curr;
}
public int countSlices(int length) {
if (length < 3) return 0;
int sum = 0;
for (int i = length; i >= 3; i--)
sum += length - (i - 1);
return sum;
}
public int betterCount(int length) {
if (length < 3)
return 0;
// use formula rather than directly count
int N = length - (3 - 1);
return N * (N + 1) / 2;
}
}
/******************************************************************************/
public static void main(String[] args) {
ArithmeticSlices.Solution tester = new ArithmeticSlices.Solution();
int[][] inputs = {
{1,2,3,4}, {3},
{1,1,2,3,4}, {3},
{1,1,2,3,4,5,6,5,4,3}, {13},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[] A = inputs[2 * i];
int answer = inputs[1 + 2 * i][0];
System.out.println(Printer.seperator());
int output = tester.numberOfArithmeticSlices(A);
System.out.println(Printer.wrapColor(Printer.array(A), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answer, answer == output ? "green" : "red"));
}
}
}
这个题目好像用sliding window可以做? 不过好像都不需要那么复杂的, 直接就跟之前有一个count palindromes的问题一样, 直接挨个搜索就行了;
虽然主体的算法是比较简单的, 但是最后写起来各种小细节还是挺烦人的, 最后的速度是3ms (10%).
我这个算法的时间应该是O(N).
感觉这个问题跟之前palindrome那个问题都可以叫做一个count substring的问题. 这种问题很多时候直接的穷搜方法往往表现都不错, palindrome的那题的extend的做法其实最后的速度并不差, 更不要说这一题的速度更是O(N).
另外一个问题, 有没有想过到底什么才是sliding window? 为什么substring match这个问题就不能用一个最naive的sliding window来完成呢? 因为sliding window解决的问题实际上一般是那种你对substring的要求是无视order, 或者说位置的, 比如说cover, 比如说anagram这种. 而substring match这种问题, 以及palindrome, 这种是对位置和order有要求的, 一个简单的sliding window是不够用的;
这个题目我自己这个算法我也不知道到底是怎么想到的, 好像visual会有一定的帮助?
这个是editorial2, 一个稍微改进的暴力搜:
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
for (int s = 0; s < A.length - 2; s++) {
int d = A[s + 1] - A[s];
for (int e = s + 2; e < A.length; e++) {
if (A[e] - A[e - 1] == d)
count++;
else
break;
}
}
return count;
}
}
虽然这个算法最后的速度只做到了O(N^2), 但是这个算法还是值得一学的.
他的做法使用count: 对于每一个start, 每一个不同的end就对应一个不同的slice, 只要start和end不重复就行; 这样的计算方式避免了我找到longest run之后按照不同的长度还要专门算一遍, 直接用increment counter的思路来count很方便; 当然, 也不是说我的方法就很有问题;
这个是editorial3:
public class Solution {
int sum = 0;
public int numberOfArithmeticSlices(int[] A) {
slices(A, A.length - 1);
return sum;
}
public int slices(int[] A, int i) {
if (i < 2)
return 0;
int ap = 0;
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
ap = 1 + slices(A, i - 1);
sum += ap;
} else
slices(A, i - 1);
return ap;
}
}
这个是一个recursive的解, 也可以说是一个DP的解. 这种解, 一个需要解决的核心问题就是, 你的recursive return value, 或者说DP value怎么选; 如果直接用target value作为DP value无法成功的时候, 我们之前介绍过一个技巧: make the root participate.
这里也是一样的, 这里的recursive返回值, 其实是number of slices that ends at root(ith element), or that the root participates. 而体现DP Property的核心一句就在于:
ap = 1 + slices(A, i - 1);
这个是一个非常简单的更新就解决了: for any slices that includes [i - 1], now we have a duplicate that contains [i] as well.
最后, 因为我们这里的target value和DP value之间不一样, 所以这里的这个recursive的函数, 除了有返回值, 还要有Side Effect. 这个也是一个很常见的做法了: 一个global的sum, 每一个recursion都更新一下就行了;
严格来说, 这个算法应该不能叫做DP, 因为DP就要有memoization, 但是这个问题是没有必要加memo的, 因为这里subproblem之间并没有overlapping.
这个算法的时间很自然的就是O(N)了;
当然, 这个recursion可以轻松的用Bottom-Up的方式来改写:
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int[] dp = new int[A.length];
int sum = 0;
for (int i = 2; i < dp.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = 1 + dp[i - 1];
sum += dp[i];
}
}
return sum;
}
}
以及这里的space还可以讲到O(1), 不过大概就是这个意思了;
editorial最后一个算法其实跟我的算法的思路是非常类似的:
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
int sum = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
count++;
} else {
sum += (count + 1) * (count) / 2;
count = 0;
}
}
return sum += count * (count + 1) / 2;
}
}
count其实count的就是length of the longest run that includes the root so far.
受到discussion里面一个帖子的启发, 这里的这个count其实是没有必要自己手动一个一个的sum的, 因为就是一个等差数列, 自己找个规律然后直接算就行了; 不过最后速度还是3ms, 并没有因此加速;
discussion里面提出一个有趣的观点:
if (A[i]-A[i-1] == A[i-1]-A[i-2])this introduces an integer overflow bug.
If the input is [Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE - 1], it returns 1, but it should be 0.
Correction:
public int numberOfArithmeticSlices(int[] A) {
int curr = 0, sum = 0;
for (int i = 2; i < A.length; i++) {
if ((long)A[i] - A[i - 1] == (long)A[i - 1] - A[i - 2]) {
curr += 1;
sum += curr;
}
else curr = 0;
}
return sum;
}
还真是这么回事:
java> int a = Integer.MIN_VALUE
int a = -2147483648
java> int b = Integer.MAX_VALUE
int b = 2147483647
java> int c = b - 1
int c = 2147483646
java> c - b == b - a
java.lang.Boolean res3 = true
Problem Description
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
Difficulty:Medium
Total Accepted:23.7K
Total Submissions:43.4K
Contributor: XiangyuLi926
Companies
aetion baidu
Related Topics
dynamic programming math
Similar Questions
Arithmetic Slices II - Subsequence