الفنون رقم 018

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

الفنون 018

هذه المادة 18

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

107. اجتياز ترتيب مستوى الشجرة الثنائية II (اجتياز ترتيب مستوى الشجرة الثنائية II)

صعوبة السؤال: سهل

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

على سبيل المثال: بالنظر إلى الشجرة الثنائية [3,9,20,null,null,15,7]،

    3
   / \
  9  20
    /  \
   15   7

قم بإرجاع اجتياز التسلسل الهرمي من الأسفل إلى الأعلى على النحو التالي:

[
  [15,7],
  [9,20],
  [3]
]

الحل

اللغة: ج

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    
}

/**

• تعريف عقدة الشجرة الثنائية.
• بناء TreeNode {
• كثافة العمليات فال؛
• بناء TreeNode *left;
• struct TreeNode *right;
• }; / /*
• إرجاع مصفوفة من المصفوفات ذات الحجم *returnSize.
• يتم إرجاع أحجام المصفوفات كصفيف *columnSizes.
• ملاحظة: يجب أن يتم وضع كل من المصفوفة التي تم إرجاعها ومصفوفة columnSizes في مكان صغير، مع افتراض أن المتصل يستدعي مجانًا (). / int**levelOrder(struct TreeNode root, int* columnSizes, int* returnSize) {

}

الطريقة 1

int getLevelOrderBottom(struct TreeNode* root, int*** ArrayRet, int** columnSizes, int length, int level) {
    if (root == NULL) return length;
    int size = length;
    if (level>size - 1) {
        *ArrayRet = realloc(*ArrayRet, sizeof(int*)*(size + 1));
        (*ArrayRet)[level]= calloc(0, sizeof(int));
        *columnSizes = realloc(*columnSizes, sizeof(int)*(size + 1));
        (*columnSizes)[level] = 0;
        size++;
    }
    (*ArrayRet)[level] = realloc((*ArrayRet)[level], sizeof(int)*((*columnSizes)[level] + 1));
    (*ArrayRet)[level][(*columnSizes)[level]] = root->val;
    (*columnSizes)[level] += 1;
    size = getLevelOrderBottom(root->left, ArrayRet, columnSizes, size, level + 1);
    size = getLevelOrderBottom(root->right, ArrayRet, columnSizes, size, level + 1);
    return size;
}
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    int **ArrayRet = calloc(0, sizeof(int *));
    *returnSize = getLevelOrderBottom(root, &ArrayRet, columnSizes, 0, 0);

    //reverse the array
    int **ret = calloc(*returnSize, sizeof(int *));
    for(int i=0;i<*returnSize;i++){
        ret[i]=calloc((* columnSizes)[*returnSize-i-1],sizeof(int));
        memcpy(ret[i],ArrayRet[*returnSize-i-1],sizeof(int)*(* columnSizes)[*returnSize-i-1]);
    }
    int k=0,j=* returnSize-1;
    while(k<j){
        int tmp=(* columnSizes)[k];
        (* columnSizes)[k++]=(* columnSizes)[j];
        (* columnSizes)[j--]=tmp;
    }
    return ret;
}

الطريقة الثانية، من سجل إرسال LeetCode:

int GetdepthofTree(struct TreeNode* root){
    if (!root) return 0;
    int left = GetdepthofTree(root->left);
    int right = GetdepthofTree(root->right);
    if (left > right)
        return left+1;
    else
        return right+1;
}
 
 
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
    if (!root){
        return NULL;
    }
    //获取二叉树的深度，最大层数或者说
    int depth = *returnSize = GetdepthofTree(root);
    
    //ret是一个指向一个二维数组的指针，这一块地址是我们自己开辟的，需要malloc
    int** ret = (int**)malloc(depth*sizeof(int*));
    
    //columnSizes是一个指向指针的指针，这个地址已经指定了，就是说这个地址了存放的下一个地址已经确定了，但是下一个地址里存放的还是地址，这个地址任然不确定，那么就需要malloc了
    //*columnSizes是一个指向一个一维数组的指针，数组的大小也是depth
    
    *columnSizes = (int*)malloc(depth*sizeof(int));
    int front = 0, back = 0;
    struct TreeNode* queue[10000];
    queue[back++] = root;
    while (front < back){
        int start = front, end = back;
        (*columnSizes)[--depth] = end - start;
        front = end;
        //开始的时候我们只给了ret的地址，因为ret是一个二维数组的起始地址，但是这个二维数组里面的一维数组的地址并没有确定，就需要malloc来确定
        ret[depth] = (int*)malloc((end - start)*sizeof(int));
        for (int i=start; i<end; i++){
            ret[depth][i-start] = queue[i]->val;
            if (queue[i]->left) queue[back++] = queue[i]->left;
            if (queue[i]->right) queue[back++] = queue[i]->right;
        }
    }
    return ret;
}

مراجعة

أنظر أيضا: هياكل البيانات والخوارزميات المشتركة: https://dandan2009.github.io/2018/11/28/data-structures-part3-language-support/

نصائح

دليل المبتدئين لترميز تظليل الرسومات.

https://gamedevelopment.tutsplus.com/series/a-beginners-guide-to-coding-graphics-shaders--cms-834

هذه السلسلة جيدة جدًا. يمكنك التحقق من ذلك كبرنامج تعليمي تمهيدي حول Graphics Shaders.

يحاكي iOS طريقة الشبكة الضعيفة:

1. استخدم جهازًا حقيقيًا. هناك خيار قيد التطوير وخيار Network Link Conditioner في إعدادات الجهاز الحقيقي.

حدد أحد أنواع الشبكات لضبط سرعة الشبكة

2. اضبط جهاز المحاكاة على بيئة شبكة ضعيفة: الطريقة الأولى: انتقل إلى Apple Developer Center لتنزيل أدوات إضافية لـ Xcode

   افتح تفضيلات النظام، وابحث عن Network Link Conditioner، وانقر نقرًا مزدوجًا لفتحه.

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

الطريقة الثانية: تشارلز

شارك

أدوات ومواقع التعلم المرئي التي ترسم عدة خوارزميات:

جامعة سان فرانسيسكو هياكل البيانات والخوارزميات http://hao.jobbole.com/visualizing-algorithms-and-data-structure/

VisuAlgo: تعلم الخوارزميات وهياكل البيانات من خلال الرسوم المتحركة http://hao.jobbole.com/visualgo/

Algomation: منصة تعليمية لعرض وإنشاء ومشاركة الخوارزميات http://hao.jobbole.com/algomation/

متخيل الخوارزمية: http://algorithm-visualizer.org يحتوي Algorithm Visualizer على أكثر من 10.6 ألف نجمة على GitHub: https://github.com/algorithm-visualizer/algorithm-visualizer

شارك موقعًا لتعلم اللغة الإنجليزية: https://learnamericanenglishonline.com/Red Level/R1 Do.html