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

最长有效括号要点栈push下标class Solution { public int longestValidParentheses(String s) { //栈 //放前哨-1 DequeInteger 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] j0){ 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 PriorityQueueInteger leftMaxHeap; // rightMinHeap: 存放较大的一半数堆顶是这一半中的最小值小顶堆 private PriorityQueueInteger 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()); } } // 情况2num 大于左半边的最大值 // 说明 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; StackInteger 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证明你有分布式意识。希望听到的回答CAPC一致性所有节点同一时间看到同一数据A可用性每个请求都能得到非错误的响应P分区容错性网络分区时系统仍能工作分布式系统只能同时满足两个P 是必须的所以要么 CPZooKeeper要么 APEurekaBASEBasically 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天以后每天就按秋招项目【javaagent】科研必做项目算法八股锻炼身体来总结。今天又是啥也没干的一天一放假就啥也不想干项目还出了好多问题唉。总结不要放弃呀1.算法要系统过一遍【灵神】2.秋招项目【java可能ok】【agent继续加油】这周一定要搞完背面试八股了3.科研要跑一下4.必搞项目也得总结文档5.训练项目看看先选择好6.背八股7.锻炼身体【最后最后请相信自己可以的】————————————————