Arifmetik Dilimlər II – Ardıcıllıq LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic google Über
BaiduBaxılıb 23

Problem bəyanat :

Arifmetik Dilimlər II – Ardıcıllıq LeetCode Həlli – Tam ədədlər massivi verilmişdir nömrə, qayıt hamısının sayı arifmetik alt ardıcıllıqlar of nömrə.

Ədədlər ardıcıllığı əgər ondan ibarətdirsə arifmetik adlanır ən azı üç element və hər hansı iki ardıcıl element arasındakı fərq eyni olarsa.

  • Misal üçün, [1, 3, 5, 7, 9][7, 7, 7, 7]və [3, -1, -5, -9] arifmetik ardıcıllıqlardır.
  • Misal üçün, [1, 1, 2, 5, 7] arifmetik ardıcıllıq deyil.

sonradan massivin bəzi elementlərini (bəlkə də heç birini) silməklə yaradıla bilən ardıcıllıqdır.

  • Misal üçün, [2,5,10] -nin alt ardıcıllığıdır [1,2,1,2, 4,1,5,10].

Test nümunələri cavabın uyğun olması üçün yaradılır 32-bit tam.

Misal:

Məsələn 1

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]

Məsələn 2 

Input: nums = [7,7,7,7,7]
Output: 16
Explanation: Any subsequence of this array is arithmetic.

Məhdudiyyətlər:

Arifmetik Dilimlər II - Ardıcıllıq LeetCode HəlliPin

Müşahidə:

    • Arifmetik ardıcıllığı təyin etmək üçün bizə ən azı iki parametr lazımdır: the ilk element ardıcıllığın və ümumi fərq.
    • Arifmetik ardıcıllığın birinci üzvü olarsa a1 və ardıcıl üzvlərin ümumi fərqi budur d, sonra ardıcıllığın n-ci üzvü (bir) tərəfindən verilir:

                                                                            an = a1 + (n-1)d  

Yanaşma:

  • Necə ki, tapmalıyıq arifmetik ardıcıllıq yəni massivin elementləri olmasından asılı olmayaraq arifmetik irəliləyişdə olmalıdır bitişik və ya bitişik olmayan.
  • yaradacağıq xəritələr massivi elementin əvvəlki elementlərinə nisbətən fərq tezliyini saxlamaq üçün.

  • Orijinal tərifində arifmetik ardıcıllıq, sonrakı ardıcıllığın uzunluğu olmalıdır ən azı 3. Ancaq biz yeni alt ardıcıllıqları müəyyənləşdiririk zəif alt ardıcıllıqlar yalnız uzunluğu 2.

  • tezlikArrayMap[i] sayını saxlayır zəif arifmetik alt ardıcıllıqlar ilə bitir nums [i] və onun ümumi fərqidir fərq.

  • Zəif hesab ardıcıllığı var iki xüsusiyyət müəyyən etdiyimiz:

    1.  İstənilən cüt üçün i,j (i != j) nums [i] və ədəd[j] həmişə a təşkil edə bilər zəif hesab sonradan.
    2.  Zəif hesab ardıcıllığına yeni element əlavə etsək, yeni ardıcıllıq arifmetik ardıcıllıq olmalıdır, çünki yeni ardıcıllıq ilkin arifmetik ardıcıllığa çevrilmişdir. ən azı 3 uzunluq.
  • İndi hər biri üçün nums [i], tapacağıq ədəd[j] zəif arifmetik ardıcıllığı əmələ gətirir uzunluq iki.

  • [j] ədədləri üçün biz təkrar edəcəyik 0-dan i-dən kiçik.

  • Artıq iki elementin ümumi fərqini saxlayan FrequencyMapArray-da nums[i] və nums[j], əgər tapa bilsək eyni ümumi fərq müxtəlif cütlər üçün o zaman bunu əlavə edəcəyik cavabımızın tezliyi.

Arifmetik Dilimlər II - Ardıcıllıq LeetCode HəlliPin

Arifmetik dilimlər üçün kod II – Ardıcıllıq:

Java Kodu:

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

C++ Kodu:

#define LL long long
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
          int n = nums.size();
        LL ans = 0;
        vector<map<int,int>>frequencyArrayMap(n);
        for(int i=0;i<n;i++){
           for(int  j=0;j<i;j++){
               LL commondiff = (LL)nums[i]-(LL)nums[j];
               if(commondiff<= INT_MIN || commondiff>= INT_MAX)continue;
               int diff =(int)commondiff;
                 int prevFreq =0;
                int currFreq=0;
               
                 if(frequencyArrayMap[j].find(diff) != frequencyArrayMap[j].end()){
                     prevFreq = frequencyArrayMap[j][diff];
                     currFreq = frequencyArrayMap[i][diff];
                    ans += prevFreq;
                      frequencyArrayMap[i][diff] = currFreq + prevFreq + 1; 
                }
                 else{
                    frequencyArrayMap[i][diff]++;
                }
               
          
             
           }
        }
        return (int)ans;
    }
};

Arifmetik Dilimlər üçün Mürəkkəblik Təhlili II – Ardıcıllıq LeetCode Həlli:

Zamanın mürəkkəbliyi

O(n2)  , çünki biz iki döngədən istifadə edirik.

Kosmik Mürəkkəblik 

O(n2)   Hər bir ədəd [i] üçün ən çox saxlamalıyıq n fərqli ümumi fərqlər, buna görə də ümumi məkan mürəkkəbliyi

Translate »