随笔记录

算法-贪心-拼接字符得到最小字典序

2022-4-18 diaba 算法

package com.jiucaiyuan.net.question; import java.util.Arrays; import java.util.Comparator; /** * 【问题】一个数组中很多字符串，怎么拼接一起得到字典序最小？ * 【思路】字符串a和b，如果a+b字典序小于b+a，则拼接方法是a+b得到小的字典序 * * @Author jiucaiyuan 2022/4/18 22:49 * @mail services@jiucaiyuan.net */ public class LowestLexicography ...

阅读全文>>

评论(0) 浏览(1432)

算法-前缀树（单词查找树）

2022-4-15 diaba 算法

package code; /** * 前缀树(单词查找树) * 是一种树形结构; 用于保存大量的字符串。 * 优点：利用字符串的公共前缀来节约存储空间。 * 字母放在路径上，节点上存储到该节点的字符数pass以及以该节点为终点的字符数end * * @Author jiucaiyuan 2022/4/15 23:30 * @mail services@jiucaiyuan.net */ public class TrieTree { public static class TrieNode { /** ...

阅读全文>>

评论(0) 浏览(1477)

图-有向无环图拓扑排序算法

2022-4-14 diaba 算法

package com.jiucaiyuan.net.algrithm.graph; import java.util.*; /** * 有向无环图拓扑排序（DAG：Direct Acyclic Graph） * * 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说 * * @Author jiucaiyuan 2022/4/14 22:20 * @mail services@jiucaiyuan.net */ public class TopologySort { /** * directed graph an...

阅读全文>>

评论(0) 浏览(1524)

图-最短路径-Dijkstra算法

2022-4-14 diaba 算法

package com.jiucaiyuan.net.algrithm.graph; import java.util.HashMap; import java.util.HashSet; import java.util.Set; /** * Dijkstra算法 * 适用于：可以有权值为负数的边，但是不能有累加为负数的环的无向图，指定一个出发点，计算到所有节点的最短路径算法 * * @Author jiucaiyuan 2022/4/14 21:36 * @mail services@jiucaiyuan.net */ public clas...

阅读全文>>

评论(0) 浏览(1426)

图-最小生成树-Prim算法

2022-4-14 diaba 算法

package com.jiucaiyuan.net.algrithm.graph; import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; /** * 图的Prim排序算法（p算法） * 适用于：无向图； * 作用：生成最小生成树 * 最小生成树：保障节点连通性的同时权值总合最小 * 思路：解锁最小的边，相邻的节点是解锁的节点，再找相邻的边，从解锁的边中找最小权重的边（这个边两个节点必有不在解锁...

阅读全文>>

评论(0) 浏览(1365)

图-最小生成树-Kruskal算法

2022-4-14 diaba 算法

package com.jiucaiyuan.net.algrithm.graph; import com.jiucaiyuan.net.algrithm.set.UnionFindSet; import java.util.*; /** * 图的Kruskal排序算法（k算法） * 适用于：无向图； * 作用：生成最小生成树 * 最小生成树：保障节点连通性的同时权值总合最小 * 思路：边权值排序，从小到大逐个增加，是否行程环，如果形成环，不要，如果未生成，继续，直到所有的边处理完毕（用到并查集） * 是否形成环判断：这个边链接的两个节点是否在同一个集...

阅读全文>>

评论(0) 浏览(1012)

算法-图-深度优先遍历

2022-4-14 diaba 数据结构

package com.jiucaiyuan.net.algrithm.graph; import java.util.HashSet; import java.util.Stack; /** * 图的深度优先遍历 * * @Author jiucaiyuan 2022/4/14 18:10 * @mail services@jiucaiyuan.net */ public class GraphMaxDepthAccess { /** * 深度优先遍历 * * @param node 从node开始遍历 ...

阅读全文>>

评论(0) 浏览(1265)

算法-图-宽度优先遍历

2022-4-14 diaba 数据结构

package com.jiucaiyuan.net.algrithm.graph; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; /** * 图的广度优先遍历（宽度优先遍历） * * @Author jiucaiyuan 2022/4/14 17:15 * @mail services@jiucaiyuan.net */ public class GraphMaxWidthAccess { /** * 宽度优先遍历（...

阅读全文>>

评论(0) 浏览(1092)

算法-leecode46-全排列

2022-4-14 diaba 算法

package com.jiucaiyuan.net.question; import java.util.ArrayList; import java.util.List; /** * * 46.全排列 * * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 * * @Author jiucaiyuan 2022/4/14 00:00 * @mail services@jiucaiyuan.net */ class FullPermutation { public static L...

阅读全文>>

评论(0) 浏览(963)

算法-leecode164-最大间距

2022-4-13 diaba 算法

package com.jiucaiyuan.net.question; import java.util.Arrays; /** * 给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。 * <p> * 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。 * <p> * 示例1: * <p> * 输入: nums = [3,6,9,1] * 输出: 3 * 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和...

阅读全文>>

评论(0) 浏览(983)

JVM垃圾回收

2022-4-12 diaba JVM

怎么定义垃圾 引用计数法 循环引用问题（循环依赖问题） 可达性分析法 GC Roots 虚拟机栈（栈帧中的本地变量表）中应用的对象 方法区中类静态引用的对象 方法区中常量引用的对象 本地方发展中JNI引用的对象 怎么回收垃圾 标记-清除算法 步骤 ...

阅读全文>>

评论(0) 浏览(1245)

算法-二叉树-折纸问题

2022-4-11 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; /** * <pre> * 【问题】折纸问题 * 【题目】请把一张纸条竖着放在桌子上，然后把纸条从下面向上方对这一次，压出折痕后展开， * 此时折痕是凹下去的，即折痕凸起的方向指向纸条的背面； * 如果从纸条的下方向上连续的折2次，压出折痕后展开，此时有三条折痕， * 从上到下依次是下折痕、下折痕和上折痕；给定一个输入参数n， * 表示纸条都从下边向上连续对着n次，请从上到下打印所有折痕方向。 * 例如：n=1时，打印：down；n=2时，打印：down dow...

阅读全文>>

评论(0) 浏览(1398)

算法-二叉树-序列化&反序列化

2022-4-11 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * 二叉树的序列化与反序列化 * * @Author jiucaiyuan 2022/4/11 22:57 * @mail services@jiucaiyuan.net */ public class SerializeAndDeserializeTree { /** * 先序遍历-序列化...

阅读全文>>

评论(0) 浏览(1186)

算法-二叉树-最低公共祖先

2022-4-11 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; /** * <pre> * 【问题】给定二叉树的两个节点node1和node2，找到他们最低公共祖先 * 【概念】最低公共祖先：两个节点往root节点的链路，第一个相交的节点 * 【思路】 * </pre> * * @Author jiucaiyuan ...

阅读全文>>

评论(0) 浏览(1233)

算法-二叉树-判断满二叉树

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; /** * <pre> * 【问题】判断一棵树是满二叉树(Full Binary Tree) * 【概念】满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。 * 也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1 ，则它就是满二叉树。 * (一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立， * 因为完全二叉树也满足这个要求，但不是满二叉树) * 【思路】获得二叉...

阅读全文>>

评论(0) 浏览(1290)

算法-二叉树-判断完全二叉树

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * <pre> * 【问题】判断一棵树是完全二叉树(Complete Binary Tree) * 【概念】完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部（树只有最后一层可能出现不满，只能是右下角缺少子树） * 【思路】通过二叉树的宽度优先遍历，判断 * >...

阅读全文>>

评论(0) 浏览(1968)

算法-二叉树-判断搜索二叉树

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.Stack; /** * <pre> * 【问题】判断一棵树是否是搜索二叉树（Binary Search Tree），（又：二叉搜索树，二叉排序树） * 【概念】搜索二叉树：树的左子树比头结点小，右子树比头结点大（左子<头<右子） * 【思路】通过二叉树的中序遍历，判断树中节点一直是升序的，不出现降序即可 * </pre> * * @Author jiucaiyuan 2022/4/10 16:42 ...

阅读全文>>

评论(0) 浏览(1172)

算法-二叉树-宽度优先遍历&树宽度

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; /** * 二叉树的宽度优先遍历（求一个二叉树的宽度） * 使用辅助工具队列LinkedList，压入队列，出队时进行访问 * * @Author jiucaiyuan 2022/4/9 23:15 * @mail services@jiucaiyuan.net */ public class TreeMax...

阅读全文>>

评论(0) 浏览(1251)

算法-二叉树遍历

2022-4-9 diaba 数据结构

package com.jiucaiyuan.net.algrithm.tree; import java.util.Stack; /** * 二叉树的遍历（前序、中序、后续遍历）递归+非递归 * * @Author jiucaiyuan 2022/4/9 22:16 * @mail services@jiucaiyuan.net */ public class PreInPostTraversal { /** * 先序遍历-非递归 */ public static void preOrderUnRecur(Nod...

阅读全文>>

评论(0) 浏览(1143)

算法-链表-找两个单项链表首个相交节点

2022-4-9 diaba 算法

package com.jiucaiyuan.net.algrithm.linked; import java.util.HashSet; import java.util.Set; /** * <pre> * 【问题】找到两个单项链表第一个相交节点 * 【解题思路】 * case1：两个无环链表相交 * 把长链表长出来部分先走完，然后两个链表一起走，如果发现两个链表当前节点相同，则该节点即是所找 * case2：两个有环链表相交 * 入环节点是否相同 * 相同：按照两个无环链表的查找思路，以入环节...

阅读全文>>

评论(0) 浏览(1120)