算法（十四）动态规划
关于动态规划内容很多，这里只列举一些我觉都有意思的题目。 二维简单动态规划最小路径和leetcode 64 思路：状态转移方程：f[i][j] = Math.min(f[i-1][j],f[i][j-1]) + grid[i][j] 因为一个位置只能从上或者左转移过来，所以状态转移方程就是这个样子的。 12345678910111213141516public int minPathSum(int[][] grid) { int n = grid.length; int m = grid[0].length; int[] dp = new int[m]; dp[0] = grid[0][0]; for(int i=1;i<m;i++){ dp[i] = grid[0][i]+dp[i-1]; } for(int i = 1;i<n;i++){ dp[0]+=grid[i][0]; for(int j = 1;j<m;j++){ ...
我们讨论分布式中的一致性到底是什么
分布式系统的“人格分裂”：当我们在谈论一致性时，我们到底在谈什么？在技术圈里摸爬滚打，你一定听过无数次“分布式系统”这个词，也背过无数次 CAP 定理、BASE 理论。 但你是否在某个深夜调试代码时感到困惑： “为什么 Seata 的文档里在谈一致性，Raft 的论文里也在谈一致性，但我总感觉它们说的不是一回事？” “微服务拆分后的一致性，和 Redis 集群的一致性，是一样的吗？” 其实，你的直觉是对的。“分布式系统”这个词是个大筐，里面装了两个完全不同的流派。 它们虽然都叫分布式，都追求一致性，但它们的灵魂截然不同。 今天，我们就把这两个流派拆开来看一看。 流派一：为了“分工与解耦” —— 分布式计算/服务化这个流派的典型代表是 微服务架构（Spring Cloud, Dubbo, gRPC）。 1. 它的本质：从“一个人干”变成“一群人干”在这个流派里，我们把一个巨大的单体应用（Monolith）拆成了订单服务、库存服务、支付服务。 目的： 为了解耦，为了让不同的团队开发不同的模块，为了逻辑清晰。 物理形态： 哪怕每个服务只部署在一台机器上（没有副本），它依然是标准...
算法（十三） 图
建图的几种方式 邻接矩阵、邻接表、链式前向星123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119// 点的最大数量 public static int MAXN = 11; // 边的最大数量 // 只有链式前向星方式建图需要这个数量 // 注意如果无向图的最大数量是m条边，数量要准备m*2 // 因为一条无向边要加两条有向边 public static int MAXM = 21; // 邻接矩阵方式建图 public static int[][] graph1 = new int[MAXN][MAXN]; // 邻接表方式建图 // pu...
算法（十二）并查集
用法 并查集模板 扁平化+小挂大123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051public static int MAXN = 1000001;public static int[] father = new int[MAXN];public static int[] size = new int[MAXN];public static int[] stack = new int[MAXN];public static int n;public static void build() { for (int i = 0; i <= n; i++) { father[i] = i; size[i] = 1; }}// i号节点，往上一直找，找到代表节点返回！public static int find(int i) { // 沿途收集了几个点 int size = 0; while (i...
AQS是什么？
【Java并发】AQS详解：JUC包背后的“幕后大佬”在 Java 并发编程（JUC）的世界里，我们经常使用 ReentrantLock、CountDownLatch、Semaphore 这些赫赫有名的工具类。 但你是否想过，这些功能各异的工具背后，其实共用着同一套“底盘”？ 这就是我们今天要聊的主角——AQS (AbstractQueuedSynchronizer，抽象队列同步器)。它是 JUC 包的心脏，掌握了它，你就掌握了 Java 并发的半壁江山。 一、 什么是 AQS？AQS 是一个用于构建锁和同步器的框架。 如果把 ReentrantLock、CountDownLatch 等比作是成品的汽车（跑车、卡车、公交车），那么 AQS 就是通用的汽车底盘和引擎。 AQS 负责脏活累活：它处理了线程的排队、阻塞、唤醒、线程安全等最复杂的底层逻辑。 同步器负责业务逻辑：具体的工具类只需要告诉 AQS，“什么时候算获取锁成功”，“资源一共有多少”，剩下的交给 AQS 即可。 简单来说，AQS 是一个“原材料”，我们可以根据它加工出各种各样的同步器。 二、 AQS 的核心架构AQ...
算法（十一） 单调队列
经典用法配合滑动窗口，可以快速得到滑动窗口内的最大值或者最小值。如果要最大值，那维护一个大到小队列（存的是下标），如果要最小值，那维护一个小到大的队列。 拿最大值举例： 扩大窗口的时候，判断新加入的元素跟队尾元素的大小，只要队尾元素小于等于新值，则队尾元素出队，直到队尾元素大于新值或者队列为空。然后这个新值的下标从队尾入队 缩小窗口时，判断这个要出去的元素下标跟单调队列队头的下标是否相等，如果相等则队头元素出队。l++.否则就不移除队头。 如果要最大值，就是数组的队头元素位置的值。 nums[deque[l]] 滑动窗口最大值leetcode 239 1234567891011121314151617181920212223242526272829public static int[] maxSlidingWindow(int[] arr, int k) { h = t = 0; int n = arr.length; // 先形成长度为k-1的窗口 for (int i = 0; i < k - 1; i++) { // 大 -> 小...
算法（十） 单调栈
经典用法单调栈问题，就是当你分析问题时，需要你找到一个索引左右两边大于或者小于自己的最近索引时，就使用单调栈！ 总结 每日最高温度leetcode 739 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 思路：将下标一次放入栈，但遵循以下要求，如果当前的温度大于栈顶的温度，则栈顶的索引出栈，并记录当前索引与栈顶索引的差值，即当前索引与栈顶索引的差值就是当前索引对应的天数。循环弹出，直到栈为空或者栈顶的索引对应的温度大于等于当前索引对应的温度。则当前索引入栈。 12345678910111213public static int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; size = 0; int[] ans = new int[n]; for(int i =0;i<n;i...
Java实现基于raft算法的kv存储系统
Java手写Raft篇：核心流程与并发模型优化前言这是一篇基于Java实现raft分布式KV存储系统的博客。本项目基于 https://github.com/stateIs0/lu-raft-kv 该开源项目进行的二次开发。主要按照Raft协议的生命周期（选主、日志复制、安全性、一致性读）进行了改造。本篇博客记录了我的改造思路，以及一些值得注意的地方。Raft 算法作为分布式一致性协议的标准解法，以其清晰的模块化设计著称。本文将基于我如何改造原开源项目，深入剖析其中的核心机制。从选主逻辑、日志复制的细节，到解决“幽灵复现”问题的 No-Op 日志，再到利用 CompletableFuture 对并发模型的重构，以此记录构建高一致性分布式存储系统的思考过程。 一、 选举机制 (Leader Election)选主是集群启动或 Leader 宕机后的首要任务。在此阶段，不仅要保证票数过半，更要严格校验节点资格。 1. 状态流转与拉票当 Follower 的心跳倒计时结束（在一定范围内随机时间，我选择的是跟最大选举时间到它的两倍这个范围，避免同时存在多个候选人导致效率下降）仍未收到 ...
算法（九） 二分
狒狒吃香蕉思路：最小值为1，最大值就是数组最大值。在这个范围上不断二分。遇到能吃完记录答案，往左侧二分寻找更小的，吃不完往不计答案，右侧二分寻找更大的。 1234567891011121314151617181920212223242526public int minEatingSpeed(int[] piles, int h) { int l=1; int r = 0; for (int i : piles) { r = Math.max(r,i); } int ans = r; while(l<=r){ int mid = l + ((r-l)>>1); if(fMinEatingSpeed(piles,mid) <= h){ ans = mid; r = mid-1; }else { l = mid+1; ...
算法（八）双指针
总结 寻找重复数 leetcode hot100 最后一题思路：当成链表找环处理。每到一个位置i 那下一次就到arr[i]对应的位置。显然入环节点就是重复的数。 12345678910111213141516public int findDuplicate(int[] nums) { int kuai = 0; int man = 0; while(true){ kuai = nums[nums[kuai]]; man = nums[man]; if(kuai == man){ kuai = 0; while(kuai != man){ kuai = nums[kuai]; man = nums[man]; } return kuai; } }} 接雨水思路：初始版，类似与前缀...