1027. Longest Arithmetic Subsequence

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

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

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

Ví dụ:

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

Output: 4

C# lời giải

đã khớp/gốc

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++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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

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

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

Заполнение mảngа dp:

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

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

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

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

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

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.