ARTES #026

ARTES 026

Este é o artigo 26

Pergunta sobre algoritmo de algoritmo

646. Cadeia de pares mais longa

Dificuldade: Média

Forneça pares de números n. Em cada par de números, o primeiro número é sempre menor que o segundo número.

Agora, definimos um seguinte relacionamento. Se e somente se b < c, o par de números (c, d) pode seguir (a, b). Usamos esta forma para construir uma cadeia de pares de números.

Dado um conjunto de pares, encontre o comprimento da maior cadeia de pares que pode ser formada. Você não precisa usar todos os pares, você pode escolher alguns deles em qualquer ordem para construir.

Exemplo:

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]

Nota:

1. O número de determinados pares de números está no intervalo [1, 1000].

Solução

Idioma: C

#define maxn 1005
struct Pair{
    int begin;
    int end;
} pair[maxn];

int cmp(const void* a, const void* b){
    struct Pair* x = (struct Pair*)a;
    struct Pair* y = (struct Pair*)b;
    if(x->end == y->end) return x->begin - y->begin;
    return x->end - y->end;
}

void matrixToStruct(int** pairs, int row){
    for(int i = 0;i < row;i++){
        pair[i].begin = pairs[i][0];
        pair[i].end = pairs[i][1];
    }
}

int findLongestChain(int** pairs, int pairsRowSize, int pairsColSize) {
    int row = pairsRowSize;
    int col = pairsColSize;
    
    matrixToStruct(pairs, row);
    qsort(pair, row, sizeof(struct Pair), cmp);
    
    int cnt = 1;
    for(int i = 1, k= 0;i < row;i++){
        if(pair[i].begin > pair[k].end){
            cnt++;
            k = i;
        }
    }
    return cnt;
}

198. Roubo

Dificuldade: Fácil

Você é um ladrão profissional que planeja roubar casas ao longo da rua. Há uma certa quantia de dinheiro escondida em cada quarto. O único factor de restrição que afecta o seu roubo é que as casas adjacentes estão equipadas com sistemas anti-roubo interligados. Se duas casas adjacentes forem invadidas por ladrões na mesma noite, o sistema irá alarmar automaticamente.

Dada uma série de números inteiros não negativos que representam a quantidade de dinheiro armazenada em cada casa, calcule a quantidade máxima de dinheiro que você pode roubar sem acionar o dispositivo de alarme.

Exemplo 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。```

**Exemplo 2:**

输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

#### Solução

Idioma: **C**

//方法一 递归法 int rob(int* nums, int numsSize) { if (numsSize <=0) { return 0; }

if (numsSize==1) {
    return nums[0];
}
int r1= rob(nums,numsSize-2) +  nums[numsSize - 1];
int r2= rob(nums,numsSize-1) ;
if (r1 > r2) {
    return r1;
}
return r2;

}

//方法二 备忘录递归法 int re[10000] = {-1};

int rob1(int* nums, int numsSize) {

if (numsSize <=0) {
    return 0;
}

if (numsSize==1) {
    return nums[0];
}

if (re[numsSize] >-1) {
    return re[numsSize];
}

int r1= rob1(nums,numsSize-2) +  nums[numsSize - 1];
int r2= rob1(nums,numsSize-1) ;
if (r1 > r2) {
    re[numsSize] = r1;
    return r1;
}

re[numsSize] = r2;
return r2;

}

int rob(int* nums, int numsSize){ for (int i=0; i<10000; i++) { re[i] = -1; } return rob1(nums, numsSize); }

```c
//方法三 动态规划
int rob(int* nums, int numsSize){
    if (numsSize <=0) {
        return 0;
    }

    if (numsSize==1) {
        return nums[0];
    }
    
    int r0 = nums[0];
    int r1 = nums[1];
    int sum = r0 > r1 ? r0 : r1;
   
    
    for (int i = 2; i < numsSize; i++) {
        r1 = r0 + nums[i];
        r0 = sum;
        sum = r0 > r1 ? r0 : r1;
    }
    
    
    return sum;
}

Revisão

O artigo aqui fala sobre o processo de procura de emprego de um americano, que finalmente conseguiu um salário anual de 300.000 dólares americanos. O nível salarial do imperador americano é realmente alto. https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/

Dicas

Depois que nosso projeto realmente crescer, à medida que o negócio for iterando, haverá muitas classes inúteis, ou seja, classes que não são referenciadas por nenhuma classe. Essas classes farão com que o pacote de instalação fique maior, por isso é necessário limpá-lo. Existe um script https://github.com/dblock/fui，很实用， no github Também é muito simples de usar: Instalação: gem instalar fui

Recuperar classes não utilizadas no diretório atual:

fui find

Há também exclusão direta e outras funções, você pode conferir para obter detalhes.

Preste atenção ao usá-lo. Classes que não são referenciadas por outras classes também podem ser úteis. Por exemplo, se o método load for implementado, todos sabem que o método load é um método que é chamado automaticamente quando o APP é iniciado. Se houver alguma lógica de negócios escrita nele, se for excluída, causará problemas. Eu ignorei esses erros. Portanto, é melhor estar familiarizado com a lógica de negócios ao excluir classes.

Compartilhar

Como interceptar falhas em aplicativos iOS, evitar falhas e reduzir as taxas de falhas. A ideia atual é conhecer a camada inferior do sistema iOS, ou seja, o sistema operacional. Estar familiarizado com o sistema operacional requer um estudo aprofundado da linguagem C e C++ para melhorar seu próprio padrão. Esta questão resume-se essencialmente a familiarizar-se com o básico. Somente quando você estiver familiarizado com os princípios básicos, poderá encontrar fundamentalmente soluções para os problemas quando os encontrar.