الفنون رقم 025

الفنون 025

هذه المادة 25

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

264. الرقم القبيح II

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

اكتب برنامجًا للعثور على الرقم القبيح n.

الرقم القبيح هو عدد صحيح موجب يحتوي فقط على العوامل الأولية 2, 3, 5.

مثال:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。```

**الوصف: **

1. `1` رقم قبيح.
2. `n` ** لا يتجاوز ** 1690.


#### الحل

اللغة: **ج**

```c
int nthUglyNumber(int n) {
    if (n<7) {
        return n;
    }


    int rs[1691] = {0};

    for (int i = 1; i < 7; i++) {
        rs[i] = i;
    }


    int N2 = 0;
    int N2_flag = 0;

    int N3 = 0;
    int N3_flag = 0;

    int N5 = 0;
    int N5_flag = 0;
    int loop = 1;

    for (int i = 7; i <= n; i++) {
         loop = i;
        for (int j = 1; j < loop; j++) {
            if (N2_flag ==0 && (rs[j] * 2 > rs[i-1])) {
                N2 = rs[j] * 2;
                N2_flag =1;
            }

            if (N3_flag ==0 && (rs[j] * 3 > rs[i-1])) {
                N3 = rs[j] * 3;
                N3_flag =1;
            }

            if (N5_flag ==0 && (rs[j] * 5 > rs[i-1])) {
                N5 = rs[j] * 5;
                N5_flag =1;
            }
        }

        //取 N2 N3 N5  最小的一个
        int r = N2;
        if (r>N3) {
            r  = N3;
        }


        if (r>N5) {
            r=N5;
        }

        rs[i] = r;
        N2_flag = 0;
        N3_flag = 0;
        N5_flag = 0;

    }

    return rs[n];
}

53. الحد الأقصى لمجموع التسلسل

الصعوبة: سهل

بالنظر إلى مصفوفة أعداد صحيحة nums، ابحث عن مصفوفة فرعية متصلة بأقصى مجموع (تحتوي المصفوفة الفرعية على عنصر واحد على الأقل) وأرجع مجموعها الأقصى.

مثال:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

متقدم:

إذا كنت قد قمت بالفعل بتنفيذ حل O(n)، فحاول استخدام حل فرق تسد الأكثر أناقة.

الحل

اللغة: ج

int maxSubArray(int* nums, int numsSize){
    if (numsSize < 1) {
        return 0;
    }
    
    int sum = nums[0];
    int max = sum;
    
    for (int  i = 1; i < numsSize; i++) {
        if (sum + nums[i] > nums[i]) {
            sum = sum + nums[i];
        }
        else{
            sum = nums[i];
        }
        
        if (sum > max) {
            max = sum;
        }
    }
    return max;
}

121. أفضل وقت لشراء وبيع الأسهم

الصعوبة: سهل

بالنظر إلى المصفوفة، فإن العنصر _i_th هو سعر السهم المحدد في اليوم i.

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

لاحظ أنه لا يمكنك بيع السهم قبل شرائه.

مثال 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

مثال 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

الحل

اللغة: ج

int maxProfit(int* prices, int pricesSize) {
    if (pricesSize < 2) {
        return 0;
    }
    
    int min = prices[0];
    int ret = 0;
    for (int i = 0; i<pricesSize; i++) {
        int tem = prices[i] - min;
        if (tem > ret ) {
            ret = tem;
        }
        
        if (min > prices[i]) {
            min = prices[i];
        }
    }
    return ret;
}

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

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

مراجعة

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

نصائح

استخدم الطريقة التالية لقياس وقت تنفيذ سطر معين من التعليمات البرمجية:

os_log_t log = os_log_create("com.example.your-app", "RefreshOperations");
os_signpost_id_t log_t = os_signpost_id_generate(log);


os_signpost_interval_begin(log, log_t, "جلب الأصول");

// الكود الذي تريد قياسه
 os_signpost_interval_end(log, log_t, "Fetch Asset1");

يشارك