y7## Java基礎(chǔ)
數(shù)組
創(chuàng)建數(shù)組
- 聲明數(shù)組的類型和名字
- 創(chuàng)建數(shù)組
- 初始化數(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];//簡寫
二維數(shù)組
靜態(tài)方法
調(diào)用
- 方法的參數(shù)按值傳遞
參數(shù)變量的初始值是由調(diào)用方提供的，方法處理的是參數(shù)的值而非參數(shù)本身 - 方法名可以被重載
重寫是子類的方法覆蓋父類的方法，要求方法名和參數(shù)都相同
重載是在同一個類中的兩個或兩個以上的方法，擁有相同的方法名，但是參數(shù)卻不相同王悍，方法體也不相同，最常見的重載的例子就是類的構(gòu)造函數(shù)，可以參考API幫助文檔看看類的構(gòu)造方法 - 方法只能返回一個值
返回被執(zhí)行的第一條語句的返回值 - 返回值可以是void
遞歸
API
Math的參數(shù)都是double類型纲熏，返回值也是double，因此可以將它們看做是double的擴展
字符串
- "+"可以拼接字符串
- 類型轉(zhuǎn)換
paseInt() toString() parseDouble()
i/o
標(biāo)準(zhǔn)輸出(StdOut)
printin（）附加一個換行符
printf()格式化輸出
命令行語句
javac .java 編譯java文件
java .class 運行Java程序
格式化輸出
printf()有兩個參數(shù)
- 格式化字符
%跟著字符的轉(zhuǎn)換代碼(d(十進(jìn)制)，f(浮點型)局劲，s(字符串))勺拣，在%和代碼之間可以添加一個整數(shù)表示輸出字符串的長度，還可以插入一個小數(shù)點表示轉(zhuǎn)換后double保留的位數(shù)或是string字符串截取的長度鱼填。\n為換行 - 要輸出的變量
標(biāo)準(zhǔn)輸入(StdIn)
Api
- isEmpty 沒有剩余值就返回true药有，有就返回false
- readInt
- readDouble
...
基于文件的輸入輸出(In/Out)
public calss In
- readInts()
- readDoubles()
- readString()
public class Out - write(int[])
- write(double[])
- write(String[])
標(biāo)準(zhǔn)繪圖庫(StdDrw)
注意
- for()頭部的代碼和主體代碼是一個作用域，while不是
- 聲明數(shù)組 int[] a ,int a[]
- ptintIn(in[] a)輸出的是他的地址
- 靜態(tài)方法不能將另一個靜態(tài)方法做參數(shù)
Week 1 union-find并查集問題
知識點
- 貪心算法 greedy algorithm
- connected component 連通組件(圖論)
快速排序的Java實現(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對于數(shù)據(jù)量很大的數(shù)據(jù)來說就太慢了
優(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;
}
}
//通過回朔苹丸，尋找根節(jié)點愤惰，id[i] = i;就是根節(jié)點,如果不是，就把i在樹上上移一層赘理，把i設(shè)為i的id
private int root(int i){
while(i != id[i]) id[i] = i;
return i;
}
//判斷根節(jié)點是否相等
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有時候快宦言，但有時候太慢了，因為樹太高了商模。查找操作代價太大了奠旺，可能要回朔一顆瘦長的樹，每個對象只是指向下一個節(jié)點施流，對子節(jié)點進(jìn)行一次查找响疚，就要回朔整個樹，操作次數(shù)多了就滿了
上面兩種都不支持巨大的連通性問題
新的:quickunionimprovement
這時引入了一種新的方法嫂沉，叫帶權(quán)(weighting),在執(zhí)行快速合并算法的時候執(zhí)行一些操作避免很深的樹稽寒，如果將大樹和小樹合并的時候，要避免把大樹放在下面趟章，避免得到更高的樹杏糙。
實現(xiàn):跟蹤每棵樹中對象的個數(shù)，然后我們會使小樹的根節(jié)點作為大樹的子節(jié)點蚓土。這樣樹的深度最多也只有四層
維護一個sz數(shù)組宏侍，在union操作中比較sz的大小，然后合并蜀漆，時間復(fù)雜度為 lg(n)
public class QuickunionIm {
private int[] id;
private int[] sz; //維護一個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;
}
}
//通過回朔确丢，尋找根節(jié)點绷耍，id[i] = i;就是根節(jié)點,如果不是，就把i在樹上上移一層鲜侥，把i設(shè)為i的id
private int root(int i){
while(i != id[i]) id[i] = i;
return i;
}
//判斷根節(jié)點是否相等
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é)點褂始，然后再回溯將樹展平,時間復(fù)雜度是接近線性的，那是否有時間復(fù)雜度為線性的呢描函？但最后有人證明合并算法沒有線性的
//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的闕值十分陡峭狐粱，要求那個值必須用計算機仿真，蒙特卡洛仿真胆数。
算法分析
FFT 快速傅里葉變換算法肌蜻，將算法信號的N個采樣波形分為若干周期分量。DVD和JPEG的基礎(chǔ)必尼，將復(fù)雜度從N^2將為N*logN
3sum問題
簡單的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)庫里面有一個秒表類蒋搜，可以計算用掉的時間
Stopwatch stopwatch = new Stopwatch();
double time = stopwatch.elapseTime();
log-log坐標(biāo)系的的斜率為B，則正比于 N^b
一般的時間復(fù)雜度
- 常數(shù) 沒有循環(huán)
- logN 被分成兩半(二叉樹查找) 時間增長也是常數(shù)
- N 遍歷了所有元素 1SUM
- NlogN 分治法 ——>并歸排序
- N^2 兩次遍歷
- 2^n
type of analyses
- 總考慮最壞的case
- 總考慮最好的case
~ 表示近似模型
- Θ記號就是表示增長階數(shù)的方法 Θ(N2)就是某個常數(shù)乘以N2的簡寫判莉。它的上下界都是常數(shù)乘以N^2齿诞。這就是我們實際用來對算法分類的記號
- 接下來是O記號，它是算法性能的上界比如O(N2)就表示當(dāng)N增長時骂租，運行時間小于某個常數(shù)乘以N2
- Ω用來表示下界，Ω(N2)表示當(dāng)N增長時運行時間比某個常數(shù)乘以N2大斑司。
內(nèi)存
8個比特是一個字節(jié)渗饮。一百萬比特是2的20次方個，十億比特是2的30次方我們通常使用2^20表示兆字節(jié)MB∷薰危現(xiàn)在老的計算機我們用了很多年的32位系統(tǒng)互站，里面的指針是4個字節(jié)的。近幾年我們基本都遷移到了新的計算模型僵缺，機器是64位的 指針是8個字節(jié)胡桃。
- bollan只占一個比特
- 字符占兩個字節(jié)，16位的字符也就是16比特
- 普通int整型是四個字節(jié)或者32位磕潮。
- 單精度浮點型也是4個字節(jié)翠胰。
- 長整型和雙精度浮點型是8個字節(jié) 大多數(shù)應(yīng)用中，我們使用雙精度浮點型表示浮點數(shù)自脯，普通整型表示整數(shù)
- 對于數(shù)組之景，需要一定量的額外空間加上，如果有N個元素膏潮，基本類型的空間開支乘以N 所以長度為N的雙精度浮點型數(shù)組需要的空間是8N+24锻狗。
- 二維數(shù)組需要的空間近似于8MN，額外空間還有一項但是對于大M和N這個式子就很準(zhǔn)確了焕参。
- 引用的開銷還有典型實現(xiàn)中內(nèi)置的用來對齊的空間使得每個對象占據(jù)的空間是8字節(jié)的倍數(shù) 例如轻纪，如果有一個日期對象，它有三個整型實例變量這個對象總共占據(jù)32字節(jié)叠纷。每個整型占據(jù)4個字節(jié)對象額外空間占16個字節(jié)刻帚，為了對齊需要4個字節(jié)，所以總共占32個字節(jié)
數(shù)據(jù)抽象
java編程主要是通過class構(gòu)建被稱為引用類型的數(shù)據(jù)類型讲岁，也被稱為oop我擂，也就是面向?qū)ο缶幊坛囊裕幢３至四硞€數(shù)據(jù)類型的實體。
數(shù)據(jù)抽象(ADT)是一種能對使用者隱藏數(shù)據(jù)表示的數(shù)據(jù)類型校摩。他的特點在于將數(shù)據(jù)和函數(shù)實現(xiàn)了關(guān)聯(lián)看峻，我們在使用數(shù)據(jù)類型時更加注重API操作；在實現(xiàn)數(shù)據(jù)類型時衙吩，我們專注于數(shù)據(jù)本身以及對數(shù)據(jù)的操作互妓。
在這門課中我們要學(xué)會在不修改用例代碼的情況下，用另一種算法替換并對實現(xiàn)性能提升
基本數(shù)據(jù)類型的算法和數(shù)據(jù)結(jié)構(gòu)
stack and queues and bag(棧和隊列和背包)
stack(棧)
后入先出 （FIFO）
public class stack<item>
stack() 創(chuàng)建一個新棧
void push （入棧 ） 插入元素
item pop （出棧）除去元素
boolean isEmpty() 棧是否為空
int size() 棧中元素的數(shù)量
queue（隊列）
先入先出 下壓（LIFO）
public class queue<item>
Queue() 創(chuàng)建一個新隊列
enqueue()（入隊）加入元素
dequeue() (出隊)除去元素
boolean isEmpty() 是否為空
int size() 元素的數(shù)量
bag (背包)
public class Bag<item>
Bag() 創(chuàng)建一個新背包
void add(Item item) 添加一個元素
boolean isEmpty() 是否為空
int size() 元素
泛型和迭代
泛型
集合類數(shù)據(jù)抽象的一個關(guān)鍵特性就是我們可以用它儲存任意類型的數(shù)據(jù)坤塞。java里面有一種特殊的機制能完成這項工作冯勉，我們稱之為泛型,也叫做參數(shù)化類型。
上面的API當(dāng)中類名后的<item>將item定義為一個類型參數(shù)摹芙，他是一個占位符灼狰，表示將使用某個數(shù)據(jù)類型「『蹋可以將Stack<item>理解為某個元素的棧交胚。
Stack<String> stack = new Stack<String>();
stack .push('Test');
Stack next = stack.pop();
自動裝箱
類型參數(shù)都必須實例化為引用類型，因此JAVA有一種特殊的機制（類型轉(zhuǎn)換）使泛型代碼處理原始數(shù)據(jù)類型盈电。在處理 賦值語句蝴簇，方法的參數(shù)和算數(shù)邏輯表達(dá)式時候，java會在引用類型和原始類型之間進(jìn)行轉(zhuǎn)換匆帚。
