首页 > 代码库 > 111111111
111111111
package algorithm.optimalpath;
import java.util.Arrays;
/**
*
* Dijkstra算法 是从一个顶点到其余各顶点的 最短路径算法，解决的是有向图中 最短路径问题。
* @param args void
* @author ex_kjkfb_chenyongh
* @date 2016-9-22 下午02:20:12
*/
public class Dijkstra {
private static final int inf = Integer.MAX_VALUE;
public static void main(String[] args) {
int[][] W1 = {
{ 0, 10, 20, 30, inf },
{ 10, 0, 5, 10, inf },
{ 20, 5, 0, inf, 30 },
{ 30, 10, inf, 0, 20 },
{ inf, inf, 30, 20, 0 },
};
int[][] di = method(W1);
System.out.println(Arrays.toString(di[0]));
System.out.println(Arrays.toString(di[1]));
}
public static int[][] method( int[][] graph) {
int min, v, u = 0;
int n = graph.length;
int[] path = new int[n];
int[] dist = new int[n]; //为每个顶点 保留目前为止 所找到的 最短路径
Arrays.fill(dist, inf);
boolean[] s = new boolean[n];
Arrays.fill(s, false);
for (int i = 0; i < n; i++) {
dist[i] = graph[u][i];//为每个顶点 保留目前为止 所找到的 最短路径
if (i != u && dist[i] < inf)
path[i] = u;
else
path[i] = -1;
}
s[u] = true;
while (true) {
min = inf;
v = -1;
for (int i = 0; i < n; i++) { //找到最小的dist
if (!s[i]) { //s[i]==false 的话就执行
if (dist[i] < min) {
min = dist[i];
v = i;
}
}
}
if (v == -1) break; //找不到更短的路径了
s[v] = true;
for (int i = 0; i < n; i++) { //更新最短路径
if (!s[i] && graph[v][i] != inf && dist[v] + graph[v][i] < dist[i]) {
dist[i] = dist[v] + graph[v][i];
path[i] = v;
}
}
}
int[] shortest = new int[n];
for (int i = 1; i < n; i++) { //输出路径
Arrays.fill(shortest, 0);
int k = 0;
shortest[k] = i;
while (path[shortest[k]] != 0) {
k++;
shortest[k] = path[shortest[k - 1]];
}
k++;
shortest[k] = 0;
}
int[] tmp = new int[shortest.length];
for (int i = 0; i < tmp.length; i++)
tmp[i] = shortest[tmp.length - i - 1];
return new int[][] { dist, tmp };
}
}
package algorithm.others;
import java.io.*;
public class CopyFile {
public static void main(String[] args) {
CopyFile c=new CopyFile();
c.copyFile();
}
public void copyFile(){
try{
FileInputStream input=new FileInputStream("D://dd.txt");
FileOutputStream output=new FileOutputStream("D://b/aa.txt");
int in=input.read();
while(in!=-1){
output.write(in);
in=input.read();
}
}catch(IOException e){
System.out.println(e.toString());
}
}
}
package algorithm.others;
import java.io.*;
/**
* 方法说明
* Input a line of characters,
* count the number of letter,
* space character,
* digit and other characters respectively.
* @param args void
* @author ex_kjkfb_chenyongh
* @date 2016-9-18 下午02:49:43
*/
public class CountNumber {
public static void main(String[] args) throws Exception{
CountNumber c=new CountNumber();
c.method1();
c.method2();
}
public void method1() {
int charCount=0;
int spaceCount=0;
int numberCount=0;
int otherCount=0;
java.util.Scanner scan=new java.util.Scanner(System.in);
String str=scan.nextLine();
char[] ch = str.toCharArray();
for(int i=0;i<ch.length;i++){
if(Character.isLetter(ch[i]))
charCount++;
else if(Character.isDigit(ch[i]))
numberCount++;
else if(Character.isSpaceChar(ch[i]))
spaceCount++;
else
otherCount++;
}
System.out.println("Letter Number: "+charCount);
System.out.println("Digit Number: "+numberCount);
System.out.println("Space Character Number: "+spaceCount);
System.out.println("Other Characters Number: "+otherCount);
}
public void method2() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer(br.readLine());
int charCount = 0;
int spaceCount = 0;
int numberCount = 0;
int otherCount = 0;
for(int i=0;i<sb.length();i++){
if((sb.charAt(i)>=‘a‘ && sb.charAt(i)<=‘z‘) || (sb.charAt(i)>=‘A‘&&sb.charAt(i)<=‘Z‘))
charCount++;
else if(sb.charAt(i)==‘ ‘)
spaceCount ++;
else if(sb.charAt(i)>‘0‘&&sb.charAt(i)<‘9‘)
numberCount++;
else
otherCount++;
}
System.out.println("Letter Number: "+charCount);
System.out.println("Digit Number: "+numberCount);
System.out.println("Space Character Number: "+spaceCount);
System.out.println("Other Characters Number: "+otherCount);
}
}
package algorithm.others;
public class NarcissusFew {
public static void main(String[] args) {
NarcissusFew n=new NarcissusFew();
n.method1();
n.method2();
}
public void method1(){
int num;
for (int i = 1; i < 10; i++) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
num = i * 100 + j * 10 + k;
if (num == i * i * i + j * j * j + k * k * k) {
System.out.print(num + "\t");
}
}
}
}
}
public void method2(){
int num;
int temp;
int sum = 0;
for (num = 100; num < 1000; num++,sum = 0) {
int numCopy = num;
while (numCopy > 0) {
temp = numCopy % 10;
numCopy/= 10;
sum += temp * temp * temp;
}
if (num == sum) {
System.out.print(sum + "\n");
}
}
}
}
package algorithm.others;
public class StringReverse {
public static void main(String[] args) {
StringReverse mReverse = new StringReverse();
String str = "12345556!";
mReverse.method1(str);
mReverse.method2(str);
}
public String method1(String str){
StringBuffer mstr = new StringBuffer(str);
System.out.println("Reversed String : "+ mstr.reverse().toString());
return mstr.reverse().toString();
}
public String method2(String str){
byte[] mchars = str.getBytes();
byte temp = 0;
int length = mchars.length;
for(int i = 0; i < length/2 ;i++){
temp = mchars[i];
mchars[i] = mchars[length -1 -i];
mchars[length -1 -i] = temp;
}
String mstr = new String(mchars);
System.out.println("Reversed String : "+ mstr);
return mstr;
}
}
package algorithm.sort.notcompare;
/**
* 类说明
* Already Learned.
* 时间
* 空间
* 稳定性
* 适用情况
* @author ex_kjkfb_chenyongh
* @date 2016-9-28 下午02:57:26
*/
public class CountSort{
public static void main(String[]args){
int arrA[]={100,93,97};
int arrB[]=countSort(arrA);
for(int i:arrB)
System.out.print(i+" ");
}
public static int[] countSort(int[] arr){
int arrb[] = new int[arr.length];
int max = arr[0], min = arr[0];
for(int i:arr){ //Find the max number and min number in arr.
if(i>max) max=i;
if(i<min) min=i;
}
int k=max-min+1;
int c[]=new int[k];
for(int i=0; i<arr.length; ++i)
c[arr[i]-min]+=1;
for(int i=1; i<c.length; ++i)
c[i]=c[i]+c[i-1];
for(int i=arr.length-1; i>=0; --i)
arrb[--c[arr[i]-min]]=arr[i];
return arrb;
}
}
package algorithm.sort.notcompare;
import java.util.Arrays;
/**
* 方法说明
* 基数排序
* 时间复杂度：O (nlog(r)m)，其中r为所采取的基数，而m为堆数
* 空间
* 稳定性：稳定
* 适用情况
* @author ex_kjkfb_chenyongh
* @date 2016-9-20 上午09:59:11
*/
public class RadixSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 111, 213, 134, 65, 77, 78, 23, 43, 321 };
radixSort (arrayA, 0, 2, arrayA.length);
System.out.println (Arrays.toString (arrayA));
}
private static void radixSort ( int[] array, int from, int radix, int d ){
int len = array.length;
int[] temporary = new int[len];
int[] count = new int[radix];
int R = 1;
for ( int i = 0; i < d; i++ ){
System.arraycopy (array, from, temporary, 0, len);
Arrays.fill (count, 0);
for ( int k = 0; k < len; k++ ){
int subkey = ( temporary[k] / R ) % radix;
count[subkey]++;
}
// for ( int j = 1; j < radix; j++ ) // 从小到大
// count[j] = count[j] + count[j - 1];
for ( int j = 1; j < radix; j++ ) //从大到小
count[j - 1] = count[j] + count[j - 1];
for ( int m = len - 1; m >= 0; m-- ){
int subkey = ( temporary[m] / R ) % radix;
--count[subkey];
array[from + count[subkey]] = temporary[m];
}
R *= radix;
}
}
}
桶排序
二叉排序树排序 （Binary tree sort） — O(nlog n)期望时间； O(n^2)最坏时间； 需要 O(n) 额外空间
鸽巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间
Gnome 排序— O(n^2)
图书馆排序— O(nlog n) with high probability，需要 （1+ε)n额外空间
不稳定的
组合排序— O(nlog n)
平滑排序— O(nlog n)
Intro sort— O(nlog n)
Patience sorting— O(nlog n+ k) 最坏情况时间，需要 额外的 O(n+ k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）
不实用的
Bogo排序— O(n× n!) 期望时间，无穷的最坏情况。
Stupid sort— O(n^3); 递归版本需要 O(n^2) 额外存储器
珠排序（Bead sort） — O(n) or O（√n)，但需要特别的硬件
Pancake sorting— O(n)，但需要特别的硬件
stooge sort——O（n^2.7）很漂亮但是很耗时
JAVA_HOME D:\Tool\jdk1.7.0_X86
%JAVA_HOME%\bin;%JAVA_HOME%\jre\bin;
Code Annotation: codetemplates.xml
Window->Preferences->Java->Code Style->Code Templates->Choose ‘comments‘ to import templates
How to use: ‘Shift+Alt+j‘
111111111