Leetcode[413] Arithmetic Slices

_ipo 發布于2019-08-16 10:26 / 2139人閱讀

摘要：復雜度思路找數組里面的等差數列的個數。想法是如果一開始三個數就滿足是等差數列的話，就在當前已有的數目上不斷的累加的結果。

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;
}

GPU云服務器云服務器 Arithmetic Slices 413 LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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