y7## Java基礎(chǔ)

數(shù)組

創(chuàng)建數(shù)組

1. 聲明數(shù)組的類型和名字
2. 創(chuàng)建數(shù)組
3. 初始化數(shù)組

double[] a; //聲明數(shù)組
a= new double[N];//創(chuàng)建數(shù)組
for(int i =0;i<N;i++){
    a[i] = 0.0
}//初始化數(shù)組
double[] a = new double[N];//簡(jiǎn)寫

二維數(shù)組

靜態(tài)方法

調(diào)用

1. 方法的參數(shù)按值傳遞
   參數(shù)變量的初始值是由調(diào)用方提供的，方法處理的是參數(shù)的值而非參數(shù)本身
2. 方法名可以被重載
   重寫是子類的方法覆蓋父類的方法，要求方法名和參數(shù)都相同
   重載是在同一個(gè)類中的兩個(gè)或兩個(gè)以上的方法，擁有相同的方法名，但是參數(shù)卻不相同，方法體也不相同，最常見(jiàn)的重載的例子就是類的構(gòu)造函數(shù)，可以參考API幫助文檔看看類的構(gòu)造方法
3. 方法只能返回一個(gè)值
   返回被執(zhí)行的第一條語(yǔ)句的返回值
4. 返回值可以是void

遞歸

API

Math的參數(shù)都是double類型，返回值也是double，因此可以將它們看做是double的擴(kuò)展

字符串

1. "+"可以拼接字符串
2. 類型轉(zhuǎn)換
   paseInt() toString() parseDouble()

i/o

標(biāo)準(zhǔn)輸出(StdOut)

printin（）附加一個(gè)換行符
printf()格式化輸出

命令行語(yǔ)句

javac .java 編譯java文件
java .class 運(yùn)行Java程序

格式化輸出

printf()有兩個(gè)參數(shù)

1. 格式化字符
   %跟著字符的轉(zhuǎn)換代碼(d(十進(jìn)制)，f(浮點(diǎn)型)，s(字符串))，在%和代碼之間可以添加一個(gè)整數(shù)表示輸出字符串的長(zhǎng)度，還可以插入一個(gè)小數(shù)點(diǎn)表示轉(zhuǎn)換后double保留的位數(shù)或是string字符串截取的長(zhǎng)度。\n為換行
2. 要輸出的變量

標(biāo)準(zhǔn)輸入(StdIn)

Api

1. isEmpty 沒(méi)有剩余值就返回true，有就返回false
2. readInt
3. readDouble
   ...

基于文件的輸入輸出(In/Out)

public calss In

1. readInts()
2. readDoubles()
3. readString()
   public class Out
4. write(int[])
5. write(double[])
6. write(String[])

標(biāo)準(zhǔn)繪圖庫(kù)(StdDrw)

注意

1. for()頭部的代碼和主體代碼是一個(gè)作用域，while不是
2. 聲明數(shù)組 int[] a ,int a[]
3. ptintIn(in[] a)輸出的是他的地址
4. 靜態(tài)方法不能將另一個(gè)靜態(tài)方法做參數(shù)

Week 1 union-find并查集問(wèn)題

知識(shí)點(diǎn)

1. 貪心算法 greedy algorithm
2. connected component 連通組件(圖論)

快速排序的Java實(shí)現(xiàn)

package com.algs4;

public class QuickFind {
    private int [] id;
    //set id of each object to itself
    public QuickFind(int N){
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }
    //check weather p and q in same component 
    public boolean connect(int p,int q){
        return id[p] == id [q]; 
    }
    //change all entries with id[p] to id[q]
    public void union(int p, int q){
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pid) {
             id[i] = qid;
            }
        }
    }
}
//o(n^2)

但是quickfind對(duì)于數(shù)據(jù)量很大的數(shù)據(jù)來(lái)說(shuō)就太慢了
優(yōu)化1: 快速合并的替代替代算法 ‘Lazy approach’
把上面的數(shù)據(jù)結(jié)構(gòu)中的一組數(shù)看做“樹”

public class Quickunion {
    private int[] id;
    //set object to item
    public Quickunion(int N){
        for (int i = 0; i < N; i++) {
            id = new int[N];
            id[i] = i;
        }
    }
    //通過(guò)回朔，尋找根節(jié)點(diǎn)，id[i] = i;就是根節(jié)點(diǎn),如果不是，就把i在樹上上移一層，把i設(shè)為i的id
    private int root(int i){
        while(i != id[i]) id[i] = i;
        return i;
    }
    //判斷根節(jié)點(diǎn)是否相等
    public boolean connect(int p,int q){
        return root(p) == root (q);
    }
    public void union(int p,int q){
        int i = root(p);
        int j = root(q);
        id[i] = i;
    }
}

quickunion有時(shí)候快，但有時(shí)候太慢了，因?yàn)闃涮吡?。查找操作代價(jià)太大了，可能要回朔一顆瘦長(zhǎng)的樹，每個(gè)對(duì)象只是指向下一個(gè)節(jié)點(diǎn)，對(duì)子節(jié)點(diǎn)進(jìn)行一次查找，就要回朔整個(gè)樹，操作次數(shù)多了就滿了

上面兩種都不支持巨大的連通性問(wèn)題

新的:quickunionimprovement

這時(shí)引入了一種新的方法，叫帶權(quán)(weighting),在執(zhí)行快速合并算法的時(shí)候執(zhí)行一些操作避免很深的樹，如果將大樹和小樹合并的時(shí)候，要避免把大樹放在下面，避免得到更高的樹。
實(shí)現(xiàn):跟蹤每棵樹中對(duì)象的個(gè)數(shù)，然后我們會(huì)使小樹的根節(jié)點(diǎn)作為大樹的子節(jié)點(diǎn)。這樣樹的深度最多也只有四層
維護(hù)一個(gè)sz數(shù)組，在union操作中比較sz的大小，然后合并，時(shí)間復(fù)雜度為 lg(n)

public class QuickunionIm {
    private int[] id;
    private int[] sz; //維護(hù)一個(gè)sz數(shù)組，在union操作中比較sz的大小，然后合并
    //set object to item
    public QuickunionIm(int N){
        for (int i = 0; i < N; i++) {
            id = new int[N];
            id[i] = i;
        }
    }
    //通過(guò)回朔，尋找根節(jié)點(diǎn)，id[i] = i;就是根節(jié)點(diǎn),如果不是，就把i在樹上上移一層，把i設(shè)為i的id
    private int root(int i){
        while(i != id[i]) id[i] = i;
        return i;
    }
    //判斷根節(jié)點(diǎn)是否相等
    public boolean connect(int p,int q){
        return root(p) == root (q);
    }
    public void union(int p,int q){
        int i = root(p);
        int j = root(q);
        if (i == j) return ;
        if (sz[i] < sz[j]){
            id[i] = j;sz[j] += sz[i]; 
        }
        else{
            id[j] = i; sz[i] += sz[j];
        }
    }
}

improve2

cath compression 路徑壓縮
回溯一次路徑找到根節(jié)點(diǎn)，然后再回溯將樹展平,時(shí)間復(fù)雜度是接近線性的，那是否有時(shí)間復(fù)雜度為線性的呢？但最后有人證明合并算法沒(méi)有線性的

//add second loop to root() to set the id[] of each examined node to root
public class Quickunionim2 {
    private int[] id;
    private int root(int i){
        while( i != id[i]){
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
}

并查集算法的應(yīng)用

滲濾（percolation） 上下是存在開放位，且聯(lián)通的,系統(tǒng)是否滲透的p的闕值十分陡峭，要求那個(gè)值必須用計(jì)算機(jī)仿真，蒙特卡洛仿真。

算法分析

FFT 快速傅里葉變換算法，將算法信號(hào)的N個(gè)采樣波形分為若干周期分量。DVD和JPEG的基礎(chǔ)，將復(fù)雜度從N^2將為N*logN

3sum問(wèn)題

簡(jiǎn)單的n^3

public class three_SUM {
    public static int count(int[] a){
        int N = a.length;
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i+1; j < a.length; j++) {
                for (int j2 = j+1; j2 < a.length; j2++) {
                    if (a[i] + a[j] +a[j2] == 0) {
                        count ++;
                    }
                }
            }
        }
        return count;
    }
    public void main(String[] args){
        int[] a = In.readInts(args[0]);
        StdOut.println(count(a));
        } 
}

n^3 -> n^2longn

Java標(biāo)準(zhǔn)庫(kù)里面有一個(gè)秒表類，可以計(jì)算用掉的時(shí)間

Stopwatch stopwatch = new Stopwatch();
double time = stopwatch.elapseTime();

log-log坐標(biāo)系的的斜率為B，則正比于 N^b

一般的時(shí)間復(fù)雜度

1. 常數(shù) 沒(méi)有循環(huán)
2. logN 被分成兩半(二叉樹查找) 時(shí)間增長(zhǎng)也是常數(shù)
3. N 遍歷了所有元素 1SUM
4. NlogN 分治法 ——>并歸排序
5. N^2 兩次遍歷
6. 2^n

type of analyses

1. 總考慮最壞的case
2. 總考慮最好的case

~ 表示近似模型

1. Θ記號(hào)就是表示增長(zhǎng)階數(shù)的方法 Θ(N^{2)就是某個(gè)常數(shù)乘以N}2的簡(jiǎn)寫。它的上下界都是常數(shù)乘以N^2。這就是我們實(shí)際用來(lái)對(duì)算法分類的記號(hào)
2. 接下來(lái)是O記號(hào)，它是算法性能的上界比如O(N^{2)就表示當(dāng)N增長(zhǎng)時(shí)，運(yùn)行時(shí)間小于某個(gè)常數(shù)乘以N}2
3. Ω用來(lái)表示下界，Ω(N^{2)表示當(dāng)N增長(zhǎng)時(shí)運(yùn)行時(shí)間比某個(gè)常數(shù)乘以N}2大。

內(nèi)存

8個(gè)比特是一個(gè)字節(jié)。一百萬(wàn)比特是2的20次方個(gè)，十億比特是2的30次方我們通常使用2^20表示兆字節(jié)MB?，F(xiàn)在老的計(jì)算機(jī)我們用了很多年的32位系統(tǒng)，里面的指針是4個(gè)字節(jié)的。近幾年我們基本都遷移到了新的計(jì)算模型，機(jī)器是64位的 指針是8個(gè)字節(jié)。

1. bollan只占一個(gè)比特
2. 字符占兩個(gè)字節(jié)，16位的字符也就是16比特
3. 普通int整型是四個(gè)字節(jié)或者32位。
4. 單精度浮點(diǎn)型也是4個(gè)字節(jié)。
5. 長(zhǎng)整型和雙精度浮點(diǎn)型是8個(gè)字節(jié) 大多數(shù)應(yīng)用中，我們使用雙精度浮點(diǎn)型表示浮點(diǎn)數(shù)，普通整型表示整數(shù)
6. 對(duì)于數(shù)組，需要一定量的額外空間加上，如果有N個(gè)元素，基本類型的空間開支乘以N 所以長(zhǎng)度為N的雙精度浮點(diǎn)型數(shù)組需要的空間是8N+24。
7. 二維數(shù)組需要的空間近似于8MN，額外空間還有一項(xiàng)但是對(duì)于大M和N這個(gè)式子就很準(zhǔn)確了。
8. 引用的開銷還有典型實(shí)現(xiàn)中內(nèi)置的用來(lái)對(duì)齊的空間使得每個(gè)對(duì)象占據(jù)的空間是8字節(jié)的倍數(shù) 例如，如果有一個(gè)日期對(duì)象，它有三個(gè)整型實(shí)例變量這個(gè)對(duì)象總共占據(jù)32字節(jié)。每個(gè)整型占據(jù)4個(gè)字節(jié)對(duì)象額外空間占16個(gè)字節(jié)，為了對(duì)齊需要4個(gè)字節(jié)，所以總共占32個(gè)字節(jié)

數(shù)據(jù)抽象

java編程主要是通過(guò)class構(gòu)建被稱為引用類型的數(shù)據(jù)類型，也被稱為oop，也就是面向?qū)ο缶幊蹋幢３至四硞€(gè)數(shù)據(jù)類型的實(shí)體。
數(shù)據(jù)抽象(ADT)是一種能對(duì)使用者隱藏?cái)?shù)據(jù)表示的數(shù)據(jù)類型。他的特點(diǎn)在于將數(shù)據(jù)和函數(shù)實(shí)現(xiàn)了關(guān)聯(lián)，我們?cè)谑褂脭?shù)據(jù)類型時(shí)更加注重API操作；在實(shí)現(xiàn)數(shù)據(jù)類型時(shí)，我們專注于數(shù)據(jù)本身以及對(duì)數(shù)據(jù)的操作。
在這門課中我們要學(xué)會(huì)在不修改用例代碼的情況下，用另一種算法替換并對(duì)實(shí)現(xiàn)性能提升

基本數(shù)據(jù)類型的算法和數(shù)據(jù)結(jié)構(gòu)

stack and queues and bag(棧和隊(duì)列和背包)

stack(棧)

后入先出 （FIFO）

public class stack<item>
    stack()  創(chuàng)建一個(gè)新棧
    void push （入棧 ） 插入元素  
    item pop （出棧）除去元素
    boolean isEmpty() 棧是否為空
    int size() 棧中元素的數(shù)量

queue（隊(duì)列）

先入先出 下壓（LIFO）

public class queue<item>
    Queue() 創(chuàng)建一個(gè)新隊(duì)列
    enqueue()（入隊(duì)）加入元素 
    dequeue()  (出隊(duì))除去元素 
    boolean isEmpty() 是否為空
    int size() 元素的數(shù)量

bag (背包)

public class Bag<item>
    Bag()  創(chuàng)建一個(gè)新背包
    void add(Item item)  添加一個(gè)元素
    boolean isEmpty() 是否為空
    int size() 元素

泛型和迭代

泛型

集合類數(shù)據(jù)抽象的一個(gè)關(guān)鍵特性就是我們可以用它儲(chǔ)存任意類型的數(shù)據(jù)。java里面有一種特殊的機(jī)制能完成這項(xiàng)工作，我們稱之為泛型,也叫做參數(shù)化類型。
上面的API當(dāng)中類名后的<item>將item定義為一個(gè)類型參數(shù)，他是一個(gè)占位符，表示將使用某個(gè)數(shù)據(jù)類型?？梢詫tack<item>理解為某個(gè)元素的棧。

Stack<String> stack = new Stack<String>();
stack .push('Test');
Stack next = stack.pop();

自動(dòng)裝箱

類型參數(shù)都必須實(shí)例化為引用類型，因此JAVA有一種特殊的機(jī)制（類型轉(zhuǎn)換）使泛型代碼處理原始數(shù)據(jù)類型。在處理 賦值語(yǔ)句，方法的參數(shù)和算數(shù)邏輯表達(dá)式時(shí)候，java會(huì)在引用類型和原始類型之間進(jìn)行轉(zhuǎn)換。