SENI #025

SENI 025

Ini adalah pasal 25

Pertanyaan algoritma algoritma

264. Jelek Nomor II

Kesulitan: Sedang

Tulis program untuk menemukan nomor jelek n.

Bilangan jelek adalah bilangan bulat positif yang hanya berisi faktor prima 2, 3, 5.

Contoh:

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

**Deskripsi: **

1. `1` adalah angka jelek.
2. `n` **tidak melebihi**1690.


#### Solusi

Bahasa: **C**

```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. Jumlah urutan maksimum

Kesulitan: Mudah

Diberikan array bilangan bulat nums , temukan subarray kontinu dengan jumlah maksimum (subarray berisi setidaknya satu elemen) dan kembalikan jumlah maksimumnya.

Contoh:

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

Lanjutan:

Jika Anda sudah menerapkan solusi O(n), coba gunakan solusi bagi-dan-taklukkan yang lebih elegan.

Solusi

Bahasa: C

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. Waktu terbaik untuk membeli dan menjual saham

Kesulitan: Mudah

Diberikan sebuah array, elemen ke i adalah harga saham tertentu pada hari i.

Jika Anda hanya diperbolehkan menyelesaikan paling banyak satu transaksi (yaitu membeli dan menjual saham), rancanglah algoritma untuk menghitung keuntungan maksimal yang dapat Anda peroleh.

Perhatikan bahwa Anda tidak dapat menjual saham sebelum membelinya.

Contoh 1:

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

Contoh 2:

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

Solusi

Bahasa: C

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;
}

Ide awal dari permasalahan ini adalah mencari nilai maksimum dan minimum, dan nilai maksimum berada di belakang nilai minimum. Cara termudah untuk memikirkan seringkali merupakan cara yang paling tidak efisien.

Kunci dari masalah ini adalah menghitung pengembalian setiap kali melalui loop dan memperbarui nilai minimum.

Ulasan

Artikel di sini membahas tentang proses pencarian kerja seorang Amerika, dan akhirnya mendapat gaji tahunan sebesar 300.000 dolar AS. Tingkat gaji kaisar Amerika memang tinggi. https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/

Kiat

Gunakan metode berikut untuk mengukur waktu eksekusi baris kode tertentu:

os_log_t log = os_log_create("com.example.aplikasi Anda", "RefreshOperations");
os_signpost_id_t log_t = os_signpost_id_generate(log);


os_signpost_interval_begin(log, log_t, "Ambil Aset");

//Kode yang ingin Anda ukur
 os_signpost_interval_end(log, log_t, "Ambil Aset1");

Membagikan