Tech Notes
Back home

ARTES #028

ARTS22 de março de 2019 às 06:523 min read

ARTES #028

Topic / ARTS # iOS # ARTS # Algorihm
简体中文العربيةEnglishEspañolBahasa IndonesiaPortuguês

ARTES 028

Este é o artigo 28

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

Pergunta sobre algoritmo de algoritmo

2. Adicione dois números

Dificuldade: Média

Dadas duas listas vinculadas não vazias para representar dois números inteiros não negativos. Entre eles, seus respectivos dígitos são armazenados em ordem inversa, e cada um de seus nós pode armazenar apenas um dígito.

Se somarmos esses dois números, uma nova lista vinculada será retornada representando sua soma.

Você pode assumir que nenhum dos números começará com 0, exceto o número 0.

Exemplo:

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

A dificuldade desta questão é média. A principal dificuldade reside em considerar casos diferentes. Minha primeira resposta é a seguinte:

Solução

Idioma: C


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    
    struct ListNode* root = NULL;//(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p = NULL;
    int sum = 0;
    while (l1 != NULL || l2 != NULL ) {
        
        if (l1 != NULL && l2 != NULL ) {
            sum = l1->val + l2->val + sum / 10;
            l1 = l1->next;
            l2 = l2->next;
        }
        else if (l1 != NULL){
            sum = l1->val+ sum / 10;
            l1 = l1->next;
        }
        else if (l2 != NULL){
            sum = l2->val +  sum / 10;
            l2 = l2->next;
        }
        
        if (p == NULL) {
            p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val =  sum % 10;
            p->next = NULL;
            root = p;
        }
        else{
            struct ListNode*  temp = (struct ListNode*)malloc(sizeof(struct ListNode));
            temp->val =  sum % 10;
            temp->next = NULL;
            
            p->next = temp;
            p=temp;
        }
    }
    
    return root;
}

A lógica acima também é muito clara e simples, mas quando a entrada é 5 ou 5, o resultado está errado. Porque pensei menos na situação.

Resultado final:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    
    struct ListNode* root = NULL;//(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p = NULL;
    int sum = 0;
    while (l1 != NULL || l2 != NULL ) {
        
        int flag = 0;
        
        if (l1 != NULL && l2 != NULL ) {
            sum = l1->val + l2->val + sum / 10;
            l1 = l1->next;
            l2 = l2->next;
            
            if (l1 == NULL && l2 == NULL) {
                flag = 1;
            }
        }
        else if (l1 != NULL){
            sum = l1->val+ sum / 10;
            l1 = l1->next;
            
            if (l1 == NULL) {
                flag = 1;
            }
        }
        else if (l2 != NULL){
            sum = l2->val +  sum / 10;
            l2 = l2->next;
            
            if (l2 == NULL) {
                flag = 1;
            }
        }
        
        if (p == NULL) {
            p = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->val =  sum % 10;
            p->next = NULL;
            root = p;
        }
        else{
            struct ListNode*  temp = (struct ListNode*)malloc(sizeof(struct ListNode));
            temp->val =  sum % 10;
            temp->next = NULL;
            
            p->next = temp;
            p=temp;
        }
        
        if (flag ==1 && sum >=10) {
            struct ListNode*  temp = (struct ListNode*)malloc(sizeof(struct ListNode));
            temp->val =  sum / 10;
            temp->next = NULL;
            
            p->next = temp;
            p=temp;
        }
    }

    return root;
}

O resultado da operação acima é:

Runtime: 40 ms, faster than 10.93% of C online submissions for Add Two Numbers.
Memory Usage: 17.7 MB, less than 55.74% of C online submissions for Add Two Numbers.

O seguinte registro de submissão tem um tempo de execução de 16ms, atualmente classificado em primeiro lugar:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* recursiveAddTwoNumbers(struct ListNode* l1, struct ListNode* l2, int carry);
struct ListNode* recursiveFinishAdd(struct ListNode* l, int carry);

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    return recursiveAddTwoNumbers(l1, l2, 0);
}

struct ListNode* recursiveAddTwoNumbers(struct ListNode* l1, struct ListNode* l2, int carry) {
    if(l1 == NULL) return recursiveFinishAdd(l2, carry);
    if(l2 == NULL) return recursiveFinishAdd(l1, carry);
    
    int val = l1->val + l2->val + carry;
    struct ListNode *next = recursiveAddTwoNumbers(l1->next, l2->next, val/10);
    
    struct ListNode *node = malloc(sizeof(struct ListNode));
    node->val = val%10;
    node->next = next;
    
    return node;
}

struct ListNode* recursiveFinishAdd(struct ListNode* l, int carry) {
    if(l == NULL) {
        if(carry == 0) return NULL;
        struct ListNode *node = malloc(sizeof(struct ListNode));
        node->val = carry;
        node->next = NULL;
        return node;
    }
    
    int val = l->val + carry;
    struct ListNode *next = recursiveFinishAdd(l->next, val/10);
    
    struct ListNode *node = malloc(sizeof(struct ListNode));
    node->val = val%10;
    node->next = next;
    
    return node;
}

Mas eu executei e os resultados são os seguintes, então o ambiente de teste também está mudando, e o tempo de execução do mesmo código também está mudando.

Runtime: 32 ms, faster than 46.07% of C online submissions for Add Two Numbers.
Memory Usage: 18.2 MB, less than 5.07% of C online submissions for Add Two Numbers.

3. A substring mais longa sem caracteres repetidos Copiar para Markdown

Dificuldade: Média

Dada uma string, encontre o comprimento da substring mais longa que não contém caracteres repetidos.

Exemplo 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

Exemplo 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

Exemplo 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

Solução

Idioma: C

Minha resposta é a seguinte:

//滑动窗口
int lengthOfLongestSubstring(char* s) {
    int maxLength = 0;
    int strLength = strlen(s);
    int leftP = 0;
    int sublength = 0;
    for(int i = 0; i < strLength; i++){
        int flag = 0;
        for(int j = leftP; j < i; j++){
            if (s[j]== s[i]) {
                flag =1;
                leftP = j+1;
                sublength = i - j;
                break;
            }
        }
        
        if (flag ==0){
            sublength++;
        }

        if(sublength > maxLength) {
            maxLength = sublength;
        }
    }
    if(sublength > maxLength) {
        maxLength = sublength;
    }
  
    return maxLength;
}

A seguir está um exemplo que leva 8 ms para ser executado, mas eu executei e o tempo de execução é igual ao do meu código (a seguir está o tempo de execução do meu código) 

int lengthOfLongestSubstring(char* s) {
int maxlen = 0,currlen = 0;
    int table[128], i, j, start = 0;
    memset(table, 0, sizeof(table));
    for (i = 0; s[i] != '\0'; ++i){
        int num =  ++table[s[i]];
        if( num == 2 ){
            if (currlen > maxlen){
                maxlen = currlen;
            }
            for(j = start; j < i; ++j){
                if (s[j] == s[i]){
                    table[s[j]] = 1;
                    start = j+1;
                    break;
                }else{
                    --currlen;
                    table[s[j]] = 0;
                }
            }
        }else{
            ++currlen;
        }
    }
    if (currlen > maxlen){
        maxlen = currlen;
    }

    return maxlen;
}

Versão em inglês: envio de amostra de 8 ms, a ideia desta implementação é

int lengthOfLongestSubstring(char* s)
{
    int len=0;
    char *end=s,*temp;
    char* addressTable[128]={NULL};
    while(*end){
        temp = addressTable[*end];
        addressTable[*end]=end;
        if(temp>=s){
            len=end-s>len?end-s:len;
            s = temp+1;
        }
        end++;
    }
    len=end-s>len?end-s:len;
    return len;
}

4. Encontre a mediana de duas matrizes ordenadas

Dificuldade: Dificuldade

Dadas duas matrizes ordenadas nums1 e nums2 de tamanho m e n.

Encontre a mediana dessas duas matrizes ordenadas e a complexidade de tempo do algoritmo deve ser O (log (m + n)).

Você pode assumir que nums1 e nums2 não estarão vazios ao mesmo tempo.

Exemplo 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

Exemplo 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

Solução

Idioma: C

Mescle as matrizes primeiro e depois calcule

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {

    int sumSize = nums1Size + nums2Size;
    int *sum =   (int*)malloc(sizeof(int) * sumSize);
    int loop1 = 0;
    int loop2 = 0;
    for (int i =0; i< sumSize; i++) {//合并数组
        if (loop1>=nums1Size) {
            for (int j = i; j < sumSize; j++) {
                sum[j] = nums2[loop2++];
            }
            break;
        }

        if (loop2>=nums2Size) {
            for (int j = i; j < sumSize; j++) {
                sum[j] = nums1[loop1++];
            }
            break;
        }

        int r1 = nums1[loop1];
        int r2 = nums2[loop2];
        if (r1 < r2) {
            sum[i] = r1;
            loop1++;
        }
        else{
           sum[i] = r2;
            loop2++;
        }

    }

    //计算最终结果
    double r = 0;
    if (sumSize  % 2 == 0 ) {
        int l1 = sumSize  / 2;
        int l2 = l1 - 1;

        r = ((double)(sum[l1] + sum[l2]))/2;
    }
    else{
        int l =  sumSize  / 2;
        r = sum[l];
    }

    return r;
}

Revisão

Este artigo fala principalmente sobre qual é o seu verdadeiro inimigo ao iniciar um negócio e fabricar produtos. https://dandan2009.github.io/2019/03/20/competitors-are-not-the-enemy/

Dicas

Quando o git envia o código, há informações do autor, como nome de usuário e endereço de e-mail. Porém, se as informações do autor estiverem acidentalmente erradas ou não estiverem de acordo com as especificações, como devo modificá-las? O script a seguir pode ajudá-lo a modificar as informações do autor enviadas. Observe que aqui estão todas as informações do autor enviadas que foram modificadas. Ao utilizá-lo, tome cuidado para não alterar os envios de outras pessoas pelos seus.


#!/bin/sh

git filter-branch --env-filter '

an="$GIT_AUTHOR_NAME"
am="$GIT_AUTHOR_EMAIL"
cn="$GIT_COMMITTER_NAME"
cm="$GIT_COMMITTER_EMAIL"
if [ "$GIT_COMMITTER_EMAIL" = "要修改的@邮箱地址.com" ]
then
    cn="想要改成的用户名"
    cm="想要改成的邮箱"
fi
if [ "$GIT_AUTHOR_EMAIL" = "要修改的@邮箱地址.com" ]
then
    an="想要改成的用户名"
    am="想要改成的邮箱"
fi
    export GIT_AUTHOR_NAME="$an"
    export GIT_AUTHOR_EMAIL="$am"
    export GIT_COMMITTER_NAME="$cn"
    export GIT_COMMITTER_EMAIL="$cm"
'

Após a execução das etapas acima, envie o histórico correto para o Github:

git push --force --tags origin 'refs/heads/*'

Nota: 1 Faça backup do código antes de executar 2 Após executar git push --force --tags origin 'refs/heads/*', exclua o warehouse local existente e clone-o novamente.

Ao executar o script acima novamente no mesmo warehouse, você será solicitado:

Cannot create a new backup.
A previous backup already exists in refs/original/
Force overwriting the backup with -f

Basta executar o seguinte comando

git update-ref -d refs/original/refs/heads/master

Compartilhar

O conteúdo a seguir é compartilhado por um internauta em um grupo WeChat.

Este caso é muito simples e interessante, mas a procura é real e forte. O compartilhamento do autor original nos trouxe muita inspiração para a descoberta de pontos problemáticos e o desenvolvimento de produtos. Situação básica

  1. Nome do produto: Software Salem
  2. Recursos do produto: versão em espanhol do aplicativo Bíblia para iOS
  3. Volume de instalação: mais de 1,3 milhão
  4. Renda mensal: mais de US$ 10.000 4 inspirações que o produto de 0 a 1 nos trouxe
  1. O autor entende espanhol, então ele fez uma versão em espanhol da Bíblia como um aplicativo Jos, e uma versão em áudio em espanhol do aplicativo foi lançada após um período de tempo.
  1. Ele mencionou uma maneira de encontrar rapidamente necessidades reais: folhear a lista da App Store, procurar aplicativos com avaliações ruins de cima para baixo e depois copiá-los para outros modelos de linguagem. Como essas necessidades foram confirmadas e o modelo foi bem-sucedido, você só precisa alterar algumas novas variáveis para obter lucros rapidamente, como alterar variáveis de idioma, alterar variáveis de canal, etc.
  2. Além de fazer uma versão em texto da Bíblia em espanhol, o autor mencionou que uma operação muito importante para o crescimento de sua renda foi fazer uma versão em áudio desses conteúdos gratuitos, o que aumentou muito sua renda passiva. A inspiração para nós é que além de variáveis ​​como idioma e canais, a forma da mídia também é uma variável. Texto, imagens, áudio e vídeo. Cada tipo tem sua demanda correspondente. Precisamos procurar e descobrir lacunas no mercado.
  3. A partir deste caso, também podemos nos inspirar: encontrar obras no campo do direito autoral público, reprocessá-las e reproduzi-las para torná-las mais alinhadas às necessidades do público, como Water Margin e Dream of Red Mansions, reprocessá-las e redistribuí-las

É mencionado aqui para fazer seu próprio APP. Se você deseja desenvolver de forma independente, mas não tem ideia, você pode tentar isso.

FAQ

What to read next

Want more posts about ARTS?

Posts in the same category are usually the best next step for reading more on this topic.

View same category

Want to keep following #iOS?

Tags are useful for related tools, specific problems, and similar troubleshooting notes.

View same tag

Want to explore another direction?

If you are not sure what to read next, return to the homepage and start from categories, topics, or latest updates.

Back home
Related

Continue reading

Back homeView same category