Ən Böyük Cəmi LeetCode Həlli ilə K ölçüsünün ardıcıllığı

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur microsoft
DRW PərakəndəMeNotBaxılıb 20

Problem bəyanat

The Ən Böyük Cəmi LeetCode Həlli ilə K ölçüsünün ardıcıllığı – “Ən böyük cüt cəmi ilə K ölçüsünün sonrakı ardıcıllığı” massivi verir nömrə və tam ədəd kKi, burada vəzifə tapmaqdır ən böyük cüt məbləğ k ölçüsündə olan massiv ədədlərindən istənilən alt ardıcıllığın.

Əgər varsa məbləği qaytarın, əks halda -1 qaytarın.

Qeyd: Ardıcıllıq, qalan elementlərin sırasını dəyişdirmədən bəzi elementləri silməklə və ya heç bir elementi silməklə başqa massivdən əldə edilə bilən massivdir.

Misal:

Daxiletmə: ədədlər: { 5, 2, 9, 7, 7, 2} k : 3

Çıxış: 18

İzahat: Cəmi cüt sayı olan sonrakı ardıcıllıq [9,7,2] = 18-dir.

Optimallaşdırılmış Həll:

Bu problemi oxuduqdan sonra sağlam düşüncə, əvvəlcə bu massivi çeşidləməklə acgözlükdən istifadə etməkdir. Sonra elementləri götürüb ən böyük ucundan əlavə edə bilərik. Yeganə çətin məqam o oldu ki, k element əldə edildikdən sonra bərabər məbləğ əldə etmədik.

Yanaşma: 

Burada əsas məqam ondan ibarətdir ki, n elementin cəmi cüt sayda tək elementlərin birləşməsi ilə cüt ola bilər və iki cüt ədədin cəmi həmişə cütdür.

  • Massivi tərs qaydada çeşidləyin.
  • İlk k elementin cəmini tapın və ən kiçik tək elementi və ən kiçik cüt elementi izləyin.
  • Əgər məbləğ hətta olarsa, məbləği qaytarın.
  • Əks halda massivi k-dan sona qədər keçin, burada iki şey şəklə gəlir:
    • Cari element hətta olarsa, cəmindən ən kiçik tək elementi çıxarın və cari elementi əlavə edin.
    • Cari element təkdirsə, cəmindən ən kiçik cüt elementi çıxarın və cari elementi əlavə edin.

Ən Böyük Cəmi LeetCode Həlli ilə K ölçüsünün ardıcıllığıPin

Kodu

C++ Proqramı Ən böyük cüt cəmi ilə K ölçüsünün sonrakı ardıcıllığı LeetCode Həlli

class Solution {
public:
    long long largestEvenSum(vector<int>& A, int k) {
        long long sum = 0;
        int n = A.size();
        long long res = -1;
        sort(A.begin(),A.end());
        reverse(A.begin(),A.end());
        
        int curr_odd = -1;
        int curr_even = -1;
        
        for (int i = 0; i < k ;i++)
        {
           sum = sum + A[i];
           if (A[i]%2 == 0)
               curr_even = A[i];
            else
                curr_odd = A[i];
            
        }
        
        if(sum % 2 == 0)
            return sum;
        
        
        for(int i = k; i < n; i++)
        {
            if(A[i]%2 == 0 && curr_odd != -1)
                res = max(res, sum + A[i] -curr_odd);
            if(A[i]%2 != 0 && curr_even != -1)
                res = max(res, sum + A[i] - curr_even);
        }
        
        if (res % 2 == 0)
            return res;
        else
            return -1;
        
    }
};

Java proqramı Ən böyük cüt cəmi ilə K ölçüsünün sonrakı ardıcıllığı LeetCode Həlli

class Solution {
    static void reverse(int a[], int n)
    {
        int i, t;
        for (i = 0; i < n / 2; i++) {
            t = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = t;
        }
    }
    public long largestEvenSum(int[] nums, int k) {
        long sum = 0;
        int n = nums.length;
        long res = -1;
        Arrays.sort(nums);
        reverse(nums,n);
        
        int curr_odd = -1;
        int curr_even = -1;
        
        for (int i = 0; i < k ;i++)
        {
           sum = sum + nums[i];
           if (nums[i]%2 == 0)
               curr_even = nums[i];
            else
                curr_odd = nums[i];
            
        }
        
        if(sum % 2 == 0)
            return sum;
        
        
        for(int i = k; i < n; i++)
        {
            if(nums[i]%2 == 0 && curr_odd != -1)
                res = Math.max(res, sum + nums[i] -curr_odd);
            if(nums[i]%2 != 0 && curr_even != -1)
                res = Math.max(res, sum + nums[i] - curr_even);
        }
        
        if (res % 2 == 0)
            return res;
        else
            return -1;
    }
}

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun Zaman Mürəkkəbliyi O(nlogn)-dir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun fəza mürəkkəbliyi O(1)-dir.

Referans: https://en.wikipedia.org/wiki/Subsequence

Şərh yaz

Translate »