Biorąc pod uwagę macierz NxN z 0 i 1. Ustaw każdy wiersz zawierający a 0
na wszystkie 0
s i ustaw każdą kolumnę zawierającą a 0
na wszystkie 0
s.
Na przykład
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
prowadzi do
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
Inżynier Microsoft powiedział mi, że istnieje rozwiązanie, które nie wymaga dodatkowej pamięci, tylko dwie zmienne boolowskie i jeden przebieg, więc szukam odpowiedzi.
Przy okazji, wyobraź sobie, że jest to macierz bitowa, dlatego tylko 1s i 0s mogą być w macierzy.
algorithm
optimization
puzzle
jaircazarin-old-account
źródło
źródło
Odpowiedzi:
Ok, więc jestem zmęczony, bo tu jest 3 rano, ale mam pierwszą próbę w miejscu z dokładnie 2 przebiegami na każdej liczbie w macierzy, więc w O (NxN) i jest liniowa w rozmiarze matrycy.
Używam pierwszej kolumny i pierwszego wiersza jako znaczników, aby wiedzieć, gdzie są wiersze / kolumny zawierające tylko jedynki. Następnie są 2 zmienne l i c do zapamiętania, jeśli pierwszy wiersz / kolumna to również 1. Tak więc pierwsze przejście ustawia znaczniki, a resztę resetuje do zera.
Drugi przebieg ustawia 1 w miejscach, w których rzędy i kolumny były oznaczone jako 1, i resetuje 1 linię / kolumnę w zależności od l i c.
Wątpię mocno, że da się zrobić w 1 przejściu, ponieważ kwadraty na początku zależą od kwadratów na końcu. Może moje drugie przejście będzie bardziej wydajne ...
źródło
Nie można tego zrobić w jednym przebiegu, ponieważ pojedynczy bit ma wpływ na bity przed i po nim w dowolnej kolejności. IOW Niezależnie od kolejności, w jakiej przechodzisz przez tablicę, możesz później napotkać 0, co oznacza, że musisz cofnąć się i zmienić poprzednie 1 na 0.
Aktualizacja
Wydaje się, że ludzie myślą, że ograniczając N do jakiejś stałej wartości (powiedzmy 8), można rozwiązać ten problem w jednym przebiegu. Cóż, to a) pomijam sedno ib) nie jest to oryginalne pytanie. Nie zadałbym pytania na temat sortowania i oczekiwałbym odpowiedzi zaczynającej się od „zakładając, że chcesz posortować tylko 8 rzeczy ...”.
To powiedziawszy, rozsądne podejście jest, jeśli wiesz, że N jest w rzeczywistości ograniczone do 8. Moja odpowiedź powyżej odpowiada na pierwotne pytanie, które nie ma takiego powtórzenia.
źródło
Więc moim pomysłem jest użycie wartości w ostatnim wierszu / kolumnie jako flagi wskazującej, czy wszystkie wartości w odpowiedniej kolumnie / wierszu to 1.
Za pomocą zygzaka przeskanuj całą macierz Z WYJĄTKIEM ostatniego wiersza / kolumny. W każdym elemencie ustawiasz wartość w ostatnim wierszu / kolumnie jako logiczne AND samego siebie z wartością w bieżącym elemencie. Innymi słowy, jeśli trafisz 0, ostatni wiersz / kolumna zostanie ustawiony na 0. Jeśli wybierzesz 1, wartość w ostatnim wierszu / kolumnie będzie wynosić 1 tylko wtedy, gdy już wynosiła 1. W każdym razie ustaw bieżący element na 0.
Kiedy skończysz, ostatni wiersz / kolumna powinien mieć 1s, jeśli odpowiadająca mu kolumna / wiersz został wypełniony 1s.
Wykonaj liniowe skanowanie ostatniego wiersza i kolumny i wyszukuj jedynki. Ustaw 1 w odpowiednich elementach w treści macierzy, gdzie ostatni wiersz i kolumna to jedynki.
Kodowanie będzie trudne, aby uniknąć błędów typu off-by-one itp., Ale powinno działać w jednym przebiegu.
źródło
Mam tutaj rozwiązanie, które działa w jednym przebiegu i wykonuje całe przetwarzanie „na miejscu” bez dodatkowej pamięci (z wyjątkiem powiększania stosu).
Używa rekurencji, aby opóźnić pisanie zer, co oczywiście zniszczyłoby macierz dla innych wierszy i kolumn:
źródło
Myślę, że to nie jest wykonalne. Kiedy jesteś na pierwszym kwadracie, a jego wartość wynosi 1, nie masz możliwości sprawdzenia, jakie są wartości innych kwadratów w tym samym wierszu i kolumnie. Musisz więc je sprawdzić i jeśli jest zero, wróć do pierwszego kwadratu i zmień jego wartość na zero. Polecam zrobić to w dwóch przebiegach - pierwszy przebieg zbiera informacje o tym, które wiersze i kolumny należy wyzerować (informacje są przechowywane w tablicy, więc używamy dodatkowej pamięci). Drugi przebieg zmienia wartości. Wiem, że nie jest to rozwiązanie, którego szukasz, ale myślę, że jest praktyczne. Ograniczenia podane przez Ciebie sprawiają, że problem jest nierozwiązywalny.
źródło
Mogę to zrobić z dwiema zmiennymi całkowitymi i dwoma przebiegami (do 32 wierszy i kolumn ...)
źródło
~
odwraca wszystkie bity w zmiennej. 0x00000000 staje się 0x00000000. Zasadniczo zaczynam od wszystkich i usuwam bit dla wiersza / kolumny, gdy znajdę 0. CompleteCols ma ustawione bity 2 i 3, a CompleteRows ma ustawione bity 2 i 4 (oparte na 0).problem można rozwiązać za jednym razem
zapis macierzy w tablicy i X j.
teraz wypisz wszystkie wartości jako 0 dla wartości i i j zapisanych w aib pozostałe wartości to 1 tj. (3,3) (3,4) (5,3) i (5,4)
źródło
Innym rozwiązaniem, które wymaga dwóch przebiegów, jest gromadzenie AND w poziomie i w pionie:
Pomyślałem, że mógłbym zaprojektować taki algorytm przy użyciu bitów parzystości , kodów Hamminga lub programowania dynamicznego , prawdopodobnie używając tych dwóch wartości logicznych jako liczby 2-bitowej, ale nie odniosłem jeszcze sukcesu.
Czy możesz ponownie sprawdzić opis problemu ze swoim inżynierem i powiadomić nas o tym? Jeśli tam jest rzeczywiście rozwiązaniem, chcę zachować Zmniejszanie problemu.
źródło
Zachowaj jedną zmienną, aby śledzić, jakie są wszystkie wiersze połączone operatorem AND.
Jeśli wiersz ma wartość -1 (wszystkie jedynki), ustaw następny wiersz jako odniesienie do tej zmiennej
Jeśli wiersz jest czymś innym niż 0. Możesz zrobić wszystko za jednym razem. Kod pseudo:
To powinno wystarczyć w jednym przebiegu - ale jest tu założenie, że N jest wystarczająco małe, aby procesor mógł wykonać operacje arytmetyczne w jednym wierszu, w przeciwnym razie będziesz musiał zapętlić każdy wiersz, aby określić, czy to wszystko 1 s lub nie, jak sądzę. Ale biorąc pod uwagę, że pytasz o algorytmy i nie ograniczasz mojego sprzętu, mógłbym po prostu rozpocząć swoją odpowiedź od „Zbuduj procesor obsługujący arytmetykę N-bitową ...”
Oto jeden przykład, jak można to zrobić w C. Uwaga: Twierdzę, że wartości i arr wzięte razem reprezentują tablicę, a p i numproduct są moim iteratorem, a zmienne iloczynu AND służą do implementacji problemu. (Mogłem zapętlić arr z arytmetyką wskaźników, aby sprawdzić poprawność mojej pracy, ale raz wystarczył!)
Daje to 0, 0, 6, 0, 6, co jest wynikiem dla podanych danych wejściowych.
Lub w PHP, jeśli ludzie uważają, że moje gry na stackach w C oszukują (sugeruję, że tak nie jest, ponieważ powinienem móc przechowywać macierz w dowolny sposób):
Czy coś mi brakuje?
źródło
Niezłe wyzwanie. To rozwiązanie używa tylko dwóch wartości logicznych utworzonych na stosie, ale wartości logiczne są tworzone kilka razy na stosie, ponieważ funkcja jest rekurencyjna.
To skanuje w następujący sposób:
i tak dalej
A następnie zmiana wartości w tym wzorze po powrocie dla każdej z funkcji skanowania. (Od dołu do góry):
i tak dalej
źródło
Okej, to jest rozwiązanie
źródło
Tak właściwie. Jeśli chcesz tylko uruchomić algorytm i wydrukować wyniki (tj. Nie je przywrócić, możesz to łatwo zrobić w jednym przebiegu) .Kłopot pojawia się, gdy próbujesz zmodyfikować tablicę w trakcie wykonywania algorytmu.
Oto moje rozwiązanie. Po prostu polega na połączeniu wartości wierszy / kolumn dla elementu Givein (i, j) i wydrukowaniu go.
źródło
Próbowałem rozwiązać ten problem w C #.
Użyłem dwóch zmiennych pętli (i i j) oprócz rzeczywistej macierzy in reprezentującej jej wymiar
Logika, której próbowałem:
Kod:
źródło
One Pass - przeszedłem dane wejściowe tylko raz, ale użyłem nowej tablicy i tylko dwóch dodatkowych zmiennych boolowskich.
źródło
Chociaż jest to niemożliwe, biorąc pod uwagę ograniczenia, najbardziej efektywnym przestrzennie sposobem na to jest przechodzenie przez matrycę w sposób nakładający się, naprzemienny rząd / kolumna, co dałoby wzór podobny do układania cegieł w zygzak:
Używając tego, przejdziesz do każdego wiersza / kolumny, jak wskazano, i jeśli napotkasz 0 w dowolnym momencie, ustaw zmienną logiczną i ponownie przejrzyj ten wiersz / kolumnę, ustawiając wpisy na 0.
Nie będzie to wymagało dodatkowej pamięci i użyje tylko jednej zmiennej boolowskiej. Niestety, jeśli „daleka” krawędź jest ustawiona na 0, jest to najgorszy przypadek i przechodzisz przez całą tablicę dwa razy.
źródło
utwórz macierz wyników i ustaw wszystkie wartości na 1. przejdź przez macierz danych, gdy tylko zostanie napotkane 0, ustaw kolumnę wiersza macierzy wyników na 0
Pod koniec pierwszego przejścia macierz wyników będzie zawierała poprawną odpowiedź.
Wygląda całkiem prosto. Czy brakuje mi jakiejś sztuczki? Czy nie możesz używać zestawu wyników?
EDYTOWAĆ:
Wygląda jak funkcja F #, ale to trochę oszukuje, ponieważ nawet jeśli wykonujesz pojedynczy przebieg, funkcja może być rekurencyjna.
Wygląda na to, że ankieter próbuje dowiedzieć się, czy znasz programowanie funkcjonalne.
źródło
Cóż, wymyśliłem jednoprzebiegowe, na miejscu (nierekurencyjne) rozwiązanie wykorzystujące 4 boole i 2 liczniki pętli. Nie udało mi się zredukować go do 2 booli i 2 int, ale nie zdziwiłbym się, gdyby to było możliwe. Wykonuje około 3 odczytów i 3 zapisów dla każdej komórki i powinno być O (N ^ 2) tj. liniowy w rozmiarze tablicy.
Rozwikłanie tego rozwiązania zajęło mi kilka godzin - nie chciałbym wymyślać tego pod presją wywiadu! Jeśli zrobiłem booboo, jestem zbyt zmęczony, żeby to zauważyć ...
Um ... Zdecydowałem się zdefiniować „jednoprzebiegowe” jako wykonanie jednego przeciągnięcia po macierzy, zamiast dotykania każdej wartości raz! :-)
źródło
Mam nadzieję, że spodoba Ci się moje jednoprzebiegowe rozwiązanie C #
możesz pobrać element za pomocą O (1) i potrzebujesz tylko miejsca na jeden wiersz i jedną kolumnę macierzy
źródło
1 przebieg, 2 wartości logiczne. Muszę tylko założyć, że indeksy całkowite w iteracjach się nie liczą.
To nie jest kompletne rozwiązanie, ale nie mogę przejść tego punktu.
Gdybym tylko mógł określić, czy 0 jest oryginalnym 0, czy 1, które zostało przekonwertowane na 0, nie musiałbym używać -1 i to zadziałałoby.
Moje wyniki wyglądają następująco:
Oryginalność mojego podejścia polega na wykorzystaniu pierwszej połowy badania wiersza lub kolumny do określenia, czy zawiera 0, a ostatniej połowy do ustawienia wartości - odbywa się to poprzez spojrzenie na x i szerokość-x, a następnie y i wysokość -y w każdej iteracji. Opierając się na wynikach pierwszej połowy iteracji, jeśli znaleziono 0 w wierszu lub kolumnie, używam ostatniej połowy iteracji, aby zmienić 1 na -1.
Właśnie zdałem sobie sprawę, że można to zrobić mając tylko 1 wartość logiczną, która pozostawia 1 do ...?
Publikuję to, mając nadzieję, że ktoś powie: „Ach, po prostu zrób to ...” (I spędziłem zbyt dużo czasu, żeby nie publikować).
Oto kod w VB:
źródło
Nikt nie używa formularzy binarnych? ponieważ jest to tylko 1 i 0. Możemy używać wektorów binarnych.
Oto test:
A wynik:
źródło
Możesz zrobić coś takiego, aby użyć jednego przebiegu, ale macierzy wejścia i wyjścia:
gdzie
col(xy)
jest bitami w kolumnie zawierającej punktxy
;row(xy)
to bity w wierszu zawierającym punktxy
.n
jest rozmiarem macierzy.Następnie po prostu wykonaj pętlę nad wejściem. Czy istnieje możliwość rozbudowy, aby zajmować więcej miejsca?
źródło
Jeden skan macierzy, dwie wartości logiczne, bez rekursji.
Jak uniknąć drugiego przejścia? Drugie przejście jest potrzebne do wyczyszczenia wierszy lub kolumn, gdy na ich końcu pojawi się zero.
Jednak ten problem można rozwiązać, ponieważ kiedy skanujemy wiersz #i, znamy już stan wiersza dla wiersza # i-1. Tak więc, podczas skanowania wiersza #i, możemy jednocześnie wyczyścić wiersz # i-1, jeśli jest to potrzebne.
To samo rozwiązanie działa dla kolumn, ale musimy skanować wiersze i kolumny jednocześnie, podczas gdy dane nie są zmieniane przez kolejną iterację.
Do przechowywania stanu pierwszego wiersza i pierwszej kolumny wymagane są dwie wartości logiczne, ponieważ ich wartości zostaną zmienione podczas wykonywania głównej części algorytmu.
Aby uniknąć dodawania większej liczby wartości logicznych, przechowujemy flagę „wyczyść” dla wierszy i kolumn w pierwszym wierszu i kolumnie macierzy.
źródło
wygląda na to, że następujące prace nie wymagają dodatkowego miejsca:
Najpierw zauważ, że pomnożenie elementów wiersza razy elementów wiersza, w którym znajduje się element, daje żądaną wartość.
Aby nie używać dodatkowej przestrzeni (nie tworzyć nowej macierzy i wypełniać ją, ale zamiast tego bezpośrednio wprowadzać zmiany w macierzy), należy rozpocząć od lewej górnej części macierzy i wykonać obliczenia dla dowolnej macierzy ixi (która „zaczyna się” od (0 , 0)) przed rozważeniem dowolnego elementu o dowolnym indeksie> i.
mam nadzieję, że to zadziała (nie mam testu)
źródło
Jest to TESTOWANE dla różnych N w C ++ i jest:
JEDNO PRZEJŚCIE , DWA BOOLE , BEZ REKURSJI , BEZ DODATKOWEJ PAMIĘCI , PRZYSŁUGUJE SIĘ NA DROBNO DUŻE N
(Póki co żadne z przedstawionych tutaj rozwiązań nie obsługuje WSZYSTKICH).
Mówiąc dokładniej, zabawne są dwa liczniki pętli. Mam dwie const unsigneds, które istnieją tylko zamiast być obliczane za każdym razem dla czytelności. Interwał pętli zewnętrznej to [0, N], a przedział pętli wewnętrznej to [1, n - 1]. Instrukcja switch jest w pętli głównie po to, aby bardzo wyraźnie pokazać, że tak naprawdę jest to tylko jeden przebieg.
Strategia algorytmu:
Pierwszą sztuczką jest dla nas wiersz i kolumna z samej macierzy, aby zgromadzić zawartość macierzy, ta pamięć staje się dostępna poprzez przeniesienie wszystkiego, co naprawdę musimy wiedzieć, z pierwszego wiersza i kolumny na dwie wartości logiczne. Druga sztuczka polega na uzyskaniu dwóch przebiegów z jednego, używając symetrii podmacierzy i jej indeksów.
Streszczenie algorytmu:
Implementacja w języku C ++ oparta na szablonach:
źródło
Ok, zdaję sobie sprawę, że to nie do końca pasuje, ale otrzymałem to w jednym przebiegu, używając bool i bajtu zamiast dwóch bool ... blisko. Nie ręczyłbym również za jego skuteczność, ale tego typu pytania często wymagają mniej niż optymalnych rozwiązań.
źródło
Możesz to zrobić w jednym przebiegu - jeśli nie liczysz dostępu do matrycy w kolejności losowej, co eliminuje korzyści płynące z robienia tego w jednym przejściu (spójność pamięci podręcznej / przepustowość pamięci).
[edytuj: usunięto proste, ale złe rozwiązanie]
Powinieneś uzyskać lepszą wydajność niż jakakolwiek metoda jednoprzebiegowa, wykonując to w dwóch przebiegach: jeden do gromadzenia informacji o wierszach / kolumnach, a drugi do ich zastosowania. Dostęp do tablicy (w kolejności wiersz-główny) jest spójny; dla tablic przekraczających rozmiar pamięci podręcznej (ale których wiersze mieszczą się w pamięci podręcznej), dane powinny być odczytywane z pamięci dwukrotnie i zapisywane raz:
źródło
Najprostsze rozwiązanie, jakie przychodzi mi do głowy, jest wklejone poniżej. Logika polega na zapisaniu, który wiersz i kolumna mają ustawić zero podczas iteracji.
źródło
Oto moja implementacja Ruby z dołączonym testem, zajęłoby to miejsce O (MN). Jeśli chcemy aktualizacji w czasie rzeczywistym (np. Aby pokazać wyniki, gdy znajdziemy zera, zamiast czekać na pierwszą pętlę znajdowania zer), możemy po prostu utworzyć inną zmienną klasy, jak
@output
i zawsze, gdy znajdziemy zero, aktualizujemy,@output
a nie@input
.źródło
Poniższy kod tworzy macierz o rozmiarze m, n. Najpierw zdecyduj o wymiarach macierzy. Chciałem wypełnić macierz [m] [n] losowo liczbami z zakresu 0..10. Następnie utwórz kolejną macierz o tych samych wymiarach i wypełnij ją -1s (ostateczna macierz). Następnie wykonaj iterację przez początkową macierz, aby zobaczyć, czy trafisz 0. Kiedy trafisz w położenie (x, y), przejdź do ostatniej macierzy i wypełnij wiersz x zerami, a kolumnę y zerami. Na koniec przeczytaj końcową macierz, jeśli wartość wynosi -1 (wartość oryginalna), skopiuj wartość w tym samym miejscu początkowej macierzy do ostatecznej.
źródło
oto moje rozwiązanie. Jak widać z kodu, biorąc pod uwagę macierz M * N, ustawia ona cały wiersz na zero po sprawdzeniu zera w tym wierszu. Złożoność czasowa mojego rozwiązania wynosi O (M * N). Udostępniam całą klasę, która ma statyczną wypełnioną tablicę do testowania i metodę tablicy wyświetlania, aby zobaczyć wynik w konsoli.
}
źródło