niiish32x 's blog

原题链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown 解法1:动态规划 1234567891011121314151617181920212223242526272829303132333435363738/** 状态机模型 与传统股票问题一样 总体上来看也是持股、不持股两个状态 由于存在冷冻期 将不持股这个状态再拆分为 不进行操作的不持股状态 和 卖了股票后因冷冻期而不能操作的不持股状态 f[i][j] 表示前i天 持股状态为j时 可获得的最大现金 f[i][0] 没有操作而不持股票 f[i][1] 持股 f[i][2] 卖出股票后处于冷静期而不能持股 */class Solution { public int maxProfit(int[] prices) { int n = prices.length; int [][] f = new int [n][3]; ...

原题链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv 解法1:动态规划承接123题 相当于120-124 这一类股票问题的最通用姐 12345678910111213141516171819202122232425262728293031323334353637383940414243444546/** f[i][j] 表示第i天 持有股票状态为k时的最大现金 f[i][0] 表示不操作 f[i][k = 奇数] 表示此时为持有状态 f[i][k = 偶数] 表示此时为不持有状态 */class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; // 这里k次买卖 那么对应的所能有的持有状态未k*2次 k = k * 2; int [][] f = new int[n][k + 1]; ...

原题链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii 解法1:动态规划 1234567891011121314151617181920212223242526272829303132333435363738394041/** f[i][j] 表示第i天 持有股票状态为j的 所持有的最大现金 f[i][0] 不操作 f[i][1] 第一次持有 f[i][2] 第一次不持有 f[i][3] 第二次持有 f[i][4] 第二次不持有 */class Solution { public int maxProfit(int[] prices) { int n = prices.length; int [][] f = new int[n + 1][5]; // 初始化 // 第0天不操作 那就是0 f[0][0] = 0; // 第1次持有 即第一次买入 ...

原题链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 解法1:贪心 只要是股票上涨日 就进行买卖那就必赚只用算隔天涨幅赚的钱即可 123456789101112131415class Solution { public int maxProfit(int[] prices) { int n = prices.length; int ans = 0; for(int i = 0 ; i < n - 1 ; i++){ int tmp = prices[i + 1] - prices[i]; if(tmp > 0){ ans += tmp; } } return ans; }} 解法2:动态规划 1234567891011121314151 ...

原题链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/ 解法1:枚举+维护前缀数组的最小值 123456789101112131415161718/* 由于卖出操作必须在买入操作之后 即该题可理解存在寻找 顺序限制的最大最小值差值问题*/class Solution {public: int maxProfit(vector<int>& prices) { int n = prices.size(); int res = 0; // 用于存储最小值 int m = 1e9; for(int i = 0 ; i < n ; i++){ m = min(m,prices[i]); res = max(prices[i] - m,res); } return res; ...

contest url :https://leetcode.cn/contest/weekly-contest-362/ 8029 与车相交的点解法1 模拟根据题意暴力解决 1234567891011121314151617181920class Solution {public: int numberOfPoints(vector<vector<int>>& nums) { int ans = 0; vector<int>q(101); for(int i = 0 ; i < nums.size() ; i++){ int a = nums[i][0],b = nums[i][1]; for(int j = a ; j <= b ; j++){ q[j] = 1; } } for(int i = 1 ...

原题链接:https://leetcode.cn/problems/course-schedule/description/ 解法1:拓扑排序 基本上照着拓扑排序模板来就行了就是题意稍微理解一下prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。所以 b -> a 拓扑排序步骤: 入队所有入度为0 的点 bfs 取出队头t -> 每取出一次队头说明有一个数已加入排序好的序列 枚举t的所有出边 t->j 删掉 t->j 即让 d[j]– (d[j] j的入度) if d[j] == 0 -> 说明j之前所有点均以排好序 -> j 入队 如果图中存在环则无法全部入队 反之则都可以入队 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647/*拓扑排序 学a 需要先学b a <- b*/class Solution {p ...

原题链接:https://leetcode.cn/problems/minimum-time-to-repair-cars/description/ 解法1: 二分需要稍微证明一下由题:r * $n^2$ <= t -> n <= $\sqrt{t/r}$n 与 r 为常量 即n越大 那么能修的车就越多 -> 即拥有单调性因此可以对t进行二分 123456789101112131415161718192021222324252627282930/* 二分: 上界为能力最低的机械工 单独修完所有车辆的时间*/class Solution {public: long long repairCars(vector<int>& ranks, int cars) { sort(ranks.begin(),ranks.end()); long long right = 1LL * ranks[0] * cars * cars; // 下界为 le ...

原题链接:https://leetcode.cn/problems/maximum-enemy-forts-that-can-be-captured/ 解法1: 双指针思路比较简单 但是题目要求其实还是要理解一下的 123456789101112131415161718192021222324252627// 双指针class Solution {public: int captureForts(vector<int>& forts) { int ans = 0; int n = forts.size(); for(int i = 0 ; i < n ; i++){ // 如果是1 找-1 即城堡走到空位 // 如果是-1 找1 if(forts[i] != 0){ int j = i + 1; while(j < n && ...

contest url :https://leetcode.cn/contest/weekly-contest-359/ 2830. 销售利润最大化很好的一道DP题虽然本质就是普通的线性DP 但是区间的那步转化非常巧妙 1234567891011121314151617181920212223242526272829303132333435363738/**状态表示: f[i] 表示销售编号不超过i的房屋的最大盈利 状态计算: 考虑编号为i的房屋卖或不卖: 不卖: f[i] = f[i - 1] 卖: 所有endj = i 的购买请求 有 f[i] = max(f[start - 1] + gold) 为方便遍历先将所有end相同的购买请求用hash进行存储 */class Solution {public: int maximizeTheProfit(int n, vector<vector<int>>& offers) { // 先存储end 相同 ...