Διάταξη σειράς σε τρία μέρη με ίση συνολική λύση Leetcode


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Microsoft
Παράταξη

Το πρόβλημα κατάτμησης Παράταξη Σε τρία μέρη με ίσο άθροισμα Το Leetcode Solution μας παρέχει έναν πίνακα ή έναν φορέα και ρωτά εάν υπάρχουν τρία πιθανά διαμερίσματα της ακολουθίας. Εδώ, με κατάτμηση εννοούμε ότι υπάρχουν δύο δείκτες i, j έτσι ώστε το άθροισμα των στοιχείων από την αρχή έως το δείκτη είναι ίσο με το άθροισμα των στοιχείων από το i + 1 έως το jth index. Και το άθροισμα των στοιχείων από το ευρετήριο j + 1 στο τελευταίο στοιχείο είναι επίσης ίσο με τα δύο πρώτα τμήματα του πίνακα. Εάν υπάρχουν τέτοιοι δύο δείκτες, λέμε ότι ο πίνακας μπορεί να χωριστεί σε τρία μέρη με ίσο άθροισμα, αλλιώς όχι. Πριν προχωρήσουμε στη λύση ας δούμε μερικά παραδείγματα.

Διάταξη σειράς σε τρία μέρη με ίση συνολική λύση Leetcode

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

Επεξήγηση: Εφόσον μπορούμε να χωρίσουμε τον πίνακα σε τρία τμήματα του ίσου αθροίσματος. Έτσι μπορούμε να πούμε ότι ο πίνακας μπορεί να χωριστεί σε τρία ίσα αθροίσματα. Πιο επίσημα, 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1.

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

Επεξήγηση: Δεδομένου ότι δεν υπάρχει τρόπος να διαιρέσετε τον πίνακα σε τρία ξεχωριστά τμήματα που έχουν τα ίδια αθροίσματα. Έτσι, η απάντηση είναι ψευδής.

Προσέγγιση συστοιχίας διαμερισμάτων σε τρία μέρη με ισότιμη λύση Leetcode

Το πρόβλημα της Διαχωριστικής Διάταξης σε Τρία Μέρη με Ίση Άθροισμα Leetcode Solution μας ρώτησε αν μπορούμε να χωρίσουμε τη δεδομένη συστοιχία σε τρία διαχωριστικά υποσύνολα που έχουν ίσα αθροίσματα. Επομένως, για να λύσουμε το πρόβλημα πρώτα πρέπει να βρούμε το συνολικό άθροισμα του πίνακα. Εάν το συνολικό άθροισμα δεν διαιρείται με 3, τότε η απάντηση είναι ψευδής. Διότι τότε δεν υπάρχει τρόπος να διαιρέσετε τον πίνακα σε τρία ίσα υπο-μέρη. Αλλά αν το άθροισμα διαιρείται με το 3. Θα ελέγξουμε αν μπορούμε να φτάσουμε το άθροισμα / 3. Προσομοιώνουμε αυτήν τη διαδικασία αποθηκεύοντας το συνεχές άθροισμα των στοιχείων μέχρι να βρούμε το σύνολο τους ίσο με το άθροισμα / 3. Εάν λάβουμε το σύνολο μέχρι το τρέχον στοιχείο = άθροισμα / 3, επαναφέρουμε το σύνολο σε 0. Και για άλλη μια φορά, αρχίστε να βρίσκετε το σύνολο των στοιχείων = άθροισμα / 3. Εάν μπορούμε να πάρουμε το άθροισμα / 3 3 φορές με αυτήν τη μέθοδο. Μπορούμε να διασφαλίσουμε ότι μπορούμε να χωρίσουμε τον πίνακα σε 3 άλλα μέρη όχι.

Κώδικας

Κωδικός C ++ για το Partition Array σε τρία μέρη με Ίση Άθροισμα Leetcode Solution

#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

Κωδικός Java για διαχωριστική σειρά σε τρία μέρη με ισότιμη λύση Leetcode

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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), παρόλο που έχουμε διαβάσει τον πίνακα δύο φορές. Αλλά αυτό θα μετρηθεί ως γραμμική πολυπλοκότητα χρόνου, επειδή οι χρόνοι που διασχίζουμε τον πίνακα δεν εξαρτάται από το μέγεθός του.

Διαστημική πολυπλοκότητα

Ο (1), αφού χρησιμοποιήσαμε έναν σταθερό αριθμό στοιχείων και δεν αποθηκεύσαμε συγκεκριμένες πληροφορίες σχετικά με κάθε ευρετήριο. Η πολυπλοκότητα του διαστήματος είναι σταθερή.