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

leecodecode【状态机DP】【2026.6.9打卡-java版本】

news 2026/6/10 22:36:26

买卖股票的最佳时机

要点：只能买一次，维护min，和 ans

class Solution { public int maxProfit(int[] prices) { int min = Integer.MAX_VALUE; int ans = 0; for(int price : prices){ min = Math.min(min, price); ans = Math.max(ans, price - min); } return ans; } }

买卖股票的最佳时机 II

要点：dp【i】【0是没持有，1是持有，两个状态切换】

dp[i+1][0] = Math.max(dp[i][0], dp[i][1] + prices[i]);
dp[i+1][1] = Math.max(dp[i][1], dp[i][0] - prices[i]);

class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n+1][2]; dp[0][1] = Integer.MIN_VALUE; for(int i = 0; i < n; i++){ dp[i+1][0] = Math.max(dp[i][0], dp[i][1] + prices[i]); dp[i+1][1] = Math.max(dp[i][1], dp[i][0] - prices[i]); } return dp[n][0]; } }

买卖股票的最佳时机含冷冻期

要点：

dp[i+2][0] = Math.max(dp[i+1][0], dp[i+1][1] + prices[i]);

dp[i+2][1] = Math.max(dp[i+1][1], dp[i][0] - prices[i]);

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n+2][2]; dp[1][1] = Integer.MIN_VALUE; for(int i = 0; i < n; i++){ dp[i+2][0] = Math.max(dp[i+1][0], dp[i+1][1] + prices[i]); dp[i+2][1] = Math.max(dp[i+1][1], dp[i][0] - prices[i]); } return dp[n+1][0]; } }

买卖股票的最佳时机 IV

要点：困难，也有点没理解

设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。也就是说，你最多可以买k次，卖k次。

class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; int[][][] f = new int[n + 1][k + 2][2]; for (int[][] mat : f) { for (int[] row : mat) { Arrays.fill(row, Integer.MIN_VALUE / 2); // 防止溢出 } } for (int j = 1; j <= k + 1; j++) { f[0][j][0] = 0; } for (int i = 0; i < n; i++) { for (int j = 1; j <= k + 1; j++) { f[i + 1][j][0] = Math.max(f[i][j][0], f[i][j][1] + prices[i]); f[i + 1][j][1] = Math.max(f[i][j][1], f[i][j - 1][0] - prices[i]); } } return f[n][k + 1][0]; } }

随机知识

二、RabbitMQ 核心概念（必问，基础到不能再基础）

核心题：RabbitMQ 里的 Exchange、Queue、Binding、Routing Key 分别是什么？整个消息流转过程是怎样的？

面试官为什么这么问？
这是 RabbitMQ 独有的模型，和 Kafka、RocketMQ 不一样。我问这个是要看你是否真正理解 AMQP 协议的设计，知道一条消息从 Producer 到 Consumer 经历了什么。

希望听到怎样的回答：

四个核心组件：
- Producer：发送消息的应用。
- Exchange：交换机，接收消息，根据规则路由到队列。
- Queue：队列，存储消息，消费者从这里取。
- Binding：绑定，把 Exchange 和 Queue 关联起来，并指定 routing key。
流转过程：
1. Producer 发消息到 Exchange，带上 Routing key。
2. Exchange 根据类型和 Binding 决定消息投递给哪些 Queue。
3. Queue 存储消息，等待 Consumer 拉取或自动推送。
4. Consumer 处理消息，返回 ACK。
常见交换机类型：
- direct：Routing key 完全匹配。
- topic：Routing key 支持通配符*（匹配一个单词）和#（匹配零或多个单词）。
- fanout：广播，忽略 routing key，所有绑定的队列都收到。
- headers：用消息头匹配（极少用）。

候选人：
这其实对应的是 AMQP 协议的核心模型。RabbitMQ 和 Kafka、RocketMQ 最大的不同，就是它多了Exchange 和 Binding这两个角色，把消息的路由规则和存储队列完全分开了。

我先分别说清这四个角色，再把整个流转过程串起来。

一、四个核心组件

Producer（生产者）：发送消息的应用。它不直接发消息到队列，而是发给 Exchange。

Exchange（交换机）：负责接收生产者发来的消息，然后根据路由规则把消息分发到一个或多个队列。注意，Exchange 本身不存储消息，它只是一个“路由器”。如果它找不到匹配的队列，消息默认会被丢弃。

Queue（队列）：真正存放消息的地方，消息在这里等待被消费。队列是消费者直接对接的对象，一个队列可以被多个消费者监听，但同一条消息只会被一个消费者消费。

Binding（绑定）：它是一根“线”，把 Exchange 和 Queue 连接起来。在绑定的同时，会指定一个Binding Key。这个 Binding Key 是路由匹配的依据，决定了 Exchange 收到的消息该投递给哪个队列。

Routing Key：是生产者在发送消息时指定的一个字符串。Exchange 就拿这个消息的 Routing Key，和队列的 Binding Key 去匹配，匹配上了就把消息投递过去。

可以这样理解：整个路由系统是一个快递分拨中心。Exchange 是分拨中心，Queue 是具体楼宇的快递柜，Binding 是把快递柜挂到分拨中心的线缆。Routing Key 是快递单上的地址标签。生产者把快递扔到分拨中心，分拨中心根据标签和线缆的匹配关系，把快递精准投入对应的某个或某些快递柜，消费者从指定的快递柜取快递。

二、完整流转过程

Producer 发送消息：它连接 Broker，将带有 Routing Key 的消息投递给指定名称的 Exchange。
Exchange 路由判断：Exchange 收到消息后，根据类型和 Binding Key 列表进行匹配。如果有队列的 Binding Key 和这条消息的 Routing Key 匹配，Exchange 就把消息的副本投递到该队列。如果不匹配，消息直接被丢弃（或者根据设置的 mandatory/alternate-exchange 来兜底）。
Queue 存储消息：消息进入队列后，等待消费者处理。多个消费者共享一个队列时，同一条消息只会投给其中一个消费者，不会重复消费。
Consumer 拉取消息：消费者通常采用 Push 模式（开启 basic.consume 自动接收），也可以 Pull 模式主动拉。收到消息后处理业务逻辑。
消息确认 ACK：消费者处理成功后，向 Broker 返回 ACK。Broker 将这条消息从队列中彻底删除。如果消费者宕机或处理失败返回 NACK，RabbitMQ 可以将消息重新入队或进入死信队列。

三、常见交换机类型

RabbitMQ 有四种 Exchange 类型，核心区别在于Routing Key 和 Binding Key 的匹配规则不同。

类型	路由规则	典型场景
Direct	Routing Key 完全等于 Binding Key	单播消息，比如订单通知
Topic	支持通配符`*`（一个词）和`#`（零或多个词），按`.`分隔的单词模式匹配	多路分发，比如日志收集：`error.order`、`info.payment`
Fanout	忽略 Routing Key，消息直接广播到所有绑定队列	广播通知，比如配置刷新、缓存失效
Headers	根据消息头自定义匹配规则，极少使用	极特殊的头匹配场景