题目描述 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。 示例： 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"ne....
题目 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 解法 可以将二叉树的直径转换为：二叉树的 每个节点的左右子树的高度和 的最大值。 go代码实现如下： var ans int = 0 func diameterOfBinaryTree(root *TreeNode) int { ans = 0 depth(root) return ans } func depth(node *TreeNode) int { if node == nil { return 0 } var leftDepth, rightDepth = depth(node.Left), depth(node.Right) ans = max(leftDepth + rightDepth, ans) return 1 + max(leftDepth, rightDep....
题目 给定一个二叉树，原地将它展开为一个单链表。 例如，给定二叉树 1 / \ 2 5 / \ \ 3 4 6 将其展开为： 1 \ 2 \ 3 \ 4 \ 5 \ 6 解法-递归 题目要求原地展开，故不能使用数组类变量存储全部节点值再重构树。将左右子树分别递归展开，将原左子树变为节点的右子树，再将原右子树变为当前右子树最右节点的右子树。 go代码实现 func flatten(root *TreeNode) { if root == nil { return } flat(root) } func flat(node *TreeNode) { if node == nil { return } flat(node.Left) flat(node.Right) var temp *TreeNode = node.Right node.Right, node.Left = node.Left, nil for node.Right != nil { node = node.Right } node.Right = temp } 或者简化一下代码： func flatte....
题目 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 解法 因为左右高度不能大于1，所以可以找个中间节点，保证二叉树的平衡性。找到中间节点作为根节点，然后用递归遍历。另外需要注意的是，求中点不要用 int mid = (begin + end)/2，有溢出风险，稳妥的方法是 int mid = begin + (end-begin)/2。 go代码实现： func sortedArrayToBST(nums []int) *TreeNode { return bst(nums, 0, len(nums)-1) } func bst(nums []int, begin int, end int) *TreeNode { if begin > end { return ni....
题目描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7 解法-递归 通过前序遍历的第一个节点可知道root节点，然后利用中序遍历，可以根据root节点把树划分为两个子树，然后递归解决 java代码实现： public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length==0||inorder.length==0){ return null; } TreeNode root=new TreeNode (preorder[0]); for(int i=0;i<preorder.length;i++){ if(preorder[0]==inorder[i]){ // 针对preOrder 左子树子序列（1，i+1） root.left=buildTree(Arr....
题目描述 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如： 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回锯齿形层次遍历如下： [ [3], [20,9], [15,7] ] 解法1-DFS 根据DFS遍历，奇数层按倒序插入。 Java代码如下： public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); zLevelOrder(root, result, 0); return result; } public void zLevelOrder(TreeNode node, List<List<Integer>> result, int level) { if (node == null) { re....
题目 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 解法-动态规划 假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则 G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n) 当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则 f(i) = G(i-1)*G(n-i)f(i)=G(i−1)∗G(n−i) 综合两个公式可以得到 卡特兰数 公式 G(n) = G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0)G(n)=G(0)∗G(n−1)+G(1)∗G(n−2)+...+G(n−1)∗G(0) Java实现 class Solution { public int numTrees(int n) ....
题目 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 输入: 2 / \ 1 3 输出: true 示例 2: 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。 解法 比较巧妙的写法：go实现，maxInt64是因为测试用例有int64的值 package main func isValidBST(root *TreeNode) bool { return validate(root, math.MinInt64, math.MaxInt64) } func validate(node *TreeNode, min int, max int) bool { if node == nil { return true } if node....
BFS（广度优先搜索）Java public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root != null) { queue.add(root); } while(!queue.isEmpty()) { int n = queue.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i<n; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { qu....
今天，我们先来学习一下贪心算法（greedy algorithm）。贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim和Kruskal最小生成树算法、还有Dijkstra单源最短路径算法。 1.买卖股票的最佳时机 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所....
3.编写整洁的代码 是否是整洁的代码，需要遵循一定的方法论，不能靠个人主观的感觉判断。推荐大家看完《代码整洁之道》这本书，遵循这里的原则。 列出一些必须要遵循的原则： 命名 做有意义的区分 区分名称，要使用读者能清洗鉴别出不同之处的方式。禁止类似customerInfo/customer、 user/userInfo、 money/moneyAmount 这种没有区分度的命名 使用可搜索的名称 例：WORK_DAYS_PER_WEEK 很容易搜索，但是数字5就无法搜索了 类名 类名和对象名应该是名词或名词短语。类名不应当是动词。正例：Customer、AddressParser；反例：Manager、Processor、Data 方法名 方法名应当是动词或者动词短语。比如：deletePage/save等 添加有意义的语境 很少有名称能自我说明，你需要良好命名的类、函数和名称空间来放置名称，给读者提供语境。如果没这么做，需要给名称添加前缀。 比如在缺少上下文的情况下，firstName、lastName、street就需要添加前缀addrFirstName、addrLastName、a....
一、数据库中间件设计思路 1.1.背景 最开始学习jdbc的时候，直接通过jdbc就能访问DB。但是这时候缺少了数据源、缺少了ORM框架，不能在生产环境使用，在后期更换DB类型时也存在很大问题。 所以出现了ORM框架。在未进行读写分离/分库分表的情况下，我们是直接在应用中通过数据源(c3p0、druid、dbcp2等)与数据库建立连接，进行读写操作，架构如下所示： ORM框架作用： 隐藏了对象的访问细节 ORM使我们构造固化数据结构变得简单易行 可以看到在操作单库单表的情况下，我们是直接在应用中通过数据源(c3p0、druid、dbcp等)与数据库建立连接，进行读写操作。 随着互联网的发展，数据规模越来越大，分库分表、读写分离成了通用的解决方案。 大部分开发人员对于访问单库的应用的架构都是很熟悉的。但是在进行读写分离/分库分表后，底层的数据库实例就会有多个，读写分离情况下一个master多个slave；分库分表的情况下，有多个不同的分库。 从应用的角度来说，除了要与多个不同的数据库建立连接，还需要处理分库分表/读写分离特定场景下的问题： 在读写分离的情况下，应用需要对读sql/写sql....
对象之间的关系就体现为类之间的关系。类之间存在不同的关系，依赖的强弱也各有不同，从强至弱依次为： 继承关系 → 组合关系 → 协作关系 继承关系 继承关系体现了“泛化-特化”的关系，父类提供更加通用的特征，子类在继承了父类的特征之外，提供了符合自身特性的特殊实现。继承关系在 UML 中使用空心三角形加实线的方式来代表子类继承父类，例如矩形类继承自形状类： 继承会导致子类与父类之间形成一种强耦合关系，父类发生任何变更，都会体现到子类中，形成所谓的“脆弱的基（父）类”。由于继承代表了一种“is”的关系，在领域建模时，父类和子类代表的其实是同一个领域概念的不同层次。 组合关系 组合关系体现了类实例之间整体与部分之间的关系，体现了“has”的概念，即一个类实例“包含了”另一个或多个类实例。组合关系体现了类概念之间的一对一、一对多和多对多关系。依据关系的强弱，组合关系又分别分为“合成（Composition）”关系与“聚合（Aggregation）”关系。前者的关系更强，例如计算机和 CPU 之间就是合成关系，因为离开了 CPU，计算机就不能正常运行；后者的关系较弱，例如计算机和键盘之间就是聚合....
一、分表键的选择 分表键即**分库/分表字段，zebra里面叫做维度，**是在水平拆分过程中用于生成拆分规则的数据表字段。Zebra 根据分表键的值将数据表水平拆分到每个物理分库中。 **拆分主要原则：**需要找到数据库表中的数据在业务逻辑上的主体，并确定大部分或者核心的数据库操作都围绕着这个主体的数据进行。可以使用该主体对应的字段作为分表键，进行分库分表。 业务逻辑上的主体，通常与业务的应用场景相关，下面的一些典型应用场景都有明确的业务逻辑主体，可用于分表键： 面向用户的互联网应用，都是围绕用户维度来做各种操作，那么业务逻辑主体就是用户，可使用用户对应的字段作为分表键； 侧重于卖家的电商应用，都是围绕卖家维度来进行各种操作，那么业务逻辑主体就是卖家，可使用卖家对应的字段作为分表键； **注意：**无论选择什么拆分键，采用何种拆分策略，都要注意拆分值是否存在热点的问题，尽量规避热点数据来选择拆分键。 1.1.多个分表键如何处理 名词解释： **主维度：**主分表键，在主维度上，数据能够增删改查； 辅维度：辅助分表键，在辅助维度上，只能进行数据查询 大部分场景下，一张表的查询条件比较单一....
一、常用命令 内存分析常用命令： // 打印每个class的实例数目,内存占用,类全名信息.live子参数加上后,只统计活的对象数量. 此时会触发FullGC jmap -histo:live <pid> > filename | head -10 // dump 内存 jmap -dump:live,format=b,file=/opt/logs/dump.hprof <pid> // 查看堆栈使用情况 jmap -head pid // 垃圾回收统计概述 jstat -gc <pid> <time> // 垃圾回收统计概述，使用空间占总空间的百分比 jstat -gcutil <pid> <time> // 用于生成java虚拟机当前时刻的线程快照 jstack <pid> 二、问题描述 我们系统中存在一个定时任务，每次执行任务时都会触发full gc，稳定复现。是一个报表计算的任务，会把原始表的数据经过加工整理汇总到指标表，涉及数据大批量插入的情况 三、排查过程 排查思路是：发生fullg....
输入top命令之后： 总共有这些指标： 每个字段具体什么意思呢？ 名称英文解释说明备注 PIDProcess Id进程IDx USERUser Name优先级 PRPriority？ NINice value虚拟镜像 VIRTVirtual Image RESResident size SHRShared Mem size SProcess Status %CPU %MEM TIME+ COMMAND
1.使用top命令查询Java进程 代码块 SQL top 定位到java进程为369 2.通过top命令定位进程包含的线程信息 代码块 SQL top -H -p 369 -d 1 -n3 查询到线程占用率最高的线程PID 为672 3.通过jstack命令查询线程堆栈 jstack 下的NID为16进制，672对应的16进制为223 代码块 SQL jstack -l 369|grep -A 20 "223" 结果内容为： 至此，可以根据代码去定位问题
1、日志中心架构图： 2、日志接入流程 第一步需要配置Category生产日志，首次生产日志，会根据Category在kafka中创建topic，日志生产完在kafka中验证
结构型 1.用例图 用例图参考： 建立用例模型首先要确定角色(Actors)，Actors表示提供或接收系统信息的人或系统，他们是与系统有交互作用的人或事务，代表一个系统的使用者或外部通信的目标。用例是系统中的一个功能单元，可以被描述为参与系统之间的一次交互作用。用例模型的用途是列出系统中的用例和参与者，并且显示哪个是用例的执行。 2.组件图（构件图） 是用来反映代码的物理结构。从组件图中，您可以了解各软件组件（如源代码文件或动态链接库）之间的编译器和运行时依赖关系。使用组件图可以将系统划分为内聚组件并显示代码自身的结构。 3.部署图 也叫做实施图，描述的是系统运行时的结构，展示了硬件的配置及其软件如何部署到网络结构中。可以了解软件和硬件的物理关系以及处理节点的组件分布情况，传达了构成应用程序的硬件和软件元素的配置和部署方式。一个部署图描述了一个运行时的硬件节点，以及在这些节点上运行的软件组件的静态视图。 4.类图 类图通过显示系统的类和它们之间的关系来概述系统。类图是静态的 - 它们显示出什么交互，但不会发生什么交互。 那么属性/方法名称前加的加号和减号是什么意思呢？它们表示了这个属....