算法总结（七） 滑动窗口
累加和大于等于k的最小长度子数组都是正数，所以滑动窗口具有单调性，加入新数肯定会导致累加和变大，减少数字会导致累加和变小。 123456789101112131415 public static int minSubArrayLen(int target, int[] nums) { int ans = Integer.MAX_VALUE; for (int l = 0, r = 0, sum = 0; r < nums.length; r++) { sum += nums[r]; while (sum - nums[l] >= target) { // sum : nums[l....r] // 如果l位置的数从窗口出去，还能继续达标，那就出去 sum -= nums[l++]; } if (sum >= target) { ans = Math.min(ans, r - l + 1); } } return ans == Integer.MAX_VALUE ?...
聚合与聚合根
这篇文章用于存放我在阅读《悟道领域驱动设计》时，关于聚合与聚合根的笔记。 1.只能通过聚合根来修改内部对象，不能绕过聚合根。 2.就算想引用聚合根里面的对象，比如订单里面的订单项列表。那么订单这个聚合根提供的get方法也必须new 一个新列表返回！ 3.只有聚合根有repository。（实体可以有factory） 4.设计聚合最好小而全，最好能做到一个实体就是聚合。但做不到也不强求，能满足要求即可，但切记不能过大，也不能太小。 5.聚合根不能在内部直接引用其他聚合根，只能根据唯一id去查询另一个聚合根，由服务进行统排。 6.一个事务只对一个聚合根保存生效。 7.跨聚合采用最终一致性（因为规定了第6条，所以在跨聚合中经常会对不同的表进行操作），具体可以由领域事件实现。 8.如果聚合根内部有一个实体列表（1：N关系）那么可以考虑把这个实体也变成聚合根，原聚合根只保留他的唯一id列表。如果是多对多关系，可以考虑再新建一个表示它们两个关系的聚合根。 9.为什么要拆分聚合根？ 因为一个聚合根保留的信息越多，那么在并发的情况下，保存聚合根时冲突的概率就越大。比如我的用户保留了资源列表，而且...
算法（六）前缀和
一维前缀和（子数组相关问题）和等于k的最长子数组长度思路：前缀和+哈希表。哈希表存的是key是前缀和，value是出现的位置。但这个位置必须是最早出现的，而且必须预先插入一条 0 ,-1表示0一开始就是。然后，依次遍历数组计算前缀和，用当前的前缀和减去k的值去哈希表里面查找，当前位置减去对应的位置就是以当前位置结尾的最长子数组长度。遍历求最大即可。 12345678910111213141516 public static int compute() { map.clear(); // 重要 : 0这个前缀和，一个数字也没有的时候，就存在了 map.put(0, -1); int ans = 0; for (int i = 0, sum = 0; i < n; i++) { sum += arr[i]; if (map.containsKey(sum - aim)) { ans = Math.max(ans, i - map.get(sum - aim)); } if (!map.containsKey(sum)) &...
Raft与Paxos
[深度对比] 分布式共识的双雄：Paxos 与 Raft，为何 Raft 成为了工程界的宠儿？在分布式系统的浩瀚宇宙中，“共识（Consensus）” 是最核心的难题之一。如何让一堆可能随时宕机、网络延迟的机器对某个值达成一致？这个问题困扰了计算机科学家几十年。 在这个领域，有两位绝对的主角：一个是理论界的“神” Paxos，另一个是工程界的“救世主” Raft。 很多开发者都知道，现在主流的分布式组件（如 Etcd, Consul, TiKV, Kafka的新版本）大多选择了 Raft。那么，Paxos 到底输在哪里？Raft 又为何如此容易实现？本文将带你深入剖析两者的区别与优劣。 一、 核心设计哲学的差异要理解它们的区别，首先要看它们诞生的初衷： Paxos (Leslie Lamport, 1990)：旨在发现共识问题的数学规律。它从数学角度证明了在分布式系统中达成一致的充要条件。它追求的是理论的完备性和一般性。 Raft (Diego Ongaro & John Ousterhout, 2013)：旨在提供一个可理解（Understandable）且易于实现...
算法（五） 前缀树
前缀树结构Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。 前缀树的基本操作 插入字符串：从根节点开始，依次插入字符串的每个字符。如果路径不存在，则创建新节点。最后一个节点标记为字符串的结束。 删除字符串：从根节点开始，依次减少路径上节点的计数。如果某节点的计数为零，则删除该节点。 查询字符串出现次数：沿路径遍历字符串，若路径完整且结束节点存在，则返回字符串的计数。 查询前缀数量：沿路径遍历前缀，若路径完整，则返回最后节点的通过计数。 节点的结构1234567891011 class TrieNode { public int pass; public int end; public TrieNode[] nexts; public TrieNode() { pass = 0; end = 0; nexts = new TrieNode[...
CAP中的一致性
关于CAP这里就不详细说明，本文主要讨论CAP中的 C 即一致性（线性一致性） 首先我们要知道什么是CAP的一致性，他跟事务的一致性有什么区别，跟分布式事务里面所谓的一致性又有什么区别？这是一个非常经典且容易混淆的问题，因为“一致性”（Consistency）这个词在计算机科学的不同领域里，虽然名字一样，但含义却大相径庭。 这三个概念分别对应了：单机数据库理论（ACID）、分布式系统理论（CAP） 和 工程实践（分布式事务）。 我们可以用一句话概括它们的区别： ACID 的一致性：关乎数据的“正确性”（符合业务约束）。 CAP 的一致性：关乎数据的“新旧”（多副本同步）。 分布式事务的一致性：关乎跨系统的“协调”（让多个独立系统的数据最终对齐）。 1. 事务的一致性 (ACID 中的 C)这里的背景通常指单机数据库（如 MySQL）的本地事务。 定义：指事务执行前后，数据库必须从一个合法状态变换到另一个合法状态。 核心关注点：业务逻辑与约束 (Business Logic & Constraints)。 详细解释：“合法状态”是指数据必须符合预定义的规则。这些规则...
算法（四）递归
递归相关的题目找一个字符串的不重复的子序列递归的思路：每次按要这个位置的字符和不要这个位置的字符两种情况去递归，当i = s.length()时，保存当前的子序列。用hashSet去重 123456789101112131415161718192021222324 public static String[] generatePermutation(String str) { char[] s = str.toCharArray(); HashSet<String> set = new HashSet<>(); f2(s, 0, new char[s.length], 0, set); int m = set.size(); String[] ans = new String[m]; int i = 0; for (String cur : set) { ans[i++] = cur; } return ans;} // i是当前要处理的字符的索引,path是当前已经保存的路径，size是path的索引pu...
算法总结（四）二叉树
二叉树相关的题目层序遍历思路：利用队列进行层序遍历，类似与BFS。 这里举一个锯齿形层序遍历的例子（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行） 123456789101112131415161718192021222324252627282930313233343536373839 public static int MAXN = 2001;public static TreeNode[] queue = new TreeNode[MAXN];public static int l, r; public static List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); if (root != null) { l = r = 0; queue[r++] = root; // false 代表从左往右 // true ...
DDD领域事件的最佳实践
DDD 实战：关于领域事件（Domain Events）的设计抉择与工程落地思考在领域驱动设计（DDD）的战术落地过程中，领域事件（Domain Event） 是连接各个子域、聚合以及限界上下文的“胶水”。它不仅解耦了复杂的业务逻辑，更是实现“最终一致性”架构的关键手段。 本文基于实际开发经验，总结领域事件的建模、生成、发布及可靠性投递的最佳实践，并探讨不同方案背后的权衡。 一、 什么是领域事件？简单来说，领域事件是聚合内已发生的业务事实。 业务事实：意味着它是过去式。比如“用户已注册”、“订单已支付”。 命名规范：推荐使用 动词过去式（如 OrderPaid, AccountActivated）。 价值： 解耦：核心业务逻辑不需要知道谁在关注它。 副作用处理：触发通知、大数据分析、报表生成等非核心逻辑。 数据一致性：跨聚合、跨服务的状态同步。 二、 建模：胖消息 vs 瘦消息领域事件通常被建模为不可变的值对象（Value Object）。但在设计消息体（Payload）时，我们面临一个经典抉择： 1. 瘦消息（Id-Only）消息体仅包含最基础的元数据：123456...
算法总结（三) 链表
链表相关的题目这里用来记录链表相关的题目以及思路 相交链表输入两个链表，找出它们的第一个公共结点。12345678910111213141516public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { /** 定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差) 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度 **/ if(headA == null || headB == null) return null; ListNode pA = headA, pB = headB; // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null ...