ARTS 025
这是第25篇
Algorihm 算法题
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。
#### 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. 最大子序和
难度: 简单
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
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. 买卖股票的最佳时机
难度: 简单
给定一个数组，它的第 i 个元素是一支给定股票第 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。
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;
}
这个问题刚开始的想法就是找出 最大值和最小值，且最大值在最小值后面，最容易想到的方法，往往是效率最低的，
这个问题的关键是每一次循环都算一次收益，并更新最小值。
Review
这边文章讲了一位美国人求职的过程，最终拿到了30万美元的年薪，美帝的工资水平确实高啊。 https://dandan2009.github.io/2019/03/01/how-I-negotiated-a-job-offer-in-silicon-valley/
Tips
用一下方法可以测量某一行代码的执行时间，
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");
//你要测量的代码
os_signpost_interval_end(log, log_t, "Fetch Asset1");
