[TOC]
算法名 | 算法描述 |
---|---|
BFS.java | 图的深度遍历 |
DFS.java | 图的广度遍历 |
Dijkstra.java | 单源最短路径算法 |
Floyd.java | 全局最短路径算法-动态规划 |
Kursal.java | 最小生成树算法-从边入手 |
Prim.java | 最小生成树算法-从点入手 |
WarShall.java | 闭包算法-动态规划 |
BackTrack.java | 回溯法(0-1背包问题) |
BestBinarySearchTree.java | 最优二叉查找树(动态规划) |
Bissearch.java | 折半查找 |
MergeSort.java | 合并排序(分治法) |
FastSort.java | 快速排序(分治法) |
HaffuManTree.java | 哈弗曼树及哈弗曼编码 |
代码中使用的图为:
邻接矩阵:
{0,1,1,1,0,0},
{1,0,1,0,1,0},
{1,1,0,1,1,1},
{1,0,1,0,0,1},
{0,1,1,0,0,1},
{0,0,1,1,1,0}
代码中使用的图为:
邻接矩阵:
{0,1,1,1,0,0},
{1,0,1,0,1,0},
{1,1,0,1,1,1},
{1,0,1,0,0,1},
{0,1,1,0,0,1},
{0,0,1,1,1,0}
单源最短路径算法,可求得在一个图中一个点到其余任意节点的最小距离及所经路径。
代码中使用的图为:
邻接矩阵:
{ 0, 6, 1, 5, INF, INF },
{ 6, 0, 5, INF, 3, INF },
{ 1, 5, 0, 5, 6, 4 },
{ 5, INF, 5, 0, INF, 2 },
{ INF, 3, 6, INF, 0, 6 },
{ INF, INF, 4, 2, 6, 0 }
Floyd算法是另一类最短路径算法,和D算法不同的是,Floyd算法所能求得的是全局任意两点之间的最短路径。
在代码中使用的图为:
邻接矩阵:
{ 0, 6, 1, 5, INF, INF },
{ 6, 0, 5, INF, 3, INF },
{ 1, 5, 0, 5, 6, 4 },
{ 5, INF, 5, 0, INF, 2 },
{ INF, 3, 6, INF, 0, 6 },
{ INF, INF, 4, 2, 6, 0 }
Kursal算法为最小生成树算法的一种,其**从边入手,在代码中为检查是否形成环,使用到了压缩路径的并查集。
代码中的图为:
邻接矩阵:
{ 0, 6, 1, 5, INF, INF },
{ 6, 0, 5, INF, 3, INF },
{ 1, 5, 0, 5, 6, 4 },
{ 5, INF, 5, 0, INF, 2 },
{ INF, 3, 6, INF, 0, 6 },
{ INF, INF, 4, 2, 6, 0 }
Prim算法是另一种最小生成树算法,该算法的核心**从边入手,每次加入一个点。在实际操作中,推荐使用该算法(因为不用使用到并查集这种额外的数据结构)。
在代码中使用到的图为:
邻接矩阵:
{ 0, 6, 1, 5, INF, INF },
{ 6, 0, 5, INF, 3, INF },
{ 1, 5, 0, 5, 6, 4 },
{ 5, INF, 5, 0, INF, 2 },
{ INF, 3, 6, INF, 0, 6 },
{ INF, INF, 4, 2, 6, 0 }
WarShall算法为一种传递闭包的算法,可用在游戏开发,检验人物是否能到达某个地点。
在代码中使用到的图为:
邻接矩阵:
{0,1,0,1,0,0},
{1,0,1,0,0,0},
{0,1,0,0,0,0},
{1,0,0,0,1,0},
{0,0,0,1,0,0},
{0,0,0,0,0,0}
回溯算法,是一种非常有用的算法,甚至有“通用解法”的美称。关于回溯算法更多介绍,可看我的博文
在代码中,使用N皇后和0-1背包问题进行说明。
最右二叉查找树:给定一个有序序列K={k1<k2<k3<,……,<kn}和他们被查询的概率P={p1,p2,p3,……,pn},要求构造一棵二叉查找树T,使得查询所有元素的总的代价最小。
二分查找也称为折半查找,是一种高效率的查找算法,不过它要求数组是有序的。
基于分治法的排序算法之一,时间复杂度低。
基于分治法的排序算法之一,时间复杂度低。
给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。常用编码中。
问题名 | 问题描述 |
---|---|
NQueen.java | N皇后问题,回溯法解决 |
TwoQueen.java | 2n皇后问题,回溯法解决 |
KnapsackB.java | 0-1背包问题,回溯法解决 |
KnapsackD.java | 0-1背包问题,动态规划解决 |
KMinSelect.java | 第K小问题 |
LongestSequence.java | 最长子序列问题 |
LongestSubstring.java | 最长公共子串问题 |
HexadecimalConversion.java | 大数据的16进制转化到8进制 |
SymbolicTriangle.java | 符号三角形问题 |
Factorial.java | 大数阶乘 |
LargeSum.java | 大数相加 |
NumberRead.java | 读数 |
TimeRead.java | 读时间 |
PalindromeeCorrection.java | 使用最小交换次数纠正回文字符串 |
一个n×n的国际象棋棋盘上放置n个皇后,使其不能相互攻击,即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上,试问共有多少种摆法?
常用n=8,解答为92种 。
问题描述
给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。
输入格式
输入的第一行为一个整数n,表示棋盘的大小。 接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。
输出格式
输出一个整数,表示总共有多少种放法。
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
给定一组随机数据,查找这个数据中的第K小元素的值。
给定两个字符串,求解两个字符串中的最长子序列的长度及该子序列。(注意和最长公共子串的不同)。如“abcdef"和“abdcef”。那么最长子序列的长度为5,为"abcef"和"abdef"。
给定两个字符串,求解两个字符串中最长的公共子串,注意和最长子序列问题的不同。如“abcefg"和"abegfc"中的最大公共子串为"ab"。
输入16进制数转换到8进制。由于数据量很大,不能使用Integer.valueOf()等方法,所以这里采用8421BCD码进行转换。
在一般情况下,符号三角形的第一行有n个符号。符号三角形问题,要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”相同。
计算类似1000!之类的结果,采用数组进位实现
问题描述 Tom教授正在给研究生讲授一门关于基因的课程,有一件事情让他颇为头疼:一条染色体上有成千上万个碱基对,它们从0开始编号,到几百万,几千万,甚至上亿。 比如说,在对学生讲解第1234567009号位置上的碱基时,光看着数字是很难准确的念出来的。 所以,他迫切地需要一个系统,然后当他输入12 3456 7009时,会给出相应的念法: 十二亿三千四百五十六万七千零九 用汉语拼音表示为 shi er yi san qian si bai wu shi liu wan qi qian ling jiu 这样他只需要照着念就可以了。 你的任务是帮他设计这样一个系统:给定一个阿拉伯数字串,你帮他按照中文读写的规范转为汉语拼音字串,相邻的两个音节用一个空格符格开。 注意必须严格按照规范,比如说“10010”读作“yi wan ling yi shi”而不是“yi wan ling shi”,“100000”读作“shi wan”而不是“yi shi wan”,“2000”读作“er qian”而不是“liang qian”。
问题描述 给定当前的时间,请用英文的读法将它读出来。 时间用时h和分m表示,在英文的读法中,读一个时间的方法是: 如果m为0,则将时读出来,然后加上“o'clock”,如3:00读作“three o'clock”。 如果m不为0,则将时读出来,然后将分读出来,如5:30读作“five thirty”。 时和分的读法使用的是英文数字的读法,其中0~20读作:
对于大于20小于60的数字,首先读整十的数,然后再加上个位数。如31首先读30再加1的读法,读作“thirty one”。 按上面的规则21:54读作“twenty one fifty four”,9:07读作“nine seven”,0:15读作“zero fifteen”。 输入格式 输入包含两个非负整数h和m,表示时间的时和分。非零的数字前没有前导0。h小于24,m小于60。 输出格式 输出时间时刻的英文。
问题描述
回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。 交换的定义是:交换两个相邻的字符 例如mamad 第一次交换 ad : mamda 第二次交换 md : madma 第三次交换 ma : madam (回文!完美!)
输入格式
第一行是一个整数N,表示接下来的字符串的长度(N <= 8000) 第二行是一个字符串,长度为N.只包含小写字母
输出格式
如果可能,输出最少的交换次数。 否则输出Impossible