1027. Longest Arithmetic Subsequence

LeetCode medium original: C# #array #csharp #dynamic-programming #hash-table #leetcode #math #medium #search

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Если задан tableau nums целых чисел, return длину самой длинной арифметической подпоследовательности в nums. Примечание: subsequence - это tableau, который может быть получен из другого tableauа путем удаления некоторых или ни одного elementа без изменения порядка оставшихся elementов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).

Exemple:

Input: nums = [3,6,9,12]

Output: 4

C# solution

correspondant/original

public class Solution {
    public int LongestArithSeqLength(int[] nums) {
        if (nums.Length == 0) return 0;
        
        var dp = new Dictionary<int, int>[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            dp[i] = new Dictionary<int, int>();
        }
        int maxLength = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (dp[j].TryGetValue(diff, out int length)) {
                    dp[i][diff] = length + 1;
                } else {
                    dp[i][diff] = 2;
                }
                maxLength = Math.Max(maxLength, dp[i][diff]);
            }
        }
        
        return maxLength;
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#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:
    public int LongestArithSeqLength(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        
        var dp = new unordered_map<int, int>[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            dp[i] = new unordered_map<int, int>();
        }
        int maxLength = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (dp[j].TryGetValue(diff, out int length)) {
                    dp[i][diff] = length + 1;
                } else {
                    dp[i][diff] = 2;
                }
                maxLength = max(maxLength, dp[i][diff]);
            }
        }
        
        return maxLength;
    }
}

Java solution

correspondant/original

public class Solution {
    public int longestArithSeqLength(int[] nums) {
        if (nums.length == 0) return 0;
        
        int n = nums.length;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }
        int maxLength = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                int length = dp[j].getOrDefault(diff, 1) + 1;
                dp[i].put(diff, length);
                maxLength = Math.max(maxLength, length);
            }
        }
        
        return maxLength;
    }
}

JavaScript solution

correspondant/original

class Solution {
    longestArithSeqLength(nums) {
        if (nums.length === 0) return 0;
        
        const dp = Array(nums.length).fill(0).map(() => new Map());
        let maxLength = 0;
        
        for (let i = 0; i < nums.length; i++) {
            for (let j = 0; j < i; j++) {
                const diff = nums[i] - nums[j];
                const length = (dp[j].get(diff) || 1) + 1;
                dp[i].set(diff, length);
                maxLength = Math.max(maxLength, length);
            }
        }
        
        return maxLength;
    }
}

Algorithm

Инициализация переменных:

Создайте tableau словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на elementе i с разностью d.

Заполнение tableauа dp:

Пройдитесь по каждому elementу tableauа nums.

Для каждого elementа nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].

Обновите dp[i][d] на основе значения dp[j][d].

Поиск максимальной длины:

Пройдите по tableauу dp и find максимальное значение среди всех значений dp[i][d].

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.