leetcode413. Arithmetic Slices

piglei 發(fā)布于2019-08-16 16:55 / 3519人閱讀

摘要：題目要求將包含大于等于三個(gè)元素且任意相鄰兩個(gè)元素之間的差相等的數(shù)組成為等差數(shù)列?，F(xiàn)在輸入一個(gè)隨機(jī)數(shù)組，問(wèn)該數(shù)組中一共可以找出多少組等差數(shù)列。

題目要求

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.

將包含大于等于三個(gè)元素且任意相鄰兩個(gè)元素之間的差相等的數(shù)組成為等差數(shù)列。現(xiàn)在輸入一個(gè)隨機(jī)數(shù)組，問(wèn)該數(shù)組中一共可以找出多少組等差數(shù)列。

思路一：動(dòng)態(tài)規(guī)劃

假設(shè)已經(jīng)知道以第i-1個(gè)數(shù)字為結(jié)尾有k個(gè)等差數(shù)列，且第i個(gè)元素與i-1號(hào)元素和i-2號(hào)元素構(gòu)成了等差數(shù)列，則第i個(gè)數(shù)字為結(jié)尾的等差數(shù)列個(gè)數(shù)為k+1。因此我們可以自底向上動(dòng)態(tài)規(guī)劃，記錄每一位作為結(jié)尾的等差數(shù)列的個(gè)數(shù)，并最終得出整個(gè)數(shù)列中等差數(shù)列的個(gè)數(shù)。代碼如下：

    public int numberOfArithmeticSlices(int[] A) {
        int[] dp = new int[A.length];
        int count = 0;
        for(int i = 2 ; i
思路二：算數(shù)方法
首先看一個(gè)簡(jiǎn)單的等差數(shù)列1 2 3， 可知該數(shù)列中一共有1個(gè)等差數(shù)列
再看1 2 3 4， 可知該數(shù)列中一共有3個(gè)等差數(shù)列，其中以3為結(jié)尾的1個(gè)，以4為結(jié)尾的2個(gè)
再看1 2 3 4 5, 可知該數(shù)列中一共有6個(gè)等差數(shù)列，其中以3為結(jié)尾的1個(gè)，4為結(jié)尾的2個(gè)，5為結(jié)尾的3個(gè)。
綜上，我們可以得出，如果是一個(gè)最大長(zhǎng)度為n的等差數(shù)列，則該等差數(shù)列中一共包含的等差數(shù)列個(gè)數(shù)為(n-2+1)*(n-2)/2，即(n-1)*(n-2)/2。
因此，我們只需要找到以當(dāng)前起點(diǎn)為開(kāi)始的最長(zhǎng)的等差數(shù)列，計(jì)算該等差數(shù)列的長(zhǎng)度并根據(jù)其長(zhǎng)度得出其共包含多少個(gè)子等差數(shù)列。
代碼如下：
    public int numberOfArithmeticSlices2(int[] A) {
        if(A.length <3) return 0;
        int diff = A[1]-A[0];
        int left = 0;
        int right = 2;
        int count = 0;
        while(right < A.length) {
            if(A[right] - A[right-1] != diff) {
                count += (right-left-1) * (right-left-2) / 2;
                diff = A[right] - A[right-1];
                left = right-1;
            }
            right++;
        }
        count += (right-left-1) * (right-left-2) / 2;
        return count;
    }

云服務(wù)器 GPU云服務(wù)器 Arithmetic Slices 413 Leetcod

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74259.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

piglei

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

批量替換WordPress文章中的文字

閱讀 883·2021-09-02 09:55
秒級(jí)容災(zāi)，UCloud內(nèi)網(wǎng)高可用服務(wù)之三代架構(gòu)演進(jìn)

閱讀 1522·2019-12-27 12:02
CSS3-線性漸變

閱讀 1732·2019-08-30 14:24
Codepen 每日精選（2018-3-28）

閱讀 1151·2019-08-30 14:18
[前端工坊]正則表達(dá)式-從模糊到清晰

閱讀 2764·2019-08-29 13:57
JavaScript工作原理（四）：事件循環(huán)，異步編程的興起以及5招async/await實(shí)踐

閱讀 2210·2019-08-26 11:51
React系列 --- 簡(jiǎn)單模擬語(yǔ)法(一)

閱讀 1379·2019-08-26 10:37
js 時(shí)間

閱讀 776·2019-08-23 16:09

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

leetcode413. Arithmetic Slices

相關(guān)文章