الفنون رقم 016

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

الفنون 016

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

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

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

226. عكس الشجرة الثنائية قلب الشجرة الثنائية

الصعوبة: سهل

عكس شجرة ثنائية.

مثال:

الإدخال:

     4
   /   \
  2     7
 / \   / \
1   3 6   9```

الإخراج:

 4

/
7 2 / \ /
9 6 3 1```

** التوافه: ** هذه المشكلة مستوحاة من:

Google: 90% من مهندسينا يستخدمون البرنامج الذي كتبته (Homebrew)، لكن لا يمكنك عكس شجرة ثنائية على السبورة البيضاء، لذا توقف عن العمل.

الحل

اللغة: ج

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    
}

//递归 rcursive
struct TreeNode* invertTree_1(struct TreeNode* root) {
    if (root == NULL) {
        return root;
    }
    if(root->left != NULL || root->right != NULL){
        struct TreeNode *temp = root->left;
        root->left  = root->right;
        root->right = temp;
    }
    if(root->left)
        invertTree(root->left);
    if(root->right)
        invertTree(root->right);
    return root;
}

//迭代 iteratively
struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) {
        return root;
    }
    
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));

    int stackCount = 0;
    struct TreeNode* p = root;
    while (p) {
        if (p->right) {
            stack[stackCount++] = p->right;
        }
        
        if (p->left || p->right) {
            struct TreeNode *temp = p->left;
            p->left  = p->right;
            p->right = temp;
        }
        
        p = p->right;
        if (!p && stackCount >0) {
            p = stack[--stackCount];
        }
    }
    return root;
}

112.مجموع المسار

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

بالنظر إلى شجرة ثنائية ومجموع مستهدف، حدد ما إذا كان هناك مسار من العقدة الجذرية إلى العقدة الورقية في الشجرة. مجموع كل قيم العقدة على هذا المسار يساوي المجموع المستهدف.

الوصف: تشير العقد الورقية إلى العقد التي لا تحتوي على عقد فرعية.

مثال: بالنظر إلى الشجرة الثنائية التالية، بالإضافة إلى الهدف وsum = 22،

              **5**
             / \
            **4 **  8
           /   / \
          **11 ** 13  4
         /  \      \
        7    **2**      1

تُرجع true نظرًا لوجود مسار 5->4->11->2 من العقدة الجذرية إلى العقدة الطرفية مع المجموع المستهدف 22.

الحل

اللغة: ج

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool hasPathSum(struct TreeNode* root, int sum) {
    
}

//递归 rcursive
bool hasPathSum_1(struct TreeNode* root, int sum) {
    if (!root) {
        return false;
    }
    
    if (root->left || root->right) {
        return (hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val));
    }
    return root->val == sum;
}

//迭代 iteratively
bool hasPathSum(struct TreeNode* root, int sum) {

    if (root == NULL) {
        return root;
    }
    
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
    int * sumStack = (int *)malloc(sizeof(int *) * (1000));
    int stackCount = 0;
    
    stack[stackCount]=root;
    sumStack[stackCount] = sum - root->val;
    stackCount++;
    while (stackCount >0) {
        stackCount--;
        struct TreeNode* p = stack[stackCount];
        int leftsum = sumStack[stackCount];
        
        printf("leftsum:%d",leftsum);
        if (!p->left && !p->right && leftsum==0) {
            return true;
        }
        
        if (p->left) {
            stack[stackCount]=p->left;
            sumStack[stackCount] = leftsum - p->left->val;
            stackCount++;
        }
        
        if (p->right) {
            stack[stackCount]=p->right;
            sumStack[stackCount] = leftsum - p->right->val;
            stackCount++;
        }
    }
    return false;
}

مراجعة

المراجعة كمقالة وحدها:

https://dandan2009.github.io/2018/11/22/data-structures-diving-into-data-structures-part1/

نصائح

• معاني مختلفة لـ NULL، nil، Nil NSNull

  علم	القيمة	معنى
  فارغة	(باطل *)0	القيمة الصفرية الحرفية لمؤشر C
  لا شيء	(معرف)0	القيمة الصفرية الحرفية لكائن Objective-C
  لا شيء	(الصف)0	القيمة الصفرية الحرفية لفئة Objective-C
  نسنول	[NSNull فارغة]	كائن واحد يستخدم لتمثيل قيمة صفر

  المرجع: https://nshipster.cn/nil/

• لتسهيل الترجمة، استخدمت Youdao SDK لإنشاء أداة ترجمة. الإدخال هو ملف نصي، والإخراج هو أيضًا ملف نصي، والذي يتم ترجمته مقطعًا مقطعًا. أنظر أيضا:

  https://github.com/dandan2009/youdaoTranslate

شارك

كمطور iOS، كيف تتعلم Java لتتمكن من قراءة الإصدار الرابع من الخوارزمية؟ كيفية إعداد بيئة تطوير جافا؟