Array-Summierung
Bestimmen Sie bei einem gegebenen ganzzahligen Array a mit n Elementen die Summe aller Elemente in a. Sie denken vielleicht, dass es sehr einfach ist, ja, es ist tatsächlich einfach, aber warum sollten Sie es sagen? Es gibt zwei Gründe: Erstens erfordert diese Frage die Verwendung einer Rekursion, wobei nur eine Codezeile verwendet wird. Zweitens ist dies die erste Interviewfrage, die mir in meinem Leben begegnet ist, und sie hat eine besondere Bedeutung.
Vereinfacht ausgedrückt gibt es zwei Situationen:
Wenn die Anzahl der Array-Elemente 0 ist, dann ist die Summe 0.
Wenn die Anzahl der Elemente im Array n beträgt, ermitteln Sie zuerst die Summe der ersten n - 1 Elemente und fügen Sie dann a[n - 1] hinzu.
Code kopieren Der Code lautet wie folgt:
//Array sum
int sum(int *a, int n)
{
return n == 0 ? 0 : sum(a, n - 1) + a[n - 1];
}
Ermitteln Sie den Maximal- und Minimalwert des Arrays.
Ermitteln Sie bei einem gegebenen ganzzahligen Array a mit n Elementen den Maximal- und Minimalwert .
Der herkömmliche Ansatz besteht darin, einmal zu durchlaufen und den Maximal- bzw. Minimalwert zu ermitteln. Ich werde hier jedoch über die Divide-and-Conquer-Methode (Divide and Couquer) sprechen Finden Sie zuerst die Maximal- und Minimalwerte des Teils, dann die Maximal- und Minimalwerte der rechten Hälfte und kombinieren Sie sie, um die gesamten Maximal- und Minimalwerte zu ermitteln. Dies ist ein rekursiver Prozess, der nach der Division wiederholt wird, bis nur noch ein oder zwei Elemente im geteilten Intervall übrig sind.
Code kopieren Der Code lautet wie folgt:
// Finden Sie die Maximal- und Minimalwerte des Arrays. Der Rückgabewert liegt zwischen maxValue und minValue
void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue)
{
if(l == r) // Es gibt nur ein Element zwischen l und r
{
maxValue = a[l]; minValue = a[l];
return ;
}
if(l + 1 == r) // Es gibt nur zwei Elemente zwischen l und r
{
if (a[l] >= a [r])
{
maxValue = a[l] ;
minValue = a[r] }
else
{
maxValue = a[r] ;
minValue = a[l] ;
}
return ;
int m = (l + r) / ; / Finden Sie den Mittelpunkt
int lmax; // Maximaler Wert der linken Hälfte
int lmin; // Minimaler Wert der linken Hälfte
MaxandMin(a, l, m, lmax, lmin) ; // Rekursive Berechnung der linken Hälfte
int rmax ; // Der Maximalwert der rechten Hälfte
int rmin ; // Der Minimalwert der rechten Hälfte
MaxandMin(a, m + 1, r, rmax, rmin) ; / / Rekursiv die rechte Hälfte berechnen
maxValue = max(lmax, rmax); // Gesamtmaximalwert
minValue = min(lmin, rmin); / Gesamter Minimalwert
}
Ermitteln Sie den Maximalwert und den zweiten Maximalwert des Arrays.
Ermitteln Sie bei einem ganzzahligen Array mit n Elementen seinen Maximalwert und seinen zweiten Maximalwert.
Die Idee ähnelt der vorherigen Frage. Es werden auch keine weiteren Details verwendet. Schauen Sie sich einfach den Code an:
Der Code lautet wie folgt.
// Finden Sie den Maximalwert des Arrays und den zweitgrößten Wert. Der Rückgabewert liegt in Max und Second.
void MaxandMin(int *a, int left, int right, int &max, int &second)
{
if(left == right)
{
max = a[left] ;
second = a[left] ;
else if(left + 1 = = rechts)
{
max = a[left] > a[left] : a[right] ; [left] : a[right] ;
else
{
int mid = left + (right - left) / 2 ; leftmin ;
MaxandMin(a, left, mid, leftmax , leftmin) ;
int rightmin ; ;
max = leftmax ? leftmax ;
second = leftmax : rightmax ; die Elemente, die mehr als die Hälfte der Zeit im Array erscheinen
Gegeben a In einem Array a mit n ganzzahligen Elementen erscheint ein Element mehr als n / 2-mal. Es soll sich um eine Interviewfrage bei Baidu handeln.
Stellen Sie einen aktuellen Wert und einen Zähler für den aktuellen Wert ein, initialisieren Sie den aktuellen Wert auf das erste Element des Arrays, der Zählerwert ist 1, und durchlaufen Sie dann für jedes das gesamte Array beginnend mit dem zweiten Element durchlaufener Wert a[i].
Wenn a[i]==currentValue, wird der Zählerwert um 1 erhöht.
Wenn a[i] != currentValue, wird der Zählerwert um 1 dekrementiert. Wenn der Zählerwert kleiner als 0 ist, wird der aktuelle Wert auf a[i] aktualisiert und der Zählerwert auf 1 zurückgesetzt.
Code kopieren Der Code lautet wie folgt:
//Suchen Sie die Elemente, die mehr als die Hälfte der Male im Array vorkommen
int Find(int* a, int n)
{
int curValue = a[0] ;
int count = 1 ;
for (int i = 1; i
Eine andere Methode besteht darin, zuerst das Array zu sortieren und dann das mittlere Element zu nehmen Denn wenn die Anzahl eines Elements mehr als die Hälfte beträgt, muss das Element nach der Sortierung des Arrays die mittlere Position des Arrays einnehmen
Finden Sie den kürzesten Abstand der Elemente im Array
Finden Sie bei einem gegebenen ganzzahligen Array mit n Elementen die beiden Elemente x und y im Array, die den Wert von abs(x - y) minimieren.
Sortieren Sie zuerst das Array und durchlaufen Sie es dann einmal:
Kopieren Sie den Code. Der Code lautet wie folgt:
int Compare(const void* a, const void* b)
{
return *(int*)a - *(int*)b }
void MinimumDistance(int* a, int n)
{
// Sortieren
qsort (a, n, sizeof(int), vergleichen) ; // Index von Nummer 1
int j ; // Index von Nummer 2
int minDistance = numeric_limits< ;int>::max() ;
for (int k = 0; k < n - 1; ++k)
{
if (a[k + 1] - a[k] < minDistance)
{
minDistance = a[k + 1] - a[k] ;
j = a[k + 1 ]
}
cout << << i << " j = " << j
}
Gegeben zwei Elemente, die n sortierte (nicht absteigende) ganzzahlige Arrays a und b von Elementen enthalten, finden ihre gemeinsamen Elemente, zum Beispiel: a = 0, 1, 2, 3, 4 und b = 1, 3, 5, 7, 9, Ausgabe 1, 3.
Nutzen Sie die geordnete Natur des Arrays voll aus, verwenden Sie zwei Zeiger i und j, um auf a bzw. b zu zeigen, vergleichen Sie a[i] und b[j] und bewegen Sie den Zeiger entsprechend dem Vergleich Als Ergebnis gibt es drei Situationen wie folgt:
a[i] < ], dann werden sowohl i als auch j um 1 erhöht und der Vergleich wird fortgesetzt
a[i]
Wiederholen Sie den obigen Vorgang, bis i oder j das Ende des Arrays erreicht.
Code kopieren Der Code lautet wie folgt:
// Finden Sie die gemeinsamen Elemente zweier Arrays
void FindCommon(int* a, int* b, int n)
{
int i = 0;
int j = 0; 🎜>++i ; i] <<
++j ; 🎜>}
}
Es gibt andere Lösungen für dieses Problem. Führen Sie beispielsweise für jedes Element in a eine binäre Suche danach durch, da es n Elemente in a gibt. und für die Durchführung einer binären Suche in b ist eine Anmeldung erforderlich. Die Zeitkomplexität zum Finden aller gleichen Elemente beträgt also O(nlogn).
Außerdem spielt es für die obige Methode keine Rolle, ob a in Ordnung ist, solange b in Ordnung ist, da wir nur die binäre Suche in b durchführen. Wenn a ebenfalls geordnet ist, ist die Verwendung der obigen Methode etwas langsam, denn wenn die Position eines Elements in a in b k ist, muss die Position des nächsten Elements in a in b auf der rechten Seite von k liegen. So kann der Suchraum dieses Mal basierend auf den letzten Suchergebnissen eingegrenzt werden, anstatt weiterhin im gesamten b zu suchen. Das heißt, wenn a und b beide geordnet sind, kann der Code wie folgt geändert werden, um die Position des Elements in b während der letzten Suche als Ausgangspunkt für die nächste Suche aufzuzeichnen.
Finden Sie das gemeinsame Element der drei Arrays.
Bestimmen Sie bei drei ganzzahligen Arrays a, b und c mit n Elementen deren kleinstes gemeinsames Element.
Wenn alle drei Arrays geordnet sind, können Sie drei Zeiger so einstellen, dass sie auf die Köpfe der drei Arrays zeigen, und dann die Zeiger basierend auf dem Vergleich der von den drei Zeigern angezeigten Werte verschieben, bis die gemeinsames Element gefunden wird.
Code kopieren Der Code lautet wie folgt:
// Gemeinsame Elemente von drei Arrays – nur das kleinste finden
void FindCommonElements(int a[], int b[], int c[] , int x , int y, int z)
{
for(int i = 0, j = 0, k = 0; i < x && j < y && k < z;)
{
if(a[i] < b[j])
{
i++ ; ;
else // a[i] >= b[j]
{
if(b[j] < c[k])
{
j++ ;}
else // b[j] >= c[k]
{
if(c[k] < a[i])
{
k++ ; ;
else // c[k] >= a[i]
{
cout << c[k] <<
return ; < "Nicht gefunden!" << endl ; Und führen Sie eine binäre Suche in c durch.
Code kopieren Der Code lautet wie folgt:
// Finden Sie das eindeutige gemeinsame Element in 3 Arrays
// O(NlogN)
int UniqueCommonItem(int *a, int *b, int *c , int n )
{
// Array a sortieren
qsort(a, n, sizeof(int), vergleichen); // NlogN
// Array b sortieren
qsort(b , n, sizeof(int), vergleichen) ; // NlogN
// Führen Sie für jedes Element in Array c eine binäre Suche in a und b durch
// Dies gilt bis zu einer Komplexität von N*2*logN
for (int i = 0; i < n; i++)
{
if(BinarySearch(a, n, c[i] ) && BinarySearch(b, n, c[i]))
return c[i] ;
return - 1 ; // nicht gefunden
Sie können a auch sortieren und dann eine binäre Suche in a nach einem beliebigen Element in b und c durchführen.
Code kopieren Der Code lautet wie folgt:
// Finden Sie das eindeutige gemeinsame Element in 3 Arrays
// O(NlogN)
int UniqueCommonItem1(int *a, int *b, int *c , int n )
{
// sort array a
qsort(a, n, sizeof(int), vergleichen); // NlogN
// Raum für Zeit
bool *bb = new bool[n] ;
memset(bb, 0, n) ;
bool *bc = new bool[n] ;
// für jedes Element in b eine BS in a durchführen und alle gemeinsamen Elemente markieren
for (int i = 0; i < n; i++) // NlogN
{
if (BinarySearch(a, n, b[i]))
bb[i] = true ;
}
// für jedes Element in c nur dann eine BS durchführen, wenn b [i] ist wahr
for (int i = 0; i < n; i++) // NlogN
{
if(b[i] && BinarySearch(a, n, c[i]) )
return c[i] ;
}
return - 1 ; // nicht gefunden
}
Der Sortier- und Binärsuchcode lautet wie folgt:
Code kopieren Der Code lautet wie folgt:
// Bestimmen Sie, ob a den Wert k enthält
bool BinarySearch(int *a, int n, int k)
{
int left = 0;
int right = n - 1;
while (left <= right)
{
int mid = (left + right) ;
if(a[mid] < k )
left = mid + 1 ;
if(a[mid] == k)
return true ;
else
right = mid - 1 ; 🎜>return false ;
}
// Vergleichsfunktion für qsort
int Compare(const void* a, const void* b)
{
return *(int*) a - *(int*)b;
}
Zusammenfassend kann das Problem der Suche in einem Array in den folgenden zwei Situationen gelöst werden:
Wenn das angegebene Array geordnet ist , dann sollte zuerst an die binäre Suche gedacht werden, erforderlich O(logn).
Wenn das angegebene Array ungeordnet ist, sollten Sie zunächst daran denken, das Array in O(nlogn)-Zeit zu sortieren und dann die binäre Suche zu verwenden. Die Gesamtzeitkomplexität beträgt immer noch O(nlogn).
Wenn Sie die beiden oben genannten Punkte befolgen können, können die meisten Probleme bei der Array-Suche leicht gelöst werden.
Suchen Sie das einzige doppelte Element im Array.
Bei einem Array mit 1001 Elementen, das Ganzzahlen zwischen 1 und 1000 speichert, wird nur eine Ganzzahl dupliziert. Suchen Sie bitte diese Zahl.
Ermitteln Sie die Summe des gesamten Arrays und subtrahieren Sie dann die Summe von 1-1000. Der Code wird weggelassen.
Suchen Sie die Elemente, die ungerade oft vorkommen.
Gegeben ist ein ganzzahliges Array a mit n Elementen, in dem nur ein Element ungerade oft vorkommt. Suchen Sie dieses Element.
Denn für jede Zahl k gibt es k ^ k = 0, k ^ 0 = k. Wenn also alle Elemente in a XOR-verknüpft sind, wird das XOR der geraden Anzahl von Elementen zu 0, so dass übrig bleibt nur das Element mit einer ungeraden Zahl.
int FindElementWithOddCount(int *a, int n)
{
int r = a[0] ;
for (int i = 1; i
Finde das Array Zahlenpaare, die die gegebene Summe in Element j in b erfüllen, erfüllen i + j = d (d ist bekannt)
Die beiden Zeiger i und j zeigen auf den Anfang bzw. das Ende des Arrays und Fahren Sie dann gleichzeitig von beiden Enden zur Mitte, bis sich die beiden Zeiger kreuzen.
Code kopieren Der Code lautet wie folgt:
// Finden Sie das Zahlenpaar, das die angegebene Summe erfüllt
void FixedSum(int * a, int* b, int n, int d)
{
for (int i = 0, j = n - 1; i < n && j >= 0)
{
if (a[i] + b[j] < d)
++ i ;
else if (a[i] + b[j] == d)
{
cout << a[i] << else // a[i] + b[j] > d
--j ; Finden Sie die Summe der größten kontinuierlichen Untersegmente. Wenn die Summe eine negative Zahl ist, wird sie als 0 berechnet, z. B. 1, 2, -5, 6, 8, die Ausgabe ist 6 + 8 = 14.
Eine klassische Frage zur Programmierung, nicht viel zu sagen
Kopieren Sie den Code. Der Code lautet wie folgt:
// Sub Die maximale Summe des Arrays
int Sum(int* a, int n)
{
int curSum = 0;
for (int i = 0; i < n; i++)
{
if (curSum + a[i] < 0)
curSum = 0;
else
{
curSum += a[i] ;
}
}
return maxSum;
}
Maximales Teilsegmentprodukt
Bestimmen Sie bei einer gegebenen Ganzzahl a das Produkt des größten kontinuierlichen Teilsegments, z. B. 1, 2, -8, 12, 7. Ausgabe 12 * 7 = 84.
Achten Sie ähnlich wie bei der maximalen Teilsegmentsumme auf den Fall negativer Zahlen.
Code kopieren Der Code lautet wie folgt:
// Maximales Produkt von Unterarrays
int MaxProduct(int *a, int n)
{
int maxProduct = 1; // max positives Produkt an aktueller Position
int minProduct = 1; // min negatives Produkt an aktueller Position
int r = 1; // Ergebnis, maximale Multiplikation total
for (int i = 0; i < n; i++)
{
if (a[i] > 0)
{
maxProduct *= a[i]; ], 1) ;
}
else if (a[i] == 0)
{
maxProduct = 1;
minProduct = 1; / a[i ] < 0
{
int temp = maxProduct;
maxProduct = max(minProduct * a[i], 1); 🎜>}
r = max(r, maxProduct);
return r;
}
Array-Zirkelverschiebung
Konvertieren eines Arrays enthält n Elemente. Das zirkuläre Verschieben des Arrays um k Bits nach rechts erfordert eine Zeitkomplexität von O(n) und es können nur zwei zusätzliche Variablen verwendet werden. Dies ist eine Frage, die ich in Microsofts Beauty of Programming gesehen habe.
Wenn beispielsweise das Array 1 2 3 4 um 1 Bit nach rechts gedreht wird, wird es zu 4 1 2 3. Es ist ersichtlich, dass sich die Reihenfolge von 1 2 3 vor und nach der Verschiebung nicht geändert hat , wurde aber mit der Position 4 vertauscht, daher ist es äquivalent. Teilen Sie zunächst 1 2 3 4 in zwei Teile 1 2 3 | 4, kehren Sie dann die Reihenfolge von 1 2 3 um und kehren Sie dann die Reihenfolge von 4 um, um 3 2 1 zu erhalten 4, und kehren Sie schließlich die gesamte Reihenfolge um, um 4 1 2 3 zu erhalten.
Code kopieren Der Code lautet wie folgt:
// Kehrt die Elemente zwischen Anfang und Ende im Puffer um
void Reverse( int buffer[], int start, int end )
{
while ( start < end )
{
int temp = buffer[ start ] ;
buffer[ start++ ] = buffer[ end ] ;
buffer[ end-- ] = temp ; }
}
// Verschiebe den Array-Puffer mit n Elementen um k Bits nach rechts
void Shift( int buffer[], int n, int k)
{
k %= n ;
Reverse( buffer, 0, n - k - 1) ;
Reverse( buffer, n - k, n - 1 ) ; - 1 ) ;
}
String-Umkehrreihenfolge
Gegebenes Zeichenarray a mit n Elementen, kehren Sie es an der richtigen Stelle um.
Vielleicht denken Sie, dass es hier nicht um Arrays, sondern um Strings geht. Ja. Vergessen Sie jedoch nicht, dass für die Frage eine direkte umgekehrte Reihenfolge erforderlich ist, d Es handelt sich also nicht um ein Integer-Array, sondern um ein Zeichen-Array. Verwenden Sie zwei Zeiger, um auf die erste Position des Zeichenarrays zu zeigen, tauschen Sie die entsprechenden Zeichen aus und bewegen Sie dann die beiden Zeiger in Richtung der Mitte des Arrays, bis sie sich kreuzen.
Code kopieren Der Code lautet wie folgt:
// String umgekehrte Reihenfolge
void Reverse(char *a, int n)
{
int left = 0;
int right = n - 1 ;
while (left < right)
{
char temp = a[left] ;
a[ right-- ] = temp ;
}
}
Kombinationsproblem
Wählen Sie aus einem ganzzahligen Array a mit n Elementen zufällig m Elemente aus und finden Sie alle Kombinationen. Zum Beispiel das folgende Beispiel:
a = 1, 2, 3, 4, 5
m = 3
Ausgabe:
1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5
3 4 5
Typische Permutations- und Kombinationsprobleme, die Die Backtracking-Methode wird bevorzugt. Um das Problem zu vereinfachen, setzen wir die n Elementwerte in a auf 1-n.
Code kopieren Der Code lautet wie folgt:
//n alle Kombinationen von m auswählen
int buffer[100]
void PrintArray(int *a, int n)
{
for (int i = 0; i < n; ++i)
cout << 🎜>}
bool IsValid(int lastIndex, int value)
{
for (int i = 0; i < lastIndex; i++)
{
if (buffer[ i] > ;= value)
return false;
}
return true;
void Select(int t, int n, int m)
{
if (t == m)
PrintArray(buffer, m);
else
{
for (int i = 1; i <= n; i++)
{
buffer [t] = i;
if (IsValid(t, i))
Select(t + 1, n, m);
}
}
Zwei Arrays zusammenführen
Gegeben seien zwei geordnete (nicht absteigende) ganzzahlige Arrays a und b mit n Elementen. Führen Sie die Elemente in den beiden Arrays im Integer-Array c zusammen, entfernen Sie doppelte Elemente und behalten Sie die Reihenfolge von c bei (nicht absteigende Reihenfolge). Beispiele sind wie folgt:
a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8
Unter Verwendung der Idee der Zusammenführungssortierung zeigen die beiden Zeiger i, j und k auf die Arrays a und b und vergleichen Sie dann die Größen der Elemente, die den beiden Zeigern entsprechen. Es gibt drei Situationen:
a[i]
a[i] == b[j] c[k] ist gleich a[ Entweder i] oder b[j] ist akzeptabel.
a[i] > b[j], dann c[k] = b[j].
Wiederholen Sie den obigen Vorgang, bis i oder j das Ende des Arrays erreicht, und kopieren Sie dann die verbleibenden Elemente direkt in das Array c.
Code kopieren Der Code lautet wie folgt:
// Zwei geordnete Arrays zusammenführen
void Merge(int *a, int *b, int *c, int n)
{
int i = 0;
int j = 0;
int k = 0 ;/ Wenn das Element von a klein ist, füge das Element in a ein
{
c [k++] = a[i] ;
++i ;
}
else if (a[i] == b[j])// Wenn die Elemente a und b gleich sind, können Sie Fügen Sie beides ein. Fügen Sie hier ein
{
c[k++] = a[i ] ;
++i ; ] > b[j] // Wenn das Element in b klein ist, füge das Element in b in c ein
{
c[k++] = b[j] ; >}
}
if (i == n) // if a Verarbeiten Sie nach Abschluss der Durchquerung die verbleibenden Elemente in b
{
for (int m = j; m < n; ++m)
c[k++] = b[m] }
else//j == n, wenn b durchlaufen wird, werden die restlichen Elemente in a
verarbeitet {
for (int m = i; m < n; ++m)
c [k++] = a[m] ;
}
}
Umordnungsproblem
Gegeben sei ein ganzzahliges Array a mit n Elementen, einschließlich 0 Elementen und Nicht-0-Elementen. Um das Array zu sortieren, gelten folgende Anforderungen:
Nach dem Sortieren stehen alle 0 Elemente vorne, alle Nicht-Null-Elemente befinden sich hinten und die relativen Positionen von Nicht-Null-Elementen bleiben vor und nach der Sortierung unverändert.
Zusätzlicher Speicher kann nicht verwendet werden.
Das Beispiel sieht wie folgt aus: Eingabe 0, 3, 0, 2, 1, 0, 0, Ausgabe 0, 0, 0, 0, 3, 2, 1.
Diese Sortierung ist keine Sortierung im herkömmlichen Sinne, da sie erfordert, dass die relative Position von Nicht-Null-Elementen vor und nach der Sortierung unverändert bleibt. Vielleicht wird sie besser als Sortierung bezeichnet. Wir können das gesamte Array von hinten nach vorne durchlaufen. Wenn das Element an einer bestimmten Position i ein Nicht-0-Element ist und a[k] 0 ist, wird a[i] a[k] zugewiesen und a[ k] wird ein Wert von 0 zugewiesen. Tatsächlich ist i der Index eines Elements ungleich Null und k der Index eines 0-Elements.
Code kopieren Der Code lautet wie folgt:
void Arrange(int* a, int n)
{
int k = n - 1;
for (int i = n - 1; i > = 0; --i)
{
if (a[i] != 0)
{
if (a[k] == 0)
{
a[k] = a[i] ;
a[i] = 0 ;
--k ;
