【Leetcode Sheet】Weekly Practice 10

Leetcode Test

123 买卖股票的最佳时机Ⅲ(10.3)

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 105

【动态规划】

int maxProfit(int* prices, int pricesSize){
    //buy1: buy once
    //sell1: buy once & sell once
    //buy2: buy twice & sell once
    //sell2: buy twice & sell twice

    //buy1[i] = max(buy1[i-1], -prices[i])
    //sell1[i] = max(sell1[i-1], buy1[i-1]+prices[i])
    //buy2[i] = max(buy2[i], sell1[i]-prices[i])
    //sell2[i] = max(sell2[i], buy2[i-1]+prices[i])

    //buy1[0]=-prices[0] 同一天买
    //sell1[0]=0 同一天买+卖
    //buy2[0]=-princes[0] 同一天买+卖+买
    //sell2[0]=0 同一天买+卖+买+卖

    int buy1=-prices[0],sell1=0;
    int buy2=buy1,sell2=sell1;

    for(int i=1;i<pricesSize;i++){
        buy1=fmax(buy1,-prices[i]);
        sell1=fmax(sell1,buy1+prices[i]);
        buy2=fmax(buy2,sell1-prices[i]);
        sell2=fmax(sell2,buy2+prices[i]);
    }
    return sell2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

188 买卖股票的最佳时机Ⅳ(10.4)

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

提示：

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

【动态规划】universal version

int maxProfit(int k, int* prices, int pricesSize){
    int n=pricesSize;
    int f[k+2][2];
    //[0]代表sell，[1]代表buy
    memset(f,-0x3f,sizeof(f));

    for(int j=1;j<k+2;j++){
        f[j][0]=0;//先把sell全部赋值为0
    }

    for(int i=0;i<n;i++){
        for(int j=1;j<k+2;j++){
            f[j][0]=fmax(f[j][0],f[j][1]+prices[i]);
            f[j][1]=fmax(f[j][1],f[j-1][0]-prices[i]);
        }
    }

    return f[k+1][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

309 买卖股票的最佳时机含冷冻期(10.5)

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

【动态规划】

int maxProfit(int* prices, int pricesSize){
    //0：手里有票，今天可以卖
    //1：前一天冻结，今天不能买
    //2：手里没票，今天可以买

    int n=pricesSize;
    int f[n][3];
    f[0][0]=-prices[0];
    f[0][1]=f[0][2]=0;

    for(int i=1;i<n;i++){
        f[i][0]=fmax(f[i-1][0],f[i-1][2]-prices[i]);
        //i-1天有票，或i-1天没票时买了票
        f[i][1]=f[i-1][0]+prices[i];
        //一定是i-1天买了票，所以i天才会冻结
        f[i][2]=fmax(f[i-1][2],f[i-1][1]);
        //i-1天没票，或冻结期刚结束
    }

    return fmax(f[n-1][2],f[n-1][1]);
    //返回最后一天手里没票，或最后一天在冻结期
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

714 买卖股票的最佳时机含手续费(10.6)

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

提示：

• 1 <= prices.length <= 5 * 104
• 1 <= prices[i] < 5 * 104
• 0 <= fee < 5 * 104

【动态规划】

int maxProfit(int* prices, int pricesSize, int fee){
    int n=pricesSize;
    int f[n+1][2];
    memset(f,0,sizeof(f));

    f[0][1]=INT_MIN/2;
    for(int i=0;i<n;i++){
        f[i+1][0]=fmax(f[i][0],f[i][1]+prices[i]-fee);
        f[i+1][1]=fmax(f[i][1],f[i][0]-prices[i]);
    }
    return f[n][0];
}
1
2
3
4
5
6
7
8
9
10
11
12

901 股票价格跨度(10.7)

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

• 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

• StockSpanner() 初始化类对象。
• int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

提示：

• 1 <= price <= 105
• 最多调用 next 方法 104 次

【单调栈】（这东西还是cpp好用…）

class StockSpanner {
    stack<pair<int, int>> st;
    int cur_day = -1; // 第一个 next 调用算作第 0 天
public:
    StockSpanner() {
        st.emplace(-1, INT_MAX); // 这样无需判断栈为空的情况
    }

    int next(int price) {
        while (price >= st.top().second) {
            st.pop(); // 栈顶数据后面不会再用到了，因为 price 更大
        }
        int ans = ++cur_day - st.top().first;
        st.emplace(cur_day, price);
        return ans;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2034 股票价格波动(10.8)

给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。

不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。

请你设计一个算法，实现：

• 更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
• 找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
• 找到当前记录里股票的 最高价格 。
• 找到当前记录里股票的 最低价格 。

请你实现 StockPrice 类：

• StockPrice() 初始化对象，当前无股票价格记录。
• void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
• int current() 返回股票 最新价格 。
• int maximum() 返回股票 最高价格 。
• int minimum() 返回股票 最低价格 。

提示：

• 1 <= timestamp, price <= 109
• update，current，maximum 和 minimum 总 调用次数不超过 105 。
• current，maximum 和 minimum 被调用时，update 操作 至少 已经被调用过 一次 。

【hash + 有序集合】

class StockPrice {
    int maxTimestamp;
    unordered_map<int,int> timePriceMap;
    multiset<int> prices;
public:
    StockPrice() {
        this->maxTimestamp=0;
        //初始化对象，当前无股票价格记录
    }
    
    void update(int timestamp, int price) {
        //在时间点 `timestamp` 更新股票价格为 `price`
        maxTimestamp=max(maxTimestamp,timestamp);
        int prevPrice=timePriceMap.count(timestamp) ? timePriceMap[timestamp] : 0;
        //上次的价格
        timePriceMap[timestamp]=price;
        //这次的价格
        if(prevPrice>0){
            //如果有上次的
            auto it=prices.find(prevPrice);
            if(it!=prices.end()){
                prices.erase(it);
            }
        }
        prices.emplace(price);
    }
    
    int current() {
        return timePriceMap[maxTimestamp];
    }
    
    int maximum() {
        return *prices.rbegin();
    }
    
    int minimum() {
        return *prices.begin();
    }
};

/**
 * Your StockPrice object will be instantiated and called as such:
 * StockPrice* obj = new StockPrice();
 * obj->update(timestamp,price);
 * int param_2 = obj->current();
 * int param_3 = obj->maximum();
 * int param_4 = obj->minimum();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

2578 最小和分割(10.9)

给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：

• num1 和 num2 直接连起来，得到 num 各数位的一个排列。

  • 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。

• num1 和 num2 可以包含前导 0 。

请你返回 num1 和 num2 可以得到的和的 最小 值。

提示：

• 10 <= num <= 10^9

【排序 + 奇偶对】

int cmp(void *a,void *b){
    return *(int*)a-*(int*)b;
}
int splitNum(int num){
    int *split=malloc(sizeof(int)*20);
    int cnt=0;
    while(num>0){
        split[cnt++]=num%10;
        num/=10;
    }
    qsort(split,cnt,sizeof(int),cmp);
    int n1=0,n2=0;
    for(int i=0;i<cnt;i++){
        if(i%2==0){
            n1*=10;
            n1+=split[i];
        }
        else{
            n2*=10;
            n2+=split[i];
        }
    }
    return n1+n2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24