Leetcode[413] Arithmetic Slices

_ipo 发布于2019-08-16 10:26 / 1901人阅读

摘要：复杂度思路找数组里面的等差数列的个数。想法是如果一开始三个数就满足是等差数列的话，就在当前已有的数目上不断的累加的结果。

Leetcode[413] Arithmetic Slices

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.

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

复杂度
O(N)

思路
找数组里面的等差数列的个数。想法是如果一开始三个数就满足是等差数列的话，就在当前已有的数目上不断的累加count的结果。然后更新sum。

代码

public int numberOfArithmeticSlices(int[] nums) {
    int cur = 0, sum = 0;
    for(int i = 2; i < nums.length; i ++) {
        if(nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 1]) {
            cur += 1;
            sum += cur;
        }
        else {
            cur = 0;
        }
    }
    return sum;
}

服务器托管云服务器 Arithmetic Slices 413 LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69792.html

leetcode413. Arithmetic Slices

摘要：题目要求将包含大于等于三个元素且任意相邻两个元素之间的差相等的数组成为等差数列。现在输入一个随机数组，问该数组中一共可以找出多少组等差数列。题目要求 A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any ...

piglei 2019-08-16 16:55 评论0 收藏0
LeetCode 3

摘要：这个题没什么好说的，用栈就可以了，注意一下两个数计算的时候谁前谁后就行了。 Evaluate Reverse Polish Notation https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/ Evaluate the value of an arithmetic expression in Reve...

rainyang 2019-08-14 11:46 评论0 收藏0
[LeetCode] 150. Evaluate Reverse Polish Notation

Problem Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two inte...

KoreyLee 2019-08-16 13:59 评论0 收藏0
[Leetcode] Evaluate Reverse Polish Notation 计算逆波兰表

摘要：栈法复杂度时间空间思路逆波兰表达式的计算十分方便，对于运算符，其运算的两个数就是这个运算符前面的两个数。注意对于减法，先弹出的是减号后面的数。 Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operato...

ephererid 2019-08-14 12:40 评论0 收藏0
leetcode150. Evaluate Reverse Polish Notation

摘要：我们一般看到的数学表达式就是中缀表达式，也就是将符号放在两个数字之间。后缀表达式也就是将运算符放在相应数字的后面。后缀表达式相当于树中的后序遍历。通过获得对应位置的操作符。如果对应的还是操作符，则继续递归往前计算。题目要求 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid...

bitkylin 2019-08-16 10:40 评论0 收藏0