الفنون رقم 024

الفنون 024

هذه المادة 24

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

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

746. الحد الأدنى لتكلفة تسلق السلالم

الصعوبة: سهل

على الدرج، تم تعيين i للخطوة i بتكلفة غير سالبة (0 مفهرسة).

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

مثال 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

مثال 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

ملاحظة:

1. سيكون لـ cost طول في النطاق [2, 1000].
2. سيكون كل cost[i] عددًا صحيحًا في النطاق [0, 999].

الحل

اللغة: ج

int minCostClimbingStairs(int* cost, int costSize) {
    if (costSize < 2) {
        return 0;
    }
    
    int dd_0 = 0;
    int dd_1  = 0;
    int result = 0;
​
    for (int i = 2;i<=costSize;i++) {
        int tem1 =  dd_0  + cost[i-2];
        int tem2 = dd_1 + cost[i-1];
        if (tem1 > tem2) {
            result = tem2;
        }
        else{
            result = tem1;
        }
        dd_0 = dd_1;
        dd_1 = result;
    }
    return result; 
}
}

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

الطريقة الأولى: العودية

int minCostClimbingStairs(int* cost, int costSize) {

    if (costSize<=0) {
        return  0;
    }
    
    int sum;
     int sum1 = minCostClimbingStairs(cost,costSize -1) + cost[costSize -1];
    int sum2 = minCostClimbingStairs(cost,costSize -2) + cost[costSize -2];
    
    if (sum1>sum2) {
        sum = sum2;
    }
    else{
        sum = sum1;
    }

    
    
    return sum;
}

انتهت مهلة الطريقة المذكورة أعلاه.

الطريقة الثانية: تكرار المذكرة

int dd[1001] = {-1};

int minCostClimbingStairs1(int* cost, int costSize) {
    if (costSize<=0) {
        return  0;
    }
    if (dd[costSize] >=0) {
        return dd[costSize];
    }
    
    int sum;
    int sum1 = minCostClimbingStairs1(cost,costSize -1) + cost[costSize -1];
    int sum2 = minCostClimbingStairs1(cost,costSize -2) + cost[costSize -2];
    
    if (sum1>sum2) {
        sum = sum2;
    }
    else{
        sum = sum1;
    }
    
    dd[costSize] = sum;
    
    return sum;
}

int minCostClimbingStairs(int* cost, int costSize) {
    for (int i = 0; i < 1001; i++) {
        dd[i] = -1;
    }
    
   int sum = minCostClimbingStairs1(cost,costSize);
    
    return sum;
}

يمكن أن تمر طريقة المذكرة العودية، والوقت هو 4 مللي ثانية

الطريقة الثالثة: البرمجة الديناميكية

int minCostClimbingStairs(int* cost, int costSize) {
    if (costSize < 2) {
        return 0;
    }
    
    int dd_0 = 0;
    int dd_1  = 0;
    int result = 0;

    for (int i = 2;i<=costSize;i++) {
        int tem1 =  dd_0  + cost[i-2];
        int tem2 = dd_1 + cost[i-1];
        if (tem1 > tem2) {
            result = tem2;
        }
        else{
            result = tem1;
        }
        dd_0 = dd_1;
        dd_1 = result;
    }
    return result; 
}

وقت البرمجة الديناميكية هو أيضًا 4 مللي ثانية

السؤال 2:

70. تسلق السلالم

الصعوبة: سهل

أنت تتسلق حالة الدرج. يستغرق الأمر n خطوات للوصول إلى القمة.

في كل مرة يمكنك إما تسلق خطوة أو خطوتين. بكم طريقة مميزة يمكنك الصعود إلى القمة؟

ملاحظة: بالنظر إلى n سيكون عددًا صحيحًا موجبًا.

مثال 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1\. 1 step + 1 step
2\. 2 steps

مثال 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1\. 1 step + 1 step + 1 step
2\. 1 step + 2 steps
3\. 2 steps + 1 step

الحل

مفتاح هذا السؤال هو أن نفهم:تسلق السلالم(n)=تسلقالدرجات(n-1) +تسلقالدرجات(n-2);

اللغة: ج

الحل 1: العودية، مهلة LeetCode

int climbStairs(int n) {
    if (n<3) {
        return n;
    }
    
    return climbStairs(n-1) + climbStairs(n-2);
}

الخيار 2: تكرار المذكرة

int dd[1001];
int climbStairs1(int n) {
    if (n < 3) {
        return n;
    }
    
    if (dd[n] > 0) {
        return dd[n];
    }
    
    int c = climbStairs1(n-1) + climbStairs1(n-2);
    dd[n] = c;
    return c;
}


int climbStairs(int n) {
    for (int i = 0; i < 1001; i++) {
                dd[i] = -1;
        }
    
    return climbStairs1(n);
}

الخيار 3: البرمجة الديناميكية

int climbStairs(int n) {
    if (n < 3) {
        return n;
    }
    int c1 = 1;
    int c2 = 2;
    int result = 0;
    
    for (int i=3; i<=n; i++) {
        result = c1 + c2;
        c1= c2;
        c2 = result;
    }
    
    return result;
}

الخوارزمية الثالثة:

509. رقم فيبوناتشي

الصعوبة: سهل

تشكل أرقام فيبوناتشي، والتي يشار إليها عادةً باسم F(n)، تسلسلًا يسمى تسلسل فيبوناتشي، بحيث يكون كل رقم هو مجموع الرقمين السابقين، بدءًا من 0 و1. هذا هو،

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

بالنظر إلى N، احسب F(N).

مثال 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

مثال 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

مثال 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

ملاحظة:

0 ≥ N ≥ 30.

الحل

اللغة: ج

البرمجة الديناميكية

int fib(int N) {
    if (N<2) {
        return N;
    }
    
    int f0 = 0;
    int f1 = 1;
    int fn = 0;
    
    for (int i=2; i<=N; i++) {
        fn = f0 + f1;
        f0= f1;
        f1 = fn;
    }
    
    return fn;
}

مراجعة

[تتحدث هذه المقالة] (https://dandan2009.github.io/2019/02/20/my-development-toolset-2019-for-ios/) بشكل أساسي عن مجموعات الأدوات ومكتبات الفئات شائعة الاستخدام لتطوير iOS.

نصائح

كيفية مراقبة حالة Runloop لموضوع ما. تحتوي حلقة التشغيل على الحالات التالية. كيف نراقبه، مثل تنفيذ حدث قبل الدخول في حالة الانتظار.

   kCFRunLoopEntry = (1UL << 0),
     kCFRunLoopBeforeTimers = (1UL << 1),
     kCFRunLoopBeforeSources = (1UL << 2),
     kCFRunLoopBeforeWaiting = (1UL << 5),
     kCFRunLoopAfterWaiting = (1UL << 6),
     kCFRunLoopExit = (1UL << 7),
     kCFRunLoopAllActivities = 0x0FFFFFFFU

وإليك الطريقة: إعداد مراقبة حلقة التشغيل

// 添加一个监听者
-(void)addRunloopObserver{
    //获取当前runloop
    CFRunLoopRef  currentRunloop =  CFRunLoopGetCurrent();
    //runloop观察者上下文， 为下面创建观察者准备，只有创建上下文才能在回调了拿到self对象，才能进行我们的监听操作. 这是一个结构体。
    /**
     typedef struct {
     CFIndex	version;
     void *	info;
     const void *(*retain)(const void *info);
     void	(*release)(const void *info);
     CFStringRef	(*copyDescription)(const void *info);
     } CFRunLoopObserverContext;
     **/
    CFRunLoopObserverContext  context = {
        0,
        (__bridge void *)(self),
        &CFRetain,
        &CFRelease,
        NULL
    };
  
    static CFRunLoopObserverRef  obserberRef;
    obserberRef =CFRunLoopObserverCreate(NULL, kCFRunLoopBeforeWaiting, YES, 0,&callback, &context);
    //给当前runloop添加观察者
    CFRunLoopAddObserver(currentRunloop, obserberRef, kCFRunLoopDefaultMode);
    //释放观察者
    CFRelease(obserberRef);
}

//观察回调
static void callback(CFRunLoopObserverRef observer, CFRunLoopActivity activity, void *info){
   //
}

شارك

كيفية تحسين القدرة التعبيرية للمرء؟ أفهم الكثير من الحقائق والأشياء، لكن عندما أعبر عنها أشعر دائمًا أنها قصور وليست واضحة بما فيه الكفاية. هل لأنني لا أفهم المشكلة بعمق كافٍ أم أنني ضعيف في التعبير عن نفسي؟ كيفية تحسينه؟

على سبيل المثال، يعلم الجميع أن وجهات نظر الناس الثلاثة هي النظرة إلى العالم، والنظرة إلى الحياة، والقيم. ولكن هل يمكنك التعبير بوضوح عما تعنيه هذه الآراء الثلاثة؟ وفيما يلي تعبير 左耳朵耗子 عن وجهات النظر الثلاثة. هل هو واضح جدا وسهل الفهم؟

يمثل 世界观 كيف ترى العالم. هل هو يسار أم يمين، متطرف أم محافظ، مثالي أم تياري؟ حقا هل هو متفائل أم متشائم؟… يمثل 人生观 نوع الشخص الذي تريد أن تكون عليه. هل أن تصبح شخصًا ثريًا أم أن تكون مجربًا للحياة؟ أن تكون معلمًا، أو خبيرًا في الصناعة، أو شخصًا مفكرًا، أو أن تكون… 价值观 يتعلق الأمر بما تعتقد أنه أكثر أهمية بالنسبة لك. هل هي الشهرة أم الثروة، العملية أم النتيجة، التفاني أم سواء كان ذلك الوطن أو الذات، الأسرة أو المهنة…