le mie informazioni di contatto
Posta[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Esistono costruttori nelle strutture C++.
#include può apparire nel mezzo di un file di programma.
I nomi dei parametri formali possono essere omessi nelle dichiarazioni di funzioni, ma non nelle definizioni.
Una struttura dati non vuota se soddisfa le due condizioni seguenti:
Si chiama struttura lineare ed è chiamata tabella lineare nelle strutture dati.
Il nodo della lista doppiamente concatenata ha due campi puntatore ed è una struttura lineare.
I puntatori di tutti i nodi nella lista concatenata circolare sono non nulli e sono anche strutture lineari.
I metodi per costruire una tabella hash includono: metodo dell'indirizzo diretto, metodo della divisione e del resto.
I metodi di risoluzione dei conflitti includono:
Dati due numeri interi sinistro e destro, che rappresentano l'intervallo [sinistra, destra], restituisce il risultato dell'AND bit a bit di tutti i numeri in questo intervallo.
Per una serie di bit, purché sia presente un bit con valore zero, il risultato dell'operazione AND bit a bit di questa serie è zero.
Nell'esempio sopra, possiamo trovarloIl risultato dell'esecuzione di un'operazione AND bit a bit su tutti i numeri è il prefisso comune di tutte le stringhe binarie corrispondenti, con i bit rimanenti riempiti con zeri.
Dato un array di numeri interi, ogni elemento appare tre volte tranne un elemento che appare solo una volta. Trova e restituisce l'elemento che appare solo una volta.
Progetta un algoritmo con complessità temporale lineare e utilizza lo spazio costante per risolvere il problema.
Determina a turno ciascun bit binario
Poiché gli elementi dell'array sono compresi nell'intervallo di int, è possibile calcolare se ciascun bit binario della risposta è a sua volta 0 o 1.
Nello specifico, considera la i-esima cifra binaria della risposta (i è numerata a partire da 0), che può essere 0 o 1.
L'i-esima cifra della risposta è il resto della somma delle i-esime cifre binarie di tutti gli elementi dell'array diviso per 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;
}
};
Potenza veloce + ricorsione
L’essenza dell’algoritmo di potenza veloce è l’algoritmo “divide et impera”.
Partendo da x, eleva direttamente al quadrato ogni volta il risultato precedente. Calcola 5 volte per ottenere x64.
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);
}
};
Dato un numero intero n, restituisce n! Il numero di zeri finali nel risultato.
Il numero di zeri di coda in n! serve a trovare il numero di fattori 10 e 10=2x5, quindi viene convertito nel trovare il valore più piccolo tra il numero di fattori primi 2 e il numero di fattori primi 5 in n!.
Poiché il numero di fattori primi 5 non sarà maggiore del numero di fattori primi 2, viene considerato solo il numero di fattori primi 5.
Il numero di fattori primi 5 in n! è uguale alla somma del numero di fattori primi 5 di ciascun numero.
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;
}
};
puntatore di velocità
/**
* 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;
}
};
Un albero è simmetrico se i suoi sottoalberi sinistro e destro sono l’uno l’immagine speculare dell’altro.
attraversamento in ampiezza
La ricerca inizia dal nodo radice, attraversa tutti i nodi nello stesso livello in ogni round, calcola il numero di nodi nel livello e la somma del numero di nodi nel livello, quindi calcola il valore medio del livello.
/**
* 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;
}
};
Un array ordinato di numeri, elimina gli elementi ripetuti sul posto, in modo che gli elementi che appaiono più di due volte appaiano solo due volte e restituiscano la nuova lunghezza dell'array dopo l'eliminazione.
L'array di input deve essere modificato sul posto ed eseguito utilizzando O(1) spazio aggiuntivo.
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;
}
};
Dato un array intero nums, ruota gli elementi nell'array k posizioni verso destra.
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];
}
};
Dato un array intero non negativo nums, inizialmente situato nel primo indice dell'array, ogni elemento dell'array rappresenta la lunghezza massima che può essere saltata.
Determina se può saltare all'ultimo indice.
avido
Per qualsiasi posizione y nell'array, purché esista una posizione x che può essere raggiunta da sola e x + nums[x] ≥ y, allora anche y può essere raggiunta.
Per ogni posizione raggiungibile x, rende raggiungibili le posizioni consecutive x+1, x+2, ..., x+nums[x].
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;
}
};
Data una stringa s, disponila a forma di z dall'alto verso il basso e da sinistra a destra in base al numero di righe numRows specificato.
Simulare utilizzando matrici 2D
Sia n la lunghezza della stringa s, r = numRows Per r=1 (solo una riga) o r >= n (solo una colonna), la risposta è la stessa di s e può essere restituita direttamente.
In altri casi, si consideri la creazione di una matrice bidimensionale, quindi il riempimento della stringa s secondo uno schema a zigzag sulla matrice e infine la scansione dei caratteri non vuoti nella matrice riga per riga per formare la risposta.
Secondo il significato della domanda, quando riempiamo i caratteri sulla matrice, riempiremo r caratteri verso il basso, quindi r-2 caratteri verso l'alto a destra e infine torneremo alla prima riga, quindi il periodo di trasformazione a forma di Z t = r + r - 2 = 2r - 2. Ogni ciclo occuperà 1+r-2 = r-1 colonne sulla matrice.
Ci sono n/t periodi per il numero di colonne, che è uguale al numero di colonne della matrice.
Crea una matrice con r righe e c colonne, quindi scorri le stringhe e riempile secondo uno schema a zigzag.
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;
}
};
Si dedica alla ricerca tecnologica da più di 30 anni ed è esperto in vari linguaggi come Java, Linux, Javascript, php, css, ecc. Ha dato numerosi contributi nel campo dell'open source stazione di documentazione per gli sviluppatori per condividere alcuni problemi nello sviluppo della tecnologia per riferimento futuro
Posta[email protected]