Compartilhamento de tecnologia

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

Solução de gerenciamento de partição variável

• Melhor adaptação: área livre aumenta por capacidade
• Pior adaptação: a área livre diminui conforme a capacidade
• Adapte primeiro: a área livre é incrementada por endereço

Existem construtores em estruturas C++.

Crie um novo usuário ou grupo no Linux

• useradd: comando é usado para criar uma conta de usuário
• usermod: modificar conta de usuário
• groupadd: Crie um novo grupo de trabalho
• userdel: excluir conta de usuário

#include pode aparecer no meio de um arquivo de programa.

Os nomes formais dos parâmetros podem ser omitidos nas declarações de funções, mas não nas definições.

mesa linear

Uma estrutura de dados não vazia se atender às duas condições a seguir:

1. Existe apenas um nó raiz
2. Cada nó possui no máximo um nó anterior e no máximo um nó seguinte.

É chamada de estrutura linear e é chamada de tabela linear em estruturas de dados.
O nó da lista duplamente vinculada possui dois campos de ponteiro e é uma estrutura linear.
Os ponteiros de todos os nós na lista vinculada circular não são nulos e também são estruturas lineares.

Encontrar tabela hash

Os métodos para construir uma tabela hash incluem: método de endereço direto, método de divisão e método de resto.

Os métodos de resolução de conflitos incluem:

• Método de endereço de cadeia: conecte elementos com o mesmo valor hash usando uma lista vinculada.
• Detecção linear e método de hash: após o conflito, faça um loop para baixo para encontrar locais vazios para posicionamento.

AND bit a bit de intervalos numéricos

Dados dois inteiros à esquerda e à direita, representando o intervalo [esquerda, direita], retorne o resultado do AND bit a bit de todos os números neste intervalo.

Para uma série de bits, desde que haja um bit com valor zero, o resultado da operação AND bit a bit desta série é zero.

No exemplo acima, podemos descobrir queO resultado da execução de uma operação AND bit a bit em todos os números é o prefixo comum de todas as strings binárias correspondentes, com os bits restantes preenchidos com zeros.

Números que aparecem apenas uma vez (2)

Dado um array inteiro nums, cada elemento aparece três vezes, exceto um elemento que aparece apenas uma vez. Encontre e retorne o elemento que aparece apenas uma vez.

Projete um algoritmo com complexidade de tempo linear e use espaço constante para resolver o problema.

Determine cada bit binário por vez
Como os elementos da matriz estão no intervalo int, você pode calcular se cada bit binário da resposta é 0 ou 1 por vez.

Especificamente, considere o i-ésimo dígito binário da resposta (i é numerado a partir de 0), que pode ser 0 ou 1.

O i-ésimo dígito da resposta é o restante da soma dos i-ésimos dígitos binários de todos os elementos da 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

Pow(x, n)

Potência rápida + recursão
A essência do algoritmo de potência rápida é o algoritmo de dividir e conquistar.
Começando em x, eleve ao quadrado diretamente o resultado anterior de cada vez. Calcule 5 vezes para obter 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

zero após fatorial

Dado um número inteiro n, retorne n! O número de zeros à direita no resultado.

O número de zeros finais em n é para encontrar o número de fatores 10, e 10=2x5, então é convertido em encontrar o menor valor do número de fatores primos 2 e o número de fatores primos 5 em n!.

Como o número de fatores primos 5 não será maior que o número de fatores primos 2, apenas o número de fatores primos 5 é considerado.

O número de fatores primos 5 em n é igual à soma do número de fatores 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 vinculada circular

ponteiro de velocidade

/**
 * 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

Mesclar duas listas vinculadas 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

Árvore binária simétrica

Uma árvore é simétrica se suas subárvores esquerda e direita são imagens espelhadas uma da outra.

• Seus dois nós raiz têm o mesmo valor
• A subárvore direita de cada árvore é uma imagem espelhada da subárvore esquerda da outra árvore

Média de nível da árvore binária

travessia em largura
A pesquisa começa no nó raiz, percorre todos os nós da mesma camada em cada rodada, calcula o número de nós na camada e a soma do número de nós na camada e, em seguida, calcula o valor médio da camada.

• Inicialmente, o nó raiz é enfileirado.
• Durante cada rodada de travessia, todos os nós da fila são retirados, o número e a soma desses nós são calculados e, em seguida, o valor médio é calculado e, em seguida, todos os nós filhos vazios do nó são adicionados à fila.

/**
 * 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

Percurso de ordem em nível de árvore binária

/**
 * 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

Remover duplicatas na matriz ordenada

Um array ordenado nums, exclui os elementos repetidos no lugar, de modo que os elementos que aparecem mais de duas vezes aparecem apenas duas vezes e retornam o novo comprimento do array após a exclusão.

A matriz de entrada deve ser modificada no local e feita usando espaço extra 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;
    }
};
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

Girar matriz

Dado um array inteiro nums, gire os elementos no array k posições para a direita.

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

Melhor momento para comprar e vender ações

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

O melhor momento para comprar ações 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

jogo de salto

Dado um array inteiro não negativo nums, inicialmente localizado no primeiro índice do array, cada elemento do array representa o comprimento máximo que pode ser saltado.
Determine se ele pode pular para o último índice.

ambicioso
Para qualquer posição y na matriz, desde que haja uma posição x que possa ser alcançada por si só, e x + nums[x] ≥ y, então y também pode ser alcançado.

Para cada posição alcançável x, torna as posições consecutivas x+1, x+2, ..., x+nums[x] alcançáveis.

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

Transformação em ziguezague

Dada uma string s, organize-a em forma de z de cima para baixo e da esquerda para a direita de acordo com o número fornecido de linhas numRows.

Simular usando matrizes 2D
Seja n o comprimento da string s, r = numRows Para r=1 (apenas uma linha) ou r >= n (apenas uma coluna), a resposta é igual a s e pode ser retornada diretamente.

Em outros casos, considere criar uma matriz bidimensional, depois preencher a string s em zigue-zague na matriz e, finalmente, digitalizar os caracteres não vazios na matriz linha por linha para formar a resposta.

De acordo com o significado da pergunta, quando preenchermos os caracteres na matriz, preencheremos r caracteres para baixo, depois r-2 caracteres para cima à direita e, finalmente, retornaremos à primeira linha, de modo que o período de transformação em forma de Z t = r + r - 2 = 2r - 2. Cada ciclo ocupará 1+r-2 = r-1 colunas na matriz.

Existem n/t períodos vezes o número de colunas, que é igual ao número de colunas da matriz.

Crie uma matriz com r linhas e c colunas, depois itere pelas strings e preencha-as em zigue-zague.

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

Reverter palavras em uma string

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