代碼隨想錄算法訓練營第四十四天|188.買賣股票的最佳時機IV、309.最佳買賣股票時機含冷凍期、714.買賣股票的最佳時機含手續費

188.買賣股票的最佳時機IV

在這里插入圖片描述

題目鏈接:188.買賣股票的最佳時機IV
文檔講解:代碼隨想錄
狀態:不會

思路:
在股票買賣1使用一維dp的基礎上,升級成二維的即可。

  1. 定義dp[k+1][2],其中 dp[j][0] 表示第j次交易后持有股票的最大利潤,dp[j][1] 表示第j次交易后不持有股票的最大利潤。
  2. 初始化時,對所有持有股票的情況要變成dp[i][0] = -prices[0];

題解:
要注意: dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);
dp[j - 1][1] - prices[i] 是因為買入股票的操作要用dp[j-1][1],也就是上次賣出去得到的錢來買這次的股票

    public int maxProfit(int k, int[] prices) {// 特殊情況處理,如果價格數組為空或只有一個元素,返回0if (prices.length == 0) return 0;// dp數組定義為k+1行,2列// dp[j][0] 表示第j次交易后持有股票的最大利潤// dp[j][1] 表示第j次交易后不持有股票的最大利潤int[][] dp = new int[k + 1][2];// 初始化第1到第k次交易后的持有股票的最大利潤為 -prices[0]for (int i = 1; i <= k; i++) {dp[i][0] = -prices[0];}// 遍歷每一天的股票價格for (int i = 1; i < prices.length; i++) {// 倒序遍歷每一次交易,也可以正序,但是倒序更快一點for (int j = k; j >= 1; j--) {// 更新第j次交易后不持有股票的最大利潤dp[j][1] = Math.max(dp[j][1], dp[j][0] + prices[i]);// 更新第j次交易后持有股票的最大利潤// dp[j - 1][1] - prices[i] 是因為買入股票的操作要用dp[j-1][1],也就是上次賣出去得到的錢來買這次的股票dp[j][0] = Math.max(dp[j][0], dp[j - 1][1] - prices[i]);}}// 返回最多k次交易后不持有股票的最大利潤return dp[k][1];}

309.最佳買賣股票時機含冷凍期

在這里插入圖片描述

題目鏈接:309.最佳買賣股票時機含冷凍期
文檔講解:代碼隨想錄
狀態:不會

思路:

第i天的最大收益由持有和不持有股票兩種狀態推導出來,考慮到由冷凍期,那么第i天持有股票可以考慮跳過昨天,從前天推導。

假設有今天持股情況下的最大收益 dp[i][0]、昨天不持股的最大收益 dp[i?1][0]、昨天持股的最大收益 dp[i?1][0]、前天不持股的最大收益 dp[i?2][1],前天持股的最大收益 dp[i?2][0]。先將目光集中在前天,分別考慮前天持股與不持股的情況,試試能不能推導出今天的最大收益。

對于 dp[i?2][0] 來說,它表示前天結束時手中還有股票,那么如果昨天選擇將前天的股票賣掉,由于冷凍期的存在,今天是不能交易的,自然今天手中也不可能還有股票,推導不出 dp[i][0],因此這種情況可以直接忽略;如果前天選擇保留股票到昨天,昨天也只能繼續保留股票才能讓今天手中也有股票,這時 dp[i][0]=dp[i?1][0],這種情況已經在上面的狀態轉移方程中考慮到了,因此也不用擔心。
對于 dp[i?2][1] 來說,它表示前天結束時手中沒有股票,如果昨天買入股票,只能是將股票保留到今天才能推出 dp[i][0],這時 dp[i]=dp[i?1][0] 在狀態轉移方程中已經考慮到了;如果昨天不買入股票,那么由于昨天手中沒有股票,只能是今天買入,同時因為昨天沒交易,昨天的最大收益和前天相同 dp[i?1][1]=dp[i?2][1],所以這種情況的最大收益是 dp[i?2][1]?prices[i]。

題解:

   public int maxProfit(int[] prices) {int n = prices.length;// 如果價格數組長度為0,直接返回0if (n == 0) {return 0;}// 定義一個二維數組 dp,dp[i][0] 表示第 i 天持有股票的最大利潤,// dp[i][1] 表示第 i 天不持有股票的最大利潤int[][] dp = new int[n + 1][2];// 初始化第一天的狀態dp[1][0] = -prices[0]; // 第一天持有股票,利潤為負的當前股票價格// 從第二天開始遍歷價格數組for (int i = 2; i <= n; i++) {// 第 i 天持有股票的最大利潤,可以選擇前一天也持有股票,或者前兩天不持有股票,今天買入dp[i][0] = Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i - 1]);// 第 i 天不持有股票的最大利潤,可以選擇前一天也不持有股票,或者前一天持有股票,今天賣出dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1]);}// 返回倒數第二天不持有股票的最大利潤return dp[n][1]; // 因為是倒數第二天,所以這里改為 dp[n][1]}

714.買賣股票的最佳時機含手續費

在這里插入圖片描述

題目鏈接:714.買賣股票的最佳時機含手續費
文檔講解:代碼隨想錄
狀態:終于做出來一道了。。。。

思路:和股票買賣第2道題一樣,不過每次賣出的時候扣除手續費就好了。

題解:

public int maxProfit(int[] prices, int fee) {if (prices.length == 1) {return 0;}int hasStock = -prices[0]; // 第一天買入股票后的收益int noStock = 0; // 第一天不買股票的收益for (int i = 1; i < prices.length; i++) {// 今天選擇買入股票或者保持昨天持有股票的狀態hasStock = Math.max(hasStock, noStock - prices[i]);// 今天選擇賣出股票或者保持昨天沒有股票的狀態noStock = Math.max(noStock, hasStock + prices[i] - fee);}return noStock; // 最后一天不持有股票的最大收益
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/40169.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/40169.shtml
英文地址,請注明出處:http://en.pswp.cn/web/40169.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

虛擬ECU:純電動汽車發展下的新選擇

人類文明的進步是一個不斷自我否定、自我超越的過程。21世紀以來&#xff0c;隨著科技進步和經濟社會發展&#xff0c;能源和交通系統已從獨立于自然環境的孤立系統&#xff0c;轉變為與自然、技術、社會深度耦合的復雜系統。為實現可持續發展和應對氣候變化&#xff0c;世界各…

【居家養老實訓室】:無障礙設施建設與評估

本文圍繞居家養老實訓室中的無障礙設施建設與評估展開討論。首先闡述了無障礙設施對于居家養老的重要性&#xff0c;接著詳細介紹了常見的居家養老無障礙設施類型&#xff0c;包括出入口、通道、臥室、衛生間等區域的設施。然后重點探討了無障礙設施的評估方法和標準&#xff0…

【C++航海王:追尋羅杰的編程之路】關聯式容器的底層結構——AVL樹

目錄 1 -> 底層結構 2 -> AVL樹 2.1 -> AVL樹的概念 2.2 -> AVL樹節點的定義 2.3 -> AVL樹的插入 2.4 -> AVL樹的旋轉 2.5 -> AVL樹的驗證 2.6 -> AVL樹的性能 1 -> 底層結構 在上文中對對map/multimap/set/multiset進行了簡單的介紹&…

《簡歷寶典》02 - 如果你是HR,你會優先打開哪份簡歷?

現在的求職環境不必多說&#xff0c;其實我們大家都還是很清楚的。所以&#xff0c;在這個環境下&#xff0c;寫一份優秀的簡歷&#xff0c;目的與作用也不必多說。那么&#xff0c;這一小節呢&#xff0c;我們先從簡歷這份文檔的文檔名開始說起。 目錄 1 你覺得HR們刷簡歷的時…

【深度學習】圖形模型基礎(5):線性回歸模型第二部分:單變量線性回歸模型

1.引言 在統計學與機器學習的廣闊領域中&#xff0c;線性回歸作為一種基礎而強大的預測技術&#xff0c;其核心在于通過輸入變量&#xff08;或稱預測器、自變量&#xff09;來估計輸出變量&#xff08;響應變量、因變量&#xff09;的連續值。本章聚焦于線性回歸的一個基本但…

Spring-@Component和@Configuration的區別

前言 在Spring框架中&#xff0c;Configuration和Component注解都是用于組件掃描和管理Bean的生命周期&#xff0c;但它們有著不同的用途和應用場景 Component 注解 Component是一個通用的 stereotype 注解&#xff0c;表明一個Java類為Spring框架中的一個Bean組件。Spring會自…

【C++】相機標定源碼筆記- 立體視覺相機的校準和圖像矯正類

類主要用于雙目相機的標定和矯正。它包含了讀取和保存相機模型、計算標定參數以及矯正圖像的功能。通過這些功能&#xff0c;可以實現雙目相機的標定和矯正&#xff0c;從而提高雙目相機的精度和穩定性。 公有函數&#xff1a; 構造函數、帶參構造函數、析構函數、讀取雙目相機…

摩斯邀您參加“WAIC 2024世界人工智能大會”

2024世界人工智能大會暨人工智能全球治理高級別會議&#xff08;簡稱“WAIC 2024”&#xff09;將于7月在上海世博中心、世博展覽館舉行&#xff0c;論壇時間為7月4日-6日&#xff0c;展覽時間為7月5日-7日。大會展覽面積超5.2萬平方米&#xff0c;重點圍繞核心技術、智能終端、…

STM32要學到什么程度才算合格?

在開始前剛好我有一些資料&#xff0c;是我根據網友給的問題精心整理了一份「嵌入式的資料從專業入門到高級教程」&#xff0c; 點個關注在評論區回復“888”之后私信回復“888”&#xff0c;全部無償共享給大家&#xff01;&#xff01;&#xff01; STM32 這玩意兒要學到啥…

今天聊聊AI

AI是在幫助開發者還是取代他們&#xff1f; 在軟件開發領域&#xff0c;生成式人工智能&#xff08;AIGC&#xff09;正在改變開發者的工作方式。無論是代碼生成、錯誤檢測還是自動化測試&#xff0c;AI工具正在成為開發者的得力助手。然而&#xff0c;這也引發了對開發者職業…

vscode 前行復制到下一行

目錄 這個技巧也比較多 選擇 python解釋器 F1 Ctrl Shift P 跳轉上一次編輯 下一次編輯 Ctrl d 會把當前行復制到下一行 步驟1&#xff1a;打開鍵綁定設置 使用VS Code設置換行 這個技巧也比較多 VS Code技巧匯總_vs code反縮進-CSDN博客 選擇 python解釋器 F1 Ctrl Shi…

Java中如何使用 tesseract-ocr 進行圖片文字提取(tesseract、tesseract訓練自己的字庫)

tesseract下載鏈接&#xff1a; github&#xff1a;https://github.com/tesseract-ocr/ db&#xff1a;https://digi.bib.uni-mannheim.de/tesseract/ 文字識別技術在許多領域都有廣泛的應用&#xff0c;例如文檔處理、自動化辦公、移動設備上的文本輸入等。而Tesseract-OCR作…

Python推導式寫出簡潔高效的代碼方法詳解

概要 推導式是Python中一種非常強大的語法特性,允許你用簡潔的語法創建列表、字典、集合等數據結構。使用推導式不僅可以讓代碼更加簡潔和易讀,還能提高代碼的執行效率。本文將詳細介紹Python中的各種推導式,并提供相應的示例代碼,幫助全面掌握這一強大的工具。 列表推導式…

【前端項目筆記】9 數據報表

數據報表 效果展示&#xff1a; 在開發代碼之前新建分支 git checkout -b report 新建分支report git branch 查看分支 git push -u origin report 將本地report分支推送到云端origin并命名為report 通過路由的形式將數據報表加載到頁面中 渲染數據報表基本布局 面包屑導航…

數據洞察:從零到一的數據倉庫與Navicat連接全攻略【實訓Day04】[完結篇]

一、數據分析 1 實現數據倉庫(在hadoop101上) 1) 創建jobdata數據庫 # cd $HIVE_HOME # bin/hive hive>create database jobdata; hive>use jobdata; 2) 創建原始職位數據事實表ods_jobdata_orgin(在hadoop101上) create table ods_jobdata_origin( city string CO…

Keepalived+LVS實現負責均衡,高可用的集群

Keepalived的設計目標是構建高可用的LVS負載均衡群集&#xff0c;可以調用ipvsadm工具來創建虛擬服務器&#xff0c;管理服務器池&#xff0c;而不僅僅用作雙機熱備。使用Keepalived構建LVS群集更加簡便易用&#xff0c;主要優勢體現在&#xff1a;對LVS負責調度器實現熱備切換…

配置并調試后端程序(sql)

1.環境準備 安裝VS Code和Node.js插件&#xff1a;確保你已經安裝了VS Code和Node.js插件。創建launch.json文件&#xff1a;在你的項目中創建一個.vscode文件夾&#xff0c;并在其中創建launch.json文件。添加以下內容&#xff1a; {"version": "0.2.0"…

uniapp 數據父傳子

文章目錄 可能出現的問題 在uni-app中&#xff0c;父組件向子組件傳遞數據主要通過屬性綁定的方式實現。這里提供一個簡單的示例來說明如何進行父傳子的數據傳遞&#xff1a; 父組件 準備數據: 在父組件的data中定義要傳遞的數據。 export default {data() {return {parentMe…

@ControllerAdice統一返回值類型【Spring源碼學習】

我們可以通過在ControllerAdvice注解類上實現ResponseBodyAdvice注解來實現統一返回值類型&#xff1b; 例如統一接口的返回類型為Result類 ControllerAdvice static class MyControllerAdvice implements ResponseBodyAdvice<Object> {Overridepublic boolean supports…

PLC基礎知識

1.PLC中的數據寄存器地址D表示存數據的地方。 2.PLC的物理存儲器的規定&#xff1a;PLC存儲器以字節為單位&#xff08;Byte&#xff09;&#xff0c;存儲單元以位&#xff08;Bit&#xff09;、字節&#xff08;B&#xff0c;8Bit&#xff09;、字&#xff08;W&#xff0c;1…