xhj的博客

二叉树结点间的最大距离问题 递归 改进的写法 完整测试代码 题目 递归解析这个也是一个二叉树的问题，分为三步: 列出所有可能性； 列出结点需要的信息，并整合信息(成一个结构体)； 改递归 ，先假设左和右都给我信息(黑盒)，然后怎么利用左边和右边的信息组出来我该返回的信息，最后basecase(边界)填什么； 具体到这个题目:第一步，列出可能性： 一个以node为头的树上，最大距离只可能来自下面三种情况: 不需要经过node这个点，node的左子树上自己的最大距离； 不需要经过node这个点，node的右子树上自己的最大距离； 要经过node这个点，此时就是左子树的高度 + 右子树的高度 + 1 ； 第二步，确定结点需要的信息，并整合: 信息一: 返回的以node为头的树的最大距离； 信息二: 返回的以node为头的高度； 第三步，封装信息，写出递归 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ...

二叉树的各种操作(递归和非递归遍历,树深度,结点个数等等) 建立二叉树 1、根据下标关系 2、前序输入(cin)建立 前序遍历 1、递归前序 2、非递归前序 中序遍历 1、递归中序 2、非递归中序 后序遍历 1、递归后序 2、非递归后序 层次遍历 寻找树中有没有值为x的结点 统计树中结点的个数 计算树的高度 判断两颗树是不是相等 完整测试代码 二叉树建立先给出结点结构: 1 2 3 4 5 6 7 8 9 static class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; } } 两种建立方式: 可以根据二叉树根节点和左右子结点的下标关系递归建立二叉树，层次输入二叉树结点； 也可以使用输入流前序建立二叉树(注意空树要输入-1)； 1、根据下标关系 1 2 3 4 5 6 7 8 9 ```...

子数组累加和为aim(小于等于aim)的三个问题 累加和 = aim的最长子数组的长度(数组可+,-,0)； 累加和 = aim的最长子数组的长度(数组+)(只有正数)； 累加和 <= aim的最长子数组的长度(数组可+,-,0)； 累加和 = aim的最长子数组的长度(数组可+,-,0)；这个题目使用HashMap来存储前面出现过的累加和的下标，具体过程如下: 使用变量sum表示从0位置开始一直加到i位置所有元素的累加和； HashMap中key表示从arr最左边开始累加过程中出现过的sum值，value表示的是sum值出现最早的位置；、 假设当前元素为arr[i]，则sum += arr[i]，之前所有累加和为sum ，查看map中是否有sum - aim这个值，如果有，且对应value为j，那么就找到一个子数组累加和为aim的，且长度为 i - j + 1； 检查现在的sum 是否在map中出现，如果不存在，说明此时是第一次出现的，把(sum,i)加入到map中； 继续遍历数组； 很重要的一个地方就是一开始map中要存(0,-1)这个值，直观理解是一个数也没有...

矩阵相关操作和矩阵快速幂 矩阵基本运算以及快速幂模板 POJ - 3070. Fibonacci Hdu - 1757A. Simple Math Problem Codeforces - 185A. Plant 矩阵基本运算以及快速幂模板先看一下矩阵的乘法规则: 直接给出一个模板题，直接包含了基本的乘法和求幂，求幂的详细解释，可以看这篇乘法快速幂。题目来源: XYNU OJ题目 注意: 矩阵的乘法必须满足第一个矩阵的列 = 第二个矩阵的行； 矩阵的求幂必须满足矩阵是一个方阵； 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 ...

乘法快速幂相关总结 & LeetCode - 50. Pow(x, n) 递归计算 (a n) % mod 非递归计算 (a n) % mod 计算 ( a * b ) % mod 配合 ( a * b ) % mod和乘法快速幂 XYNUOJ - 1872. 次方求模题解 LeetCode - 50. Pow(x, n)题解 递归计算 (a n) % mod递归计算其实是更容易理解的: 为了求an，我们先递归去求出an/2，得到结果记录为halfRes； 然后如果n为偶数，很好办，再乘以一个halfRes就可以了(再取模一下)，也就是可以返回halfRes*halfRes； 但是如果n为奇数的话，就需要再乘以一个a，然后再返回； 代码: 1 2 3 4 5 6 7 8 9 10 11 12 static long pow_mod(long a, long n, long mod) { if (n == 0) // a^0 = 1 return 1; // 先求一半的 --> 你先给我求出...

素数回文以及素数相关总结 普通筛素数法 埃式筛法 优化筛法 整数分解(唯一分解定理) 约数枚举 Hdu - 1431. 素数回文 普通筛素数法这个也是普通的素数判定的方法，这个方法判定素数时间复杂度为O (sqrt(n))。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 static ArrayList<Integer> sieve(boolean[] is_prime, int MAX) { ArrayList<Integer> prime = new ArrayList<>(); is_prime[0] = is_prime[1] = false; // 01 不是素数 boolean flag; for (int i = 2; i <= MAX; i++) { flag = true; for (int j = 2; j * j <= i; j++) {// 根号i的时间复杂度 ...

最小生成树模板题(Kruskal算法和Prim算法实现) Kruskal算法思想及流程 Prim算法思想及流程: 题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1863 题目 题意就是一个求最小生成树的模板题(一般是无向图)。 Kruskal算法思想及流程 首先各个顶点看成一个集合，每个顶点的根就是自己； 从整个图中边的集合中取出最小的一条(一开始对边的集合排序)，判断该边的两个定点是不是同一个集合，如果不是，合并两个集合； 如果是同一个集合，舍弃，继续取下一条边； 直到集合中有n - 1条边为止； 时间复杂度为为O(e2), 使用并查集优化后复杂度为 O（eloge），与网中的边数有关，适用于求边稀疏的网的最小生成树 推荐写法 建图和上面稍有不同，kruskal的特性只需要用到Edge这个类即可，对边集排序然后不断合并两个顶点即可； 这里并查集使用的数组，和上面有点不同，但是原理都是一样的； 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2...

## 最短路dijkstra模板 dijkstra算法总结 常用模板解决 其他写法 题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1874 题目 dijkstra算法总结总结一下dijkstra算法大致的流程: 一开始有一个dist[]数组(也可以是map)来保存从start(起点)到每个点的最短路径(一开始的话，如果start和某个点没有边，就为INF(或者为null)，如果有连线的话就是边的权值)； 然后每次从dist数组中取出一个dist[i]最小的i(不能取已经用过的顶点(vis数组标记))，也就是start距离某个结点最近的一个； 取出这个结点之后，用这个结点更新和它相连的边的dist数组； 直到把所有的dist数组都更新一遍； 注意: dijkstra为什么不能有负权边? 因为如果有的话，我们找最小的那个结构的时候，没准它还能通过松弛变得更短，例如上面我们一开始选出0~2这条边的时候，试想如果2~1的那条边权值为-4，那一开始我们找的0~2这条边就是错的，所以不能有负权边。 常用模板解决推荐的写法 ...

Ordering Tasks | LeetCode - 207. Course Schedule (拓扑排序) Uva - 10305. Ordering Tasks LeetCode - 207. Course Schedule Uva - 10305. Ordering Tasks题目链接 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1246 题意 给你n、m，n代表点的个数，m代表边的条数，然后下面给出m条边，都是有向的(有向图)，要你建出一个图，并且找出一种序列，这种序列即拓扑序列 。 拓扑排序 是对有向无环图（DAG)进行的一种操作，这种操作是将DAG中的所有顶点排成一个线性序列，使得图中的任意一对顶点u,v满足如下条件：若边(u,v) ∈ E(G)，则u在最终的线性序列中出现在v的前面;拓扑排序的应用常常和AOV网相联系，在一个大型的工程中，某些项目不是独立于其他项目的，这意味着这种非独立的...

Instrction Arrangement以及关键路径详解 关键路径详解 Hdu4109-Instrction Arrangement题解 关键路径详解AOE网概念: 在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE(Activity On Edge)网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。 如下图的 V...表示事件，a...表示活动。 对比AOV (Activity On Vertex Network)网: 用顶点表示活动，用弧表示活动间的优先关系的有向图。 AOE网可用来估算工程的完成时间，对于AOE网，有两个关键的问题: ① 完成整个工程至少需要多少时间？ ② 哪些活动是影响工程进度的关键？（或者说，为缩短完成工程所需要的时间，应该加快哪些活动 ?） 性质: 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始； 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。 关键路径 在AOE网中，从始点到终...