Anwendung der Zusammenführungssortierung in Java-Interviews
Nov 18, 2020 pm 03:41 PM
Hintergrund des Artikels:
Beim Durchsehen von Algorithmen und Datenstrukturen habe ich die im Interview geschriebenen Testfragen gefunden:
(Teilen von Lernvideos: Java-Lehrvideo)
In Das Array aus zwei Zahlen. Wenn die vorherige Zahl gr??er als die folgende Zahl ist, bilden die beiden Zahlen ein Paar in umgekehrter Reihenfolge. Geben Sie ein Array ein und ermitteln Sie die Gesamtzahl der Paare P in umgekehrter Reihenfolge im Array. Und geben Sie das Ergebnis von P modulo 1000000007 aus. Das hei?t, Ausgabe P%1000000007
Eingabebeschreibung:
Die Frage stellt sicher, dass sich nicht dieselbe Zahl im Eingabearray befindet
Datenbereich:
Für %50 Daten, Gr??e<=10^4
Für %75 Daten, Gr??e<=10^5
Für %100 Daten, Gr??e<=2*10^5
Analyse:
Diese Frage l?sst sich leicht direkt l?sen, aber die Zeitkomplexit?t betr?gt o(n*n), at Der Anfang Als ich diese Frage bekam, schrieb ich sie direkt in dp, ohne darüber nachzudenken. Dann stellte ich fest, dass dp nicht so gut ist wie die direkte L?sung. Die Komplexit?t betr?gt auch 2*10 ^5 Leerzeichen. Das Folgende ist direkt: Sowohl die Methode als auch dp haben eine Zeitüberschreitung.
(Empfehlungen für weitere verwandte Interviewfragen: Java-Interviewfragen und -antworten)
Codefreigabe:
//直接求法 ,超時(shí)
public class solution{
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
sum += 1;
}
}
sum %= 1000000007;
}
}
}public class solution{
//一維數(shù)組dp
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static int count[] = new int[200004];
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
count[j] = count[j+1]+1;
}else {
count[j] = count[j+1];
}
}
sum += count[0];
sum %= 1000000007;
for(int k = 0 ; k < array.length ; k ++)
count[k] = 0;
}
}
}dp ist hier überflüssig.
Das Folgende ist eine L?sung für die Zusammenführungssortierung. Wenn Sie die Zusammenführungssortierung nicht verstehen, Sie k?nnen mich sehen. Vorheriger Blog Merge-Sortierung:
public class solution{
//歸并排序AC
public static int cnt ;
public static int InversePairs(int [] array) {
if(array != null){
RecusionSorted(array,0,array.length - 1);
}
return cnt%1000000007;
}
public static void MegerArray(int[] data, int start, int mid, int end) {
int temp[] = new int[end-start+1];
int i = mid;
int j = end;
int m = mid+1;
int z = 0;
while(j >= m && i >= start) {
if(data[i] > data[j]) {
temp[z++] = data[i--];
cnt += (j-mid)%1000000007;
cnt %= 1000000007;
}else {
temp[z++] = data[j--];
}
}
while(j >= m) {
temp[z++] = data[j--];
}
while(i >= start) {
temp[z++] = data[i--];
}
for(int k = start ; k <= end ; k ++) {
data[k] = temp[end - k];
}
}
public static void RecusionSorted(int data[] , int start , int end ) {
if(start < end) {
int mid = (start + end) >> 1;
RecusionSorted(data,start,mid);
RecusionSorted(data,mid+1,end);
MegerArray(data,start,mid,end);
}
}
}Verwandte Empfehlungen: Java-Einführungs-Tutorial
Das obige ist der detaillierte Inhalt vonAnwendung der Zusammenführungssortierung in Java-Interviews. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Hei?e KI -Werkzeuge
Undress AI Tool
Ausziehbilder kostenlos
Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos
AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.
Clothoff.io
KI-Kleiderentferner
Video Face Swap
Tauschen Sie Gesichter in jedem Video mühelos mit unserem v?llig kostenlosen KI-Gesichtstausch-Tool aus!
Hei?er Artikel
Hei?e Werkzeuge
Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor
SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen
Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung
Dreamweaver CS6
Visuelle Webentwicklungstools
SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)
Wie gehe ich mit Transaktionen in Java mit JDBC um?
Aug 02, 2025 pm 12:29 PM
Um JDBC -Transaktionen korrekt zu verarbeiten, müssen Sie zun?chst den automatischen Komiti -Modus ausschalten und dann mehrere Vorg?nge ausführen und schlie?lich entsprechend den Ergebnissen festlegen oder rollen. 1. Nennen Sie Conn.SetAutoCommit (False), um die Transaktion zu starten. 2. Führen Sie mehrere SQL -Operationen aus, z. B. einfügen und aktualisieren. 3. Rufen Sie Conn.Commit () an, wenn alle Vorg?nge erfolgreich sind, und rufen Sie Conn.Rollback () auf, wenn eine Ausnahme auftritt, um die Datenkonsistenz zu gew?hrleisten. Gleichzeitig sollten Try-with-Ressourcen verwendet werden, um Ressourcen zu verwalten, Ausnahmen ordnungsgem?? zu behandeln und Verbindungen zu schlie?en, um Verbindungsleckage zu vermeiden. Darüber hinaus wird empfohlen, Verbindungspools zu verwenden und Save -Punkte zu setzen, um teilweise Rollback zu erreichen und Transaktionen so kurz wie m?glich zu halten, um die Leistung zu verbessern.
Wie arbeite man mit Kalender in Java?
Aug 02, 2025 am 02:38 AM
Verwenden Sie Klassen im Java.Time -Paket, um das alte Datum und die Kalenderklassen zu ersetzen. 2. Erhalten Sie das aktuelle Datum und die aktuelle Uhrzeit durch LocalDate, LocalDatetime und Local Time; 3. Erstellen Sie ein bestimmtes Datum und eine bestimmte Uhrzeit mit der von () Methode; 4.. Verwenden Sie die Plus/Minus -Methode, um die Zeit nicht zu erh?hen und zu verkürzen. 5. Verwenden Sie ZonedDatetime und zoneId, um die Zeitzone zu verarbeiten. 6. Format und analysieren Sie Datumszeichenfolgen über DateTimeFormatter; 7. Verwenden Sie sofortige, um bei Bedarf mit den alten Datumstypen kompatibel zu sein. Die Verarbeitung der Datum in der modernen Java sollte der Verwendung von Java.Timeapi vorrangig machen, was klare, unver?nderliche und linear ist
Vergleich von Java Frameworks: Spring Boot vs Quarkus gegen Micronaut
Aug 04, 2025 pm 12:48 PM
Pre-Formancetartuptimemoryusage, QuarkusandmicronautleadduToCompile-Time-foringandgraalvSupport, WithQuarkusofttenperformLightBetterin serverloser Szenarien.2. Thyvelopecosystem,
Wie funktioniert die Müllsammlung in Java?
Aug 02, 2025 pm 01:55 PM
Die Müllsammlung von Java (GC) ist ein Mechanismus, der automatisch den Speicher verwaltet, der das Risiko eines Speicherlecks verringert, indem unerreichbare Objekte zurückgeführt werden. 1.GC beurteilt die Zug?nglichkeit des Objekts aus dem Stammobjekt (z. B. Stapelvariablen, aktive Threads, statische Felder usw.) und nicht erreichbare Objekte als Müll markiert. 2. Basierend auf dem markierten Algorithmus markieren Sie alle erreichbaren Objekte und l?schen Sie nicht markierte Objekte. 3.. Verfolgen Sie eine Generationskollektionsstrategie: Die neue Generation (Eden, S0, S1) führt h?ufig MollGC aus; Die ?lteren Menschen erzielen weniger, dauert jedoch l?nger, um MajorGC durchzuführen. MetaPace speichert Klassenmetadaten. 4. JVM bietet eine Vielzahl von GC -Ger?ten: SerialGC ist für kleine Anwendungen geeignet; ParallelgC verbessert den Durchsatz; CMS reduziert sich
Gehen Sie zum Beispiel für HTTP Middleware -Protokollierung
Aug 03, 2025 am 11:35 AM
HTTP-Protokoll Middleware in Go kann Anforderungsmethoden, Pfade, Client-IP und zeitaufw?ndiges Aufzeichnen aufzeichnen. 1. Verwenden Sie http.Handlerfunc, um den Prozessor zu wickeln, 2. Nehmen Sie die Startzeit und die Endzeit vor und nach dem Aufrufen als n?chstes auf. Der vollst?ndige Beispielcode wurde überprüft, um auszuführen und eignet sich zum Starten eines kleinen und mittelgro?en Projekts. Zu den Erweiterungsvorschl?gen geh?ren das Erfassen von Statuscodes, die Unterstützung von JSON -Protokollen und die Nachverfolgung von ID -IDs.
Verwenden von HTML `Input` -Typen für Benutzerdaten
Aug 03, 2025 am 11:07 AM
Durch die Auswahl des richtigen HTMlinput -Typs kann die Datengenauigkeit verbessert, die Benutzererfahrung verbessert und die Benutzerfreundlichkeit verbessert werden. 1. W?hlen Sie die entsprechenden Eingabetypen gem?? dem Datentyp aus, z. B. Text, E -Mail, Tel, Nummer und Datum, die automatisch überprüft und an die Tastatur anpassen k?nnen. 2. Verwenden Sie HTML5, um neue Typen wie URL, Farbe, Reichweite und Suche hinzuzufügen, die eine intuitivere Interaktionsmethode bieten k?nnen. 3.. Verwenden Sie Platzhalter und erforderliche Attribute, um die Effizienz und Genauigkeit der Formulierung zu verbessern. Es sollte jedoch beachtet werden, dass der Platzhalter das Etikett nicht ersetzen kann.
Vergleich von Java -Build -Werkzeugen: Maven vs. Gradle
Aug 03, 2025 pm 01:36 PM
GradleStheBetterChoiceFormostnewProjectsDuetoitSuperiorFlexibilit?t, Leistung und ModerntoolingSupport.1.GRADLE'SGROOVY/KOTLINDSLISMORECONCISEANDEIPRESSIVETHANMANMANBOSEXML.2.GRAGRECONCISEANDEPRPRESSIVETHANMAVENSVOSEXML.2.
Gehen Sie mit einer Beispielverschiebung erkl?rt
Aug 02, 2025 am 06:26 AM
Auf Defer wird verwendet, um bestimmte Vorg?nge auszuführen, bevor die Funktion zurückgibt, z. B. die Reinigungsressourcen. Die Parameter werden sofort bewertet, wenn sie aufgeschoben werden, und die Funktionen werden in der Reihenfolge von Last-In-First-Out (LIFO) ausgeführt. 1. Mehrere Defers werden in umgekehrter Reihenfolge der Erkl?rungen ausgeführt. 2. h?ufig für die sichere Reinigung wie das Schlie?en von Dateien verwendet; 3. Der benannte Rückgabewert kann ge?ndert werden; V. 5. Vermeiden Sie den Missbrauch von Verschiebungen in Schleifen, um Ressourcenleckage zu verhindern. Die korrekte Verwendung kann die Sicherheit und die Lesbarkeit der Code verbessern.
