446. Arithmetic Slices II - Subsequence

leetcode hard

#array#bit-manipulation#csharp#graph#hard#leetcode#search

Task

Дан целочисленный массив nums, вернуть количество всех арифметических подпоследовательностей nums.

Последовательность чисел называется арифметической, если она состоит как минимум из трех элементов и если разница между любыми двумя последовательными элементами одинаковая.

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.

Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.

Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].

Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]

Output: 7

Explanation: All arithmetic subsequence slices are:

[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]

C# solution

matched/original

public class Solution {
    private int n;
    private int ans;
    private void Dfs(int dep, int[] A, List<long> cur) {
        if (dep == n) {
            if (cur.Count < 3) return;
            for (int i = 1; i < cur.Count; i++) {
                if (cur[i] - cur[i - 1] != cur[1] - cur[0]) return;
            }
            ans++;
            return;
        }
        Dfs(dep + 1, A, cur);
        cur.Add(A[dep]);
        Dfs(dep + 1, A, cur);
        cur.RemoveAt(cur.Count - 1);
    }
    public int NumberOfArithmeticSlices(int[] A) {
        n = A.Length;
        ans = 0;
        Dfs(0, A, new List<long>());
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int n;
    private int ans;
    private void Dfs(int dep, vector<int>& A, List<long> cur) {
        if (dep == n) {
            if (cur.size() < 3) return;
            for (int i = 1; i < cur.size(); i++) {
                if (cur[i] - cur[i - 1] != cur[1] - cur[0]) return;
            }
            ans++;
            return;
        }
        Dfs(dep + 1, A, cur);
        cur.push_back(A[dep]);
        Dfs(dep + 1, A, cur);
        cur.RemoveAt(cur.size() - 1);
    }
    public int NumberOfArithmeticSlices(vector<int>& A) {
        n = A.size();
        ans = 0;
        Dfs(0, A, new List<long>());
        return ans;
    }
}

Java solution

matched/original

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;
            for (int i = 1; i < cur.size(); i++) {
                if (cur.get(i) - cur.get(i - 1) != cur.get(1) - cur.get(0)) return;
            }
            ans++;
            return;
        }
        dfs(dep + 1, A, cur);
        cur.add((long) A[dep]);
        dfs(dep + 1, A, cur);
        cur.remove(cur.size() - 1);
    }

    public int numberOfArithmeticSlices(int[] A) {
        n = A.length;
        ans = 0;
        dfs(0, A, new ArrayList<>());
        return ans;
    }
}

JavaScript solution

matched/original

class Solution {
    constructor() {
        this.n = 0;
        this.ans = 0;
    }

    dfs(dep, A, cur) {
        if (dep === this.n) {
            if (cur.length < 3) return;
            for (let i = 1; i < cur.length; i++) {
                if (cur[i] - cur[i - 1] !== cur[1] - cur[0]) return;
            }
            this.ans++;
            return;
        }
        this.dfs(dep + 1, A, cur);
        cur.push(A[dep]);
        this.dfs(dep + 1, A, cur);
        cur.pop();
    }

    numberOfArithmeticSlices(A) {
        this.n = A.length;
        this.ans = 0;
        this.dfs(0, A, []);
        return this.ans;
    }
}

Python solution

matched/original

class Solution:
    def __init__(self):
        self.n = 0
        self.ans = 0

    def dfs(self, dep, A, cur):
        if dep == self.n:
            if len(cur) < 3:
                return
            for i in range(1, len(cur)):
                if cur[i] - cur[i - 1] != cur[1] - cur[0]:
                    return
            self.ans += 1
            return
        self.dfs(dep + 1, A, cur)
        cur.append(A[dep])
        self.dfs(dep + 1, A, cur)
        cur.pop()

    def numberOfArithmeticSlices(self, A):
        self.n = len(A)
        self.ans = 0
        self.dfs(0, A, [])
        return self.ans

Go solution

matched/original

type Solution struct {
    n   int
    ans int
}

func (sol *Solution) dfs(dep int, A []int, cur []int64) {
    if dep == sol.n {
        if len(cur) < 3 {
            return
        }
        for i := 1; i < len(cur); i++ {
            if cur[i]-cur[i-1] != cur[1]-cur[0] {
                return
            }
        }
        sol.ans++
        return
    }
    sol.dfs(dep+1, A, cur)
    cur = append(cur, int64(A[dep]))
    sol.dfs(dep+1, A, cur)
    cur = cur[:len(cur)-1]
}

func numberOfArithmeticSlices(A []int) int {
    sol := Solution{n: len(A), ans: 0}
    sol.dfs(0, A, []int64{})
    return sol.ans
}

Explanation

Algorithm

Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

Возвращаем количество всех арифметических подпоследовательностей.

😎