446、等差数列划分 II - 子序列

leetcode

Created At : 2020-07-26 00:19

Count:841 Views 👀 :

Comment:

446、等差数列划分 II - 子序列
1. 示例：

题解

1、深度优先暴力递归
1、动态规划

446、等差数列划分 II - 子序列

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

以下数列不是等差数列。

1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从 0 开始。该数组子序列将划分为整数序列 $(P0, P1, …, Pk)$，P 与 Q 是整数且满足 $0 ≤ P0 < P1 < … < Pk < N$。

如果序列 $A[P0]，A[P1]，…，A[Pk-1]，A[Pk]$ 是等差的，那么数组 A 的子序列 $(P0，P1，…，PK)$ 称为等差序列。值得注意的是，这意味着 $k ≥ 2$。

函数要返回数组 A 中所有等差子序列的个数。

输入包含 N 个整数。每个整数都在 $[-2^{31} ,2^{31}-1]$ 之间，另外 $0 ≤ N ≤ 1000$。保证输出小于 231-1。

示例：

输入：[2, 4, 6, 8, 10]

输出：7

解释：
所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence

题解

1、深度优先暴力递归

代码

// java

class Solution {
    private int n;
    private int ans;
    private void dfs(int dep, int[] A, List<Long> cur) {
        if (dep == n) {
            if (cur.size() < 3) {
                return;
            }
            long diff = cur.get(1) - cur.get(0);
            for (int i = 1; i < cur.size(); i++) {                
                if (cur.get(i) - cur.get(i - 1) != diff) {
                    return;
                }
            }
            ans ++;
            return;
        }
        dfs(dep + 1, A, cur);
        cur.add((long)A[dep]);
        dfs(dep + 1, A, cur);
        cur.remove((long)A[dep]);
    }
    public int numberOfArithmeticSlices(int[] A) {
        n = A.length;
        ans = 0;
        List<Long> cur = new ArrayList<Long>();
        dfs(0, A, cur);
        return (int)ans;        
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/solution/deng-chai-shu-lie-hua-fen-ii-zi-xu-lie-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1、动态规划

f[i][d] ，代表以 A[i] 结束且公差为 d 的等差数列个数。

$对于j < i，f[i][A[i] - A[j]] += f[j][A[i] - A[j]]$。

代码

// java

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        long ans = 0;
        Map<Integer, Integer>[] cnt = new Map[n];
        for (int i = 0; i < n; i++) {
            cnt[i] = new HashMap<>(i);
            for (int j = 0; j < i; j++) {
                long delta = (long)A[i] - (long)A[j];
                if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE) {
                    continue;
                }
                int diff = (int)delta;
                int sum = cnt[j].getOrDefault(diff, 0);
                int origin = cnt[i].getOrDefault(diff, 0);
                cnt[i].put(diff, origin + sum + 1);
                ans += sum;
            }
        }
        return (int)ans;        
    }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/solution/deng-chai-shu-lie-hua-fen-ii-zi-xu-lie-by-leetcode/


class Solution {

    // 等差数列2
    // 动态规划
    // dp[j][i] 表示以nums[j]和nums[i]为末尾两个元素构成的等差数列
    public int numberOfArithmeticSlices(int[] nums) {

        int n = nums.length;
        int[][] dp = new int[n][n];

        // <数，索引位置>
        Map<Long,List<Integer>> map = new HashMap<>();

        for(int i = 0; i < n; i ++){
           map.putIfAbsent((long)nums[i],new ArrayList<>());
           map.get((long)nums[i]).add(i);
        }

        int res = 0;
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < i ;j ++) {

                Long taregt = 2 * (long)nums[j] - nums[i];
                if(map.containsKey(taregt)){
                    for(int k : map.get(taregt)){
                        if(k < j){
                            dp[i][j] += (dp[j][k] + 1);
                        }
                    }
                }

                res += dp[i][j];
            }
        }

        return res;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com