Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Solución de gestión de particiones variables

• Mejor adaptación: la superficie libre aumenta según el aforo
• Peor adaptación: la superficie libre disminuye según el aforo
• Adaptarse primero: el área libre se incrementa según la dirección

Hay constructores en estructuras C++.

Crear un nuevo usuario o grupo en Linux

• useradd: el comando se utiliza para crear una cuenta de usuario
• usermod: modificar cuenta de usuario
• groupadd: crea un nuevo grupo de trabajo
• userdel: eliminar cuenta de usuario

#include puede aparecer en medio de un archivo de programa.

Los nombres de parámetros formales se pueden omitir en las declaraciones de funciones, pero no en las definiciones.

mesa lineal

Una estructura de datos no vacía si cumple las dos condiciones siguientes:

1. Sólo hay un nodo raíz
2. Cada nodo tiene como máximo un nodo anterior y como máximo un nodo siguiente.

Se llama estructura lineal y se llama tabla lineal en estructuras de datos.
El nodo de lista doblemente enlazado tiene dos campos de puntero y es una estructura lineal.
Los punteros de todos los nodos en la lista enlazada circular no son nulos y también son estructuras lineales.

encontrar tabla hash

Los métodos para construir una tabla hash incluyen: método de dirección directa, método de división y resto.

Los métodos de resolución de conflictos incluyen:

• Método de dirección en cadena: conecta elementos con el mismo valor hash mediante una lista vinculada.
• Detección lineal y luego método de hash: después del conflicto, haga un bucle hacia abajo para encontrar ubicaciones vacías para su ubicación.

Bit a bit Y de rangos numéricos

Dados dos números enteros izquierdo y derecho, que representan el intervalo [izquierda, derecha], devuelve el resultado del AND bit a bit de todos los números en este intervalo.

Para una serie de bits, siempre que haya un bit con valor cero, el resultado de la operación AND bit a bit de esta serie es cero.

En el ejemplo anterior podemos encontrar queEl resultado de realizar una operación AND bit a bit en todos los números es el prefijo común de todas las cadenas binarias correspondientes y los bits restantes se rellenan con ceros.

Números que aparecen solo una vez (2)

Dada una matriz de números enteros, cada elemento aparece tres veces excepto un elemento que aparece solo una vez. Encuentra y devuelve el elemento que aparece solo una vez.

Diseñe un algoritmo con complejidad de tiempo lineal y utilice espacio constante para resolver el problema.

Determine cada bit binario por turno
Dado que los elementos de la matriz están en el rango int, puede calcular si cada bit binario de la respuesta es 0 o 1 por turno.

Específicamente, considere el i-ésimo dígito binario de la respuesta (i está numerado a partir de 0), que puede ser 0 o 1.

El i-ésimo dígito de la respuesta es el resto de la suma de los i-ésimo dígito binario de todos los elementos de la matriz dividido por 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Poder(x, n)

Potencia rápida + recursividad
La esencia del algoritmo de potencia rápida es el algoritmo de divide y vencerás.
A partir de x, eleva directamente al cuadrado el resultado anterior cada vez. Calcula 5 veces para obtener 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); 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

cero después del factorial

Dado un número entero n, devuelve n! El número de ceros finales en el resultado.

El número de ceros de cola en n! es para encontrar el número de factores primos 10, y 10 = 2x5, por lo que se convierte para encontrar el valor más pequeño del número de factores primos 2 y el número de factores primos 5 en n!.

Dado que el número de factores primos 5 no será mayor que el número de factores primos 2, solo se considera el número de factores primos 5.

El número de factores primos 5 en n! es igual a la suma del número de factores primos 5 de cada número.

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

lista circular enlazada

puntero de velocidad

/**
 * 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Fusionar dos listas enlazadas ordenadas

/**
 * 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

Árbol binario simétrico

Un árbol es simétrico si sus subárboles izquierdo y derecho son imágenes especulares entre sí.

• Sus dos nodos raíz tienen el mismo valor.
• El subárbol derecho de cada árbol es una imagen especular del subárbol izquierdo del otro árbol.

Nivel promedio del árbol binario

recorrido de amplitud primero
La búsqueda comienza desde el nodo raíz, atraviesa todos los nodos en la misma capa en cada ronda, calcula el número de nodos en la capa y la suma del número de nodos en la capa, y luego calcula el valor promedio de la capa.

• Inicialmente, el nodo raíz está en cola.
• Durante cada ronda de recorrido, se eliminan todos los nodos de la cola, se calcula el número y la suma de estos nodos, luego se calcula el valor promedio y luego todos los nodos secundarios vacíos del nodo se agregan a la cola.

/**
 * 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

Recorrido de orden a nivel de árbol binario

/**
 * 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Eliminar duplicados en una matriz ordenada

Una matriz ordenada numera, elimina los elementos repetidos en su lugar, de modo que los elementos que aparecen más de dos veces solo aparecen dos veces y devuelve la nueva longitud de la matriz después de la eliminación.

La matriz de entrada debe modificarse en el lugar y realizarse utilizando O(1) espacio adicional.

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Rotar matriz

Dada una matriz de números enteros, gire los elementos en la matriz k posiciones hacia la derecha.

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());
    }
};
1
2
3
4
5
6
7
8
9
10

El mejor momento para comprar y vender acciones

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

El mejor momento para comprar acciones 2

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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

juego de saltos

Dada una matriz de números enteros no negativos, inicialmente ubicada en el primer índice de la matriz, cada elemento de la matriz representa la longitud máxima que se puede saltar.
Determine si puede saltar al último índice.

avaro
Para cualquier posición y en la matriz, siempre que haya una posición x que pueda alcanzarse por sí sola y x + nums[x] ≥ y, entonces también se puede alcanzar y.

Para cada posición x alcanzable, hace que las posiciones consecutivas x+1, x+2, ..., x+nums[x] sean alcanzables.

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Transformación en zigzag

Dada una cadena s, colóquela en forma de z de arriba a abajo y de izquierda a derecha de acuerdo con el número dado de filas numRows.

Simular usando matrices 2D
Sea n la longitud de la cadena s, r = numRows. Para r=1 (solo una fila), o r >= n (solo una columna), la respuesta es la misma que s y se puede devolver directamente.

En otros casos, considere crear una matriz bidimensional, luego completar la cadena s en un patrón de zigzag en la matriz y finalmente escanear los caracteres no vacíos en la matriz línea por línea para formar la respuesta.

Según el significado de la pregunta, cuando completamos caracteres en la matriz, completaremos r caracteres hacia abajo, luego r-2 caracteres hacia arriba a la derecha y finalmente regresaremos a la primera fila, por lo que el período de transformación en forma de Z t = r + r - 2 = 2r - 2. Cada ciclo ocupará 1+r-2 = r-1 columnas en la matriz.

Hay n/t períodos multiplicados por el número de columnas, que es igual al número de columnas de la matriz.

Cree una matriz con r filas yc columnas, luego repita las cadenas y rellénelas en un patrón de 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

Invertir palabras en una cadena

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21