美文网首页
413. Arithmetic Slices

413. Arithmetic Slices

作者: 殷水臣 | 来源:发表于2017-02-20 20:50 被阅读0次

    简单的动归,若i-2, i-1, i等差,则以第i个数结尾的等差数列总数=以i-1个数结尾的等差数列总数+1。需要多加考虑,自己的想法是求出每一段的最长等差数列,然后求和即可,效率不高。

    自己的代码

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int i = 1, output = 0, length = 0;
            while (i < A.size()){
                if (i != A.size() - 1 && A[i] - A[i-1] == A[i+1] - A[i]){
                    ++length;
                }else{
                    while (length != 0){
                        output += length;
                        --length;
                    }
                    
                }
                ++i;
            }
            return output;
        }
    };
    

    DP解法

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int n = A.size();
            if (n < 3) return 0;
            vector<int> dp(n, 0); // dp[i] means the number of arithmetic slices ending with A[i]
            if (A[2]-A[1] == A[1]-A[0]) dp[2] = 1; // if the first three numbers are arithmetic or not
            int result = dp[2];
            for (int i = 3; i < n; ++i) {
                // if A[i-2], A[i-1], A[i] are arithmetic, then the number of arithmetic slices ending with A[i] (dp[i])
                // equals to:
                //      the number of arithmetic slices ending with A[i-1] (dp[i-1], all these arithmetic slices appending A[i] are also arithmetic)
                //      +
                //      A[i-2], A[i-1], A[i] (a brand new arithmetic slice)
                // it is how dp[i] = dp[i-1] + 1 comes
                if (A[i]-A[i-1] == A[i-1]-A[i-2]) 
                    dp[i] = dp[i-1] + 1;
                result += dp[i]; // accumulate all valid slices
            }
            return result;
        }
    };
    

    相关文章

      网友评论

          本文标题:413. Arithmetic Slices

          本文链接:https://www.haomeiwen.com/subject/wynewttx.html