[TOC]
algorithm 4th笔记(1.1)
第一章知识点
第一章整体结构图
二分查找
前提：数组有序
BinarySearch.java
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import java.util.Arrays;
public class BinarySearch {
public static int rank(int key, int[] a) {
int lo = 0;
int 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;
}
public static void main(String[] args) {
int[] whitelist= In.readInts(args[0]);
Arrays.sort(whitelist);
while(!StdIn.isEmpty()){
int key = StdIn.readInt();
if(rank(key,whitelist) == -1){
StdOut.println(key);
}
}
}
}
- stdlib.jar 下载
- alg4.jar 下载
- 运行此程序的步骤：
- 运行程序（为了方便，把BinarySearch.java 、largeW.txt 、largeT.txt放在同一个目录）
- 编译
javac -Djava.ext.dirs=E:\code\javacode\alg4th BinarySearch.java
- 运行
java -Djava.ext.dirs=E:\code\javacode\alg4th -cp ./ BinarySearch tinyW.txt < tinyT.txt
注意：关于-Djava.ext.dirs参考
初学Java的人经常遇到的一个问题是：如果一个程序依赖某个文件夹下的一堆jar包，那么启动它的时候就需要在java -cp参数后面一个一个的加上jar包的名称，很不方便。比如主程序类叫Main，在目录lib下有aaa.jar,bbb.jar,ccc.jar，则需要输入以下命令才能执行 (linux系统下用冒号，windows下用分号)：
java -cp lib/aaa.jar;lib/bbb.jar;/lib.ccc.jar Main
如果jar包少，倒也不是很麻烦，但如果依赖的jar包数量很多的话，一个个的输就比较麻烦了，当然我们也可以借助一些脚本或者Ant来实现自动化，但总觉得杀鸡焉用牛刀，反而把事情弄麻烦了。我自己是这样解决的:
java -Djava.ext.dirs=./lib -cp ./bin Main (假设主程序类Mian.class放在bin目录下)
说明：
BinarySearch 从largeW.txt中读入数据，存入whitelist数组中，然后将largeT.txt的数字重定向到控制台。
先把largeW.txt中的数排序，然后用二分查找，找出largeT.txt中的数字是否存在largeW.txt中，不存在就输出。
在Java程序中创建一个数组需要三步：
- 声明数组的名字和类型；
- 创建数组；
- 初始化数组元素。
典型的数组处理代码，典型的静态方法实现
/*
** 典型的数组处理代码
*/
//求数组的最大值
public double findMaxFromDoubleArray(double[] a) {
double max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) max = a[i];
}
return max;
}
//计算数组元素的平均值
public double calcAvg(double[] arr){
int N=arr.length;
double sum = 0.0;
for(int i=0;i<N;i++){
sum+=arr[i];
}
return sum/N;
}
//复制数组
public double[] copyArray(double[] arr){
int N=arr.length;
double[] b=new double[N];
for(int i=0;i<N;i++){
b[i]=arr[i];
}
return b;
}
//颠倒数组元素的顺序
public double[] reverseArray(double[] arr){
int N=arr.length;
for(int i=0;i<N/2;i++){
double tmp=arr[i];
arr[i]=arr[N-i-1];
arr[N-i-1]=tmp;
}
return arr;
}
//矩阵相乘
public double[][] mul(double[][] a,double[][] b){
int N=a.length;
double[][] c=new double[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
c[i][j]=a[i][k]*b[k][j];
}
}
}
return c;
}
/*
*典型静态方法实现
*/
//计算一个整数的绝对值
public static int abs(int x){
if(x<0) return -x;
else return x;
}
//计算一个浮点数的绝对值
public static double abs(double x){
if(x<0.0) return -x;
else return x;
}
//判断一个数是否为负数
public static boolean isPrime(int N){
if(N<2) return false;
for(int i=2;i*i<N;i++){
if(N%i==0) return false;
}
return true;
}
//计算平方根（牛顿迭代法）
public static double sqrt(double c){
if(c<0) return Double.NaN;
double err=1e-15;
double t=c;
while(Math.abs(t-c/t)>err*t){
t=(c/t+t)/2.0;
}
return t;
}
//计算直角三角形的斜边
public static double hypotenuse(double a,double b){
return Math.sqrt(a*a+b*b);
}
//计算调和级数
public static double H(int N){
double sum = 0.0;
for(int i=1;i<=N;i++){
sum+=1.0/i;
}
return sum;
}
编写递归代码时最重要的有以下三点:
- 递归总有一个最简单的情况---方法的第一条语句总是一个包含return的条件语句。
- 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。在下面的代码中，第四个参数和第三个参数的差值一直在缩小。
- 递归调用的父问题和尝试解决的子问题之间不应该有交集。在下面的代码中，有个子问题个字操作的数组部分是不同的。
public static int rank(int key, int[] a) {
return rank(key, a, 0, a.length - 1);
}
public static int rank(int key, int[] a, int lo, int hi) {
//
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank(key, a, lo, mid - 1);
else if (key > a[mid]) return rank(key, a, mid + 1, hi);
else return mid;
}
使用 Idea运行程序
private static String[] readDataFromFile(String fileName) throws Exception {
/*
*从data.in中读取数据，然后把数据转换成Integer(包装了有Comparable接口)
*/
URL url = Merge2.class.getClassLoader().getResource(fileName);
File file = new File(url.getPath());
Scanner sc = new Scanner(file);
String str = sc.nextLine();
return str.split(" ");
}
在主函数中读取只需要使用：
String[] ss = readDataFromFile("ch02/tiny.txt");
注意：
- 需要在maven工程中，resources文件夹下，新建一个和要运行的类同样的目录存放要读入的文件。
- idea中选择运行方式为Debug方式。
