Leetcode(C++)
題目 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/submissions/ 。
想法 :
原本以為跟第309題一樣的轉移方程,因為多了FEE的關係,導致可能會有買2次的轉移,所以刪掉rest。
buy(i) = max(buy(i-1), sell(i-1) - price[i]);
sell(i) = max(sell(i-1), buy(i-1) + price[i] - fee);
時間複雜度 : O(n)。
程式碼 :
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int l=prices.size(), sell_1=0, sell, buy_1=-1*prices[0], buy;
if(l == 1) return 0;
for(int i=1 ; i<l ; i++){
buy=max(buy_1,sell_1-prices[i]);
sell=max(sell_1,buy_1+prices[i]-fee);
buy_1=buy;
sell_1=sell;
}
return sell;
}
};
題目 : https://leetcode.com/problems/richest-customer-wealth/ 。 想法 : 語法。 時間複雜度 : O(n*m)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/coin-change-2/ 。 想法 : 無窮背包問題。 時間複雜度 : O(n*m)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/integer-break/ 。 想法 : 規律就在2跟3身上(?),把一個數字分解成2跟3的總和就好。 時間複雜度 : O(1)。 程式碼 : (JAVA)
Feb 5, 2022題目 : https://leetcode.com/problems/longest-common-subsequence/ 。 想法 : LCS。 if(str[i] == str[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
Feb 5, 2022or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up