Tech Notes
Back home

ARTES #028

ARTS22 de marzo de 2019 a las 06:523 min read

ARTES #028

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

##ARTES 028

este es el articulo 28

ARTES es una actividad iniciada por 由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.

Pregunta sobre el algoritmo del algoritmo

2. Suma dos números

Dificultad: Media

Dadas dos listas enlazadas no vacías para representar dos números enteros no negativos. Entre ellos, sus respectivos dígitos se almacenan en orden inverso y cada uno de sus nodos solo puede almacenar un dígito.

Si sumamos estos dos números, se devolverá una nueva lista vinculada que representa su suma.

Puedes asumir que ningún número comenzará con 0 excepto el número 0.

Ejemplo:

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

La dificultad de esta pregunta es media. La principal dificultad radica en considerar diferentes casos. Mi primera respuesta es la siguiente:

Solución

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;
}

La lógica anterior también es muy clara y simple, pero cuando la entrada es 5 o 5, el resultado es incorrecto. Porque pensé menos en la situación.

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;
}

El resultado de la operación anterior es:

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.

El siguiente registro de envío tiene un tiempo de ejecución de 16 ms y actualmente ocupa el primer 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;
}

Pero lo ejecuté y los resultados son los siguientes, por lo que el entorno de prueba también está cambiando y el tiempo de ejecución del mismo código también está cambiando.

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. La subcadena más larga sin caracteres repetidos Copiar para Markdown

Dificultad: Media

Dada una cadena, busque la longitud de la subcadena más larga que no contenga caracteres repetidos.

Ejemplo 1:

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

Ejemplo 2:

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

Ejemplo 3:

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

Solución

Idioma: C

Mi respuesta es la siguiente:

//滑动窗口
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;
}

El siguiente es un ejemplo que tarda 8 ms en ejecutarse, pero lo ejecuté y el tiempo de ejecución es el mismo que el de mi código (el siguiente es el tiempo de ejecución de mi 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;
}

Versión en inglés: envío de muestra de 8 ms, la idea de esta implementación es

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. Encuentre la mediana de dos matrices ordenadas

Dificultad: Dificultad

Dadas dos matrices ordenadas nums1 y nums2 de tamaño my n.

Encuentre la mediana de estas dos matrices ordenadas y se requiere que la complejidad temporal del algoritmo sea O (log (m + n)).

Puede suponer que nums1 y nums2 no estarán vacíos al mismo tiempo.

Ejemplo 1:

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

则中位数是 2.0

Ejemplo 2:

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

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

Solución

Idioma: C

Primero combine matrices, luego 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;
}

Revisión

Este artículo habla principalmente sobre cuál es su verdadero enemigo al iniciar un negocio y fabricar productos. https://dandan2009.github.io/2019/03/20/competitors-are-not-the-enemy/

Consejos

Cuando git envía código, hay información del autor, como el nombre de usuario y la dirección de correo electrónico. Sin embargo, si la información del autor es accidentalmente errónea o no cumple con las especificaciones, ¿cómo debo modificarla? El siguiente script puede ayudarle a modificar la información del autor enviada. Tenga en cuenta que aquí está toda la información del autor enviada que ha sido modificada. Al usarlo, tenga cuidado de no cambiar los envíos de otras personas por los suyos.


#!/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"
'

Después de ejecutar los pasos anteriores, envíe el historial correcto a Github:

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

Nota: 1 Haga una copia de seguridad del código antes de ejecutar 2 Después de ejecutar git push --force --tags origin 'refs/heads/*', elimine el almacén local existente y clónelo nuevamente.

Cuando vuelva a ejecutar el script anterior en el mismo almacén, se le preguntará:

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

Simplemente ejecute el siguiente comando

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

Compartir

El siguiente contenido es compartido por un internauta en un grupo de WeChat.

Este caso es muy simple e interesante, pero la demanda es real y fuerte. El intercambio del autor original nos ha brindado mucha inspiración para el descubrimiento de puntos débiles y el desarrollo de productos. Situación básica

  1. Nombre del producto: Salem Software
  2. Características del producto: Versión en español de la Biblia iOS App
  3. Volumen de instalación: más de 1,3 millones
  4. Ingresos mensuales: más de $10,000 4 inspiraciones que nos trae el producto del 0 al 1
  1. El autor entiende español, por lo que creó una versión en español de la Biblia como una aplicación Jos, y después de un tiempo se lanzó una versión de audio en español de la aplicación.
  1. Mencionó una forma de encontrar rápidamente necesidades reales: hojear la lista de la App Store, buscar aplicaciones con malas críticas de arriba a abajo y luego copiarlas a otros modelos de lenguaje. Debido a que estas necesidades se han confirmado y el modelo ha tenido éxito, solo necesita cambiar algunas variables nuevas para obtener ganancias rápidamente, como cambiar las variables de idioma, cambiar las variables de canal, etc.
  2. Además de realizar una versión en texto de la Biblia en español, el autor mencionó que una operación muy clave para el crecimiento de sus ingresos fue realizar una versión en audio de estos contenidos gratuitos, lo que incrementó considerablemente sus ingresos pasivos. La inspiración para nosotros es que, además de variables como el idioma y los canales, la forma de los medios también es una variable. Texto, imágenes, audio y vídeo. Cada tipo tiene su correspondiente demanda. Necesitamos buscar y descubrir huecos en el mercado.
  3. De este caso, también podemos inspirarnos: encontrar obras en el campo de los derechos de autor públicos, reprocesarlas y reproducirlas para adaptarlas más a las necesidades del público, como Water Margin y Dream of Red Mansions, reprocesarlas y redistribuirlas.

Se menciona aquí para crear su propia APLICACIÓN. Si quieres desarrollarte de forma independiente pero no tienes idea, puedes probar esto.

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