Bərabər Cəmi Leetcode Həlli ilə Üç Hissəyə Bölmə Array

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon microsoft
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 42

Problem Bölmə Geyim Bərabər Cəmi Leetcode Çözümlü Üç Hissəyə bizə bir sıra və ya vektor təqdim edir və ardıcıllığın mümkün olan üç hissəsinin olub olmadığını soruşur. Burada bölmə dedikdə, i, j iki indeks var ki, başlanğıcdan ith indeksədək elementlərin cəmi i + 1-dən jth indeksinə qədər olan elementlərin cəminə bərabər olsun. Və j + 1 indeksindən son elementə qədər olan elementlərin cəmi də massivin ilk iki hissəsinə bərabərdir. Əgər belə iki indeks varsa, deyirik ki, massiv bərabər bir cəmlə üç hissəyə bölünə bilər, əks halda yox. Çözümə keçməmişdən əvvəl bir neçə nümunəyə baxaq.

Bərabər Cəmi Leetcode Həlli ilə Üç Hissəyə Bölmə ArrayPin

arr = [0,2,1,-6,6,-7,9,1,2,0,1]
true

İzahat: Diziyi bərabər cəmin üç hissəsinə bölə bildiyimizdən. Beləliklə, serialın üç bərabər cəmdə bölünə biləcəyini deyə bilərik. Daha formal olaraq 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1.

arr = [0,2,1,-6,6,7,9,-1,2,0,1]
false

İzahat: massivi eyni cəmi olan üç ayrı hissəyə bölmək üçün bir yol olmadığından. Beləliklə cavab yalandır.

Bərabər cəmi Leetcode həlli ilə üç hissəyə bölmə massivinə yanaşma

Problemi bərabər cəm Leetcode həlli ilə üç hissəyə bölmə massivi, verilmiş massivi bərabər cəmlərə sahib olan üç ayrı subaraya bölə biləcəyimizi soruşdu. Beləliklə, əvvəlcə problemi həll etmək üçün serialın ümumi cəmini tapmaq lazımdır. Ümumi cəmi 3-ə bölünmürsə, cavab yalan olur. Çünki o zaman massivi üç bərabər alt hissəyə bölməyin yolu yoxdur. Ancaq cəm 3-ə bölünürsə, cəmi / 3-ə çata biləcəyimizi yoxlayacağıq. Bu prosesi elementlərin davamlı cəmini cəmi / 3 cəminə bərabər tapana qədər saxlayaraq simulyasiya edirik. Cəmi cari element = cəmi / 3-ə qədər əldə etsək, cəmi 0-a sıfırlayırıq və bir daha elementlərin cəmi = cəmi / 3-ü tapmağa başlayın. Bu üsulla cəmi / 3 3 dəfə əldə edə bilsək. Arrayı 3 hissəyə bölə biləcəyimizə əmin ola bilərik, yoxsa yox.

Kodu

Bərabər Cəmi Leetcode Həllli Üç Hissəyə Bölmə Array üçün C ++ kodu

#include <bits/stdc++.h>
using namespace std;

bool canThreePartsEqualSum(vector<int>& arr) {
    int sum = 0;
    for(int i=0;i<arr.size();i++)
        sum += arr[i];
    if(sum % 3 != 0)
        return false;
    int sum3 = sum/3, partitions = 0;
    sum = 0;
    for(int i=0;i<arr.size();i++){
        sum += arr[i];
        if(sum == sum3){
            ++partitions;
            sum = 0;
        }
    }
    return partitions >= 3;
}

int main() {
  vector<int> arr({0,2,1,-6,6,-7,9,1,2,0,1}); 
  cout<<canThreePartsEqualSum(arr);
  return 0;
}
true

Bərabər Cəmi Leetcode Həlli ilə Üç Hissəyə Bölmə Array üçün Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
  public static boolean canThreePartsEqualSum(int[] arr) {
        int sum = 0;
        for(int i=0;i<arr.length;i++)
            sum += arr[i];
        if(sum % 3 != 0)
            return false;
        int sum3 = sum/3, partitions = 0;
        sum = 0;
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
            if(sum == sum3){
                ++partitions;
                sum = 0;
            }
        }
        return partitions >= 3;
    }
 
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {0,2,1,-6,6,-7,9,1,2,0,1};
 
    System.out.print(canThreePartsEqualSum(arr));
  }
}
true

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), serialı iki dəfə keçdiyimizə baxmayaraq. Lakin bu, xətti zaman mürəkkəbliyi sayılacaqdır, çünki massivi keçdiyimiz vaxtlar onun ölçüsündən asılı deyildir.

Kosmik Mürəkkəblik

O (1), davamlı sayda element istifadə etdikdən və hər bir indekslə əlaqəli bəzi məlumatları saxlamadığımızdan. Kosmik mürəkkəblik sabitdir.

Şərh yaz

Translate »
1