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

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.

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

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şik və saymaq 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şik və saymaq 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ımlar və addı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);
    }
};