Java知识梳理（二）——算法与编程

Posted on 2017-09-05 Word count in article: 7.3k Reading time ≈ 26 mins.

Java算法编程。java排序算法，经典问题算法，单例模式

编写一个程序，将a.txt文件中的单词与b.txt文件中的单词交替合并到c.txt文件中，a.txt文件中的单词用回车符分隔，b.txt文件中用回车或空格进行分隔。

答：

import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;

public class MainClass {
	public static void main(String[] args) throws Exception {
		FileManager a = new FileManager("a.txt", new char[] { '\n' });
		FileManager b = new FileManager("b.txt", new char[] { '\n', ' ' });
		FileWriter c = new FileWriter("c.txt");
		String aWord = null;
		String bWord = null;
		while ((aWord = a.nextWord()) != null) {
			c.write(aWord + "\n");
			bWord = b.nextWord();
			if (bWord != null)
				c.write(bWord + "\n");
		}
		while ((bWord = b.nextWord()) != null) {
			c.write(bWord + "\n");
		}
		c.close();
	}
}

class FileManager {
	String[] words = null;
	int pos = 0;

	public FileManager(String filename, char[] seperators) throws Exception {
		File f = new File(filename);
		FileReader reader = new FileReader(f);
		char[] buf = new char[(int) f.length()];
		int len = reader.read(buf);
		String results = new String(buf, 0, len);
		String regex = null;
		if (seperators.length > 1) {
			regex = "" + seperators[0] + "|" + seperators[1];
		} else {
			regex = "" + seperators[0];
		}
		words = results.split(regex);
	}

	public String nextWord() {
		if (pos == words.length)
			return null;
		return words[pos++];
	}
}

编写一个程序，将d:\java目录下的所有.java文件复制到d:\jad目录下，并将原来文件的扩展名从.java改为.jad。

（大家正在做上面这道题，网上迟到的朋友也请做做这道题，找工作必须能编写这些简单问题的代码！）

答：listFiles方法接受一个FileFilter对象，这个FileFilter对象就是过虑的策略对象，不同的人提供不同的FileFilter实现，即提供了不同的过滤策略。

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FilenameFilter;
import java.io.InputStream;
import java.io.OutputStream;

public class Jad2Java {
	public static void main(String[] args) throws Exception {
		File srcDir = new File("java");
		if (!(srcDir.exists() && srcDir.isDirectory()))
			throw new Exception("目录不存在");
		File[] files = srcDir.listFiles(new FilenameFilter() {
			public boolean accept(File dir, String name) {
				return name.endsWith(".java");
			}
		});
		System.out.println(files.length);
		File destDir = new File("jad");
		if (!destDir.exists())
			destDir.mkdir();
		for (File f : files) {
			FileInputStream fis = new FileInputStream(f);
			String destFileName = f.getName().replaceAll(".java", ".jad");
			FileOutputStream fos = new FileOutputStream(new File(destDir, destFileName));
			copy(fis, fos);
			fis.close();
			fos.close();
		}
	}

	private static void copy(InputStream ips, OutputStream ops) throws Exception {
		int len = 0;
		byte[] buf = new byte[1024];
		while ((len = ips.read(buf)) != -1) {
			ops.write(buf, 0, len);
		}
	}
}

由本题总结的思想及策略模式的解析：

import java.io.File;
import java.io.FileFilter;
import java.util.Arrays;
class jad2java1{
//得到某个目录下的所有的java文件集合
//1.1得到目录 
	File srcDir =new File("d:java");
//1.2 得到目录下的所有java文件：
	File[] files =srcDir.listFiles(new MyFileFilter());
//1.3 只想得到.java的文件： 
	class MyFileFilter implements FileFilter{
		public boolean accept(File pathname){
		return pathname.getName().endsWith(".java");
	}
}
//2.将每个文件复制到另外一个目录，并改扩展名
//2.1 得到目标目录，如果目标目录不存在，则创建之
//2.2 根据源文件名得到目标文件名，注意要用正则表达式，注意.的转义。
//2.3 根据表示目录的File和目标文件名的字符串，得到表示目标文件的File。
	//要在硬盘中准确地创建出一个文件，需要知道文件名和文件的目录。
//2.4 将源文件的流拷贝成目标文件流，拷贝方法独立成为一个方法，方法的参数采用抽象流的形式。
	//方法接受的参数类型尽量面向父类，越抽象越好，这样适应面更宽广。
}
//分析listFiles方法内部的策略模式实现原理
File[] listFiles(FileFilter filter){
File[] files = listFiles(filter);
//Arraylist acceptedFilesList = newArrayList();
File[] acceptedFiles = new File[files.length];
int pos = 0;
for(File file: files){
boolean accepted = filter.accept(file);
if(accepted){
//acceptedFilesList.add(file);
acceptedFiles[pos++] = file;
	}
}
Arrays.copyOf(acceptedFiles,pos);
//return (File[])accpetedFilesList.toArray();
	}
}

编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串，但要保证汉字不被截取半个，如“我ABC”，4，应该截取“我AB”，输入“我ABC汉DEF”，6，应该输出“我ABC”，而不是“我ABC+汉的半个”。

答：

首先要了解中文字符有多种编码及各种编码的特征。

假设n为要截取的字节数。

public class TrimGBK {
	public static void main(String[] args) throws Exception {
		String str = "我a爱中华abc我爱传智def";
		int num = trimGBK(str.getBytes("GBK"), 5);
		System.out.println(str.substring(0, num));
	}

	public static int trimGBK(byte[] buf, int n) {
		int num = 0;
		boolean bChineseFirstHalf = false;
		for (int i = 0; i < n; i++) {
			if (buf[i] < 0 && !bChineseFirstHalf) {
				bChineseFirstHalf = true;
			} else {
				num++;
				bChineseFirstHalf = false;
			}
		}
		return num;
	}
}

有一个字符串，其中包含中文字符、英文字符和数字字符，请统计和打印出各个字符的个数。

答：如果一串字符如”aaaabbc中国1512”要分别统计英文字符的数量，中文字符的数量，和数字字符的数量，假设字符中没有中文字符、英文字符、数字字符之外的其他特殊字符。

public class CountABC {
	public static void main(String[] args) {
		String str = "aaaabbc中国1512";
		int engishCount = 0;
		int chineseCount = 0;
		int digitCount = 0;
		for (int i = 0; i < str.length(); i++) {
			char ch = str.charAt(i);
			if (ch >= '0' && ch <= '9') {
				digitCount++;
			} else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
				engishCount++;
			} else {
				chineseCount++;
			}
		}
		System.out.println("英文字符的数量" + engishCount + ",中文字符的数量" + chineseCount + "，和数字字符的数量"
				+ digitCount);
	}
}

说明生活中遇到的二叉树，用java实现二叉树

这是组合设计模式。

我有很多个(假设10万个)数据要保存起来，以后还需要从保存的这些数据中检索是否存在某个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，那么，碰巧要找的数字位于99999那个地方，那查找的速度将很慢，因为要从第1个依次往后取，取出来后进行比较。平衡二叉树（构建平衡二叉树需要先排序，我们这里就不作考虑了）可以很好地解决这个问题，但二叉树的遍历（前序，中序，后序）效率要比数组低很多。

代码如下：

public class Node {
	public int value;
	public Node left;
	public Node right;

	public void store(int value) {
		if (value < this.value) {
			if (left == null) {
				left = new Node();
				left.value = value;
			} else {
				left.store(value);
			}
		} else if (value > this.value)

		{
			if (right == null) {
				right = new Node();
				right.value = value;
			} else {
				right.store(value);
			}
		}
	}

	public boolean find(int value) {
		System.out.println("happen" + this.value);
		if (value == this.value) {
			return true;
		} else if (value > this.value) {
			if (right == null)
				return false;
			return right.find(value);
		} else {
			if (left == null)
				return false;
			return left.find(value);
		}
	}

	public void preList() {
		System.out.print(this.value + ",");
		if (left != null)
			left.preList();
		if (right != null)
			right.preList();
	}

	public void middleList() {
		if (left != null)
			left.preList();
		System.out.print(this.value + ",");
		if (right != null)
			right.preList();
	}

	public void afterList() {
		if (left != null)
			left.preList();
		if (right != null)
			right.preList();
		System.out.print(this.value + ",");
	}

	public static void main(String[] args) {
		int[] data = new int[20];
		for (int i = 0; i < data.length; i++) {
			data[i] = (int) (Math.random() * 100) + 1;
			System.out.print(data[i] + ",");
		}
		System.out.println();
		Node root = new Node();
		root.value = data[0];
		for (int i = 1; i < data.length; i++) {
			root.store(data[i]);
		}
		root.find(data[19]);
		root.preList();
		System.out.println();
		root.middleList();
		System.out.println();
		root.afterList();
	}
}

从类似如下的文本文件中读取出所有的姓名，并打印出重复的姓名和重复的次数，并按重复次数排序：

1,张三,28 2,李四,35 3,张三,28 4,王五,35 5,张三,28 6,李四,35 7,赵六,28 8,田七,35

程序代码如下:

/*
 * 从类似如下的文本文件中读取出所有的姓名，并打印出重复的
 * 姓名和重复的次数，并按重复次数排序：
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class CopyOfGetNameTest {
	public static void main(String[] args) {
		Map<String, Integer> results = new TreeMap<String, Integer>();
		List<User> tm = new ArrayList<User>();
		tm.add(new User("张三", 28));
		tm.add(new User("李四", 35));
		tm.add(new User("张三", 28));
		tm.add(new User("王五", 35));
		tm.add(new User("张三", 28));
		tm.add(new User("李四", 35));
		tm.add(new User("赵六", 28));
		tm.add(new User("田七", 35));

		for (User x : tm) {
			dealLine(x, results);
		}
		for (Map.Entry<String, Integer> m : results.entrySet()) {
			System.out.println(m);
		}
	}

	private static void dealLine(User x, Map<String, Integer> map) {
		String name = x.getName();
		Integer value = (Integer) map.get(name);
		if (value == null) {
			value = 0;
		}
		map.put(name, value + 1);
	}

	public static void dealLine(String line, Map<String, Integer> map) {
		if (!"".equals(line.trim())) {
			String[] results = line.split(",");
			if (results.length == 3) {
				String name = results[1];
				Integer value = (Integer) map.get(name);
				if (value == null) {
					value = 0;
				}
				map.put(name, value + 1);
			}

		}
	}
}

class User implements Comparable<User> {
	public String name;
	public Integer value;

	public User(String name, Integer value) {
		this.name = name;
		this.value = value;
	}

	public String getName() {
		return name;
	}

	public Integer getAge() {
		return value;
	}

	@Override
	public String toString() {
		return "name = " + name + "   value = " + value;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj instanceof User) {
			User user = (User) obj;
			if ((this.name.equals(user.name)) && (this.value == user.value)) {
				return true;
			}
		}
		return false;
	}

	public int compareTo(User user) {
		int num = 0;
		int i = this.name.compareTo(user.name);
		if (i > 0) {
			num = 1;
		} else if (i < 0) {
			num = -1;
		} else {
			num = this.value > user.value ? 1 : (this.value == user.value ? 0 : -1);
		}
		return num;
	}
}

单实例Singleton设计模式

单实例Singleton设计模式可能是被讨论和使用的最广泛的一个设计模式了，这可能也是面试中问得最多的一个设计模式了。这个设计模式主要目的是想在整个系统中只能出现一个类的实例。这样做当然是有必然的，比如你的软件的全局配置信息，或者是一个Factory，或是一个主控类，等等。你希望这个类在整个系统中只能出现一个实例。当然，作为一个技术负责人的你，你当然有权利通过使用非技术的手段来达到你的目的。比如：你在团队内部明文规定，“XX类只能有一个全局实例，如果某人使用两次以上，那么该人将被处于2000元的罚款！”（呵呵），你当然有权这么做。但是如果你的设计的是东西是一个类库，或是一个需要提供给用户使用的API，恐怕你的这项规定将会失效。因为，你无权要求别人会那么做。所以，这就是为什么，我们希望通过使用技术的手段来达成这样一个目的的原因。

本文会带着你深入整个Singleton的世界，当然，我会放弃使用C++语言而改用Java语言，因为使用Java这个语言可能更容易让我说明一些事情。

Singleton的教学版本

这里，我将直接给出一个Singleton的简单实现，因为我相信你已经有这方面的一些基础了。我们姑且把这个版本叫做1.0版

// version 1.0
public class Singleton {
    private static Singleton singleton = null;
    private Singleton() {  }
    public static Singleton getInstance() {
        if (singleton== null) {
            singleton= new Singleton();
        }
        return singleton;
    }
}

在上面的实例中，我想说明下面几个Singleton的特点：（下面这些东西可能是尽人皆知的，没有什么新鲜的）

私有（private）的构造函数，表明这个类是不可能形成实例了。这主要是怕这个类会有多个实例。
即然这个类是不可能形成实例，那么，我们需要一个静态的方式让其形成实例：getInstance()。注意这个方法是在new自己，因为其可以访问私有的构造函数，所以他是可以保证实例被创建出来的。
在getInstance()中，先做判断是否已形成实例，如果已形成则直接返回，否则创建实例。
所形成的实例保存在自己类中的私有成员中。
我们取实例时，只需要使用Singleton.getInstance()就行了。

当然，如果你觉得知道了上面这些事情后就学成了，那得给你当头棒喝一下了，事情远远没有那么简单。

Singleton的实际版本

上面的这个程序存在比较严重的问题，因为是全局性的实例，所以，在多线程情况下，所有的全局共享的东西都会变得非常的危险，这个也一样，在多线程情况下，如果多个线程同时调用getInstance()的话，那么，可能会有多个进程同时通过 (singleton== null)的条件检查，于是，多个实例就创建出来，并且很可能造成内存泄露问题。嗯，熟悉多线程的你一定会说——“我们需要线程互斥或同步”，没错，我们需要这个事情，于是我们的Singleton升级成1.1版，如下所示：

// version 1.1
public class Singleton
{
    private static Singleton singleton = null;
    private Singleton() {  }
    public static Singleton getInstance() {
        if (singleton== null) {
            synchronized (Singleton.class) {
                singleton= new Singleton();
            }
        }
        return singleton;
    }
}

嗯，使用了Java的synchronized方法，看起来不错哦。应该没有问题了吧？！错！这还是有问题！为什么呢？前面已经说过，如果有多个线程同时通过(singleton== null)的条件检查（因为他们并行运行），虽然我们的synchronized方法会帮助我们同步所有的线程，让我们并行线程变成串行的一个一个去new，那不还是一样的吗？同样会出现很多实例。嗯，确实如此！看来，还得把那个判断(singleton== null)条件也同步起来。于是，我们的Singleton再次升级成1.2版本，如下所示：

// version 1.2
public class Singleton
{
    private static Singleton singleton = null;
    private Singleton()  {  }
    public static Singleton getInstance()  {
        synchronized (Singleton.class) {
            if (singleton== null) {
        singleton= new Singleton();
            }
         }
        return singleton;
    }
}

不错不错，看似很不错了。在多线程下应该没有什么问题了，不是吗？的确是这样的，1.2版的Singleton在多线程下的确没有问题了，因为我们同步了所有的线程。只不过嘛……，什么？！还不行？！是的，还是有点小问题，我们本来只是想让new这个操作并行就可以了，现在，只要是进入getInstance()的线程都得同步啊，注意，创建对象的动作只有一次，后面的动作全是读取那个成员变量，这些读取的动作不需要线程同步啊。这样的作法感觉非常极端啊，为了一个初始化的创建动作，居然让我们达上了所有的读操作，严重影响后续的性能啊！

还得改！嗯，看来，在线程同步前还得加一个(singleton== null)的条件判断，如果对象已经创建了，那么就不需要线程的同步了。OK，下面是1.3版的Singleton。

// version 1.3
public class Singleton
{
    private static Singleton singleton = null;
    private Singleton()  {    }
    public static Singleton getInstance() {
        if (singleton== null)  {
            synchronized (Singleton.class) {
                if (singleton== null)  {
                    singleton= new Singleton();
                }
            }
        }
        return singleton;
    }
}

感觉代码开始变得有点罗嗦和复杂了，不过，这可能是最不错的一个版本了，这个版本又叫“双重检查”Double-Check。下面是说明：

第一个条件是说，如果实例创建了，那就不需要同步了，直接返回就好了。
不然，我们就开始同步线程。
第二个条件是说，如果被同步的线程中，有一个线程创建了对象，那么别的线程就不用再创建了。

相当不错啊，干得非常漂亮！请大家为我们的1.3版起立鼓掌！

但是，如果你认为这个版本大攻告成，你就错了。

主要在于**singleton = new Singleton()**这句，这并非是一个原子操作，事实上在 JVM 中这句话大概做了下面 3 件事情。

给 singleton 分配内存
调用 Singleton 的构造函数来初始化成员变量，形成实例
将singleton对象指向分配的内存空间（执行完这步 singleton才是非 null 了）

但是在 JVM 的即时编译器中存在指令重排序的优化。也就是说上面的第二步和第三步的顺序是不能保证的，最终的执行顺序可能是 1-2-3 也可能是 1-3-2。如果是后者，则在 3 执行完毕、2 未执行之前，被线程二抢占了，这时 instance 已经是非 null 了（但却没有初始化），所以线程二会直接返回 instance，然后使用，然后顺理成章地报错。

对此，我们只需要把singleton声明成 volatile 就可以了。下面是1.4版：

// version 1.4
public class Singleton
{
    private volatile static Singleton singleton = null;
    private Singleton()  {    }
    public static Singleton getInstance()   {
        if (singleton== null)  {
            synchronized (Singleton.class) {
                if (singleton== null)  {
                    singleton= new Singleton();
                }
            }
        }
        return singleton;
    }
}

使用 volatile 有两个功用：

1）这个变量不会在多个线程中存在复本，直接从内存读取。

2）这个关键字会禁止指令重排序优化。也就是说，在 volatile 变量的赋值操作后面会有一个内存屏障（生成的汇编代码上），读操作不会被重排序到内存屏障之前。

但是，这个事情仅在Java 1.5版后有用，1.5版之前用这个变量也有问题，因为老版本的Java的内存模型是有缺陷的。

Singleton 的简化版本

上面的玩法实在是太复杂了，一点也不优雅，下面是一种更为优雅的方式：

这种方法非常简单，因为单例的实例被声明成 static 和 final 变量了，在第一次加载类到内存中时就会初始化，所以创建实例本身是线程安全的。

// version 1.5
public class Singleton
{
    private volatile static Singleton singleton = new Singleton();
    private Singleton()  {    }
    public static Singleton getInstance()   {
        return singleton;
    }
}

但是，这种玩法的最大问题是——当这个类被加载的时候，new Singleton() 这句话就会被执行，就算是getInstance()没有被调用，类也被初始化了。

于是，这个可能会与我们想要的行为不一样，比如，我的类的构造函数中，有一些事可能需要依赖于别的类干的一些事（比如某个配置文件，或是某个被其它类创建的资源），我们希望他能在我第一次getInstance()时才被真正的创建。这样，我们可以控制真正的类创建的时刻，而不是把类的创建委托给了类装载器。

好吧，我们还得绕一下：

下面的这个1.6版是老版《Effective Java》中推荐的方式。

// version 1.6
public class Singleton {
    private static class SingletonHolder {
        private static final Singleton INSTANCE = new Singleton();
    }
    private Singleton (){}
    public static final Singleton getInstance() {
        return SingletonHolder.INSTANCE;
    }
}

上面这种方式，仍然使用JVM本身机制保证了线程安全问题；由于 SingletonHolder 是私有的，除了 getInstance() 之外没有办法访问它，因此它只有在getInstance()被调用时才会真正创建；同时读取实例的时候不会进行同步，没有性能缺陷；也不依赖 JDK 版本。

Singleton 优雅版本

public enum Singleton{
   INSTANCE;
}

居然用枚举！！看上去好牛逼，通过EasySingleton.INSTANCE来访问，这比调用getInstance()方法简单多了。

默认枚举实例的创建是线程安全的，所以不需要担心线程安全的问题。但是在枚举中的其他任何方法的线程安全由程序员自己负责。还有防止上面的通过反射机制调用私用构造器。

这个版本基本上消除了绝大多数的问题。代码也非常简单，实在无法不用。这也是新版的《Effective Java》中推荐的模式。

Singleton的其它问题

怎么？还有问题？！当然还有，请记住下面这条规则——“无论你的代码写得有多好，其只能在特定的范围内工作，超出这个范围就要出Bug了”，这是“陈式第一定理”，呵呵。你能想一想还有什么情况会让这个我们上面的代码出问题吗？

在C++下，我不是很好举例，但是在Java的环境下，嘿嘿，还是让我们来看看下面的一些反例和一些别的事情的讨论（当然，有些反例可能属于钻牛角尖，可能有点学院派，不过也不排除其实际可能性，就算是提个醒吧）：

Class Loader。不知道你对Java的Class Loader熟悉吗？“类装载器”？！C++可没有这个东西啊。这是Java动态性的核心。顾名思义，类装载器是用来把类(class)装载进JVM的。JVM规范定义了两种类型的类装载器：启动内装载器(bootstrap)和用户自定义装载器(user-defined class loader)。在一个JVM中可能存在多个ClassLoader，每个ClassLoader拥有自己的NameSpace。一个ClassLoader只能拥有一个class对象类型的实例，但是不同的ClassLoader可能拥有相同的class对象实例，这时可能产生致命的问题。如ClassLoaderA，装载了类A的类型实例A1，而ClassLoaderB，也装载了类A的对象实例A2。逻辑上讲A1=A2，但是由于A1和A2来自于不同的ClassLoader，它们实际上是完全不同的，如果A中定义了一个静态变量c，则c在不同的ClassLoader中的值是不同的。

于是，如果咱们的Singleton 1.3版本如果面对着多个Class Loader会怎么样？呵呵，多个实例同样会被多个Class Loader创建出来，当然，这个有点牵强，不过他确实存在。难道我们还要整出个1.4版吗？可是，我们怎么可能在我的Singleton类中操作Class Loader啊？是的，你根本不可能。在这种情况下，你能做的只有是——“保证多个Class Loader不会装载同一个Singleton”。

序例化。如果我们的这个Singleton类是一个关于我们程序配置信息的类。我们需要它有序列化的功能，那么，当反序列化的时候，我们将无法控制别人不多次反序列化。不过，我们可以利用一下Serializable接口的readResolve()方法，比如：

public class Singleton implements Serializable
{
    ......
    ......
    protected Object readResolve()
    {
        return getInstance();
    }
}

多个Java虚拟机。如果我们的程序运行在多个Java的虚拟机中。什么？多个虚拟机？这是一种什么样的情况啊。嗯，这种情况是有点极端，不过还是可能出现，比如EJB或RMI之流的东西。要在这种环境下避免多实例，看来只能通过良好的设计或非技术来解决了。
volatile变量。关于volatile这个关键字所声明的变量可以被看作是一种 “程度较轻的同步synchronized”；与 synchronized 块相比，volatile 变量所需的编码较少，并且运行时开销也较少，但是它所能实现的功能也仅是synchronized的一部分。当然，如前面所述，我们需要的Singleton只是在创建的时候线程同步，而后面的读取则不需要同步。所以，volatile变量并不能帮助我们即能解决问题，又有好的性能。而且，这种变量只能在JDK 1.5+版后才能使用。
关于继承。是的，继承于Singleton后的子类也有可能造成多实例的问题。不过，因为我们早把Singleton的构造函数声明成了私有的，所以也就杜绝了继承这种事情。
关于代码重用。也话我们的系统中有很多个类需要用到这个模式，如果我们在每一个类都中有这样的代码，那么就显得有点傻了。那么，我们是否可以使用一种方法，把这具模式抽象出去？在C++下这是很容易的，因为有模板和友元，还支持栈上分配内存，所以比较容易一些（程序如下所示），Java下可能比较复杂一些，聪明的你知道怎么做吗？

template class Singleton
{
    public:
        static T& Instance()
        {
            static T theSingleInstance; //假设T有一个protected默认构造函数
            return theSingleInstance;
        }
};
class OnlyOne : public Singleton
{
    friend class Singleton;
    int example_data;
    public:
        int GetExampleData() const {return example_data;}
    protected:
        OnlyOne(): example_data(42) {}   // 默认构造函数
        OnlyOne(OnlyOne&) {}
};
int main( )
{
    cout << OnlyOne::Instance().GetExampleData() << endl;
    return 0;
}

递归算法题1

一个整数，大于0，不用循环和本地变量，按照n，2n，4n，8n的顺序递增，当值大于5000时，把值按照指定顺序输出来。
例：n=1237
则输出为：
1237，2474，4948，9896，9896，4948，2474，1237，

提示：写程序时，先致谢按递增方式的代码，写好递增的以后，再增加考虑递减部分。

public static void doubleNum(int n){
		System.out.println(n);
	if(n<=5000)
	doubleNum(n*2);
		System.out.println(n);
}

递归算法题2

第1个人10，第2个比第1个人大2岁，依次递推，请用递归方式计算出第8个人多大？

public class Test {
    public static void main(String[] args) {
        System.out.println(computeAge(8));
    }
    public static int computeAge(int n) {
        if (n == 1) {
            return 10;
        } else {
            return computeAge(n - 1) + 2;
        }
    }
}

排序算法

//插入排序:
 
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class InsertSort implements SortUtil.Sort{
    public void sort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }        
    }
}
//冒泡排序: 
 
for(var i=0; i<arr.length; i++) {    
    for(var j=i+1; j<=arr.length-1; j++) {
        if(eval(arr[i]) < eval(arr[j])) {        
            temp = arr[i];                      
            arr[i] = arr[j];                        
            arr[j] = temp;                                              
        }
    }
} 
 
package org.rut.util.algorithm.support; 
import org.rut.util.algorithm.SortUtil;
public class BubbleSort implements SortUtil.Sort
    public void sort(int[] data) {
        int temp;
        for(int i=0;i<data.length;i++){
            for(int j=data.length-1;j>i;j--){
                if(data[j]<data[j-1]){
                    SortUtil.swap(data,j,j-1);
                }
            }
        }
    }
 
}
 
//选择排序:
 
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class SelectionSort implements SortUtil.Sort {
    public void sort(int[] data) {
        int temp;
        for (int i = 0; i < data.length; i++) {
            int lowIndex = i;
            for (int j = data.length - 1; j > i; j--) {
                if (data[j] < data[lowIndex]) {
                    lowIndex = j;
                }
            }
            SortUtil.swap(data,i,lowIndex);
        }
    }
 
}
 
//Shell排序:
 
package org.rut.util.algorithm.support; 
import org.rut.util.algorithm.SortUtil;
public class ShellSort implements SortUtil.Sort{
    public void sort(int[] data) {
        for(int i=data.length/2;i>2;i/=2){
            for(int j=0;j<i;j++){
                insertSort(data,j,i);
            }
        }
        insertSort(data,0,1);
    }
    private void insertSort(int[] data, int start, int inc) {
        int temp;
        for(int i=start+inc;i<data.length;i+=inc){
            for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
                SortUtil.swap(data,j,j-inc);
            }
        }
    }
 
}
 
//快速排序:
 
package org.rut.util.algorithm.support; 
import org.rut.util.algorithm.SortUtil;
public class QuickSort implements SortUtil.Sort{
    public void sort(int[] data) {
        quickSort(data,0,data.length-1);        
    }
    private void quickSort(int[] data,int i,int j){
        int pivotIndex=(i+j)/2;
        //swap
        SortUtil.swap(data,pivotIndex,j);
         
        int k=partition(data,i-1,j,data[j]);
        SortUtil.swap(data,k,j);
        if((k-i)>1) quickSort(data,i,k-1);
        if((j-k)>1) quickSort(data,k+1,j);
         
    }
    private int partition(int[] data, int l, int r,int pivot) {
        do{
           while(data[++l]<pivot);
           while((r!=0)&&data[--r]>pivot);
           SortUtil.swap(data,l,r);
        }
        while(l<r);
        SortUtil.swap(data,l,r);        
        return l;
    }
 
}
//改进后的快速排序:
 
package org.rut.util.algorithm.support; 
import org.rut.util.algorithm.SortUtil;
public class ImprovedQuickSort implements SortUtil.Sort {
    private static int MAX_STACK_SIZE=4096;
    private static int THRESHOLD=10;
    public void sort(int[] data) {
        int[] stack=new int[MAX_STACK_SIZE];
         
        int top=-1;
        int pivot;
        int pivotIndex,l,r;
         
        stack[++top]=0;
        stack[++top]=data.length-1;
         
        while(top>0){
            int j=stack[top--];
            int i=stack[top--];
             
            pivotIndex=(i+j)/2;
            pivot=data[pivotIndex];
             
            SortUtil.swap(data,pivotIndex,j);
             
            //partition
            l=i-1;
            r=j;
            do{
                while(data[++l]<pivot);
                while((r!=0)&&(data[--r]>pivot));
                SortUtil.swap(data,l,r);
            }
            while(l<r);
            SortUtil.swap(data,l,r);
            SortUtil.swap(data,l,j);
             
            if((l-i)>THRESHOLD){
                stack[++top]=i;
                stack[++top]=l-1;
            }
            if((j-l)>THRESHOLD){
                stack[++top]=l+1;
                stack[++top]=j;
            }
             
        }
        //new InsertSort().sort(data);
        insertSort(data);
    }
   
    private void insertSort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }       
    }
 
}
 
//归并排序:
 
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class MergeSort implements SortUtil.Sort{
    public void sort(int[] data) {
        int[] temp=new int[data.length];
        mergeSort(data,temp,0,data.length-1);
    }
     
    private void mergeSort(int[] data,int[] temp,int l,int r){
        int mid=(l+r)/2;
        if(l==r) return ;
        mergeSort(data,temp,l,mid);
        mergeSort(data,temp,mid+1,r);
        for(int i=l;i<=r;i++){
            temp[i]=data[i];
        }
        int i1=l;
        int i2=mid+1;
        for(int cur=l;cur<=r;cur++){
            if(i1==mid+1)
                data[cur]=temp[i2++];
            else if(i2>r)
                data[cur]=temp[i1++];
            else if(temp[i1]<temp[i2])
                data[cur]=temp[i1++];
            else
                data[cur]=temp[i2++];            
        }
    }
 
}
 
//改进后的归并排序:
 
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class ImprovedMergeSort implements SortUtil.Sort {
    private static final int THRESHOLD = 10;
    public void sort(int[] data) {
        int[] temp=new int[data.length];
        mergeSort(data,temp,0,data.length-1);
    }
 
    private void mergeSort(int[] data, int[] temp, int l, int r) {
        int i, j, k;
        int mid = (l + r) / 2;
        if (l == r)
            return;
        if ((mid - l) >= THRESHOLD)
            mergeSort(data, temp, l, mid);
        else
            insertSort(data, l, mid - l + 1);
        if ((r - mid) > THRESHOLD)
            mergeSort(data, temp, mid + 1, r);
        else
            insertSort(data, mid + 1, r - mid);
 
        for (i = l; i <= mid; i++) {
            temp[i] = data[i];
        }
        for (j = 1; j <= r - mid; j++) {
            temp[r - j + 1] = data[j + mid];
        }
        int a = temp[l];
        int b = temp[r];
        for (i = l, j = r, k = l; k <= r; k++) {
            if (a < b) {
                data[k] = temp[i++];
                a = temp[i];
            } else {
                data[k] = temp[j--];
                b = temp[j];
            }
        }
    
    private void insertSort(int[] data, int start, int len) {
        for(int i=start+1;i<start+len;i++){
            for(int j=i;(j>start) && data[j]<data[j-1];j--){
                SortUtil.swap(data,j,j-1);
            }
        }
    }
 
}
//堆排序:
 
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
public class HeapSort implements SortUtil.Sort{
    public void sort(int[] data) {
        MaxHeap h=new MaxHeap();
        h.init(data);
        for(int i=0;i<data.length;i++)
            h.remove();
        System.arraycopy(h.queue,1,data,0,data.length);
    }
 
 
     private static class MaxHeap{
          
         
        void init(int[] data){
            this.queue=new int[data.length+1];
            for(int i=0;i<data.length;i++){
                queue[++size]=data[i];
                fixUp(size);
            }
        }
          
        private int size=0;
 
        private int[] queue;
                 
        public int get() {
            return queue[1];
        }
 
        public void remove() {
            SortUtil.swap(queue,1,size--);
            fixDown(1);
        }
        //fixdown
        private void fixDown(int k) {
            int j;
            while ((j = k << 1) <= size) {
                if (j < size && queue[j]<queue[j+1])
                    j++; 
                if (queue[k]>queue[j]) //不用交换
                    break;
                SortUtil.swap(queue,j,k);
                k = j;
            }
        }
        private void fixUp(int k) {
            while (k > 1) {
                int j = k >> 1;
                if (queue[j]>queue[k])
                    break;
                SortUtil.swap(queue,j,k);
                k = j;
            }
        }
 
    }
 
}
 
  
 
//SortUtil:
 
package org.rut.util.algorithm;
 
import org.rut.util.algorithm.support.BubbleSort;
import org.rut.util.algorithm.support.HeapSort;
import org.rut.util.algorithm.support.ImprovedMergeSort;
import org.rut.util.algorithm.support.ImprovedQuickSort;
import org.rut.util.algorithm.support.InsertSort;
import org.rut.util.algorithm.support.MergeSort;
import org.rut.util.algorithm.support.QuickSort;
import org.rut.util.algorithm.support.SelectionSort;
import org.rut.util.algorithm.support.ShellSort;
public class SortUtil {
    public final static int INSERT = 1;
    public final static int BUBBLE = 2;
    public final static int SELECTION = 3; 
    public final static int SHELL = 4; 
    public final static int QUICK = 5; 
    public final static int IMPROVED_QUICK = 6; 
    public final static int MERGE = 7; 
    public final static int IMPROVED_MERGE = 8; 
    public final static int HEAP = 9;
    public static void sort(int[] data) {
        sort(data, IMPROVED_QUICK);
    }
    private static String[] name={
            "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
    };
     
    private static Sort[] impl=new Sort[]{
            new InsertSort(),
            new BubbleSort(),
            new SelectionSort(),
            new ShellSort(),
            new QuickSort(),
            new ImprovedQuickSort(),
            new MergeSort(),
            new ImprovedMergeSort(),
            new HeapSort()
    };
 
    public static String toString(int algorithm){
        return name[algorithm-1];
    }
     
    public static void sort(int[] data, int algorithm) {
        impl[algorithm-1].sort(data);
    }
 
    public static interface Sort {
        public void sort(int[] data);
    }
 
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

有数组a[n]，用java代码将数组元素顺序颠倒

public class Test {   
  public static void reverse(int[] a, int left, int right) {   
    if (left >= right)   
      return;   
    int temp;   
    temp = a[left];   
    a[left] = a[right];   
    a[right] = temp;   
    reverse(a, ++left, --right);   
  }     
  public static void main(String args[]) {   
    int[] a = { 1, 2, 3, 4, 5 };   
    reverse(a, 0, a.length - 1);   
    for (int i = 0; i < a.length; i++)   
      System.out.println(a[i]);   
  }   
}

12．金额转换，阿拉伯数字的金额转换成中国传统的形式如：（￥1011）－>（一千零一拾一元整）输出。

public class Test {   
    private static final char[] data = new char[]{'零','壹','贰','叁','肆','伍','陆','柒','捌','玖'}; 
    private static final char[] units = new char[]{'元','拾','佰','仟','万','拾','佰','仟','亿'}; 
    /*去零的代码
    return sb.reverse().toString().replaceAll("零[拾佰仟]","零").replaceAll("零+万","万").replaceAll("零+元","元").replaceAll("零+","零");*/
    /*去零倒序
    return sb.reverse().toString().replaceAll("零[拾佰仟]","零").replaceAll("零+万","万").replaceAll("零+元","元").replaceAll("零+","零");*/ 
    public static void main(String[] args) {
        System.out.println(convert(230009));
    }
    private static String convert(int money) {
        StringBuffer sbf = new StringBuffer();
        int unit = 0;
        while(money!=0)
        {
            sbf.insert(0,units[unit++]);
            int number = money%10;
            sbf.insert(0, data[number]);
            money /= 10;
        }
        return sbf.toString().replaceAll("零[拾佰仟]","零").replaceAll("零+万","万").replaceAll("零+元","元").replaceAll("零+","零");
    } 
}