fbpx

Jaka jest różnica pomiędzy uczeniem się programowania biernie i aktywnie? Zasadnicza.

Jednak sposób analizy kodu w obu przypadkach różni się już mniej. Niezależenie do tego, czy czytasz kod innych, czy piszesz go sam, ostatecznie uczysz się nowych rzeczy. A ludzie z natury lubią się uczyć.

„Nauka to pokarm dla rozumu.”

Lew Tołstoj

W przypadku programowania zazwyczaj zaczynamy od nauki biernej czytając i dalej powinien nastąpić krok drugi, czyli nauka aktywna, która jak wiemy, nie zawsze ma miejsce. Zwłaszcza w przypadku nauki programowania jest bardzo istotne, by z nauki biernej szybko przejść do aktywnej.

Mam nadzieje, że po tym wstępie będziemy gotowi do przeczytania, analizy i własnych eksperymentów, ponieważ tematem dzisiejszego artykułu będzie jedno z zadań z platformy LeetCode, które miałem przyjemność rozwiązywać w ramach jednego z pytań rekrutacyjnych. Zadanie na rekrutacji było pochodną tego zadania, jednak wystarczy zrozumieć sens danego zbioru zagadnień, by później poradzić sobie z każdym podobnym przykładem zadania.

LINK DO ZADANIA

Zaczynajmy!

Iloczyn elementów tablicy — Wprowadzenie

Celem naszego zadania jest, wydawać by się mogło prosta operacja — wystarczy przemnożyć wszystkie elementy listy i zapisać wyniki do osobnej listy. Jest jednak haczyk, musimy mnożyć elementy tablicy z pominięciem elementu, na którym aktualnie się znajdujemy podczas iteracji.

Aby jeszcze bardziej utrudnić rozwiązanie, twórcy dodali kolejne dwa warunki, czyli nie możemy dzielić oraz musimy osiągnąć złożoność czasową na poziomie O(n). I tu zaczynają się schody, bo nie możemy użyć po prostu pętli, w której będzie kolejna pętla, która będzie iterować po całej kolekcji i sprawdzać, czy przypadkiem indeks elementu z pętli nadrzędnej nie pokrył się z indeksem elementu z pętli podrzędnej.

Przykład działającego kodu z użyciem dwóch pętli, który nie jest akceptowany przez silnik sprawdzający zadania.

Python 3

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:  
        ret = 1
        retArr = []
        for x in nums:
            for y in nums:
                if x != y:
                    ret *= nums[y]
            retArr.append(ret)
            ret = 1

        return retArr
Iloczyn elementów tablicy - przykład błędnego rozwiązania

W powyższym rozwiązaniu oraz na powyższym obrazie widzimy dokładnie rozpisany schemat działania algorytmu. Problemem jest złożoność czasowa, która wynosi dokładnie O(n^2), ponieważ w każdej iteracji pętli nadrzędnej będziemy musieli raz jeszcze przeiterować tę samą listę. 

W przypadku listy 4-elementowej tych iteracji będzie dokładnie 4 * 4 zgodnie ze wzorem powyżej.

Poniżej przykład wartości iteratorów.

Pierwsza krok: i=1, j=1
Drugi krok: i=1, j=2
Trzeci krok: i=1, j=3
Czwarty krok: i=1, j=4
Piąty krok: i=2, j=1
Szósty krok: i=2, j=2
Siódmy krok: i=2, j=3
Ósmy krok: i=2, j=4
Dziewiąty krok: i=3, j=1
Dziesiąty krok: i=3, j=2
Jedenasty krok: i=3, j=3
Dwunasty krok: i=3, j=4
Trzynasty krok: i=4, j=1
Czternasty krok: i=4, j=2
Piętnasty krok: i=4, j=3
Szesnasty krok: i=4, j=4

Sporo jak na tak małą listę. W przypadku 100-elementowego zbioru liczb robi się to już 10000 kroków, ale pozwól, że nie będę tego rozpisywał.

Co więc możemy zrobić? Podpowiedź leży w treści zadania, a dokładniej we fragmencie „You must write an algorithm that runs in O(n) time”.

Wywnioskować możemy, że do zbudowania algorytmu z taką złożonością potrzebujemy użyć tylko jednej pętli. 

Skoro tak to zabieramy się do właściwego rozwiązania!

Iloczyn elementów tablicy — Właściwe rozwiązanie

Czas trochę pomyśleć. Najlepiej do analizy i rozpisania możliwości służy kartka papieru lub tablica suchościeralna. U mnie sprawdza się rewelacyjnie jedno i drugie rozwiązanie.

W przypadku tego zadania musimy wyjść poza schemat i uwierz mi, nad tym zadaniem spędziłem długie godziny. Analizowałem różne możliwości, próbowałem znalezionych w sieci sztuczek czy wreszcie eksperymentowałem z własnymi pomysłami. Koniec końców wyszła z tego niezła zabawa i końcowy efekt był niezwykle satysfakcjonujący.

Twórca zadania narzuca nam obiekt, jakim jest klasa Solution oraz funkcja o nazwie productExceptSelf. Na wejście funkcji podać musimy listę, na której będziemy pracować. Na potrzeby testów lista o wartościach 1, 2, 3, 4 jest idealna. Dla takiej listy wejściowej, na wyjściu powinniśmy dostać listę 24, 12, 8, 6. Dokładnie tak, jak w analizie zrobionej we wprowadzeniu do artykułu.

Nasza wyjściowa tablica zostanie nazwana retArr. Może nie jest to zbyt trafne nazwanie zmiennej, ale na potrzeby tego zadania wystarczy. To, co musimy zrobić z taką tablicą, to stworzyć ją z wartościami początkowymi równymi 1. Dlaczego tak? A no dlatego, że cyfra 1 jest obojętna w przypadku mnożenia, gdyby były tam zera, to już mnożenie przez 0 wypaczy nasz wynik.

RetArr w takim przypadku na start będzie wyglądać tak => [1, 1, 1, 1]. Pamiętajmy, że musi ona mieć taką samą długość, jak tabela wejściowa, czyli 4.

Kolejnym krokiem jest zadeklarowanie trzech zmiennych pomocniczych — left, right oraz size. Ostatnia zmienna potrzebna będzie nam do jedynej pętli programu. Zmienne left i right omówię za chwilę.

Główna pętla programu

Teraz czas na magię. Pętla będzie nam wykonywać się od pierwszego do ostatniego elementu tylko raz. Więc musimy w sprytny sposób uzupełniać tablicę wyjściową. Najlepiej działanie pętli zobrazuje poniższy opis.

PIERWSZA ITERACJA

Mnożymy pierwszy i ostatni element listy przez zmienną left i right

[1 * left(1), 1, 1, 1 * right(1)]

retarr = [1, 1, 1, 1]

Zmienną left przemnażamy przez pierwszy element listy wejściowej i wynosić będzie 1

Zmienną right przemnażamy przez ostatni element listy wejściowej i wynosić będzie 4

 

DRUGA ITERACJA

Mnożymy drugi i trzeci element listy przez zmienną left i right

[1, 1 * left(1), 1 * right(4), 1]

retarr = [1, 1, 4, 1]

Zmienną left przemnażamy przez drugi element listy wejściowej i wynosić będzie 2

Zmienną right przemnażamy przez trzeci element listy wejściowej i wynosić będzie 12

 

TRZECIA ITERACJA

Mnożymy trzeci i drugi element listy przez zmienną left i right

[1, 1 * RIGHT(12), 4 * LEFT(2), 1]

retarr = [1, 12, 8, 1]

Zmienną left przemnażamy przez trzeci element listy listy wejściowej i wynosić będzie 6

Zmienną right przemnażamy przez drugi element listy wejściowej i wynosić będzie 24

 

CZWARTA ITERACJA

Mnożymy czwarty i pierwszy element listy przez zmienną left i right

[1 * right(24), 12, 8, 1 * LEFT(6)]

retarr = [24, 12, 8, 6]

Po czwartej iteracji mamy gotowy wynik. Jak możesz zauważyć, zmienna left pomaga przejść tablicę od lewej do prawej strony, zmienna right natomiast od prawej do lewej. I to wszystko w jednej pętli! Piękne rozwiązanie prawda?

Dodatkowo powyższy algorytm jest jednym ze sposobów na to, by pozbyć się pętli podrzędnej, która operuje na tych samych danych co pętla nadrzędna.

Poniżej rozwiązanie w pięciu językach.

Python 3

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        retArr = [1] * len(nums)

        left = 1
        right = 1
        size = len(nums)

        for x in range(size):
            retArr[x] *= left
            retArr[-1 - x] *= right
            left *= nums[x]
            right *= nums[-1 - x]

        return retArr

Java

import java.util.Arrays;
class Solution {
    public static int[] productExceptSelf(int[] nums) {
        int[] retArr = new int[nums.length];
        Arrays.fill(retArr, 1);
        int left = 1;
        int right = 1;
        int size = nums.length;
        for (int i = 0; i < nums.length; i++)
        {
            retArr[i] *= left;
            retArr[size - 1] *= right;
            left *= nums[i];
            right *= nums[size - 1];

            size -= 1;
        }

        return retArr;
    }
}

C#

using System.Linq;

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        var retArr = Enumerable.Repeat<int>(1, nums.Length).ToArray();
        int left = 1;
        int right = 1;
        int size = nums.Length;
        for (int i = 0; i < nums.Length; i++)
        {
            retArr[i] *= left;
            retArr[size - 1] *= right;
            left *= nums[i];
            right *= nums[size - 1];

            size -= 1;
        }

        return retArr;  
    }
}

JavaScript

var productExceptSelf = function(nums) { 
   var retArr = Array(nums.length).fill(1)
   
   var left = 1;
   var right = 1;
   var size = nums.length;
   
   for (var i = 0; i < nums.length; i++)
   {        
        retArr[i] *= left;
        retArr[size - 1] *= right;
        left *= nums[i];
        right *= nums[size - 1];
        size -= 1;
    }
     
	return retArr;
};

C++

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        vector<int> retArr(nums.size(), 1);

        int left = 1;
        int right = 1;
        int size = nums.size();

        for (int i = 0; i < nums.size(); i++)
        {
            retArr[i] *= left;
            retArr[size - 1] *= right;
            left *= nums[i];
            right *= nums[size - 1];

            size -= 1;
        }

        return retArr;
    }
};

Iloczyn elementów tablicy — Podsumowanie

Zadania takie jak iloczyn elementów tablicy pokazują, że nie zawsze oczywiste rozwiązanie okazuje się tym najlepszym. Często też dwie pętle da się zastąpić jedną i ograniczyć czas wykonywania algorytmu. Grunt to zmienić sposób myślenia o zadanym problemie.

Jest to drugi wpis z serii zadań programistycznych, więc koniecznie daj znać, co o takiej formie myślisz i sprawdź pierwsze zadanie z platformy SPOJ, które miałem przyjemność rozwiązać we wpisie numer 9.

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!

PS4. Dołącz do naszego serwera na Discord!

Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci e-booka z 10 omówionymi algorytmami pojawiającymi się w pytaniach podczas REKRUTACJI.

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 419 osób!.
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.

Dołącz do naszego serwera Discord i rozmawiaj o programowaniu!

X