[TOC]
algorithm 4th笔记(1.2)
1.2 数据抽象
Counter类 ，计数器
public class Counter {
private final String name;
private int val;
public Counter(String name) {
this.name = name;
val = 0;
}
public int tally() {
return val;
}
public void increment() {
val = val + 1;
}
@Override
public String toString() {
return "Counter{" +
"name='" + name + '\'' +
", val=" + val +
'}';
}
}
使用Counter模拟翻硬币
import java.util.Random;
public class Flips{
//Flip Max返回引用
public static Counter max(Counter x, Counter y) {
if (x.tally() > y.tally()) return x;
else return y;
}
//模拟抛硬币[0,100) [0,50) 表示 headers [50,100) 表示tails
public static void main(String[] args) {
args = new String[]{"1000"};
int T = Integer.parseInt(args[0]);
Counter heads = new Counter("headers");
Counter tails = new Counter("tails");
Random random = new Random();
for (int i = 0; i < T; i++) {
if (random.nextInt(100) / 50 == 0)
heads.increment();
else
tails.increment();
}
System.out.println((float) heads.tally() / (1.0 * T));
System.out.println((float) tails.tally() / (1.0 * T));
if (heads.tally() == tails.tally())
System.out.println("Tie");
else
System.out.println(max(heads, tails) + " wins");
}
}
使用Counter模拟置筛子
import java.util.Random;
/**
* 在Java中，对象数组即是一个由对象引用组成的数组，而非所有对象本身组成的数组。如果对象非常大，那么在移动
* 它们时由于只需要操作引用而非对象本身，这就会大大提高效率；如果对象很小，每次获取信息是都需要通过引用反
* 而会降低效率
*/
public class Rolls1_2_1_12 {
public static void main(String[] args) {
args = new String[]{"1000"};
final int SIDES = 6;
int T = Integer.parseInt(args[0]);
Counter[] rolls = new Counter[SIDES + 1];
for(int i=1;i<= SIDES;i++){
rolls[i]=new Counter(i+"'s");
}
Random random =new Random();
for(int i = 0;i < T;i++){
int result = random.nextInt(6) + 1;
rolls[result].increment();
}
for (int i = 0; i < SIDES; i++) {
System.out.println(rolls[i]);
}
}
}
一种能够累加数据的抽象数据类型
public class Accumulator {
private double total;
private int N;
public void addDataBalue(double val) {
N++;
total += val;
}
public double mean() {
return total / N;
}
@Override
public String toString() {
return "Mean(" + N + " values):" + String.format("%7.5f", mean());
}
}
StringOperator类，String类的常用操作
public class StringOperator{
//判断字符穿是否是一条回文
public static boolean isPalindrome(String s) {
int len = s.length();
for (int i = 0; i < len; i++) {//此处换成len/2更好
if (s.charAt(i) != s.charAt(len - i - 1))
return false;
}
return true;
}
//从命令行参数中提取文件名和扩展名
public static void getFileName(String fullName) {
int dot = fullName.indexOf(".");
String base = fullName.substring(0, dot);
String extension = fullName.substring(dot + 1, fullName.length());
System.out.println("basename:" + base + ",extension:" + extension);
}
//以空白字符为分隔符从StdIn中创建一个字符串数组
public static String[] spitWords(String s) {
String[] words = s.split("\\s+");
for (int i = 0; i < words.length; i++) {
System.out.println(words[i]);
}
return words;
}
//检查一个字符串数组中的元素是否已按照字母表顺序排列
public boolean isSorted(String[] a) {
for (int i = 1; i < a.length; i++) {
if (a[i - 1].compareTo(a[i]) > 0)
return false;
}
return true;
}
}
StaticSETofInts 类，封装
将二分查找重写为一段面向对象的程序（用于在整数集合中进行查找一种抽象的数据类型）
import java.util.Arrays;
public class StaticSETofInts {
private int[] a;
public StaticSETofInts(int[] keys) {
a = new int[keys.length];
for (int i = 0; i < keys.length; i++) {
a[i] = keys[i];
}
Arrays.sort(a);
}
public boolean contains(int key) {
return rank(key) != -1;
}
//二分查找
private int rank(int key) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
}
利用StaticSETofInts，找出数组中不存在的数
import java.util.Random;
public class Whitelist {
private static int INT_BOUND = 10000;
public static int[] genIntArr(int count) {
Random random = new Random();
int[] arr = new int[count];
for (int i = 0; i < count; i++) {
arr[i] = random.nextInt(INT_BOUND);
}
return arr;
}
public static void main(String[] args) {
//
int[] arr1 = genIntArr(1000);
StaticSETofInts set = new StaticSETofInts(arr1);
int[] arr2 = genIntArr(1000);
for (int i = 0; i < arr2.length; i++) {
if (!set.contains(arr2[i])) {
System.out.println(arr2[i]);
}
}
}
}
