Beantworten Sie bei einer nicht negativen Liste der Skyline-Höhen ganzzahlig, wie viele ununterbrochene horizontale Pinselstriche mit einer Höhe von 1 Einheit erforderlich sind, um die Skyline abzudecken.
[1,3,2,1,2,1,5,3,3,4,2]
, visualisiert als:
5
5 4
3 5334
32 2 53342
13212153342
braucht neun Pinselstriche:
1
2 3
4 5555
66 7 88888
99999999999
Beispiele
[1,3,2,1,2,1,5,3,3,4,2]
→ 9
[5,8]
→ 8
[1,1,1,1]
→ 1
[]
→ 0
[0,0]
→ 0
[2]
→ 2
[2,0,2]
→ 4
[10,9,8,9]
→ 11
Antworten:
JavaScript (Node.js) , 38 Byte
Probieren Sie es online!
Einfach ein gieriger Algorithmus, der von links nach rechts scannt, nur bei Bedarf Linien zeichnet und diese so lange wie möglich zeichnet.
Danke Arnauld, spare
23 Bytesquelle
05AB1E ,
8 75 Bytes2 Bytes dank @Adnan gespart
Probieren Sie es online!
Wie?
Hierbei wird der Algorithmus verwendet, der zuerst von @tsh gefunden wurde . Wenn Ihnen diese Antwort gefällt, stellen Sie sicher, dass Sie auch die Antwort positiv bewerten !
Jedes Mal, wenn ein Wolkenkratzer niedriger als oder so hoch wie der vorherige ist, kann er durch einfaches Ausfahren der Pinselstriche "kostenlos" bemalt werden.
Das Malen der Wolkenkratzer und in der folgenden Abbildung kostet beispielsweise nichts.B C
Auf der anderen Seite brauchen wir 2 neue Pinselstriche, um Wolkenkratzer zu malen , egal ob sie danach wiederverwendet werden oder nicht.E
Für den ersten Wolkenkratzer brauchen wir immer so viele Pinselstriche, wie Böden darin sind.
Das in Mathematik umwandeln:
Wenn wir der Liste voranstellen , kann dies vereinfacht werden, um:0
Kommentiert
quelle
0š¥ʒd}O
spart dir ein Byte.ʒd}
durchþ
sollten Sie zwei Bytes sparen.Python 3 , 37 Bytes
Probieren Sie es online!
-5 Bytes durch Umstieg auf Python 3 dank Sarien
Python 2 ,
474342 BytesProbieren Sie es online!
Alt:
Probieren Sie es online!
quelle
Haskell , 32 Bytes
Probieren Sie es online!
Eine Verbesserung von Lynns Lösung , die das vorherige Element verfolgt,
p
anstatt das nächste Element zu betrachten. Dies verkürzt den Basisfall und den rekursiven Aufruf, wenn ein Aufruf erforderlich ist(0%)
.max(h-p)0
könntemax h p-p
für die gleiche Länge sein.quelle
Haskell , 35 Bytes
Probieren Sie es online!
Linie 2 könnte sein,
f[a]=a
wenn ich den Fall nicht auch behandeln müsste[]
.quelle
K (OK) ,
127 Bytes-5 Bytes dank ngn!
Ein k (oK) -Port der 05AB1E-Lösung von Arnauld (und der JavaScript-Lösung von tsh):
Probieren Sie es online!
J , 15 Bytes
AJ-Port der 05AB1E-Lösung von Arnauld (und der JavaScript-Lösung von tsh):
Probieren Sie es online!
Meine naive Lösung:
J , 27 Bytes
Probieren Sie es online!
quelle
':
) verwendet ein implizites Identitätselement (0
for-
) vor der Liste,0,
ist also nicht erforderlich. Sie können es unterlassen{
x}
, eine Komposition daraus zu machen:+/0|-':
Some primitive verbs result in a different special-cased initial value: +, *, - and & are provided with 0, 1, 0 or the first element of the sequence, respectively
Haskell ,
3432 Bytes2 Bytes von Lynn getrimmt
Probieren Sie es online!
Also zu Beginn haben wir
zipWith(-)
. Dies nimmt zwei Listen und erzeugt eine neue Liste ihrer paarweisen Unterschiede. Wir kombinieren es dann mitx
und(0:x)
.(0:)
ist eine Funktion, die der Vorderseite einer Liste eine Null hinzufügt. Durch die Kombination mit dieser Funktion erhaltenzipWith(-)
wir die Unterschiede zwischen aufeinanderfolgenden Elementen dieser Liste mit einer Null an der Vorderseite. Dann setzen wir alle negativen auf Null mit(max 0<$>)
. Dadurch wird eine neue Liste erstellt, in der jedes Element die Anzahl der neuen Striche angibt, die an jedem Turm gestartet werden müssen. Um die Summe zu erhalten, addieren wir diese einfach mitsum
.quelle
g x=sum$max 0<$>zipWith(-)x(0:x)
ist 32 Bytes :)sum.zipWith((max 0.).(-))<*>(0:)
.
eine höhere Priorität haben als<*>
.Japt , 8 Bytes
-2 Bytes von @Shaggy
Erläuterung
Probieren Sie es online!
quelle
mîT Õ¸¸è
A.y()
's Polsterung.MATL , 8 Bytes
Probieren Sie es online!
So ziemlich der Algorithmus von @ Arnauld. 1 Byte gespart (danke @LuisMendo), indem auf positive Einträge gewechselt wurde,
uint64
anstatt sie auszuwählen)
.quelle
Gelee , 5 Bytes
Ein Port meiner 05AB1E-Antwort , der selbst der @tsh JS-Antwort ähnelt .
Probieren Sie es online!
Kommentiert
quelle
Japt ,
76 BytesVersuch es
Dank Oliver 1 Byte gespart.
quelle
R , 30 Bytes
Probieren Sie es online!
Portierung der @Arnauld-Lösung, die sich wiederum aus der @tsh-great-Lösung ergibt
quelle
Retina 0.8.2 , 21 Bytes
Probieren Sie es online! Link enthält Testfälle. Erläuterung:
In Unary konvertieren.
Löschen Sie alle Überlappungen mit dem nächsten Turm, für die kein neuer Strich erforderlich ist.
Zählen Sie die verbleibenden Striche.
quelle
Common Lisp,
8887 Bytesnicht minimiert
Probier es aus
Wenn ein Turm bemalt ist, sind mehrere Pinselstriche erforderlich, die seiner Höhe entsprechen. Diese Pinselstriche werden in alle folgenden übersetzt, was hier durch Subtrahieren der Höhe des aktuellen Turms von allen anderen Türmen (und von sich selbst, aber das spielt keine Rolle) angezeigt wird. Wenn ein nachfolgender Turm kürzer ist, wird er auf eine negative Zahl verschoben, und diese negative Zahl wird anschließend von den nachfolgenden Türmen abgezogen (was auf Pinselstriche hinweist, die nicht von einem vorherigen Turm auf den nächsten übertragen werden konnten). Es subtrahiert tatsächlich nur die Anzahl von allen Turmhöhen, einschließlich der vorherigen, aber das spielt keine Rolle, da wir die vorherigen nicht noch einmal betrachten.
quelle
05AB1E ,
1310 BytesProbieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
quelle
C # (Visual C # Interactive Compiler) mit Flag
/u:System.Math
, 47 ByteProbieren Sie es online!
Alte Version, mit Flag
/u:System.Math
, 63 BytesIch finde, diese Lösung ist eleganter als die erste. Es durchläuft das Array mit einem zweiwertigen Tupel als Startwert, nimmt Werte auf und speichert den Wert davor im zweiten Teil des Tupels.
Probieren Sie es online!
quelle
Pyth, 8 Bytes
Noch eine Portierung von @ tshs wunderbarer Antwort . Nimmt die Summe (
s
) der positiven Werte (>#0
) der Deltas (. +) Der Eingabe mit vorangestelltem Wert ( 0+0Q
, gefolgt von Q).Versuchen Sie es online hier oder überprüfen alle Testfälle auf einmal hier .
Zeichenkettenverbindungsmethode, 10 Bytes
Dies war die Lösung, die ich geschrieben habe, bevor ich die anderen Antworten durchgesehen habe.
Testsuite.
quelle
Clojure, 50 Bytes
Probieren Sie es online! (Warum druckt das nichts?)
quelle
Java (JDK) , 57 Byte
Probieren Sie es online!
Ein weiterer Hafen von tsh ist Javascript Antwort . Stellen Sie also sicher, dass Sie sie positiv bewertet haben.
Beachten Sie, dass ich anstelle der Addition die Subtraktion verwendet habe, weil ich damit
(p=x)
in der gleichen Anweisung als rechter Operand schreiben konnte .quelle
MATL ,
151413 BytesDie Eingabe ist ein Spaltenvektor, der
;
als Trennzeichen verwendet wird.Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Erläuterung
quelle
Perl 5, 21 Bytes
TIO
Wie
-p
+}{
+$\
trick//
Entspricht einer leeren Zeichenfolge, sodass die Nachanpassung für die nächste Zeile$'
die vorherige Zeile enthält$\+=$_>$'&&$_-$'
um die Differenz zwischen der aktuellen und der vorherigen Zeile zu akkumulieren, wenn die aktuelle größer als die vorherige ist (könnte auch geschrieben werden$\+=$_-$' if$_>$'
, aber Perl parst nicht$\+=$_-$'if$_>$'
dasselbe)quelle
Stax , 8 Bytes
Führen Sie es aus und debuggen Sie es
Verwendet den weit verbreiteten Ansatz der JavaScript-Lösung von tsh.
quelle
Wolfram Language (Mathematica) , 34 Byte
Ein Port von @Arnauld 's Lösung .
Probieren Sie es online!
quelle