ARTES #027

##ARTES 027

este es el articulo 27

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

Revisando el pasado y aprendiendo algo nuevo, decidí volver a hacer las preguntas que había hecho en orden. Aunque esta pregunta es simple, todavía es difícil optimizar tanto el tiempo como la memoria.

La solución más estúpida a esta cuestión es el método de fuerza bruta. Supongo que todos pueden pensar en esto y se puede transmitir a LeetCode.

Una idea un poco mejor es ordenar primero y luego usar la búsqueda binaria, pero tenga en cuenta que hay un problema aquí, es decir, si la matriz original se ordena directamente, la información de posición de los elementos cambiará, pero la pregunta requiere que se devuelva la información de posición. Para resolver este problema, lo primero que se puede pensar es hacer una copia de seguridad de la matriz original, luego encontrar el valor y luego encontrar el subíndice correspondiente, pero esto es casi lo mismo que una solución de fuerza bruta.

Un mejor enfoque es construir una estructura de datos, como una estructura, registrar los valores y las posiciones correspondientes y luego ordenarlos. Esto resuelve el problema de encontrar el subíndice correspondiente después de encontrar el valor.

1. Suma de dos números

Dificultad: Fácil

Dada una matriz de enteros nums y un valor objetivo target, busque los dos enteros en la matriz cuya suma es el valor objetivo y devuelva sus subíndices de matriz.

Puede suponer que cada entrada corresponderá a una sola respuesta. Sin embargo, no puede reutilizar los mismos elementos en esta matriz.

Ejemplo:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Solución

Idioma: C

#include <stdio.h>
#include <stdlib.h>

struct object {
    int val;
    int index;
};

static int compare(const void *a, const void *b)
{
    return ((struct object *) a)->val - ((struct object *) b)->val;
}

static int * twoSum(int *nums, int numsSize, int target)
{
    int i, j;
    struct object *objs = malloc(numsSize * sizeof(*objs));
    for (i = 0; i < numsSize; i++) {
        objs[i].val = nums[i];
        objs[i].index = i;
    }
    qsort(objs, numsSize, sizeof(*objs), compare);
    
    int count = 0;
    int *results = malloc(2 * sizeof(int));
    i = 0;
    j = numsSize - 1;
    while (i < j) {
        int diff = target - objs[i].val;
        if (diff > objs[j].val) {
            while (++i < j && objs[i].val == objs[i - 1].val) {}
        } else if (diff < objs[j].val) {
            while (--j > i && objs[j].val == objs[j + 1].val) {}
        } else {
            results[0] = objs[i].index;
            results[1] = objs[j].index;
            return results;
        }
    }
    return NULL;
}

La siguiente es la solución para 4ms.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int *res = calloc(2, sizeof(int));
    struct hash {
        int id;
        int pair;
        UT_hash_handle hh;
    } *hashTable = NULL;
    
    for (int i = 0; i < numsSize; i++) {
        struct hash *h;
        HASH_FIND_INT(hashTable, nums + i, h);
        if (h == NULL) {
            h = calloc(1, sizeof(struct hash));
            h->id = target - nums[i];
            h->pair = i;
            HASH_ADD_INT(hashTable, id, h);
        } else {
            res[0] = h->pair;
            res[1] = i;
            return res;
        }
    }
    
    return res;
​
}

Solución de 8 ms:

void swap(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

void heapify(int *arr, int n, int i)
{
    int largest = i; // Initialize largest as root
    int l = (i << 1) + 1; // left = 2*i + 1
    int r = (i << 1) + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        swap(&arr[i], &arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

void heap_sort(int *arr, int len)
{
    int i;
    for (i = len >> 1; i >= 0; --i)
        heapify(arr, len, i);
    for(i = len - 1; i > 0; --i) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

int* twoSum(int* nums, int numsSize, int target) {
    if (!nums || numsSize < 2)
        return NULL;

    if (numsSize > 50) {
        int i, j, sum;
        int *sort = malloc(sizeof(int) * numsSize);
        memcpy(sort, nums, sizeof(int) * numsSize);
        heap_sort(sort, numsSize);
        for (i = 0, j = numsSize - 1; i < j;) {
            sum = sort[i] + sort[j];
            if (sum == target) {
                int k;
                int *res = malloc(sizeof(int) << 1);
                for (k = 0; k < numsSize; k++) {
                    if (nums[k] == sort[i])
                        res[0] = k;
                }
                for (k = 0; k < numsSize; k++) {
                    if (nums[k] == sort[j])
                        res[1] = k;
                }
                free(sort);
                return res;
            } else if (sum < target)
                i++;
            else
                j--;
        }
    } else if (numsSize > 10) {
        int i, j, k, c, l;
        bool back;

        for (i = 0, j = numsSize - 1, back = false; i < j; back = !back) {
            if (back)
                l = j--;
            else
                l = i++;
            c = target - nums[l];
            for (k = i; k <= j; k++) {
                if (nums[k] == c) {
                    int *res = malloc(sizeof(int) << 1);
                    res[0] = l;
                    res[1] = k;
                    return res;
                }
            }
        }
    } else {
        int i, j, c;

        for (i = 0; i < numsSize - 1; i++) {
            c = target - nums[i];
            for (j = i + 1; j < numsSize; j++) {
                if (nums[j] == c) {
                    int *res = malloc(sizeof(int) << 1);
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
    }

    return NULL;
}

Aunque las preguntas son simples, aún puedes aprender nuevos conocimientos estudiando las soluciones de otras personas.

Revisión

Este artículo habla sobre procesos e subprocesos, principalmente sobre subprocesos y seguridad de subprocesos. https://dandan2009.github.io/2019/03/18/a-gentle-introduction-to-multithreading/

Consejos

Con la fragmentación de los dispositivos iOS, la adaptación de iOS se está volviendo cada vez más problemática. El tamaño de nuestra vista se amplía según la proporción del dispositivo. Por ejemplo, la altura de la etiqueta en el 6s es 18 y en el 6p es 18 * (540/375), que es 25,94. Tenga en cuenta que aquí hay decimales. En este momento, algunas vistas tendrán una línea muy delgada inexplicablemente. Por ejemplo, la UIlabel que encontré en el iPhone xr tendrá una línea adicional en la parte superior, y es solo iPhone Cuando aparece xr, la solución es muy simple, que es convertirlo a un número entero; por lo que es mejor convertir los valores relacionados con la posición de la vista a números enteros durante el proceso de conversión.

Compartir

Me siento muy ocupado todos los días, pero no sé en qué estoy ocupado. Mirando retrospectivamente la semana, siento que he progresado muy poco. En el futuro, decidí adoptar un valor objetivo, que es planificar el trabajo que se completará al día siguiente con un día de anticipación. Esto mejorará la eficiencia en el trabajo y el estudio.