Çipləri eyni mövqeyə köçürmək üçün minimum xərclər LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma BloombergBaxılıb 62

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

The Çipləri eyni mövqeyə köçürmək üçün minimum xərclər LeetCode Həlli – “Fişləri eyni mövqeyə daşımaq üçün minimum xərc” sizin malik olduğunuzu bildirir n cips, harada mövqeyi ith çipdir position[i].

Siz bütün fişləri köçürməlisiniz eyni mövqe. Bir addımda mövqeyini dəyişə bilərik ith çipdən position[i] üçün:

position[i] + 2 or position[i] - 2 ilə cost = 0.

position[i] + 1 or position[i] - 1 ilə cost = 1.

Qayıtmalısan bu minimum qiymət bütün fişləri eyni mövqeyə köçürmək lazımdır.

misal

Çipləri eyni mövqeyə köçürmək üçün minimum xərclər LeetCode HəlliPin

Input 
[1,2,3]
Output
1

Izahat

Diqqətlə baxsaq, 0 qiymətində çipləri cüt yerlərə köçürə bilərik, yəni nömrələri 2 fərqlə köçürmək üçün heç bir xərc yoxdur. Beləliklə, biz hərəkət edə bilərik. bütün cüt ədədləri 0-a qədərbütün tək ədədləri 1-ə qədər heç bir xərc olmadan.

İndi, nəhayət, hamısını gətirməliyik nömrələri sıfıra qədər və ya 1. Beləliklə, hərəkət edib-etmədiyini öyrənirik tək rəqəmlər ya da cüt ədədlər daha çox xərc çəkərdi. İkisinin minimumunu qaytarırıq.

Beləliklə, verilmiş massivdə biz cüt yerlərdə olan çiplərin sayını (c_even) və tək yerlərdəki çiplərin sayını (c_odd) tapa bilərik və ikisinin minimumunu götürə bilərik.

NİYƏ Minimum iki?

Bütün çipləri bir yerə gətirməli olduğumuz üçün c_even çipləri 0-da və c_odd çipləri 1-də olduqda, ya bütün cüt çipləri 1-ə, ya da bütün tək çipləri 0-a gətirməliyik ki, minimum dəyəri götürək. ikidən, belə ki, minimum sayda fişin yerini dəyişdirməliyik.

Optimallaşdırma

Nəzərə alaq ki, x çipləri cüt mövqedə tapılır, onda tək mövqedəki çiplərin sayı belə olacaq: massiv_ölçüsü – x

Beləliklə, biz sadəcə bərabər yerləşdirilmiş çiplərin sayını saymalıyıq.

Kodu

class Solution {
    public int minCostToMoveChips(int[] chips) {
        int even = 0;
        for(int i:chips)
            if(i%2==0)
                even++;
        return Math.min(even,chips.length-even);
    }
}

class Solution:
    def minCostToMoveChips(self, chips: List[int]) -> int:
        even = 0
        for i in chips:
            if(i%2==0):
                even+=1
        return min(even,len(chips)-even);
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int even=0,odd=0;
        for(int i=0;i<chips.size();i++){
            if(chips[i]%2==0)
                even++;
            else
                odd++;
        }
        if(even>odd)
            return odd;
        return even;
        
    }
};

Çipləri eyni mövqeyə daşımaq üçün minimum xərc üçün vaxt və məkan mürəkkəbliyi LeetCode Həlli

Cüt/tək çiplərin sayını hesablayandan bəri massivdə bir keçid alır:

Zaman Mürəkkəbliyi: O (n)
Kosmik Mürəkkəblik: O(1) [ Hər hansı bir giriş ölçüsü üçün yalnız iki/bir dəyişəni saxladığımız üçün]

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