topcode【随机算法题】【2026.5.24打卡-java版本】

最长有效括号

要点：栈，push下标

class Solution { public int longestValidParentheses(String s) { //栈 //放前哨-1 Deque<Integer> stack = new ArrayDeque<>(); stack.push(-1); int ans = 0; for(int i = 0; i < s.length(); i++){ char c = s.charAt(i); if(c =='('){ stack.push(i); }else{ stack.pop(); if(stack.isEmpty()){ stack.push(i); }else{ ans = Math.max(ans, i - stack.peek()); } } } return ans; } }

下一个排列

要点：从后往前找第一个小的数，再找比这个数大一点的数，换位置，旋转

class Solution { public void nextPermutation(int[] nums) { //找下降点 int i = nums.length - 1; while((i-1)>=0 && nums[i]<=nums[i-1] ){ i--; } if(i-1>= 0){ int j = nums.length -1; while(nums[j]<=nums[i-1] && j>=0){ j--; } swap(nums,i-1,j); } reverse(nums, i); } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } private void reverse(int[] nums, int start) { int end = nums.length - 1; while (start < end) { swap(nums, start, end); start++; end--; } } }

数据流的中位数

要点：大顶堆，小盯堆分成两边

class MedianFinder { // leftMaxHeap: 存放较小的一半数，堆顶是这一半中的最大值（大顶堆） private PriorityQueue<Integer> leftMaxHeap; // rightMinHeap: 存放较大的一半数，堆顶是这一半中的最小值（小顶堆） private PriorityQueue<Integer> rightMinHeap; public MedianFinder() { // 大顶堆：使用 lambda 表达式 (a, b) -> b - a，让大的元素在堆顶 leftMaxHeap = new PriorityQueue<>((a, b) -> b - a); // 小顶堆：默认排序，小的元素在堆顶 rightMinHeap = new PriorityQueue<>(); } public void addNum(int num) { // 情况1：左半边为空，或者 num 小于等于左半边的最大值 // 说明 num 应该放在左半边（较小的一半） if (leftMaxHeap.isEmpty() || num <= leftMaxHeap.peek()) { leftMaxHeap.offer(num); // 平衡：左半边最多只能比右半边多1个元素 // 如果左半边比右半边多了2个以上，就把左半边的最大值移到右半边 if (leftMaxHeap.size() > rightMinHeap.size() + 1) { rightMinHeap.offer(leftMaxHeap.poll()); } } // 情况2：num 大于左半边的最大值 // 说明 num 应该放在右半边（较大的一半） else { rightMinHeap.offer(num); // 平衡：右半边的大小不能超过左半边 // 如果右半边比左半边还大，就把右半边的最小值移到左半边 if (rightMinHeap.size() > leftMaxHeap.size()) { leftMaxHeap.offer(rightMinHeap.poll()); } } } public double findMedian() { // 如果左半边多一个元素（总数为奇数），中位数就是左半边的最大值 if (leftMaxHeap.size() > rightMinHeap.size()) { return leftMaxHeap.peek(); } // 如果两边数量相等（总数为偶数），中位数是（左最大 + 右最小）/ 2 return (leftMaxHeap.peek() + rightMinHeap.peek()) / 2.0; } }

柱状图中最大的矩形

要点：栈，哨兵，高度*宽度

import java.util.*; class Solution { public int largestRectangleArea(int[] heights) { if (heights == null || heights.length == 0) { return 0; } int n = heights.length; // 创建一个新数组，在原数组前后各添加一个0，方便处理边界 int[] newHeights = new int[n + 2]; for (int i = 0; i < n; i++) { newHeights[i + 1] = heights[i]; } // 前后哨兵为0 newHeights[0] = 0; newHeights[n + 1] = 0; Stack<Integer> stack = new Stack<>(); int maxArea = 0; for (int i = 0; i < newHeights.length; i++) { // 当当前柱子高度小于栈顶柱子高度时 while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) { // 弹出栈顶柱子 int height = newHeights[stack.pop()]; // 计算宽度：右边界i，左边界是新的栈顶元素 int left = stack.isEmpty() ? -1 : stack.peek(); int width = i - left - 1; maxArea = Math.max(maxArea, height * width); } // 将当前索引入栈 stack.push(i); } return maxArea; } }

，

寻找两个正序数组的中位数

要点：最笨的方法

class Solution { public double findMedianSortedArrays(int[] a, int[] b) { int m = a.length; int n = b.length; int[] merged = new int[m + n]; System.arraycopy(a, 0, merged, 0, m); System.arraycopy(b, 0, merged, m, n); Arrays.sort(merged); int s = m + n; int k = (s - 1) / 2; return s % 2 > 0 ? merged[k] : (merged[k] + merged[k + 1]) / 2.0; } }

随机知识

二、分布式系统理论（概念级，加分项）

核心题：什么是 CAP 定理？BASE 理论是什么？分布式事务了解吗？

面试官为什么这么问：现在很少有系统真单机，实习生至少要知道 CAP 和 BASE，证明你有分布式意识。

希望听到的回答：

• CAP：
  • C（一致性）：所有节点同一时间看到同一数据
  • A（可用性）：每个请求都能得到非错误的响应
  • P（分区容错性）：网络分区时系统仍能工作
  • 分布式系统只能同时满足两个，P 是必须的，所以要么 CP（ZooKeeper）要么 AP（Eureka）
• BASE：
  • Basically Available（基本可用）
  • Soft state（软状态）
  • Eventually consistent（最终一致性）
  • 是和 ACID 的对照，用于 NoSQL 和分布式缓存场景
• 分布式事务概念：2PC、TCC、本地消息表、RocketMQ 事务消息，知道名字和大概思路就行，不要求细节。

结合项目说的话：“我们用 RabbitMQ 做异步处理，保证投递可靠，就是基于 BASE 思想实现最终一致性，不强求强一致。”

候选人:
好的。这三个概念是分布式系统的基石,CAP是理论约束,BASE是工程妥协,分布式事务是具体实践。我从CAP讲起,再说明BASE如何放宽约束,最后介绍几种常见的分布式事务方案。

第一,CAP定理——分布式系统的“不可能三角”。

CAP定理告诉我们:一个分布式系统最多只能同时满足以下三个特性中的两个。

C是一致性。所有节点在同一时刻看到的数据完全相同。客户端向节点A写入数据后,立即去节点B读取,节点B必须返回最新写入的值。对于客户端来说,系统表现得就像只有一个节点一样,这是最理想但也最难实现的状态。

A是可用性。每个请求都能得到非错误的响应,但不保证返回的数据是最新的。系统可能返回旧数据,但必须响应。

P是分区容错性。当网络发生分区时,也就是部分节点之间无法通信,系统仍然能继续工作。网络分区在分布式系统中是不可避免的,交换机故障、光缆被挖断、网络抖动都可能导致分区。所以P是分布式系统的“生存底线”,任何跨网络的节点通信都必须考虑P。

为什么只能三选二？

关键是:当网络分区发生时,系统必须在C和A之间做选择。

假设系统有节点A和节点B,它们之间网络断了。客户端向A发送写请求。如果系统选择保证一致性,A必须拒绝这次写入,因为它无法把数据同步给B,于是牺牲了可用性——这就是CP系统。

如果系统选择保证可用性,A接受写入并返回成功,但B此时无法同步到新数据。客户端访问A看到新数据,访问B看到旧数据,两个节点不一致——这就是AP系统。

没有网络分区的时候,系统可以同时满足C和A。一旦分区发生,就必须在两者之间取舍。

典型产品的选择

ZooKeeper是典型的CP系统。当Leader节点故障时,集群会暂停服务进行重新选举,期间拒绝所有请求,保证数据一致性。这适合配置管理、分布式锁这类对一致性要求严格的场景。

Eureka是典型的AP系统。服务之间有过期检查,但网络分区时优先保证服务可用,允许各节点数据短暂不一致,适合服务注册发现的场景,宁可让调用方拿到可能过期的服务列表,也不能停止服务。

Redis本身设计偏向AP。主从复制是异步的,主节点故障切换时可能有短暂的数据丢失窗口。Redis Cluster也是去中心化设计,优先保证分片可用,不保证多节点间强一致性。

第二,BASE理论——对CAP的工程妥协。

CAP定理要求我们在C和A之间做选择,但现实业务往往不需要绝对的强一致性。BASE理论就是针对AP系统的一种实践指导,它是对ACID(原子性、一致性、隔离性、持久性)严格事务模型的放松。

BA是基本可用。系统出现故障时允许损失部分可用性,但核心功能仍可用。比如双十一高峰时,阿里会关闭退款、账单明细等非核心功能,保证下单和支付链路正常。用户虽然不能查去年的订单,但能完成购买。

S是软状态。允许系统中的数据存在中间状态,不要求所有节点数据时刻一致。比如订单支付成功后,订单状态从“待支付”变成“支付成功”,但积分系统可能还没有加上积分。这个中间状态窗口可以接受。

E是最终一致性。不强求实时一致,但保证经过一段时间后,所有副本最终达到一致状态。比如用户用积分兑换了优惠券,几分钟后积分才被冻结,最终结果正确就行。

BASE和ACID不是对立关系,而是不同场景的选择。金融转账、账户余额必须是ACID强一致;社交帖子、点赞数、商品库存展示这些场景,BASE的最终一致性完全可接受。CAP告诉我们“没有完美的分布式系统”,BASE则回答了“在不完美的系统中,如何让业务还能正常运转”。

第三,分布式事务——如何跨服务保证最终一致性。

单体应用用数据库自带的事务保证ACID。微服务架构下,一笔业务跨越多个服务实例和多个数据库,就需要分布式事务方案。我对以下几种方案各有理解:

2PC两阶段提交。协调者先问所有参与者“能提交吗”(准备阶段),所有参与者都回复可以,再通知“正式提交”(提交阶段)。问题是协调者单点故障、参与者同步阻塞时间长、性能最差。XA协议是2PC的标准实现,但生产环境很少用在核心链路上。

TCC补偿事务。把操作拆成Try(预留资源)、Confirm(确认执行)、Cancel(取消回滚)三个阶段。每个参与方都要提供对业务的三段接口。比2PC灵活,但代码侵入性强,每个业务接口都要按TCC规范设计,开发成本高。

本地消息表。服务的本地事务里同时写业务数据和消息表,用定时任务扫描未发送消息投递到MQ,消费方处理并回调确认。完全依赖本地事务保证原子性,不要求跨服务的实时协调,但需要消费方接口做成幂等。比较适合单体拆分或简单链路。

RocketMQ事务消息。生产者先向MQ发一条半消息,然后执行本地事务。本地事务成功则提交半消息,失败则回滚半消息。MQ会定期反查生产者的本地事务状态来确认未知状态的消息。这是最佳生产实践,不需要消费者额外开发确认接口,RocketMQ自身承担事务反查的职责。

项目中的实际选择

我的项目用RabbitMQ实现最终一致性。核心链路是先写数据库确认业务成功,然后发消息到MQ。消费方从队列取出消息处理。需要考虑两种异常:发消息失败时,把待发送记录写入重试表,定时任务扫描补偿;消费处理失败时,重试几次仍失败转死信队列,人工介入处理。同时消费者做好幂等,用唯一业务键加数据库唯一索引来防止重复处理。

这就是典型的BASE思想实践——不强求跨服务的实时强一致,但通过消息重试、死信兜底、幂等设计保证最终数据对齐。

总结:CAP告诉我们分布式系统必须在一致性和可用性之间做取舍,P是必须满足的底线。BASE告诉我们大多数互联网业务可以接受最终一致性,用软状态换可用性和性能。分布式事务方案从强一致的2PC到弱一致的本地消息表再到事务消息,选择什么方案取决于业务对一致性的要求和对复杂性的容忍度。基本规律是:大部分场景用MQ加幂等实现最终一致性就够了,只有极少数的资金交易才需要强一致性的分布式事务框架介入。

碎碎念：后续会更新每天学习的八股和算法 题，开始准备秋招的第14天。努力连续更新100天！以后每天就按，秋招项目【java+agent】，科研，必做项目，算法，八股，锻炼身体来总结。今天又是啥也没干的一天，一放假就啥也不想干，项目还出了好多问题，唉。

总结：不要放弃呀，

1.算法要系统过一遍【灵神】

2.秋招项目【java可能ok？】【agent继续加油】，这周一定要搞完背面试八股了

3.科研要跑一下

4.必搞项目也得总结文档

5.训练项目看看先选择好

6.背八股

7.锻炼身体

【最后最后，请相信自己可以的！！！！！】
————————————————