الفنون رقم 009

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

فنون 009

هذه هي المادة 9

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

سؤال خوارزمية leetcode 338. عد البتات: الصعوبة: معتدلة

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2
Output: [0,1,1]
Example 2:

Input: 5
Output: [0,1,1,2,1,2]
Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

عملية حل المشكلات:

0	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	1	2	1	2	2	3	1	2	2	3	2	3

إذا كان i مرفوعًا للأس n، فإن التمثيل الثنائي لـ i يحتوي على 1 واحد فقط. إذا لم يكن i مرفوعًا تمامًا للقوة n، فكيف يجب أن نحسبه؟ يمكن تقسيمها إلى 2^n + m، 2^n < i و 2^n+1 > i. على سبيل المثال، يمكن تقسيم 13 إلى 2^3 + 5. عدد 1s الموجود في البيانات الثنائية لـ 13 يساوي عدد 1s الموجود في البيانات الثنائية 1 زائد 5. يمكن ملاحظة أنه يمكننا استخدام البيانات المعروفة للعثور على البيانات غير المعروفة. مفتاح التنفيذ هنا هو كيفية العثور على n، وهي العملية اللوغاريتمية ذات الأساس 2. التنفيذ كما يلي، وقت التشغيل هو 20 مللي ثانية:

int* countBits(int num, int* returnSize) {
    int* nums = (int*)malloc(sizeof(int) * (num + 1));
    nums[0]  = 0;
    if (num >0) {
        nums[1]  = 1;
        for (int i = 2; i <=num; i++) {
            double log2Dou = log2((double)i);
            int log2int = log2Dou;
            int  remainder = i - pow(2, log2int);
            nums[i] = nums[remainder] + 1;
        }
    }
    *returnSize = num+1;
    return nums;
}

رأيت تنفيذًا قصيرًا، على النحو التالي، وقت التشغيل هو 16 مللي ثانية

int* countBits(int num, int* returnSize) 
{
    int* dp = (int*)malloc(sizeof(int) * (num + 1));
    for (dp[0] = 0, *returnSize = 1; *returnSize <= num; ++*returnSize)
        dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1);
    return dp;
}

دعونا نحلل هذا التنفيذ: مفتاح هذه الخوارزمية هو فهم dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1); من الأسهل فهم ما إذا كان *returnSize مكتوبًا بالنظام الثنائي. افترض أن *returnSiz يساوي 13، التمثيل الثنائي لـ 13 هو: 0000 1101، 0000 1101 >> 1، متبوعًا بـ 0000 0110، تتم إزالة البت الأخير، ويتم ملء البت العالي بـ 0؛ إذا كان الرقم الأخير هو 0، مثل 12، فإن عدد الآحاد الموجود في 0000 1100 هو نفس عدد الآحاد الموجود في الرقم الذي تم إزاحته إلى اليمين 0000 0110. إذا كان الرقم الأخير هو 1، مثل 13، فإن عدد الآحاد الموجود في 00001101 يزيد بمقدار 1 عن عدد الآحاد الموجود في الرقم 00000110 بعد الإزاحة اليمنى. تم حساب عدد الأرقام الثنائية التي تحتوي على 1 بعد التحول إلى اليمين مسبقًا.

ما إذا كان يساوي أو 1 أكثر من بعد التحول إلى اليمين يمكن الحصول عليه عن طريق البت AND (*returnSize & 1)، أو يمكن أيضًا استخدام *returnSize % 2.

دعونا نلقي نظرة على خوارزمية أخرى:

int* countBits(int num, int* returnSize) {
    int *dp, i, nearest;

    dp = (int *)malloc(sizeof(int) * (num + 1));
    *returnSize = num + 1;
    if (dp == NULL)
        return NULL;

    dp[0] = 0;

    if (num >= 1)
        dp[1] = 1;

    i = nearest = 2;

    while (i <= num)
    {
        nearest = (i & (i - 1)) == 0 ? i : nearest;
        dp[i] = 1 + dp[i - nearest];
        i++;
    }

    return dp;
}

المفتاح لهذه الخوارزمية هو

    while (i <= num)
    {
        nearest = (i & (i - 1)) == 0 ? i : nearest;
        dp[i] = 1 + dp[i - nearest];
        i++;
    }

بعد فهم nearest = (i & (i - 1)) == 0 ? i : nearest;، ستفهم أيضًا هذه الخوارزمية. عندما أستحق شيئًا ما، (i & (i - 1)) == 0 سيكون صحيحًا. سيكون صحيحًا فقط عندما يكون عمري 2^n بالضبط. لذلك فإن فكرة هذه الخوارزمية هي نفس فكرتي في التنفيذ، ولكنها أكثر ذكاءً في العثور على n وتستحق التعلم.

هناك أيضًا الخوارزمية التالية، وهي أيضًا أكثر ذكاءً عند العثور على n. العلامة هي 2 ^ ن:

int* countBits(int num, int* returnSize) { 20
    int* nums=(int *)calloc(num+1,sizeof(int));

    for(int i=1,sign=1;i<=num;i++){
        if(i>1&&i%sign==0){
            sign*=2;
        }
        int n=i%sign;
        nums[i]=nums[n]+1;
    }

    *returnSize=num+1;
    return nums;
}

دعونا نحلل خوارزمية أخرى:

int* countBits(int num, int* returnSize) { //28
    int bit = 1;
    *returnSize = num+1;
    int *table = (int *) malloc((*returnSize)*sizeof(int));
    memset(table, 0, (*returnSize)*sizeof(int));
    


    for (int i = 1; i <= num; i++)
    {
        if ((1 << (bit-1)) == i)
        {
            table[i] = 1;
            bit++;
        }

        else
            table[i] = 1 + table[i & ~(1 << (bit-2))];
    }
    return table;
}

وتنقسم فكرة تنفيذ هذه الخوارزمية أيضًا إلى 2^n + m. إذا كان يعادل البحث عن n، وإلا فإنه يبحث عن m. table[i] = 1 + table[i & ~(1 << (bit-2))];، الرقم 1 الموجود على الجانب الأيسر من علامة الجمع هو أعلى 1، وهو 2^n. i & ~(1 << (bit-2)) في الجدول[i & ~(1 << (bit-2)]); هو م، وهو ما يعادل ط - 2^ن.

تم تحليل تطبيقات العديد من الأشخاص الآخرين أعلاه، ويمكنك أن ترى أنها في الأساس تقنيات لتشغيل البيانات الثنائية.

مراجعة

هذه المقالة مأخوذة من: https://blog.google/technology/developers/pushing-limits-streaming-technology/ دفع حدود تكنولوجيا البث تحدي حدود تكنولوجيا البث

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

لقد كنا نعمل على Project Stream، وهو اختبار تقني لحل بعض أكبر تحديات البث. في هذا الاختبار، سنتجاوز الحدود باستخدام أحد أكثر تطبيقات البث تطلبًا، وهي لعبة فيديو رائجة. لقد عملنا على Project Stream، وهو اختبار تكنولوجي يحل أكبر التحديات التي تواجه تدفق الوسائط. في هذا الاختبار، سنتخطى الحدود باستخدام أحد تطبيقات البث الأكثر تطلبًا - وهي لعبة فيديو رائجة.

لقد عقدنا شراكة مع أحد ناشري ألعاب الفيديو الأكثر ابتكارًا ونجاحًا، Ubisoft، لبث لعبة Assassin’s Creed Odyssey®‎ التي سيتم إصدارها قريبًا إلى متصفح Chrome على جهاز كمبيوتر محمول أو سطح مكتب. بدءًا من 5 أكتوبر، سيتمكن عدد محدود من المشاركين من لعب أحدث إصدار من هذه السلسلة الأكثر مبيعًا مجانًا طوال مدة اختبار Project Stream. نحن نعمل مع أحد ناشري ألعاب الفيديو الأكثر ابتكارًا ونجاحًا، Ubisoft، لبث إصدارهم القادم من Assassin’s Creed Odyssey® في Chrome لأجهزة الكمبيوتر المحمول أو سطح المكتب. بدءًا من 5 أكتوبر، سيتمكن عدد محدود من المشاركين من لعب أحدث لعبة في السلسلة الأكثر مبيعًا مجانًا خلال الفترة التجريبية للمشروع. لقد عقدنا شراكة مع Ubisoft، أحد أكثر ناشري ألعاب الفيديو ابتكارًا ونجاحًا، لجلب Assassin’s Creed Odyssey® القادمة إلى متصفح Chrome على الكمبيوتر المحمول أو سطح المكتب. بدءًا من 5 أكتوبر، سيلعب عدد محدود من المشاركين السلسلة الأكثر مبيعًا مجانًا أثناء البث التجريبي للمشروع.

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

إن التكنولوجيا والإبداع وراء ألعاب الفيديو AAA هذه غير عادية - بدءًا من التفاصيل المذهلة والحركة الواقعية لجلد الشخصيات وملابسها وشعرها، إلى النطاق الهائل للعالم الذي تتكشف فيه اللعبة، وصولاً إلى كل شفرة أخيرة من العشب. يتم تشغيل كل بكسل بواسطة مجموعة من تقنيات العرض في الوقت الفعلي، والبراعة الفنية، والمؤثرات البصرية، والرسوم المتحركة، والمحاكاة، والفيزياء، والديناميكيات. لقد استلهمنا منشئي الألعاب الذين أمضوا سنوات في صياغة هذه العوالم والمغامرات والتجارب المذهلة، ونحن نبني التكنولوجيا التي نأمل أن تدعم هذا الإبداع وتمكنه. تعتبر التكنولوجيا والإبداع وراء ألعاب الفيديو AAA هذه استثنائية - بدءًا من التفاصيل المذهلة والحركة النابضة بالحياة لجلود الشخصيات وملابسها وشعرها، إلى الحجم الهائل للعوالم التي تتكشف فيها الألعاب، وصولاً إلى كل شفرة من العشب. يتم تشغيل كل بكسل بواسطة مجموعة من تقنيات العرض في الوقت الفعلي، والفنية، والمؤثرات البصرية، والرسوم المتحركة، والمحاكاة، والفيزياء والديناميكيات. نحن نستمد الإلهام من مطوري الألعاب الذين أمضوا سنوات في إنشاء هذه العوالم والمغامرات والتجارب المذهلة، ونحن نعمل على تطوير التكنولوجيا التي نأمل أن تدعم هذا الإبداع وتمكنه.هناك مساحات محدودة متاحة لـ Project Stream، ولكن إذا كنت مهتمًا بالمشاركة، فيمكنك التقديم على موقعنا الإلكتروني. تم تصميم Project Stream نحو اتصالات الإنترنت المنزلية التي تبلغ سرعتها 25 ميجابت في الثانية، ويجب أن يكون عمرك 17 عامًا أو أكثر وتعيش في الولايات المتحدة للمشاركة (يمكن العثور على المتطلبات الأخرى في مركز المساعدة).

المساحة المتاحة في Project Stream محدودة، ولكن إذا كنت مهتمًا بالمشاركة، فيمكنك التقديم على موقعنا الإلكتروني. يعمل Project Stream على اتصال إنترنت منزلي بسرعة 25 ميجابت في الثانية، ويجب أن يكون عمرك 17 عامًا أو أكثر وتقيم في الولايات المتحدة للمشاركة (يمكن العثور على المتطلبات الإضافية في مركز المساعدة).

نحن نتطلع إلى ما يخبئه مستقبل البث، وتعليقات المشاركين في Project Stream. نشكرك على مساعدتنا في الارتقاء بالبث إلى المستوى التالي. نحن نتطلع إلى مستقبل البث وتعليقات المشاركين في Project Stream. نشكرك على مساعدتنا في الارتقاء بالبث إلى المستوى التالي.

<عرض الإطار = “560” الارتفاع = “315” src = “https://www.youtube.com/embed/sE53eSbzxoU” إطار الحدود = “1” تسمح = "التشغيل التلقائي؛ الوسائط المشفرة"allowfullscreen></iframe>

Ubisoft وAssassin’s Creed Odyssey هما علامتان تجاريتان لشركة Ubisoft Entertainment في الولايات المتحدة و/أو البلدان الأخرى.

نشر في: المطورين

نصائح:

كيفية تنفيذ الرسوم المتحركة الخطية مثل ما يلي

يمكن تنفيذه باستخدام CAShapeLayer + UIBezierPath. تكمن الصعوبة هنا في كيفية تحديد CGPath. إنها بسيطة ويمكن تعديلها ببطء بنفسك. بالنسبة للرسوم المتحركة المعقدة، يمكن إنشاء الكود تلقائيًا.

الفكرة العامة هي كما يلي 1 اسمح للمصمم بتصدير الرسومات التي رسمها Sketch بتنسيق SVG 2 اسحب ملف SVG إلى PaintCode، وسيقوم برنامج PaintCode تلقائيًا بإنشاء رمز مسار OC. 3 باستخدام رمز المسار هذا، يمكننا رسم هذا الرسم 4 ثم استخدم CABasicAnimation لإضافة الرسوم المتحركة

شارك:

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

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