算法-字符串全部子序列

2022-4-21 diaba 算法

package com.jiucaiyuan.net.question; import java.util.ArrayList; import java.util.List; /** * 【问题】打印一个字符串的全部子序列,包含空字符串 * 【思路】从第一个字符开始,逐个字符进行处理,每个字符都可以选择要还是不要,分两条路递归 * * @Author jiucaiyuan 2022/4/20 23:57 * @mail services@jiucaiyuan.net */ public class PrintAllSubSequence { ...

阅读全文>>

评论(0) 浏览(562)

算法-N皇后问题(含加速版本)

2022-4-20 diaba 算法

package com.jiucaiyuan.net.question; /** * 【问题】N皇后问题,指的是n*n的棋盘,可以放n个皇后,要求任何两个皇后不同行、不同列,也不在同一条斜线上 * 给出一个整数n,返回n皇后的摆法有多少种 * 给n=1,返回1 * n=2或者3,2皇后和3皇后,无论怎么摆放都不行,返回0 * n=8,返回92 * 【思路】按照行往下摆放,然后一列一列尝试(加速版本会使用按照位操作来加速器处理,但是整体上也是所有都尝试一遍) * 时间复杂度O(N^N) * * @Author jiucaiyuan 2022/4/19 ...

阅读全文>>

评论(0) 浏览(560)

算法-贪心-做项目获得最大收益

2022-4-18 diaba 算法

package com.jiucaiyuan.net.question; import java.util.Comparator; import java.util.PriorityQueue; /** * 【问题】做一个项目,有成本,也有利润,一堆项目,如何选择做,实现收益最大? * 【思路】把所有项目,按照成本放入小根堆,从小根堆中拿出可以做的项目,然后按照利润放入大跟堆,开始先做大根堆的对顶项目 * * @Author jiucaiyuan 2022/4/18 23:10 * @mail services@jiucaiyuan.net */ pu...

阅读全文>>

评论(0) 浏览(582)

算法-贪心-会议安排问题

2022-4-18 diaba 算法

package com.jiucaiyuan.net.question; import java.util.Arrays; import java.util.Comparator; /** * <pre> * 贪心算法 * 在某一个标准下,优先考虑最满足标准的样本,最后考虑最不满足标准的样本, * 最终得到一个答案的算法,叫做贪心算法 * 也就是说,不从整体最优上加以考虑,所做出的是在某种意义上的局部最优解 * * 实例题:会议问题 * 问题内容:一些项目要占用会议室宣讲,会议室不能同时容纳两个项目同时宣讲。 * 给你每个项...

阅读全文>>

评论(0) 浏览(643)

算法-贪心-成本最小切金条

2022-4-18 diaba 算法

package com.jiucaiyuan.net.question; import java.util.PriorityQueue; /** * 【问题】一个金条切成两半,需要花费和长度一样的铜板。比如:长度为20的金条,不管切成多大的两块,都需要花费20个铜板 * 一群人想整分整块金条,怎么分最省钱? * 例如:给定一个数组[10,20,30],代表一共三个人,整块金条长度为10+20+30=60. * 金条要分成10、20、30三个部分,如果先把长度为60的金条分成10和50,花费60,再把 * 长度为50的分成20和30,花费50,一共花费110个铜板...

阅读全文>>

评论(0) 浏览(617)

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

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) 浏览(538)

算法-前缀树(单词查找树)

2022-4-15 diaba 算法

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

阅读全文>>

评论(0) 浏览(649)

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

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) 浏览(671)

图-最短路径-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) 浏览(625)

图-最小生成树-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) 浏览(622)

图-最小生成树-Kruskal算法

2022-4-14 diaba 算法

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

阅读全文>>

评论(0) 浏览(602)

算法-图-深度优先遍历

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) 浏览(628)

算法-图-宽度优先遍历

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) 浏览(500)

算法-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) 浏览(619)

算法-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) 浏览(544)

算法-二叉树-折纸问题

2022-4-11 diaba 笔试题

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

阅读全文>>

评论(0) 浏览(658)

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

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) 浏览(563)

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

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) 浏览(585)

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

2022-4-10 diaba 笔试题

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

阅读全文>>

评论(0) 浏览(632)

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

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) 浏览(1352)

Powered by emlog 京ICP备15045175号-1 Copyright © 2022