2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Es gibt Konstruktoren in C++-Strukturen.
#include kann in der Mitte einer Programmdatei stehen.
Formale Parameternamen können in Funktionsdeklarationen weggelassen werden, nicht jedoch in Definitionen.
Eine nicht leere Datenstruktur, wenn sie die folgenden zwei Bedingungen erfüllt:
Es wird als lineare Struktur bezeichnet und in Datenstrukturen als lineare Tabelle bezeichnet.
Der doppelt verknüpfte Listenknoten verfügt über zwei Zeigerfelder und ist eine lineare Struktur.
Die Zeiger aller Knoten in der zirkulär verknüpften Liste sind ungleich Null und ebenfalls lineare Strukturen.
Zu den Methoden zum Erstellen einer Hash-Tabelle gehören: direkte Adressmethode, Divisions- und Restmethode.
Zu den Konfliktlösungsmethoden gehören:
Wenn links und rechts zwei ganze Zahlen vorhanden sind, die das Intervall [links, rechts] darstellen, wird das Ergebnis der bitweisen UND-Verknüpfung aller Zahlen in diesem Intervall zurückgegeben.
Für eine Reihe von Bits ist das Ergebnis der bitweisen UND-Verknüpfung dieser Reihe Null, solange es ein Bit mit dem Wert Null gibt.
Im obigen Beispiel können wir das findenDas Ergebnis einer bitweisen UND-Operation für alle Zahlen ist das gemeinsame Präfix aller entsprechenden Binärzeichenfolgen, wobei die verbleibenden Bits mit Nullen aufgefüllt werden.
Bei einem ganzzahligen Array „nums“ kommt jedes Element dreimal vor, mit Ausnahme eines Elements, das nur einmal vorkommt. Suchen Sie das Element, das nur einmal vorkommt, und geben Sie es zurück.
Entwerfen Sie einen Algorithmus mit linearer Zeitkomplexität und verwenden Sie konstanten Raum, um das Problem zu lösen.
Bestimmen Sie nacheinander jedes Binärbit
Da die Elemente im Array im Bereich von int liegen, können Sie nacheinander berechnen, ob jedes Binärbit der Antwort 0 oder 1 ist.
Betrachten Sie insbesondere die i-te Binärziffer der Antwort (i wird beginnend mit 0 nummeriert), die 0 oder 1 sein kann.
Die i-te Ziffer der Antwort ist der Rest der Summe der i-ten Binärziffern aller Elemente im Array dividiert durch 3.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(int i=0; i<32; i++){
int sum = 0;
for(int num : nums){
sum += ((num >> i) & 1);
}
ret += ((sum%3) << i);
}
return ret;
}
};
Schnelle Leistung + Rekursion
Die Essenz des Fast-Power-Algorithmus ist der Divide-and-Conquer-Algorithmus.
Beginnen Sie mit x und quadrieren Sie jedes Mal direkt das vorherige Ergebnis. Berechnen Sie 5 Mal, um x64 zu erhalten.
class Solution {
public:
double quickMul(double x, long long N){
if(N == 0){
return 1.0;
}
double y = quickMul(x, N/2);
return N%2 == 0 ? y * y : y * y * x;
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
Geben Sie bei einer gegebenen Ganzzahl n zurück: n! Die Anzahl der nachgestellten Nullen im Ergebnis.
Die Anzahl der Endnullen in n! besteht darin, die Anzahl der Faktoren 10 zu ermitteln, und 10 = 2x5, sodass sie in die Ermittlung des kleineren Werts der Anzahl der Primfaktoren 2 und der Anzahl der Primfaktoren 5 in n! umgewandelt wird.
Da die Anzahl der Primfaktoren 5 nicht größer sein wird als die Anzahl der Primfaktoren 2, wird nur die Anzahl der Primfaktoren 5 berücksichtigt.
Die Anzahl der Primfaktoren 5 in n! ist gleich der Summe der Anzahl der Primfaktoren 5 jeder Zahl.
class Solution {
public:
int trailingZeroes(int n) {
int res = 0;
for(int i=5; i<=n; i += 5){
for(int j=i; j%5 == 0; j/=5){
res++;
}
}
return res;
}
};
Geschwindigkeitszeiger
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr){
return false;
}
ListNode* slow = head->next;
ListNode* fast = head->next->next;
while(fast != nullptr){
if(slow == fast){
return true;
}
if(fast->next == nullptr){
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return false;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr){
return list2;
}
if(list2 == nullptr){
return list1;
}
ListNode* newHead;
if(list1->val <= list2->val){
newHead = list1;
list1 = list1->next;
}else{
newHead = list2;
list2 = list2->next;
}
ListNode* p = newHead;
while(list1 && list2){
if(list1->val <= list2->val){
p->next = list1;
p = p->next;
list1 = list1->next;
}else{
p->next = list2;
p = p->next;
list2 = list2->next;
}
}
while(list1){
p->next = list1;
p = p->next;
list1 = list1->next;
}
while(list2){
p->next = list2;
p = p->next;
list2 = list2->next;
}
return newHead;
}
};
Ein Baum ist symmetrisch, wenn sein linker und rechter Teilbaum Spiegelbilder voneinander sind.
Breitendurchquerung
Die Suche beginnt am Wurzelknoten, durchläuft in jeder Runde alle Knoten in derselben Schicht, berechnet die Anzahl der Knoten in der Schicht und die Summe der Anzahl der Knoten in der Schicht und berechnet dann den Durchschnittswert der Schicht.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> average;
queue<TreeNode *> que;
que.push(root);
while(!que.empty()){
double sum = 0;
int size = que.size();
for(int i=0; i<size; i++){
TreeNode* node = que.front();
que.pop();
sum += node->val;
TreeNode* left = node->left;
TreeNode* right = node->right;
if(left){
que.push(left);
}
if(right){
que.push(right);
}
}
average.push_back(sum / size);
}
return average;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode* > que;
if(!root){
return res;
}
que.push(root);
while(!que.empty()){
vector<int> temp;
int size = que.size();
for(int i=0; i<size; i++){
TreeNode* node = que.front();
que.pop();
temp.push_back(node->val);
TreeNode* left = node->left;
TreeNode* right = node->right;
if(left){
que.push(left);
}
if(right){
que.push(right);
}
}
res.push_back(temp);
}
return res;
}
};
Ein geordnetes Array nums, löscht wiederholte Elemente an Ort und Stelle, sodass Elemente, die mehr als zweimal vorkommen, nur zweimal erscheinen, und gibt nach dem Löschen die neue Länge des Arrays zurück.
Das Eingabearray muss vor Ort geändert werden und unter Verwendung von O(1) zusätzlichem Speicherplatz erfolgen.
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int left = 0;
int right = 0;
int n = nums.size();
int count = 0;
int sum = 0;
while (right < n) {
if (nums[left] == nums[right]) {
count++;
right++;
} else {
if (count > 1) {
nums[++left] = nums[left];
sum += 2;
} else {
sum += 1;
}
nums[++left] = nums[right++];
count = 1;
}
}
if (count > 1) {
nums[++left] = nums[left];
sum += 2;
} else {
sum += 1;
}
return sum;
}
};
Drehen Sie bei einem gegebenen ganzzahligen Array nums die Elemente im Array um k Positionen nach rechts.
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
int price = prices[0];
for(int i=1; i<prices.size(); i++){
if(prices[i] > price){
result = max(result, prices[i] - price);
}else{
price = prices[i];
}
}
return result;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n,vector<int>(2)); //dp[i][0]第i天没有股票
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1; i<n; i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
}
return dp[n-1][0];
}
};
Bei einem nichtnegativen Ganzzahl-Array nums, das sich zunächst am ersten Index des Arrays befindet, stellt jedes Element im Array die maximale Länge dar, die übersprungen werden kann.
Bestimmen Sie, ob zum letzten Index gesprungen werden kann.
gierig
Für jede Position y im Array kann y auch erreicht werden, solange es eine Position x gibt, die von selbst erreicht werden kann, und x + nums[x] ≥ y.
Für jede erreichbare Position x macht es die aufeinanderfolgenden Positionen x+1, x+2, ..., x+nums[x] erreichbar.
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for(int i=0; i<n; i++){
if(i <= rightmost){
rightmost = max(rightmost, i+nums[i]);
if(rightmost >= n-1){
return true;
}
}
}
return false;
}
};
Ordnen Sie eine gegebene Zeichenfolge s in einer Z-Form von oben nach unten und von links nach rechts entsprechend der angegebenen Anzahl von Zeilen numRows an.
Simulieren Sie mit 2D-Matrizen
Sei n die Länge der Zeichenfolge s, r = numRows. Für r=1 (nur eine Zeile) oder r >= n (nur eine Spalte) ist die Antwort dieselbe wie s und kann direkt zurückgegeben werden.
In anderen Fällen können Sie erwägen, eine zweidimensionale Matrix zu erstellen, dann die Zeichenfolge s in einem Zickzackmuster auf der Matrix auszufüllen und schließlich die nicht leeren Zeichen in der Matrix Zeile für Zeile zu scannen, um die Antwort zu erhalten.
Entsprechend der Bedeutung der Frage füllen wir beim Ausfüllen der Zeichen in der Matrix r Zeichen nach unten, dann r-2 Zeichen nach oben nach rechts und kehren schließlich zur ersten Zeile zurück, also zur Z-förmigen Transformationsperiode t = r + r - 2 = 2r - 2. Jeder Zyklus belegt 1+r-2 = r-1 Spalten in der Matrix.
Es gibt n/t Perioden mal der Anzahl der Spalten, was gleich der Anzahl der Spalten der Matrix ist.
Erstellen Sie eine Matrix mit r Zeilen und c Spalten, durchlaufen Sie dann die Zeichenfolgen und füllen Sie sie in einem Zickzackmuster.
class Solution {
public:
string convert(string s, int numRows) {
int n = s.length(), r = numRows;
if(r == 1 || r >= n){
return s;
}
//变换周期
int t = 2*r - 2;
int c = (n + t -1) / t * (r - 1);
//创建二维字符串
vector<string> mat(r, string(c, 0));
for(int i = 0, x = 0, y =0; i<n; i++){
mat[x][y] = s[i];
if(i % t < r - 1){
++x; //向下移动
}else{
--x;
++y; //向右上移动
}
}
string ans;
for(auto &row : mat){
for(char ch : row){
if(ch){
ans += ch;
}
}
}
return ans;
}
};
class Solution {
public:
vector<string> splitString(string s){
istringstream iss(s);
vector<string> res;
string word;
while(iss >> word){
res.push_back(word);
}
return res;
}
string reverseWords(string s) {
vector<string> words = splitString(s);
string res;
for(int i=words.size()-1; i>=0; i--){
res += words[i] + " ";
}
res.pop_back();
return res;
}
};
Er widmet sich seit mehr als 30 Jahren der Technologieforschung und beherrscht verschiedene Sprachen wie Java, Linux, Javascript, PHP, CSS usw. Er hat viele Beiträge im Open-Source-Bereich geleistet Entwicklerdokumentationsstation, um einige Themen in der Technologieentwicklung als zukünftige Referenz zu teilen
