ARTES #027

ARTES 027

Este é o artigo 27

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

Revendo o passado e aprendendo algo novo, decidi fazer novamente as perguntas que havia feito na ordem. Embora esta questão seja simples, ainda é difícil otimizar tempo e memória.

A solução mais estúpida para esta questão é o método da força bruta. Acho que todos podem pensar nisso e pode ser repassado ao LeetCode.

Uma ideia um pouco melhor é ordenar primeiro e depois usar a busca binária, mas observe que há um problema aqui, ou seja, se o array original for ordenado diretamente, as informações de posição dos elementos mudarão, mas a questão exige que as informações de posição sejam retornadas. Para resolver este problema, a primeira coisa que se pode pensar é fazer uma cópia de backup do array original, encontrar o valor e depois encontrar o subscrito correspondente, mas isso é quase o mesmo que uma solução de força bruta.

Uma abordagem melhor é construir uma estrutura de dados, como uma estrutura, registrar os valores e as posições correspondentes e, em seguida, classificá-los. Isso resolve o problema de encontrar o subscrito correspondente após encontrar o valor.

1. Soma de dois números

Dificuldade: Fácil

Dado um array de inteiros nums e um valor alvo target, encontre os dois inteiros no array cuja soma é o valor alvo e retorne seus subscritos do array.

Você pode assumir que cada entrada corresponderá a apenas uma resposta. No entanto, você não pode reutilizar os mesmos elementos nesta matriz.

Exemplo:

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

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

Solução

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

A seguir está a solução 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;
​
}

Solução de 8ms:

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

Embora as perguntas sejam simples, você ainda pode aprender novos conhecimentos estudando as soluções de outras pessoas.

Revisão

Este artigo fala sobre processos e threads, principalmente sobre threads e segurança de threads. https://dandan2009.github.io/2019/03/18/a-gentle-introduction-to-multithreading/

Dicas

Com a fragmentação dos dispositivos iOS, a adaptação do iOS está se tornando cada vez mais problemática. Nosso tamanho de visualização é ampliado de acordo com a proporção do dispositivo. Por exemplo, a altura do rótulo no 6s é 18 e no 6p é 18 * (540/375), que é 25,94. Observe que existem decimais aqui. Neste momento, algumas visualizações terão uma linha extra fina, inexplicavelmente. Por exemplo, o UIlabel que encontrei no iPhone xr terá uma linha extra na parte superior, e é apenas iPhone. Quando xr aparece, a solução é muito simples, que é convertê-lo para um número inteiro; portanto, os valores relacionados à posição de visualização são melhor convertidos em números inteiros durante o processo de conversão.

Compartilhar

Sinto-me muito ocupado todos os dias, mas não sei com o que estou ocupado. Olhando para trás na semana, sinto que fiz muito pouco progresso. Futuramente, decidi adotar um valor meta, que é planejar a obra a ser concluída no dia seguinte com um dia de antecedência. Isso melhorará a eficiência do trabalho e do estudo.