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); } 运行结果：
题目描述 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。 进阶： 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题? 示例 1： 输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。 示例 2： 输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。 示例 3： 输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。 示例 4： 输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出....
题目描述 颠倒给定的 32 位无符号整数的二进制位。 示例 1： 输入: 00000010100101000001111010011100 输出: 00111001011110000010100101000000 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。 示例 2： 输入：11111111111111111111111111111101 输出：10111111111111111111111111111111 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。 解法 JDK实现 public int reverseBits(int n) { return Inte....
题目描述 给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。 如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。 示例 1： 输入：arr = [1,2,2,1,1,3] 输出：true 解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。 示例 2： 输入：arr = [1,2] 输出：false 示例 3： 输入：arr = [-3,0,1,-3,1,1,1,-3,10,0] 输出：true 解法 使用哈希表解决，第一遍存储每个数字出现的次数，第二遍存储用set存储出现的次数，如果set插入重复，即不是独一无二的出现次数 public boolean uniqueOccurrences(int[] arr) { Map<Integer, Integer> arrCountMap = new HashMap<>(); for(int i = 0; i < arr.length; i++) { arrCountMap.put(ar....
题目描述 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2 解法 摩尔投票法 思路： 候选人(cand_num)初始化为nums[0]，票数count初始化为1。 当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。 当票数count为0时，更换候选人，并将票数count重置为1。 遍历完数组后，cand_num即为最终答案。 go代码如下： func majorityElement(nums []int) int { /** * 摩尔投票法 */ var count = 1 var base = nums[0] for i:=1; i<len(nums); i++ { if base == nums[i] { count += 1 ....
题目 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4 解法 1.哈希表 这种方式大家都能想到，比较简单。不过需要额外的空间复杂度，就不写代码了。 2.位运算-异或 异或的逻辑是相同为0， 不同为1，相同两个数经过两次异或运算都是0. go代码如下： func singleNumber(nums []int) int { result := 0 for _, v := range nums { result ^= v } return result } 运行结果如下：
题目描述 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。 更正式地说，root.val = min(root.left.val, root.right.val) 总成立。 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。 示例 1： 输入：root = [2,2,5,null,null,5,7] 输出：5 解释：最小的值是 2 ，第二小的值是 5 。 示例 2： 输入：root = [2,2,2] 输出：-1 解释：最小的值是 2, 但是不存在第二小的值。 提示： 树中节点数目在范围 [1, 25] 内 1 <= Node.val <= 231 - 1 对于树中每个节点 root.val == min(root.left.val, root.right.val) 解法 递归的解法，go代码如下： func findSecondMinimumValue(ro....
题目描述 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。 说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。 示例 1: 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1 示例 2: 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 3 解法 中序遍历 因为是二叉搜索树，树的结构是有序的。通过中序遍历可以得到一个有序数组，求第k个元素即可。 public int kthSmallest(TreeNode root, int k) { List<Integer> result = new ArrayList<>(); inOrder(root, result); return result.get(k-1); } public void inOrder(TreeNode node, List<Int....
题目描述 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 示例 1： 输入：[1,2,3] 1 / \ 2 3 输出：6 示例 2： 输入：[-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 输出：42 解法-递归 private int ret = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { /** 对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况: 1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径 2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径 **/ getMax(root); return ret;....
题目描述 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A: 3 / \ 4 5 / \ 1 2 给定的树 B： 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。 示例 1： 输入：A = [1,2,3], B = [3,1] 输出：false 示例 2： 输入：A = [3,4,5,1,2], B = [4,1] 输出：true 限制： 0 <= 节点个数 <= 10000 解法 利用递归的思想解决。用A的根节点、左节点、右节点依次尝试是否等B的根节点，如果是则尝试对比下一个节点 go代码如下： func isSubStructure(A *TreeNode, B *TreeNode) bool { if A == ni....
题目 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入： 4 / \ 2 7 / \ / \ 1 3 6 9 镜像输出： 4 / \ 7 2 / \ / \ 9 6 3 1 解法-递归 go代码实现如下： func mirrorTree(root *TreeNode) *TreeNode { if root == nil { return root; } var node = mirrorTree(root.Left) root.Left = mirrorTree(root.Right) root.Right = node return root } 解法-非递归（栈） 辅助栈（或队列） 利用栈（或队列）遍历树的....