الفنون رقم 027

الفنون 027

هذه المادة 27

ARTS هو نشاط بدأه 由左耳朵耗子--陈皓: قم بإجراء سؤال واحد على الأقل عن خوارزمية leetcode كل أسبوع، واقرأ مقالًا تقنيًا واحدًا على الأقل باللغة الإنجليزية وعلق عليه، وتعلم مهارة فنية واحدة على الأقل، وشارك المقالة مع الآراء والأفكار. (أي أن الخوارزمية والمراجعة والنصائح والمشاركة يشار إليها باسم ARTS) وتستمر لمدة عام واحد على الأقل.

سؤال خوارزمية الخوارزمية

بمراجعة الماضي وتعلم شيء جديد، قررت أن أعيد الأسئلة التي قمت بها مرة أخرى بالترتيب. على الرغم من أن هذا السؤال بسيط، إلا أنه لا يزال من الصعب تحسين الوقت والذاكرة.

الحل الأغبى لهذا السؤال هو طريقة القوة الغاشمة. أعتقد أن الجميع يمكن أن يفكروا في هذا، ويمكن تمريره على LeetCode.

الفكرة الأفضل قليلاً هي الفرز أولاً ثم استخدام البحث الثنائي، لكن لاحظ أن هناك مشكلة هنا، وهي أنه إذا تم فرز المصفوفة الأصلية مباشرة، فستتغير معلومات موضع العناصر، لكن السؤال يتطلب إرجاع معلومات الموضع. من أجل حل هذه المشكلة، أول ما يمكن التفكير فيه هو عمل نسخة احتياطية من المصفوفة الأصلية، ثم العثور على القيمة ثم العثور على الرمز المنخفض المقابل، ولكن هذا يشبه تقريبًا حل القوة الغاشمة.

الطريقة الأفضل هي إنشاء بنية بيانات، مثل البنية، وتسجيل القيم والمواضع المقابلة، ثم فرزها. يؤدي هذا إلى حل مشكلة العثور على الحرف المقابل بعد العثور على القيمة.

1. مجموع رقمين

الصعوبة: سهل

بالنظر إلى مصفوفة أعداد صحيحة nums وقيمة مستهدفة target، يرجى العثور على العددين الصحيحين ** في المصفوفة التي يكون مجموعها هو القيمة المستهدفة، وإرجاع اشتراكات المصفوفة الخاصة بها.

يمكنك أن تفترض أن كل إدخال سيتوافق مع إجابة واحدة فقط. ومع ذلك، لا يمكنك إعادة استخدام نفس العناصر في هذا الصفيف.

مثال:

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

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

الحل

اللغة: ج

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

فيما يلي الحل لـ 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;
​
}

الحل 8 مللي ثانية:

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

على الرغم من أن الأسئلة بسيطة، إلا أنه لا يزال بإمكانك تعلم معرفة جديدة من خلال دراسة حلول الآخرين.

مراجعة

تتحدث هذه المقالة عن العمليات والخيوط، بشكل أساسي حول الخيوط وسلامة الخيوط. https://dandan2009.github.io/2019/03/18/a-gentle-introduction-to-multithreading/

نصائح

مع تجزئة أجهزة iOS، أصبح التكيف مع نظام iOS أكثر إزعاجًا. يتم تكبير حجم العرض الخاص بنا وفقًا لنسبة الجهاز. على سبيل المثال، ارتفاع الملصق على 6s هو 18، وعلى 6p هو 18 * (540/375)، وهو 25.94. لاحظ أن هناك أعدادًا عشرية هنا. في هذا الوقت، سيكون لبعض طرق العرض خط رفيع للغاية لسبب غير مفهوم. على سبيل المثال، سيكون UIlabel الذي واجهته على iPhone xr يحتوي على خط إضافي في الأعلى، وهو iPhone فقط عندما يظهر xr، يكون الحل بسيطًا للغاية، وهو تحويله إلى عدد صحيح؛ لذلك من الأفضل تحويل القيم المتعلقة بموضع العرض إلى أعداد صحيحة أثناء عملية التحويل.

شارك

أشعر بأنني مشغول جدًا كل يوم، لكن لا أعرف ما الذي أنا مشغول به. إذا نظرنا إلى الوراء في هذا الأسبوع، أشعر أنني لم أحقق سوى تقدم ضئيل للغاية. في المستقبل، قررت اعتماد قيمة مستهدفة، وهي التخطيط للعمل الذي سيتم إنجازه في اليوم التالي قبل يوم واحد. سيؤدي ذلك إلى تحسين كفاءة العمل والدراسة.