Massivi bölmək üçün yolların maksimum sayı LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Facebook googleBaxı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

Massivi bölmək üçün yolların maksimum sayı LeetCode Həlli – Sizə verilir 0 indeksli tam sıra nums uzunluğu n. Yolların sayı arakəsmə nums sayıdır pivot hər iki şərti ödəyən indekslər:

  • 1 <= pivot < n
  • nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]

Sizə tam ədəd də verilir k. Dəyərini dəyişdirməyi seçə bilərsiniz bir elementi nums üçün k, və ya massivdən çıxmaq üçün dəyişməz.

Qayıtmaq bu maksimum yollarının mümkün sayı arakəsmə nums dəyişdirildikdən sonra hər iki şərti təmin etmək ən çox bir element.

Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2].
There is one way to partition the array:
- For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.

Izahat

Birincisi, hər hansı bir rəqəmi dəyişməsək, bu massivi neçə yolla bölə bilərik A bərabər cəmi ilə iki hissəyə? Biz prefiksi ala bilərik cəm dizisi A-nın neçə dəfə baş verdiyini sayın sum(A) / 2 prefiks cəmi massivində. (Əgər cəmi(A) % 2 = 1 olarsa, onu bölmək üçün heç bir yol yoxdur)
Massivə nəzər salın A nümunə olaraq aşağıdakı şəkildə.

Massivi bölmək üçün yolların maksimum sayı LeetCode HəlliPin

prefiks cəmini aldıqdan sonra A, və cəmidir A olan 0, neçəsini sayaq 0s prefiks cəmində. Diqqət yetirin ki, biz HEÇ VAXT üçün dayandığı üçün son prefiksin cəmini sayın A özü.

Massivi bölmək üçün yolların maksimum sayı LeetCode HəlliPin

4 tapırıq 0 prefiks cəmi massivində. Bu o deməkdir ki, nömrə dəyişmədən onu bölmək üçün 4 yol var.
Bir ədədi dəyişsək, deyək ki, A[i], yenə də cəmin yarısının baş verməsini saymaqla və ya bəzi oxşar üsullarla bölünmə yollarının sayını əldə edə bilərikmi? bəli.

Massivi götürün A aşağıda bir nümunədir. Tutaq ki, biz dəyişdik A[4] etibarən 3 üçün 4, bir ədədin dəyişməsinə görə prefiksin cəmi massivi necə dəyişəcək?

Massivi bölmək üçün yolların maksimum sayı LeetCode HəlliPin

Bunu deyə bilərik Yalnız prefiks cəmi və sonrakı A[4] dəyişdirilir. ildən A[4] bir əlavə edilir, bütün dəyişdirilmiş prefiks məbləğləri də bir əlavə olunur.

Biz iki həşməpdən istifadə edirik (gəlin onları çağıraq əvvəlcədən və sufd) bütün prefiks cəminin meydana gəlməsini saxlamaq üçün Orijinal A, biz hər iki həşmənin heç bir açarını dəyişmirik, çünki o, O(N^2) vaxt mürəkkəbliyi gətirəcək və onu dəyişdirməyə ehtiyac yoxdur.Massivi bölmək üçün yolların maksimum sayı LeetCode HəlliPin

İndi bir dəfə dəyişdik A[4] etibarən 3 üçün 4, bütün bölmə yollarını tapmaq üçün növbəti addım nədir? Eynilə, biz heşməpdə yarım məbləğin hadisələrini axtarırıq.

  • Biz baxanda əvvəlcədən, meydana gəlməsini axtarırıq newSum / 2.
  • Biz baxanda sufd, biz axtarmırıq newSum / 2, Lakin (newSum - k + A[i]) / 2.

Niyə?

Unutmayın ki, biz heç bir həşməpdə açarları yeniləmirik, ona görə də onlar yalnız orijinal A-nın məlumatlarını ehtiva edir. Nəticəni əldə etmək istədikdə. newSum / 2, biz onu dəyişdirməliyik A[i] - k orijinal A-nın dəyişdiyi tərs dəyərdir.

Bu ehtimalın baş verməsini yeniləməyi unutmayın pre[i] hər iki hasshmapda. Yəni birini "hərəkət et" pre[i] etibarən sufd üçün əvvəlcədən və növbəti indeksə keçin.

Kodu

Massivi bölmək üçün maksimum yolların sayı üçün C++ kodu

class Solution {
public:
    int waysToPartition(vector<int>& A, int k) {
        int n = A.size();
        long long s = 0, ans = 0;
        vector<int> pre;
        unordered_map<long long, long long> pred, sufd;
        
        for (int a : A) {
            s += a;
            pre.push_back(s);
            sufd[s] += 1;
        }
        sufd[s] -= 1;
        
        if (s % 2 == 0) {
            ans += sufd[s / 2];
        }
       
        for (int i = 0; i < n; ++i) {
            long long cur = 0;
            if (A[i] != k) {
                int news = s + k - A[i];
                if (news % 2 == 0) {
                    if (i > 0) 
                        cur += pred[news / 2];
                    if (i < n - 1)
                        cur += sufd[news / 2 + A[i] - k];
                }
            }
            ans = max(ans, cur);
            sufd[pre[i]] -= 1;
            pred[pre[i]] += 1;
        }
        return ans;        
    }
};

 

Massivi bölmək üçün maksimum yolların sayı üçün Java kodu

public int waysToPartition(int[] nums, int k) {
    int n = nums.length;
    
    int[] pref = new int[n];
    pref[0] = nums[0];        
    Map<Integer, Integer> count = new HashMap<>(); //contribution of prefixes without changing
    count.put(pref[0], 1); 
    
    for (int i = 1; i < n - 1; i++){
        pref[i] += pref[i - 1] + nums[i];
        count.put(pref[i], count.getOrDefault(pref[i], 0) + 1);
    }
    pref[n - 1] += pref[n - 2] + nums[n - 1]; //last step doesn't add into 'count' map, because we're trying to find at least two parts.
    int sum = pref[n - 1];
    int max = 0;
    if (sum % 2 == 0)
        max = count.getOrDefault(sum / 2, 0); //max without changing
    Map<Integer, Integer> countPrev = new HashMap<>(); //contribution of prefixes before current step
    for (int i = 0; i < n; i++){
        int diff = k - nums[i];
        int changedSum = sum + diff;
        if (changedSum % 2 == 0) 
            max = Math.max(max, count.getOrDefault(changedSum / 2 - diff, 0) + countPrev.getOrDefault(changedSum / 2, 0));            
        count.put(pref[i], count.getOrDefault(pref[i], 0) - 1);
        countPrev.put(pref[i], countPrev.getOrDefault(pref[i], 0) + 1);
    }
    return max;
}

 

Massivi bölmək üçün maksimum yolların sayı üçün Python kodu

class Solution:
    def waysToPartition(self, A: List[int], k: int) -> int:
        n = len(A) 
        pre, s = list(itertools.accumulate(A)), sum(A)
        ans = 0
        # pred contains all the presum BEFORE i-th number.
        # sufd contains all the presum AFTER and WITH i-th number.
        pred = collections.defaultdict(int)
        sufd = collections.Counter(pre)
        
        # The last prefix sum is NEVER used. 
        sufd[sum(A)] -= 1
        
        # The number of ways if we do not change any number.
        if s % 2 == 0:
            ans = sufd[s // 2]
        # The number of ways if we split i-th number to k.
        for i in range(n):
            cur = 0
            
            # We only count number of ways when A[i] != k (otherwise change makes no difference)
            # and when the SUM after the change is dividable by 2.
            if A[i] != k:
                news = s + k - A[i]
                if news % 2 == 0:
                    
                    # If i == 0, only count suffix part.
                    if i > 0:
                        cur += pred[news // 2]
                        
                    # If i == n - 1, only count prefix part.
                    if i < n - 1:
                        cur += sufd[news // 2 + A[i] - k]
            ans = max(ans, cur)
            
            # Don't forget to change the values in the two counters.
            sufd[pre[i]] -= 1
            pred[pre[i]] += 1
            
        return ans

 

Massiv LeetCode Həllini Bölmə Yollarının Maksimum Sayı üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O(N) biz 0-dan n-1-ə qədər hər i-ni döngə kimi götürüb yoxlayardıq.

Kosmik Mürəkkəblik

O(N) bütün prefiks məbləğləri fərqli olarsa, həşməpdə maksimum n düyməsi olacaqdır.

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