algs001-《算法》4th笔记

《算法》4th笔记

第一章基础

利用这段时间，借助这本大作把该补的全部补上。

//  本书以Java为例,一个典型的Java类
import package(packageName);
public(optional) class ClassName extends FatherClass implement InterfaceName｛

  构造函数；（默认自动创建）

  static 类变量；
  static 类方法；

  成员变量；（实例变量）
  成员函数；（成员方法）
｝

从一个计数器类开始－ Counter
当我们声明一个Counter类型的变量时，发生了什么？

1	Counter heads;

对象是能承接数据类型的值的实体，具有以下三个特征：状态标示和行为

1
2
3

对象的状态  | 数据类型中的值
对象的标识  | 能将每个对象区分，可以理解为内存中的位置
对象的行为  | 数据类型的操作

对象的表示

基础部分就不按照书上介绍的来了，有其他oop经验，快速入手分将以下问题各个击破即可开始本书的阅读，至于继承多态流程控制之类的就不废话了：

基础观感

1. 没有什么比直接上代码给合适的说明这个问题了：


public class HelloJava {

  public static void main(String[] args) {

    System.Out.println("Hello World");
  }
}

文件保存为 HelloJava.java，源文件名必须和类名一致即 ClassName.java
编译：

javac HelloJava.java

编译完成，对应目录之下生成HelloJava.class文件

运行：在对应的目录之下有java虚拟机运行.class文件

java HelloJava

可以看到程序入口就是public static void main(String[] args)方法
一个源文件可以有多个Class，但只能有一个public的

2. 修饰符

Java中的修饰符根所有oop设计一样，有访问修饰符和非访问修饰符2种
主要要说明的是非访问修饰符：

static : 静态变量和静态方法的修饰符，也就是用于创建类方法,类变量，所声明自然是在静态区，不管多少对象，全局一份不多余分配
final : 不同情况有一些差别，但总体是有表达“这是无法改变的意思”，细微的差别常常令人困惑

三种使用final的情况：数据，方法和类

final 数据 - 告知编译器一块数据是恒定不变的

同public + static配合作为全局常量，并且变量名要大写和初始化，eg：
static final PRICE
1
2
3
4
> 如果是对象的final了,表示引用的恒定不变，eg：
> ```java
  final ClassName a = new ClassName();
  a = new ClassName(); // Error: Cannot change reference
final方法－可被继承但不能修改，private默认会带上final

final类－类不可被继承

abstract : 抽象的自身都不能实现，抽象类也可以包含非抽象方法，但抽象方法有一个那这个类就必须是抽象类，一旦子类继承了就需要全部实现

还有其他线程相关的修饰符暂且搁下

类的设计：如计数器Counter的设计

Stream，File及IO

基本都在Java.io中

1 控制台IO － `System.in` `System.out`

import java.io.*;

public class IODemo2 {
        public static void main(String[] args) throws IOException {
            // read() 读取字符
//            IODemo2.charRead();
            // readLine() 读取字符串
            IODemo2.stringRead();
        }

        protected static void charRead() throws IOException{
            char c;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            System.out.println("请输入文字，并以'q'结束");
            do {
                    c = (char) br.read();
                    System.out.println(c);
            } while(c != 'q');
        }

        protected static void stringRead() throws IOException{
            String str;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            System.out.println("请输入字符串，并以“q”结束");
            do {
                str = br.readLine();
                System.out.println(str);
                } while(!str.equals("q"));
        }
}

虽然与read()对应的是write(),但都习惯使用更方便的print()，当然要是硬要用System.out.write('a')输出字符‘a’的话也可以的

2 文件IO

文件的io,先是Java中系统文件读写包，还是看例子

import java.io.*;

public class FileStreamDemo {
    public static void main (String[] avgs) throws IOException {
//        FileStreamDemo.fileWriter();
        FileStreamDemo.fileReader();
    }

    // 写入文件
    protected static void fileWriter() throws IOException {

        // 1 构建FileOutputStream对象，如果没有文件会自动创建
        File f = new File("HelloJava.txt");
        FileOutputStream fop = new FileOutputStream(f);

        // 2 构建指定编码的OutputStreamWriter
        OutputStreamWriter writer = new OutputStreamWriter(fop, "UTF-8");

        writer.append("输入内容：\r\n");

        writer.append("hello java，this has been write to file！ ");

        writer.close();
        fop.close();
    }

    // 读文件
    protected static void fileReader() throws IOException {

        // 1 构建FileInputStream对象，如果没有文件会自动创建
        File f = new File("HelloJava.txt");
        FileInputStream fip = new FileInputStream(f);

        // 2 构建指定编码的InputStreamReader
        InputStreamReader reader = new InputStreamReader(fip, "UTF-8");

        // 3 写入buffer
        StringBuffer sb = new StringBuffer();

        while(reader.ready()) {
            sb.append((char)reader.read());
        }

        // 打印
        System.out.println(sb.toString());

        reader.close();

        fip.close();
    }
}

                            ｜--
      ｜－－ OutputStream－－｜--
      ｜                    ｜--
      ｜
Object
      ｜
      ｜                    ｜--
      ｜－－ InputStream －－｜ --
                            ｜--

3 本书中的IO

本书使用的是Wayne为课程专门提供的StdIn和StdOut两个包以及In``Out等类，都在algs4.jar中包含
提供的包简化了文件IO的操作，可使用命令行重定向指定文件的输入输出,还可以管道输入，eg：
命令行的重定向和管道

需要其他API，可自行查找，下面给出一个用二分法,做白名单过滤的Demo

import java.util.Arrays;

public class BinarySearch {

    /**
     * This class should not be instantiated.
     */
    private BinarySearch() { }

    public static int indexOf(int[] a, int key) {
        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 int rank(int key, int[] a) {
        return indexOf(a, key);
    }

    public static void main(String[] args) {
        // 1 从文件读取整数放倒数组
        In in = new In(args[0]);
        int[] whitelist = in.readAllInts();   

        // 2 数组排序
        Arrays.sort(whitelist);

        // 3 从终端输入要查询的数字key，如果不在白名单中就输出
        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            if (BinarySearch.indexOf(whitelist, key) < 0)
                StdOut.println(key);
        }

        // - 打印出输入的对照白名单文件
        System.out.printf(" totol length: %d  \n  ", whitelist.length);
        for (int i = 0; i < whitelist.length; i ++) {
            System.out.println(whitelist[i]);
        }
    }

在用小数据测试时，可以打印输出，要是大文件就别作了
二分法，先排序，这里使用Arrays.sort()排序
查找改为使用递归，看起来会更加简洁和优雅，故将现有的rank()函数替换为：


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 a[mid];
}

递归就是数学归纳法,并且：

递归总要有最简单的情况

递归总是趋近于一个更加简单的情况

递归嵌套时，各个子问题不能根父问题不能有交集