文章列表
将阿拉伯数字转换成中文数字表示
- 博客分类：
- 随写
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;
...