题目 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 解法-滑动窗口 什么是滑动窗口？ 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！ 如何移动？ 我们只要把队列的左边的元素移出就行了，直到满足题目要求！ 一直维持这样的队列，找出队列出现最长的长度时候，求出解！ 时间复杂度：O(n) public int lengthOfLongestSubstrin....
题目描述 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 进阶： 你是否可以使用 O(1) 空间解决此题？ 解法： 1.哈希表 遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环 2.双指针 代码： public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { fast = head; while(fast != slow) ....
题目描述 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 解法： 1. 递归解法： int cur = 0; public ListNode removeNthFromEnd(ListNode head, int n) { if (head == null) { return null; } head.next = removeNthFromEnd(head.next, n); cur++; if(n == cur) { return head.next; } return head; } 运行结果： 2. 快慢指针 利用快慢指针，快指针先走n不，然后快慢指针一起走，当快指针到链表尾部时，slow刚好到n-1的位置。删除slow.next 即可 public ListNode removeNthFromEnd(ListNode head, int n) { if (he....
题目描述： 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 解法： 两个链表顺序遍历，对应两个节点的值相加作为新链表的值，如果产生进位，需要加到下一位。 sumVal / 10 等于1就是产生了进位，为0则没有进位 sumVal % 10则是新节点的值 构造root空节点，作为新链表的头节点（最终返回root.next节点） 构造游标节点的作用 ？ 为了标记处理新节点的当前位置 为什么不复用root节点新建了游标节点？这样做最终返回新节点时找不到头节点 Java代码如下： public ListNode addTwoNumbers(List....
题目描述： 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 解法： 利用归并排序，从中间节点断开，分别排序，排序时利用递归。再合并排序结果。 public ListNode sortList(ListNode head) { // 1、递归结束条件 if (head == null || head.next == null) { return head; } // 2、找到链表中间节点并断开链表 & 递归下探 ListNode midNode = middleNode(head); ListNode rightHead = midNode.next; midNode.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); // 3、当前层业务操作（合并有序链表） return mergeTwoList....
题目描述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 解法： 先遍历数据，把不为空的数字移动到数组前面，记录下不为空的个数j，大于j小于nums.length 的位置都填充为零 public void moveZeroes(int[] nums) { int j = 0; int length = nums.length; for(int i = 0; i < length; i++) { if (nums[i] != 0) { nums[j++] = nums[i]; } } while(j < length) { nums[j++] = 0; } } 运行结果：
题目描述 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。 解法 public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } 运行结果：
文档 本工程采用DDD的架构风格，经过组内DDD实践的沉淀形成的工程规范 DDD实践的参考文档详见： DDD实践参考文档 工程结构： --client/ |-- src |----|-- main |----|----|-- java |----|----|----|-- com.sankuai.crayfish.xxxx |----|----|----|----|-- service -- thrift服务 |----|----|----|----|-- model -- thrift对象定义 --server/ |-- deploy |-- src |----|-- main |----|----|-- java |----|----|----|-- com.sankuai.crayfish.xxxx |----|----|----|-- application -- 应用层 |----|----|----|----|-- service -- 应用服务 |----|----|----|----|-- factory -- 对象转换工程（非必须） |----|----|----|....
背景 X项目组后端工程都是根据DDD的规范搭建的工程，整体结构上是统一的，但是在实现细节上，每个人习惯不同，代码风格有很大差异，导致工程之间的风格迥异，维护成本变高，因此需要梳理一套组内通用的项目工程规范，通过规范让编码风格统一 目标 建立一套组内通用的工程规范，组内成员达成一致，严格按照规范执行，以达到提供代码可读性、工程可维护性的目的。同时提高协作沟通效率。 调研 领域驱动设计调研 结论：需要根据自己的业务需求，建立适合业务场景的架构模式。没有统一的答案，每个团队在DDD实践上都有自己的理解，并没有统一的标准 1.规范组成 主要有两大部分组成： 开发规范 运维规范 名词解释 规范约束词： 强制： 必须遵守 推荐： 建议的做法，通常情况下是最合理的 参考： 提供一种综合考虑较优的方案 2.DDD工程实践概述 领域驱动-补充资料-分层架构的背景 分为四层： （1）用户界面层（或表示层） （2）应用层 （3）领域层 （4）基础设施层 各层的关联方式： 各层之间是松散连接的 层与层之间的依赖关系只能是单向的 上层可以直接使用或操作下层元素，方法是通过调用下层元素的公共接口，保持对下层元素的....
分层领域模型命名约定 DDD分层领域模型规约： DTO（Data Transfer Object ）：Thrift/pigeon 接口定义对象命名方式，命名方式XxxDTO DO（Data Object）：持久层对象命名方式。命名方式XxxDO Entity（实体）：代表一个领域实体。命名方式XxxEntity ValueObject（值对象）：代表一个领域值对象。命名方式XxxValue 应用层 1.【强制】禁止在应用层写任何领域逻辑，仅负责协调领域模型对象，通过它们的领域能力来组合完成一个完整的应用目标 2.【强制】与横切关注点相关的内容应该放在应用层 3.【强制】thrift接口参数校验属于横切关注点，应该放在应用服务来做 实体 1.【强制】实体对象的命名以Entity结尾。比如UserEntity、CompanyEntity 2.【推荐】Entity<->DO转换建议使用Mapstruct（参考本文【mapstruct对象转换示例】），除非有足够的理由不使用。 3.【推荐】实体尽量使用充血模型。属于实体的行为必须放在实体中，不能放在聚合根中，否则会造成实体贫血 4.....
1.分层架构的背景 为什么要分层 在软件中，虽然专门用于解决领域问题的那部分通常只占整个软件系统的很小一部分，但其却出乎意料的重要。我们需要将领域对象与系统中的其他功能分离，这样就能避免将领域概念和其他只与软件技术相关的概念搞混了，也不会再纷繁芜杂的系统中完全迷失了领域。 分离领域的复杂技术早已出现，而且都是我们耳熟能详的 软件系统有各种各样的划分方式，但是根据软件行业的经验和惯例，普遍采用LAYERED ARCHITECTURE(分层架构)，特别是有几个层基本上已成了标准层。分层这种隐喻被广泛采用， 大多数开发人员都对其有着直观的认识。许多文献对LAYERED ARCHITECTURE也进行了充分的讨论，有些是以模式的形式给出的。LAYERED ARCHITECTURE的基本原则是层中的任何元素都仅依赖于本层的其他元素或其下层的元素，向上的通信必须通过间接的方式进行。 四层架构的依据 分层的价值在于每一层都只代表程序中的某一特定方面。这种限制使每个方面的设计都更具 内聚性，更容易解释。当然，要分离出内聚设计中最重要的方面，选择恰当的分层方式是至关重要的。在这里，经验和惯例又一次为我们....
题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 解法 迭代解法： public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode current = head; while(current != null) { ListNode next = current.next; current.next = pre; pre = current; current = next; } return pre; } 运行结果： 递归解法 head.next 之下的节点都已经反转好 head.next.next = head 节点 head.next 置为null public ListNode reverseList(ListNode head) { if (head == null || head.next ....
题目描述 编写一个程序，找到两个单链表相交的起始节点。 解法 定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差) 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode nodeA = headA; ListNode nodeB = headB; while(nodeA != nodeB) { nodeA = nodeA == null ? headB : nodeA.next; nodeB = nodeB == null ? headA : nodeB.next; } return nodeA; } 运行结果：
题目描述 给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返回 false 。 解法 经典解法、快慢指针 public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; boolean hasCycle = false; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { hasCycle = true; break; } } return hasCycle; } 运行结果：
题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 解法 递归 解法如下： public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 递归 if (l1 == null) { return l2; } if(l2 == null) { return l1; } if(l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } 运行结果： 迭代 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyHead = new L....
题目 给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。 示例 1: 输入: 16 输出: true 示例 2: 输入: 5 输出: false 解法 位运算、借助 & 和 % 。4的幂次方最高位是1，其他位都是0，且 % 3 值为1 public boolean isPowerOfFour(int num) { return num > 0 && (num & (num - 1)) == 0 && (num % 3 == 1); }
题目描述 给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。 示例 1： 输入：num = 14 输出：6 解释： 步骤 1) 14 是偶数，除以 2 得到 7 。 步骤 2） 7 是奇数，减 1 得到 6 。 步骤 3） 6 是偶数，除以 2 得到 3 。 步骤 4） 3 是奇数，减 1 得到 2 。 步骤 5） 2 是偶数，除以 2 得到 1 。 步骤 6） 1 是奇数，减 1 得到 0 。 示例 2： 输入：num = 8 输出：4 解释： 步骤 1） 8 是偶数，除以 2 得到 4 。 步骤 2） 4 是偶数，除以 2 得到 2 。 步骤 3） 2 是偶数，除以 2 得到 1 。 步骤 4） 1 是奇数，减 1 得到 0 。 示例 3： 输入：num = 123 输出：12 解法 如果是偶数，向左移1位（相当于除以2），如果是奇数，跟1做异或，可以去掉低位的1，变成偶数。记录次数，直到num为0. public int numberOfSteps (int num) ....
题目描述 给定一个整数，编写一个函数来判断它是否是 2 的幂次方。 示例 1: 输入: 1 输出: true 解释: 20 = 1 示例 2: 输入: 16 输出: true 解释: 24 = 16 示例 3: 输入: 218 输出: false 解法 思路：2的n次幂有个特点，最高位为1，其他位都是0。2的n次幂-1 最高位为0，其他位都是1，所以两个数做与运算，如果为0，则是2的n次幂 public boolean isPowerOfTwo(int n) { if (n <= 0) { return false; } return (n & (n - 1)) == 0; } 运行结果：
题目描述 给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。 让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组： A.length >= 3 在 0 < i < A.length - 1 条件下，存在 i 使得： A[0] < A[1] < ... A[i-1] < A[i] A[i] > A[i+1] > ... > A[A.length - 1] 示例 1： 输入：[2,1] 输出：false 示例 2： 输入：[3,5,5] 输出：false 示例 3： 输入：[0,3,2,1] 输出：true 提示： 0 <= A.length <= 10000 0 <= A[i] <= 10000 解法 利用二分的思路。从两头往中间找。判断中间节点是否相同。 if (A.length < 3) { return false; } if(A[0] > A[1])....
题目描述 不使用运算符 + 和 - ，计算两整数 a 、b 之和。 示例 1: 输入: a = 1, b = 2 输出: 3 示例 2: 输入: a = -2, b = 3 输出: 1 解法 无进位加法使用异或运算计算得出 进位结果使用与运算和移位运算计算得出 循环此过程，直到进位为 0 非递归写法 public int missingNumber(int[] nums) { int res = nums.length; for(int i = 0; i < nums.length; i++) { res = res ^ i ^ nums[i]; } return res; } 运行结果： 递归写法： public int getSum(int a, int b) { return b == 0 ? a : getSum(a ^ b, (a & b) << 1); } 运行结果：