2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Il existe des constructeurs dans les structures C++.
#include peut apparaître au milieu d'un fichier programme.
Les noms de paramètres formels peuvent être omis dans les déclarations de fonctions, mais pas dans les définitions.
Une structure de données non vide si elle remplit les deux conditions suivantes :
C'est ce qu'on appelle une structure linéaire et un tableau linéaire dans les structures de données.
Le nœud de liste doublement chaîné possède deux champs de pointeur et est une structure linéaire.
Les pointeurs de tous les nœuds de la liste chaînée circulaire ne sont pas nuls et sont également des structures linéaires.
Les méthodes pour construire une table de hachage comprennent : la méthode d’adresse directe, la méthode de division et de reste.
Les méthodes de résolution des conflits comprennent :
Étant donné deux entiers gauche et droit, représentant l'intervalle [gauche, droite], renvoie le résultat du ET au niveau du bit de tous les nombres de cet intervalle.
Pour une série de bits, tant qu'il existe un bit avec une valeur nulle, le résultat de l'opération ET au niveau du bit de cette série est nul.
Dans l’exemple ci-dessus, nous pouvons constater queLe résultat de l’exécution d’une opération ET au niveau du bit sur tous les nombres est le préfixe commun de toutes les chaînes binaires correspondantes, les bits restants étant complétés par des zéros.
Étant donné un tableau d'entiers nums, chaque élément apparaît trois fois à l'exception d'un élément qui n'apparaît qu'une seule fois. Recherchez et renvoyez l'élément qui n'apparaît qu'une seule fois.
Concevez un algorithme avec une complexité temporelle linéaire et utilisez un espace constant pour résoudre le problème.
Déterminez chaque bit binaire tour à tour
Étant donné que les éléments du tableau sont dans la plage int, vous pouvez calculer si chaque bit binaire de la réponse est tour à tour 0 ou 1.
Plus précisément, considérons le i-ème chiffre binaire de la réponse (i est numéroté à partir de 0), qui peut être 0 ou 1.
Le i-ème chiffre de la réponse est le reste de la somme des i-ème chiffres binaires de tous les éléments du tableau divisé par 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;
}
};
Puissance rapide + récursion
L’essence de l’algorithme de puissance rapide est l’algorithme diviser pour régner.
En partant de x, mettez directement au carré le résultat précédent à chaque fois. Calculez 5 fois pour obtenir 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);
}
};
Étant donné un entier n, renvoie n ! Le nombre de zéros à droite dans le résultat.
Le nombre de zéros de queue dans n ! consiste à trouver le nombre de facteurs 10, et 10 = 2x5, il est donc converti en la recherche de la plus petite valeur du nombre de facteurs premiers 2 et du nombre de facteurs premiers 5 dans n !.
Puisque le nombre de facteurs premiers 5 ne sera pas supérieur au nombre de facteurs premiers 2, seul le nombre de facteurs premiers 5 est considéré.
Le nombre de facteurs premiers 5 dans n ! est égal à la somme du nombre de facteurs premiers 5 de chaque nombre.
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;
}
};
pointeur de vitesse
/**
* 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 arbre est symétrique si ses sous-arbres gauche et droit sont des images miroir l’un de l’autre.
parcours en largeur d'abord
La recherche commence à partir du nœud racine, parcourt tous les nœuds de la même couche à chaque tour, calcule le nombre de nœuds dans la couche et la somme du nombre de nœuds dans la couche, puis calcule la valeur moyenne de la couche.
/**
* 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 tableau ordonné nums, supprime les éléments répétés sur place, de sorte que les éléments qui apparaissent plus de deux fois n'apparaissent que deux fois et renvoie la nouvelle longueur du tableau après la suppression.
Le tableau d'entrée doit être modifié sur place et réalisé en utilisant l'espace supplémentaire O(1).
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;
}
};
Étant donné un tableau entier nums, faites pivoter les éléments du tableau k positions vers la droite.
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];
}
};
Étant donné un tableau d'entiers non négatifs nums, initialement situé au premier index du tableau, chaque élément du tableau représente la longueur maximale qui peut être sautée.
Déterminez s'il peut accéder au dernier index.
cupide
Pour toute position y dans le tableau, tant qu'il existe une position x qui peut être atteinte par elle-même et que x + nums[x] ≥ y, alors y peut également être atteint.
Pour chaque position accessible x, cela rend les positions consécutives x+1, x+2, ..., x+nums[x] accessibles.
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;
}
};
Étant donné une chaîne s, disposez-la en forme de z de haut en bas et de gauche à droite en fonction du nombre de lignes donné numRows.
Simuler à l'aide de matrices 2D
Soit n la longueur de la chaîne s, r = numRows. Pour r=1 (une seule ligne) ou r >= n (une seule colonne), la réponse est la même que s et peut être renvoyée directement.
Dans d'autres cas, envisagez de créer une matrice bidimensionnelle, puis de remplir la chaîne s en zigzag sur la matrice, et enfin de numériser les caractères non vides de la matrice ligne par ligne pour former la réponse.
Selon le sens de la question, lorsque l'on remplira des caractères sur la matrice, on remplira r caractères vers le bas, puis r-2 caractères vers le haut vers la droite, et enfin retourner à la première ligne, donc la période de transformation en Z t = r + r - 2 = 2r - 2. Chaque cycle occupera 1+r-2 = r-1 colonnes sur la matrice.
Il y a n/t périodes multipliées par le nombre de colonnes, ce qui est égal au nombre de colonnes de la matrice.
Créez une matrice avec r lignes et c colonnes, puis parcourez les chaînes et remplissez-les selon un motif en 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;
}
};
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
