德州网站网站建设,恒峰网站建设问题,手机开网店的免费平台,中国商务商会官方网站Leetcode Test
123 买卖股票的最佳时机Ⅲ(10.3)
给定一个数组#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
**注意#xff1a;**你不能同时参与多笔交易#xff08;你必须在再次购…Leetcode Test
123 买卖股票的最佳时机Ⅲ(10.3)
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
**注意**你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
提示
1 prices.length 1050 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],sell10;int buy2buy1,sell2sell1;for(int i1;ipricesSize;i){buy1fmax(buy1,-prices[i]);sell1fmax(sell1,buy1prices[i]);buy2fmax(buy2,sell1-prices[i]);sell2fmax(sell2,buy2prices[i]);}return sell2;
}188 买卖股票的最佳时机Ⅳ(10.4)
给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。
**注意**你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
提示
1 k 1001 prices.length 10000 prices[i] 1000
【动态规划】universal version
int maxProfit(int k, int* prices, int pricesSize){int npricesSize;int f[k2][2];//[0]代表sell[1]代表buymemset(f,-0x3f,sizeof(f));for(int j1;jk2;j){f[j][0]0;//先把sell全部赋值为0}for(int i0;in;i){for(int j1;jk2;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[k1][0];
}309 买卖股票的最佳时机含冷冻期(10.5)
给定一个整数数组prices其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意**你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
提示
1 prices.length 50000 prices[i] 1000
【动态规划】
int maxProfit(int* prices, int pricesSize){//0手里有票今天可以卖//1前一天冻结今天不能买//2手里没票今天可以买int npricesSize;int f[n][3];f[0][0]-prices[0];f[0][1]f[0][2]0;for(int i1;in;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]);//返回最后一天手里没票或最后一天在冻结期
}714 买卖股票的最佳时机含手续费(10.6)
给定一个整数数组 prices其中 prices[i]表示第 i 天的股票价格 整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
**注意**这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。
提示
1 prices.length 5 * 1041 prices[i] 5 * 1040 fee 5 * 104
【动态规划】
int maxProfit(int* prices, int pricesSize, int fee){int npricesSize;int f[n1][2];memset(f,0,sizeof(f));f[0][1]INT_MIN/2;for(int i0;in;i){f[i1][0]fmax(f[i][0],f[i][1]prices[i]-fee);f[i1][1]fmax(f[i][1],f[i][0]-prices[i]);}return f[n][0];
}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 {stackpairint, 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);*/2034 股票价格波动(10.8)
给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。
不巧的是由于股票市场内在的波动性股票价格记录可能不是按时间顺序到来的。某些情况下有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中前一条记录视为错误记录后出现的记录 更正 前一条错误的记录。
请你设计一个算法实现
更新 股票在某一时间戳的股票价格如果有之前同一时间戳的价格这一操作将 更正 之前的错误价格。找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。找到当前记录里股票的 最高价格 。找到当前记录里股票的 最低价格 。
请你实现 StockPrice 类
StockPrice() 初始化对象当前无股票价格记录。void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。int current() 返回股票 最新价格 。int maximum() 返回股票 最高价格 。int minimum() 返回股票 最低价格 。
提示
1 timestamp, price 109updatecurrentmaximum 和 minimum 总 调用次数不超过 105 。currentmaximum 和 minimum 被调用时update 操作 至少 已经被调用过 一次 。
【hash 有序集合】
class StockPrice {int maxTimestamp;unordered_mapint,int timePriceMap;multisetint prices;
public:StockPrice() {this-maxTimestamp0;//初始化对象当前无股票价格记录}void update(int timestamp, int price) {//在时间点 timestamp 更新股票价格为 pricemaxTimestampmax(maxTimestamp,timestamp);int prevPricetimePriceMap.count(timestamp) ? timePriceMap[timestamp] : 0;//上次的价格timePriceMap[timestamp]price;//这次的价格if(prevPrice0){//如果有上次的auto itprices.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();*/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 *splitmalloc(sizeof(int)*20);int cnt0;while(num0){split[cnt]num%10;num/10;}qsort(split,cnt,sizeof(int),cmp);int n10,n20;for(int i0;icnt;i){if(i%20){n1*10;n1split[i];}else{n2*10;n2split[i];}}return n1n2;
}
