- 浏览: 10727 次
- 性别:
- 来自: 辽宁
最新评论
-
陈琰琰:
写得不错,学习了, ...
将阿拉伯数字转换成中文数字表示
文章列表
将阿拉伯数字转换成中文数字表示
- 博客分类:
- 随写
package contest.numtochi;
import java.util.HashMap;
import java.util.Scanner;
public class NumToChi{
//创建数字和中文数字一一对应的映射
private HashMap<Integer, String> map;
//创建位数和中文单位的一一映射
private HashMap<Integer, String> unit;
// 判断输入的字符串是否全是数字
public boolean isNum(String str) { ...
贪心算法
贪心算法:贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。
贪心算法基本思路:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的求的更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
贪心算法存在的问题:
1.不能保证求的最后解是最佳的。
2.不能用来求最大或最小解问题。
3.只能求满足某些约束条件的可行解的范围。
贪心算法的基本要求:
1.贪心选择性质:指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。
2.具有最优子结构性质:一个问题的最优解包含其子问题的最优解。
...
五种常见算法之分治策略
- 博客分类:
- 算法
分治策略
分治法基本思想:
1.大问题分解为子问题,这些子问题相互独立且与原问题相同。
2.分别求解子问题。如果子问题的规模依然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。
3.合并解集,自底向上逐步求出原来问题的解。
4.分治发的设计思想是,讲一个难以直接解决的大问题分割成一些规模较小的相同问题,以便各个击破,分而治之。
分治法的使用条件:
1.该问题的规模缩小到一定程度就可以容易的解决。
2.该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质(当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质)。
3.利用该 ...
基数排序算法
(radixsort)则是属于“分配式排序”(distribution sort),基数排序法又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排 ...
计数排序
计数排序思想:就是对于每一个输入元素x,确定出小于x的元素个数。有了这一信息就可以把x直接放在它最终输出的数组中的位置。(当有元素相同时,此方案还要修改)。
package com.countingsort.yy;
/**
* 计数排序算法
*@author yuyang_csu
*@data 2013-4-7
*/
class CountingSort {
/**
* 计数排序方法
*
* @param a
* :待排序数组
* @param b
* :存放排序好 ...
快速排序算法
基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都小,然后再按此方法对这两部分数据进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
算法过程:
step1:指定枢纽
step2:通过一趟排序将以枢纽为中心,把待排记录分割为独立的两部分,使得左边记录的关键字小于枢纽值,右边记录的关键字大于枢纽值。
step3:对左右两部分记录序列重复上述过程,依此类推,直到子序列中只剩下一个记录或不含记录为止。
package com.quicksort.yy;
/**
* 快速排序
*@author y ...
冒泡排序算法
冒泡排序基本思想:
设数组arr中存放了n个元素,循环n-1次如下的排序过程:
step1:一次比较相邻两个数据元素,若a[i]>a[i+1],则交换两个数据元素,否则不交换。
step2:当完成一趟交换以后,最大的元素将会出现 ...
归并排序算法
归并排序思想:将待排序的元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排序好的子集合合并成为索要要求的排好序的集合。
step1:把待排序的n个记录看作是长度为1的有序序列。将相邻的子序列两两归并成为长度为2或1的有序序列。
step2:把得到的n/2个长度为2的有序子序列在归并为长度为2*2的有序序列。
step3:按step2的方式,重复对相邻的有序子序列进行归并操作,直到成为一个有序序列为止。
package com.mergesort.yy;
/**
* 归并排序
*@author yuyang_csu
*@data 2013 ...
堆排序算法
首先介绍一下什么是堆,这里所说的堆其实是二叉堆。二叉堆是完全二叉树的应用,此外二叉堆又分为最小和最大二叉堆之分。最小二叉堆满足父节点的值小于儿子节点的值(除根节点外,因为根节点没有父节点)。很明显,说道这里最大二叉堆大家也就知道了,就不再叙述。
堆排序分为两个阶段:第一个阶段就是构建一个最小或者最大二叉堆。第二阶段就是采用选择排序的思想,将根节点交换到后面,再将其余的节点进行调整,成为新的二叉堆,重复进行,直到排序完成。下面将为大家展示如何用堆排序输出降序排列的序列。
按降序排列
package com.heapsort.yy;
/**
* 堆排序算法
*@auth ...
优先队列(堆)
1.优先队列模型:
优先队列是允许下列两种操作的数据结构:insert(插入)以及deleteMin(删除最小者)。insert操作等价于入队,而deleteMin操作则等价于出队,它的工作是找到,返回并删除优先队列中的最小元素 ...
希尔排序
希尔排序的思想是分组的直接插入排序。由直接插入排序可知,若数据序列越接近有序,则时间效率越高;再者,当n越小时,时间效率越高。希尔排序就是基于这两点对直接插入排序进行改进的。
希尔排序算法描述如下:
1.将一个数据序列分成若干组,每组由若干相隔一段距离的元素组成,这段距离称为增量,在一个组内采用直接插入排序算法进行排序。
2.增量的初值通常为数据序列长度的一半,以后每趟增量逐渐缩小,最后为1.随着增量的逐渐减小,组数也减少,组内元素个数增加,整个序列接近有序。当增量为1时,只有一组,元素是整个序列,在进行一次直接插入排序即可。
package com.shellsort.yy;
...