الفنون رقم 026

الفنون 026

هذه المادة 26

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

646. أطول سلسلة زوجية

الصعوبة: متوسطة

قم بإعطاء أزواج أرقام n. في كل زوج من الأرقام، يكون الرقم الأول دائمًا أصغر من الرقم الثاني.

الآن، نحدد العلاقة التالية. إذا وفقط إذا كان b < c، فيمكن أن يتبع زوج الأرقام (c, d) (a, b). نستخدم هذا النموذج لبناء سلسلة من أزواج الأرقام.

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

مثال:

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]

ملاحظة:

1. يقع عدد أزواج الأرقام المحددة في النطاق [1، 1000].

الحل

اللغة: ج

#define maxn 1005
struct Pair{
    int begin;
    int end;
} pair[maxn];

int cmp(const void* a, const void* b){
    struct Pair* x = (struct Pair*)a;
    struct Pair* y = (struct Pair*)b;
    if(x->end == y->end) return x->begin - y->begin;
    return x->end - y->end;
}

void matrixToStruct(int** pairs, int row){
    for(int i = 0;i < row;i++){
        pair[i].begin = pairs[i][0];
        pair[i].end = pairs[i][1];
    }
}

int findLongestChain(int** pairs, int pairsRowSize, int pairsColSize) {
    int row = pairsRowSize;
    int col = pairsColSize;
    
    matrixToStruct(pairs, row);
    qsort(pair, row, sizeof(struct Pair), cmp);
    
    int cnt = 1;
    for(int i = 1, k= 0;i < row;i++){
        if(pair[i].begin > pair[k].end){
            cnt++;
            k = i;
        }
    }
    return cnt;
}

198. سرقة

الصعوبة: سهل

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

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

مثال 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。```

**مثال 2:**

输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

#### الحل

اللغة: **ج**

//方法一 递归法 int rob(int* nums, int numsSize) { if (numsSize <=0) { return 0; }

if (numsSize==1) {
    return nums[0];
}
int r1= rob(nums,numsSize-2) +  nums[numsSize - 1];
int r2= rob(nums,numsSize-1) ;
if (r1 > r2) {
    return r1;
}
return r2;

}

//方法二 备忘录递归法 int re[10000] = {-1};

int rob1(int* nums, int numsSize) {

if (numsSize <=0) {
    return 0;
}

if (numsSize==1) {
    return nums[0];
}

if (re[numsSize] >-1) {
    return re[numsSize];
}

int r1= rob1(nums,numsSize-2) +  nums[numsSize - 1];
int r2= rob1(nums,numsSize-1) ;
if (r1 > r2) {
    re[numsSize] = r1;
    return r1;
}

re[numsSize] = r2;
return r2;

}

int rob(int* nums, int numsSize){ for (int i=0; i<10000; i++) { re[i] = -1; } return rob1(nums, numsSize); }

```c
//方法三 动态规划
int rob(int* nums, int numsSize){
    if (numsSize <=0) {
        return 0;
    }

    if (numsSize==1) {
        return nums[0];
    }
    
    int r0 = nums[0];
    int r1 = nums[1];
    int sum = r0 > r1 ? r0 : r1;
   
    
    for (int i = 2; i < numsSize; i++) {
        r1 = r0 + nums[i];
        r0 = sum;
        sum = r0 > r1 ? r0 : r1;
    }
    
    
    return sum;
}

مراجعة

المقال هنا يتحدث عن عملية البحث عن عمل لأميركي، وأخيراً حصل على راتب سنوي قدره 300 ألف دولار أمريكي. مستوى رواتب الإمبراطور الأمريكي مرتفع بالفعل. https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/

نصائح

بعد أن ينمو مشروعنا بالفعل، مع تكرار الأعمال، سيكون هناك العديد من الفئات غير المفيدة، أي الفئات التي لم تتم الإشارة إليها بواسطة أي فئة. ستؤدي هذه الفئات إلى زيادة حجم حزمة التثبيت، لذا من الضروري تنظيفها. يوجد برنامج نصي https://github.com/dblock/fui，很实用， على جيثب كما أنه سهل الاستخدام للغاية: التثبيت: جوهرة تثبيت فوي

استرداد الفئات غير المستخدمة في الدليل الحالي:

fui find

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

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

شارك

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