当前位置：首页 > news >正文

算法刷题记录——LeetCode篇(2.7) [第161~170题](持续更新)

news 来源：原创 2025/8/24 13:22:59

更新时间：2025-04-06

算法题解目录汇总：算法刷题记录——题解目录汇总
技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

n == nums.length
1 <= n <= 5*10^4
-10^9 <= nums[i] <= 10^9

进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

188. 买卖股票的最佳时机 IV

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2

解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7

解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

方法一：动态规划（通用解法）

使用三维状态压缩的动态规划，将状态定义为 dp[j][0] 和 dp[j][1]，分别表示完成 j 次交易后不持有股票和持有股票的最大利润。通过逆序处理交易次数避免状态覆盖问题，并增加无效状态判断。

代码实现(Java)：

public class Solution {public int maxProfit(int k, int[] prices) {int n = prices.length;if (k == 0 || n < 2) return 0;// 处理 k 很大的情况，退化为贪心算法if (k >= n / 2) {int maxProfit = 0;for (int i = 1; i < n; i++) {if (prices[i] > prices[i - 1]) {maxProfit += prices[i] - prices[i - 1];}}return maxProfit;}// 动态规划初始化int[][] prevDp = new int[k + 1][2];for (int j = 0; j <= k; j++) {Arrays.fill(prevDp[j], Integer.MIN_VALUE);}prevDp[0][0] = 0;          // 0次交易，不持有股票prevDp[0][1] = -prices[0]; // 0次交易，持有股票for (int i = 1; i < n; i++) {int[][] currDp = new int[k + 1][2];for (int j = 0; j <= k; j++) {currDp[j][0] = prevDp[j][0];currDp[j][1] = prevDp[j][1];}int price = prices[i];// 逆序处理交易次数，避免状态覆盖for (int j = k; j >= 1; j--) {// 不持有股票：卖出操作if (prevDp[j][1] != Integer.MIN_VALUE) {currDp[j][0] = Math.max(currDp[j][0], prevDp[j][1] + price);}// 持有股票：买入操作（需要前一次交易完成）if (prevDp[j - 1][0] != Integer.MIN_VALUE) {currDp[j][1] = Math.max(currDp[j][1], prevDp[j - 1][0] - price);}}// 处理 j=0 的持有状态（允许第一次买入）currDp[0][1] = Math.max(prevDp[0][1], -price);prevDp = currDp;}// 寻找最大利润（所有交易次数中的最大不持有状态）int maxProfit = 0;for (int j = 0; j <= k; j++) {maxProfit = Math.max(maxProfit, prevDp[j][0]);}return maxProfit;}
}

复杂度分析

时间复杂度：O(nk)，每个价格处理 k 次交易状态。
空间复杂度：O(k)，使用两个数组交替保存状态。

方法二：状态压缩优化

进一步压缩动态规划空间，使用一维数组代替二维数组。通过逆序遍历交易次数减少空间使用。

代码实现(Java)：

public class Solution {public int maxProfit(int k, int[] prices) {int n = prices.length;if (k == 0 || n < 2) return 0;if (k >= n / 2) {int profit = 0;for (int i = 1; i < n; i++) {if (prices[i] > prices[i - 1]) {profit += prices[i] - prices[i - 1];}}return profit;}int[] buy = new int[k + 1];int[] sell = new int[k + 1];Arrays.fill(buy, Integer.MIN_VALUE);for (int price : prices) {for (int j = k; j >= 1; j--) {buy[j] = Math.max(buy[j], sell[j - 1] - price);sell[j] = Math.max(sell[j], buy[j] + price);}}return sell[k];}
}

复杂度分析

时间复杂度：O(nk)，每个价格处理 k 次交易。
空间复杂度：O(k)，仅用两个一维数组。

声明

本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

169. 多数元素

188. 买卖股票的最佳时机 IV

方法一：动态规划（通用解法）

复杂度分析

方法二：状态压缩优化

复杂度分析

相关文章：