ARTS #025

ARTS 025

This is article 25

Algorihm algorithm question

264. Ugly Number II

Difficulty: Medium

Write a program to find the ugly number n.

An ugly number is a positive integer containing only prime factors 2, 3, 5.

Example:

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

**Description: **

1. `1` is an ugly number.
2. `n` **not exceed**1690.


#### Solution

Language: **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. Maximum subsequence sum

Difficulty: Easy

Given an integer array nums , find a continuous subarray with the maximum sum (the subarray contains at least one element) and return its maximum sum.

Example:

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

Advanced:

If you have already implemented an O(n) solution, try using the more elegant divide-and-conquer solution.

Solution

Language: 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. The best time to buy and sell stocks

Difficulty: Easy

Given an array, the _i_th element is the price of a given stock on day i.

If you are only allowed to complete one transaction at most (i.e. buying and selling a stock), design an algorithm to calculate the maximum profit you can make.

Note that you cannot sell a stock before buying it.

Example 1:

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

Example 2:

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

Solution

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

The initial idea of ​​this problem is to find the maximum and minimum values, and the maximum value is behind the minimum value. The easiest way to think of is often the least efficient.

The key to this problem is to calculate the return each time through the loop and update the minimum value.

Review

The article here talks about the job search process of an American, and finally got an annual salary of 300,000 US dollars. The salary level of the American emperor is indeed high. https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/

Tips

Use the following method to measure the execution time of a certain line of code:

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, "Fetch Asset");

//The code you want to measure
 os_signpost_interval_end(log, log_t, "Fetch Asset1");

Share