SENI #027

SENI 027

Ini adalah pasal 27

SENI adalah kegiatan yang diprakarsai oleh 由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI) dan bertahan setidaknya selama satu tahun.

Pertanyaan algoritma algoritma

Meninjau masa lalu dan mempelajari sesuatu yang baru, saya memutuskan untuk mengerjakan soal-soal yang telah saya kerjakan lagi secara berurutan. Meskipun pertanyaan ini sederhana, namun masih sulit untuk mengoptimalkan waktu dan memori.

Solusi paling bodoh untuk pertanyaan ini adalah metode brute force. Saya rasa semua orang dapat memikirkan hal ini, dan ini dapat diteruskan ke LeetCode.

Ide yang sedikit lebih baik adalah mengurutkan terlebih dahulu dan kemudian menggunakan pencarian biner, tetapi perhatikan bahwa ada masalah di sini, yaitu jika array asli diurutkan secara langsung, informasi posisi elemen akan berubah, tetapi pertanyaannya mengharuskan informasi posisi dikembalikan. Untuk mengatasi masalah ini, hal pertama yang harus dipikirkan adalah membuat salinan cadangan dari array asli, lalu mencari nilainya dan kemudian menemukan subskrip yang sesuai, tetapi ini hampir sama dengan solusi brute force.

Pendekatan yang lebih baik adalah dengan membangun struktur data, seperti struktur, mencatat nilai dan posisi terkait, lalu mengurutkannya. Ini memecahkan masalah menemukan subskrip yang sesuai setelah menemukan nilainya.

1. Jumlah dua angka

Kesulitan: Mudah

Mengingat array bilangan bulat nums dan nilai target target, temukan dua bilangan bulat dalam array yang jumlahnya adalah nilai target, dan kembalikan subskrip arraynya.

Anda dapat berasumsi bahwa setiap masukan hanya akan berhubungan dengan satu jawaban. Namun, Anda tidak dapat menggunakan kembali elemen yang sama dalam array ini.

Contoh:

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

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

Solusi

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

Berikut ini adalah solusi untuk 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;
​
}

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

Meski soalnya sederhana, Anda tetap bisa mempelajari ilmu baru dengan mempelajari solusi orang lain.

Ulasan

Artikel ini membahas tentang proses dan thread, terutama tentang thread dan keamanan thread. https://dandan2009.github.io/2019/03/18/a-gentle-introduction-to-multithreading/

Kiat

Dengan fragmentasi perangkat iOS, adaptasi iOS menjadi semakin merepotkan. Ukuran tampilan kami diperbesar sesuai dengan proporsi perangkat. Misalnya, tinggi label pada 6s adalah 18, dan pada 6p adalah 18 * (540/375), yaitu 25,94. Perhatikan bahwa ada desimal di sini. Saat ini, beberapa tampilan akan memiliki garis ekstra tipis yang tidak dapat dijelaskan. Misalnya UIlabel yang saya temui di iPhone xr akan memiliki garis tambahan di bagian atas, dan itu hanya iPhone. Ketika xr muncul, solusinya sangat sederhana, yaitu mengubahnya menjadi integer; jadi nilai yang terkait dengan posisi tampilan sebaiknya dikonversi ke bilangan bulat selama proses konversi.

Bagikan

Saya merasa sangat sibuk setiap hari, tetapi saya tidak tahu kesibukan saya apa. Melihat ke belakang pada minggu ini, saya merasa kemajuan yang saya buat terlalu sedikit. Kedepannya, saya memutuskan untuk mengadopsi nilai target, yaitu merencanakan pekerjaan yang akan diselesaikan keesokan harinya satu hari sebelumnya. Ini akan meningkatkan efisiensi kerja dan belajar.