Massiv Ziqzaq LeetCode Həlli etmək üçün Elementləri Azaldın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur googleBaxılıb 65

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat :

Massiv Ziqzaq etmək üçün elementləri azaldın LeetCode Həlli – Massiv verilmişdir nömrə tam ədədlər, a hərəkət istənilən elementi seçməkdən ibarətdir və 1 azaldılır.

Bir sıra A birdir ziqzaq massivi əgər hər ikisi:

  • Hər bir cüt indeksli element qonşu elementlərdən daha böyükdür, yəni. A[0] > A[1] < A[2] > A[3] < A[4] > …
  • YA, hər bir tək indeksli element qonşu elementlərdən böyükdür, yəni. A[0] < A[1] > A[2] < A[3] > A[4] < …

Verilmiş massivi çevirmək üçün minimum hərəkət sayını qaytarın nömrə a daxil ziqzaq serial.

Misal:

Məsələn 1

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Məsələn 2

Input: nums = [9,6,1,6,2]
Output: 4

Məhdudiyyətlər:

Massiv Ziqzaq LeetCode Həlli etmək üçün Elementləri Azaldın

İntuisiya:

  • Massivi ziqzaq etməyin yalnız 2 yolu var, ya da hamısını götürün qəribə elementlər və onları etmək kiçik qonşularından daha çox, ya da hamısını götür hətta elementlər və onları etmək kiçik qonşularından daha çox.
  • Cavabımızı acgözlüklə axtarırıq, ona görə də istifadə edəcəyik Greedy alqoritmi.

Alqoritm:

  • əvvəlcə hər bir elementi bir anda düzəldəcəyik hətta indeks kiçik olduğundan bitişiksaymaq etmək üçün addımlar kiçik.
  • sonra hər bir elementi bir anda düzəldəcəyik tək indeks kiçik daha çox bitişiksaymaq etmək üçün addımlar kiçik.
  • İki döngədən istifadə edəcəyik, üçün biri tək indeks digəri üçün hətta indeks.
  • İterasiya edərkən biz yoxlayacağıq cari indeks onun qonşuluğundan kiçik deyilsə o zaman edəcəyik minimum bitişik elementi götürün və addımların sayını hesablayın, yəni nums[i]-min(nums[i]+1,nums[i- 1]) +1.
  • Nəhayət, geri qaytaracağıq hesablamaların minimum dəyəri əldə edilmişdir 1 addımlaraddım 2.

Massiv Ziqzaq etmək üçün Elementləri Azaltmaq Kodu:

Java kodu

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        
        int even = 0, odd = 0, n = nums.length;
    //for odd
        for(int i=1; i < n; i+= 2){
            int min = Math.min(nums[i-1], i+1 < n ? nums[i+1] : 1001);
            if(min <= nums[i])
                odd += (nums[i]-min+1);
        }
    // For Even
        for(int i=0; i < n; i+= 2){
            int min = Math.min(i > 0 ? nums[i-1] : 1001, i+1 < n ? nums[i+1] : 1001);
            if(min <= nums[i])
                even += (nums[i]-min+1);
        }
        return Math.min(even,odd);
    }
    
}

C ++ kodu

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
         int even = 0, odd = 0, n = nums.size();
    //for odd
        for(int i=1; i < n; i+= 2){
            int minVal = min(nums[i-1], i+1 < n ? nums[i+1] : 1001);
            if(minVal <= nums[i])
                odd += (nums[i]-minVal+1);
        }
    // For Even
        for(int i=0; i < n; i+= 2){
            int minVal = min(i > 0 ? nums[i-1] : 1001, i+1 < n ? nums[i+1] : 1001);
            if(minVal <= nums[i])
                even += (nums[i]-minVal+1);
        }
        return min(even,odd);
    }
};

Massiv Ziqzaq etmək üçün Elementləri Azaltmaq üçün Mürəkkəblik Təhlili LeetCode Həlli:

Zamanın mürəkkəbliyi

O(N), N massivin uzunluğudur və biz təkrar edirik cəmi iki dəfə massivdə.

Kosmik Mürəkkəblik 

O(1), çünki əlavə yer istifadə olunmur.

Crack Sistemi Dizayn Müsahibələri
Translate »