摘要：含有純虛擬函數(shù)的類稱為抽象類它不能生成對象不能放在等號右邊但可以聲明指向?qū)崿F(xiàn)該抽象類的具體類的指針或引用。純虛函數(shù)的意義讓所有的類對象主要是派生類對象都可以執(zhí)行純虛函數(shù)的動作但類無法為純虛函數(shù)提供一個合理的缺省實現(xiàn)。

博客鏈接

JavaNotes

Java 學(xué)習(xí)筆記

基本數(shù)據(jù)類型

// 整數(shù)
byte 1
short 2
int 4
long 8

// 浮點數(shù)
float 4
double 8

// 邏輯
boolean 1

// 字符
char 2, Unicode

Override, 覆蓋/重寫, 返回值和形參都不能改變

Overload, 重載

基本數(shù)據(jù)類型的變量, 在棧里面, 復(fù)制變量的時候, 復(fù)制的是值

引用類型的變量, 在堆, 變量只是引用, 類似于指針, 只能指向特定對象, 不能亂指, 復(fù)制變量的時候, 復(fù)制的是引用

引用類型: 數(shù)組, 類, 接口

抽象類跟接口的區(qū)別

JavaNotes

抽象類和接口的區(qū)別

抽象類, 是聲明, 抽象類不能instantiate(實例化), 也就是不能制造對象。抽象方法只聲明, 不實現(xiàn)。具體的實現(xiàn)由繼承它的子類來實現(xiàn)。

public abstract class Shape{
    // 抽象的方法, 注意沒有大括號, ()后面直接分號結(jié)尾
    // 有abstract方法的類必須是abstract
    public abstract void draw();
}

接口, 讓其他類能夠有接口的方法

public interface Cell{
    // 不需要顯示寫abstract
    void draw(Graphics g, int x, int y, int size);
}

public class Fox extends Animal implements Cell{
    @Override
    public void draw(...){
        // ...
    }

    public void run()
    {

    }
}

抽象類可以有非抽象的方法(具體實現(xiàn)), 接口是純抽象類, 只有抽象方法

一個子類只能存在一個父類, 但是可以存在多個接口。

數(shù)據(jù)模型、表現(xiàn)、控制, 三者分離

M, Model, 模型, 保存和維護數(shù)據(jù), 還可以 通知 View 進行界面的更新.

V, View, 表現(xiàn), 從 Model 獲得數(shù)據(jù), 并以此畫出表現(xiàn)(界面). View 是被動的, 只有在 Model 通知 View 之后, View才會去Model取數(shù)據(jù), 并畫出來.

C, Control, 控制, 得到用戶輸入, 以此調(diào)整數(shù)據(jù). C 和 V 并不直接交互. C只能更新Model中的數(shù)據(jù), 也就是說, 用戶在界面上所作的操作, 不會直接修改界面上的顯示. 而是先去修改后臺的數(shù)據(jù), 再由Model通知View, 再整體重畫.

創(chuàng)建線程的方式, 繼承 Thread 類, 實現(xiàn) Runnable 接口

start(), run(), stop(), destroy()

新建 --- 就緒 --- 運行 --- 阻塞 --- 運行 --- 終止

40 個 Java 多線程問題總結(jié)

Java多線程學(xué)習(xí)

Java 多線程編程

分類

ArrayIndexOutOfBoundsException
OpenFileException
AllocateMemoryException
LoadFileException

OutOfMemoryError

處理方式

try{

}
catch(ArrayIndexOutOfBoundsException e){

}

Wikipedia, GC)

某個對象在未來的程序運行中, 將不會被訪問, 就可以回收它的內(nèi)存

回收方法，策略

引用計數(shù)收集器, 當(dāng)有其他數(shù)據(jù)與其相關(guān)時則加一, 反之相關(guān)解除時減一, 最后計數(shù)為 0 的對象可以回收

跟蹤收集器, 定期對若干根儲存對象開始遍歷, 對與其相關(guān)的對象進行標(biāo)記, 最后, 沒有被標(biāo)記的對象就可以回收

鄰接鏈表，也就是hash值對應(yīng)了一個數(shù)組的下標(biāo)，然后數(shù)組的元素又是一個鏈表

負(fù)載因子超過 0.75 后, 數(shù)組會 resize() 到原來的 2 倍

Java HashMap工作原理及實現(xiàn)

HashMap 的實現(xiàn)原理

棧 stack

局部變量, 函數(shù)參數(shù)

全局/靜態(tài) 存儲區(qū)

全局變量, 靜態(tài)全局變量, 靜態(tài)局部變量

若沒有手動初始化, 則會自動初始化為0

堆 heap

new --- delete / malloc --- free

常量存儲區(qū)

存放字符串常量和const修飾的全局變量

預(yù)處理Pre Pocess：包含頭文件, 條件編譯, 宏替換

編譯：檢查語法錯誤. 檢查無誤后, 將代碼翻譯成匯編語言

匯編：將匯編語言轉(zhuǎn)化成二進制代碼表示的目標(biāo)文件. 每一個源文件(.c)產(chǎn)生一個目標(biāo)文件(.obj)

鏈接：與庫函數(shù)進行鏈接, 形成可執(zhí)行文件

整體過程

預(yù)處理 --- 編譯 --- 匯編 --- 鏈接 --- 裝載 --- 運行

malloc, 分配內(nèi)存, 是在 運行 這一階段。即在 heap 上動態(tài)分配

gcc編譯程序的四個階段（預(yù)處理-編譯-匯編-鏈接）

C++ 預(yù)處理、編譯、匯編、鏈接

C語言編譯過程詳解

指向二維數(shù)組的指針

int a[4][2];
int (*p) [2];

p = a;
p[3][1];

[] 的優(yōu)先級高于 *, 所以要加括號

二級指針

void getMemory(char **p){
    *p = (char *)malloc(100);
}

int main(){
    char *str = NULL;
    getMemory(&str);
    strcpy(str, "Thurs");
    strcat(str+2, " day");

    printf("%s
", str);
    return 0;
}

首先 str 被分配了100字節(jié)的空間, 然后在 str 開頭粘貼了 Thurs, 接著, 由于 strcat 總是先找到末尾再粘貼, 所以 day 不會覆蓋 urs

正數(shù)與原碼和反碼相同。對于負(fù)數(shù), 以 -1 為例

1)先寫出原碼, `1000 0001`
2)符號位不變, 其余各位取反, `1111 1110`
3)最后 +1, `1111 1111`

數(shù)據(jù)類型在內(nèi)存中的表達形式

整數(shù)：二進制數(shù)（補碼）, 可以直接在加法器里面做加法
浮點數(shù)：要進行編碼

結(jié)構(gòu)體內(nèi)定義指針

typedef struct{
    int val;
    struct Node *lchild, *rchild;
}Node;

Node root = {1, NULL, NULL};

struct node{
    int val;
    struct Node *lchild, *rchild;
};

struct node root = {1, NULL, NULL};

const 在 * 之前, 意思是對 i 只讀

/* const 在 * 之前, 意思是 對 i 只讀
** 可以通過 *p 讀取i的值, 但不能通過 *p 修改i的值
** 另外, 指針作為函數(shù)參數(shù)時, 這樣寫 (const int * p)
*/
int i = 1;
const int * p1 = &i;
int const * p2 = &i;

const 在 * 的后面, 意思是 指針 不能指向其他地址

/* const 在 * 的后面, 意思是 指針 不能指向其他地址
** p3 被綁定到了 j, 就無法再指向其他地址
** 可以通過p3來讀寫j的值
*/
int j = 2;
int * const p3 = &j;
*p3;            // ok
*p3 = 3;        // ok

int k = 123;
p3 = &k;        // error

用法

int *a = (int *)malloc( 10*sizeof(int) )

man malloc 可以看到參數(shù)要求是(size_t size), 所以實參是(10*sizeof(int)), 表示申請到了10*4=40個字節(jié)的空間, 同樣的也可以40*sizeof(char), 或者直接寫40
可以看到返回類型是 void * , 這也就解釋了為什么要在前面加上(int *), 由此劃分空間, 來區(qū)分類型

sizeof()是靜態(tài)的, 程序編譯完成后已經(jīng)定下來, 直接填進去了, 并不會真的去做計算

int a = 1;

printf("%d
", sizeof(a++));    // 4
printf("%d
", a);        // 1, sizeof()是靜態(tài)的, 程序編譯完成后已經(jīng)定下來, 直接填進去了, 并不會真的去做a的++

printf("%d
", sizeof(a + 2.0));// 8, 已經(jīng)轉(zhuǎn)換成了double
printf("%d
", sizeof(double));    // 8
return 0;

編譯器處理方式不同

define 宏是在預(yù)處理階段展開, const 常量是編譯運行階段使用.

類型和安全檢查不同

define宏沒有類型, 不做任何類型檢查, 僅僅是展開. const常量有具體的類型, 在編譯階段會執(zhí)行類型檢查.

存儲方式不同

define宏僅僅是展開, 有多少地方使用, 就展開多少次, 不會分配內(nèi)存. const常量會在內(nèi)存中分配(堆或棧).

全局 static, 初始化為 0, 作用域是文件內(nèi)部, 放在全局/靜態(tài) 存儲區(qū), 生命周期從程序開始到程序結(jié)束

局部 static, 局部作用域

extern 全局 (extern可省略)

宏 --- 字符替換

main可以作為變量名

浮點數(shù) --- 不可以用 == 作為判斷條件

函數(shù)名前面加了 virtual 的函數(shù)叫做虛函數(shù)

用于 多態(tài) (即 動態(tài)綁定, 覆蓋Override, 運行的時候根據(jù)實例對象來調(diào)用方法)

class Animal {
public:
    void run(){
        cout << "That animal is running
";
    }
    virtual void eat(){
        cout << "That animal is eating
";
    }
};
class Dog : public Animal{
public:
    void run(){
        cout << "The dog is running
";
    }
    void eat(){
        cout << "The dog is eating
";
    }
};
int main(){
    // 父類 `Animal` 類型的 `指針` 可以管理子類對象
    // 如果方法名前面有 virtual, 則可以動態(tài)綁定
    Animal * animal = new Dog();
    animal->run(); // That animal is running, 隱藏子類方法
    animal->eat(); // The dog is eating, 子類方法覆蓋父類, 多態(tài)

    // 注意指針才可以, 普通變量形式仍然會隱藏子類方法
    Animal ani = Dog();
    ani.eat(); // That animal is eating, 隱藏子類方法
    return 0;
}

父類方法被聲明為 virtual 后, 直接/間接子類中的這個方法都會變成 virtual, 也即子類中的 virtual 可以省略, 但最好還是寫上去

什么是C++虛函數(shù)、虛函數(shù)的作用和使用方法

虛函數(shù)表

純虛函數(shù)只有聲明, 沒有實現(xiàn), 相當(dāng)于接口規(guī)范。含有純虛擬函數(shù)的類稱為抽象類, 它不能生成對象(不能放在等號右邊), 但可以聲明指向?qū)崿F(xiàn)該抽象類的具體類的指針或引用。

class Flyable {
public:
    virtual void fly() = 0; // 純虛函數(shù), 只有聲明, 后接 = 0
    virtual void run() = 0; 
};

class Bird : public Flyable{
public:
    void fly(){
        cout << "Bird can fly
"; // 子類只有實現(xiàn)純虛函數(shù)才能實例化
    }
};

class Superman : public Flyable{
public:
    void fly(){
        cout << "Superman can fly
";
    }
    void run(){
        cout << "Superman is running
";
    }
};

int main(){
    Flyable * f1 = new Bird();
    f1->fly(); // 出錯, 因為沒有實現(xiàn)所有的純虛函數(shù), 所以仍然是抽象類, 無法實例化
    Flyable f2 = new Superman();
    f2->fly(); // Superman can fly
    return 0;
}

定義純虛函數(shù)的目的在于, 使派生類僅僅只是繼承函數(shù)的接口。純虛函數(shù)的意義, 讓所有的類對象（主要是派生類對象）都可以執(zhí)行純虛函數(shù)的動作, 但類無法為純虛函數(shù)提供一個合理的缺省實現(xiàn)。所以類純虛函數(shù)的聲明就是在告訴子類的設(shè)計者, “你必須提供一個純虛函數(shù)的實現(xiàn), 但我不知道你會怎樣實現(xiàn)它”。

C++中虛函數(shù)的作用是什么？它應(yīng)該怎么用呢？

返回類型安全性

new 操作符內(nèi)存分配成功時, 返回的是對象類型的指針, 類型嚴(yán)格與對象匹配, 無須進行類型轉(zhuǎn)換, 故 new 是符合類型安全性的操作符。而 malloc 內(nèi)存分配成功則是返回 void *, 需要通過強制類型轉(zhuǎn)換將 void * 指針轉(zhuǎn)換成我們需要的類型。

類型安全很大程度上可以等價于內(nèi)存安全, 類型安全的代碼不會試圖方法自己沒被授權(quán)的內(nèi)存區(qū)域。關(guān)于 C++ 的類型安全性可說的又有很多了

細(xì)說new與malloc的10點區(qū)別

C++ 自由存儲區(qū)是否等價于堆？

vector 擴容的時候增加 50% 的容量, Java 的 ArrayList 也是如此

cpp string 字符串拼接，重載了 + 運算符，重新申請 len1 + len2 的內(nèi)存空間，然后把 s1, s2 復(fù)制進去

選擇器

// 按ID查找
document.getElementById("xxx");

// 按tagname查找
document.getElementsByTagName("xxx");

// classname
document.getElementsByClassName("xxx");

jQuery, 選擇器是 jQuery 的核心

// DOM 操作
var ele = document.getElementById("id1");
var divlist = document.getElementsByTagName("div");

// jQuery 的寫法
// 返回一個 jQuery 對象, 即若 id1 存在, 那么返回 [
...
]
// 若不存在, 則返回 []
var ele = $("#id1");

// jQuery 對象和 dom 對象相互轉(zhuǎn)化
var eledom = ele.get(0);
ele = $(eledom);

// 按 class 查找
var a = $(".red.green"); // 多個 class 時中間沒有空格

// 按屬性查找
var email = $("[name=email]"); // 找出
var passwordInput = $("[type=password]"); // 找出

var icons = $("[name^=icon]"); // 找出所有name屬性值以icon開頭的DOM
var names = $("[name$=with]"); // 找出所有name屬性值以with結(jié)尾的DOM

// 組合查找
var emailInput = $("input[name=email]");
// 找到所有 input 中的 name="email" 的屬性
// 不會找出 


// 多項選擇器(不會重復(fù)選擇)
$("p,div"); // 把
和
都選出來
$("p.red,p.green"); // 把
和
都選出來

正則表達式

`d` 數(shù)字
`w` 字母或數(shù)字
`.`  至少 1 個任意字符
`*`  至少 0 個任意字符
`d{3}` 匹配 3 個字符
`[0-9a-zA-Z\_]` 匹配一個數(shù)字, 字母或者下劃線
var re1 = /^d{11}$/;
re1.test("12345678");    // false

AJAX, Asynchronous JavaScript and XML, 意思就是用 JavaScript 執(zhí)行異步網(wǎng)絡(luò)請求

AJAX請求是異步執(zhí)行的, 也就是說, 要通過回調(diào)函數(shù)獲得響應(yīng)

function success(text) {
    var textarea = document.getElementById("test-response-text");
    textarea.value = text;
}

function fail(code) {
    var textarea = document.getElementById("test-response-text");
    textarea.value = "Error code: " + code;
}

var request = new XMLHttpRequest(); // 新建XMLHttpRequest對象
request.onreadystatechange = function () { // 狀態(tài)發(fā)生變化時, 函數(shù)被回調(diào)
    if (request.readyState === 4) { // 成功完成
        // 判斷響應(yīng)結(jié)果:
        if (request.status === 200) {
            // 成功, 通過responseText拿到響應(yīng)的文本:
            return success(request.responseText);
        } else {
            // 失敗, 根據(jù)響應(yīng)碼判斷失敗原因:
            return fail(request.status);
        }
    } else {
        // HTTP請求還在繼續(xù)...
    }
}

// 發(fā)送請求:
request.open("GET", "/api/categories");
request.send();

如何管理內(nèi)存, 垃圾回收

引用計數(shù), del對象

Unix/Linux 推薦多進程, 提供了一個 fork() 系統(tǒng)調(diào)用(System call)

pid = fork(), 調(diào)用一次返回兩次, 子進程中返回的 pid == 0, 父進程中返回的是子進程的 pid > 0, ppid = getppid() 可以得到父進程的 pid

import os
# 得到當(dāng)前進程的 pid
print( os.getpid() )
pid = os.fork()
if pid == 0:
    print("This is child process %s, parent is %s" % (os.getpid(), os.getppid()))
else:
    print("This is parent process %s, child is %s" % (os.getpid(), pid))

結(jié)果

17420
This is parent process 17420, child is 17421
This is child process 17421, parent is 17420

Windows 沒有 fork(), Python 多進程需要使用 multiprocessing

from multiprocessing import Process
import os

def proc(name):
    print("child process %s, pid = %s" % (name, os.getpid()))

p = Process( target=proc, args=("test",) )
print("child process start")
p.start()
p.join()
print("child process end")

結(jié)果

child process start
child process test, pid = 17491
child process end

創(chuàng)建子進程時, 只需要傳入待執(zhí)行函數(shù) target 和函數(shù)的參數(shù), 創(chuàng)建一個 Process 實例, 用 start() 方法啟動

join() 方法可以等待子進程結(jié)束后再繼續(xù)往下運行, 通常用于進程間的同步。

多線程. 進程是由若干線程組成的, 一個進程至少有一個線程, 線程是操作系統(tǒng)直接支持的基本執(zhí)行單元.

啟動一個線程就是把一個函數(shù)傳入并創(chuàng)建 Thread 實例, 然后調(diào)用 start() 開始執(zhí)行

import time, threading
def loop():
    print("%s is running" % threading.current_thread.name)

print( "%s is running" % threading.current_thread().name )
t = threading.Thread(target=func, name="myThread")
t.start()
t.join()
print( "%s ended" % threading.current_thread().name )

區(qū)別: 多進程中, 同一個變量, 各自有一份拷貝存在于每個進程中, 互不影響, 而多線程中, 所有全局變量都由所有線程共享, 所以, 任何一個變量都可以被任何一個線程修改, 因此, 線程之間共享數(shù)據(jù)最大的危險在于多個線程同時改一個變量, 把內(nèi)容給改亂了。

多線程共享的內(nèi)容: 虛擬地址空間,只讀代碼塊,讀、寫數(shù)據(jù), 堆(全局, 靜態(tài)), 打開的文件集合

鎖

balance = 0
def change_balance(n):
    global balance
    balance += n
    balance -= n

lock = threading.lock()

def run_thread(n):
    for i in range(10000):
        # 用之前先獲得 balance 等全局變量的獨占權(quán)
        lock.acquire()
        try:
            change_balance(n)
        finally:
            # 用完后釋放鎖
            lock.release()

Java 靜態(tài)類型語言, 編譯的時候就確定了數(shù)據(jù)類型了, 編寫代碼的時候要明確變量的數(shù)據(jù)類型

Python 動態(tài)類型語言, 運行期間才檢查數(shù)據(jù)類型

語法不一樣, Java 用大括號劃分代碼塊, Python 用縮進劃分代碼塊

Java 分號結(jié)尾, Python 不需要

結(jié)構(gòu)定義

struct Node{
public:
    int val;
    Node * next;
    Node(int x) : val(x), next(NULL) {}
};

插到第 n 個結(jié)點前面, n 從 0 開始

Node * insertBefore(Node * head, int n, int val){
    Node * p = head;
    Node * node = new Node(val);
    if( n == 0 ){
        node->next = head;
        head = node;
    }
    else{
        --n;
        while( p != NULL && n > 0 ){
            p = p->next;
            --n;
        }
        node->next = p->next;
        p->next = node;
    }

    return head;
}

插到第 n 個結(jié)點后面, n 從 0 開始

Node * insertAfter(Node * head, int n, int val){
    Node * p = head;
    Node * node = new Node(val);
    while( p != NULL && n > 0 ){
        p = p->next;
        --n;
    }

    node->next = p->next;
    p->next = node;

    return head;
}

刪除第 n 個結(jié)點, n 從 0 開始

Node * deleteAt(Node * head, int n){
    if( head == NULL ){
        return head;
    }

    if( n == 0 ){
        Node * now = head->next;
        delete head;
        return now;
    }

    --n;
    Node * pre = head;
    Node * now = head->next;
    while( now != NULL && n > 0 ){
        now = now->next;
        pre = pre->next;
        n--;
    }

    if( now != NULL ){
        pre->next = now->next;
        delete now;
    }
    return head;
}

為什么 map 用紅黑樹不用 AVL

功能、性能、空間開銷的折中結(jié)果。

AVL更平衡，結(jié)構(gòu)上更加直觀，時間效能針對讀取而言更高；維護稍慢，空間開銷較大。

紅黑樹，讀取略遜于AVL，維護強于AVL，空間開銷與AVL類似，內(nèi)容極多時略優(yōu)于AVL，維護優(yōu)于AVL。

如果插入一個node引起了樹的不平衡，AVL和RB-Tree都是最多只需要2次旋轉(zhuǎn)操作，即兩者都是O(1)；但是在刪除node引起樹的不平衡時，最壞情況下，AVL需要維護從被刪node到root這條路徑上所有node的平衡性，因此需要旋轉(zhuǎn)的量級O(logN)，而RB-Tree最多只需3次旋轉(zhuǎn)，只需要O(1)的復(fù)雜度。

其次，AVL的結(jié)構(gòu)相較RB-Tree來說更為平衡，在插入和刪除node更容易引起Tree的unbalance，因此在大量數(shù)據(jù)需要插入或者刪除時，AVL需要rebalance的頻率會更高。因此，RB-Tree在需要大量插入和刪除node的場景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

map的實現(xiàn)只是折衷了兩者在search、insert以及delete下的效率?？傮w來說，RB-tree的統(tǒng)計性能是高于AVL的。

為什么STL和linux都使用紅黑樹作為平衡樹的實現(xiàn)？

紅黑樹是 BST，且有如下規(guī)則

1) 結(jié)點是紅色或黑色
2) 根是黑色
3) 葉子是黑色結(jié)點(葉子是 NULL)
4) 紅結(jié)點必有兩個黑色孩子，也即，從根到葉子路徑上不能有連續(xù)的紅結(jié)點
5) 任一結(jié)點向下到葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(黑高度相同)

筆記

遞歸查找LCA

// LeetCode 235, 236 都適用
TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * p, TreeNode * q){
    if( root == NULL || root == p || root == q ){
        return root;
    }
    TreeNode * left = lowestCommonAncestor(root->left, p, q);
    TreeNode * right = lowestCommonAncestor(root->right, p, q);
    if( left != NULL && right != NULL ){
        return root;
    }
    else{
        return left==NULL ? right : left;
    }
}

筆記

幾個考點: 復(fù)雜度, 穩(wěn)定性, 實現(xiàn)

冒泡, 最好 O(n), 最壞 O(n^2)

// 升序
void bubble_sort(int a[], int len){
    for(int i=0; i < len; i++ ){
        for( int j = len - 1; j > i; j-- ){
            if( a[j] < a[j-1] ){
                swap(a[j], a[j-1]);
            }
        }
    }
}

int main(){
    const int len = 8;
    int a[len]={4, 2, 5, 1, 3, 2, 5, 1};

    bubble_sort(a, len);
    for( int i = 0; i < len; i++){
        cout << a[i] << "	";
    }
    return 0;
}

快排, 最壞 O(n^2), 平均 O(nlgn)

int a[MAXSIZE] = {4, 2, 6, 3, 1, 5, 7};

int partQuickSort(int left, int right){
    int i = left, j = right;
    int key = a[i];
    while( i < j ){
        while( i < j && a[j] > key ){
            j--;
        }
        if( i < j ){
            // a[j] < key, 換到左邊
            a[i++] = a[j];
        }

        while( i < j && a[i] < key ){
            i++;
        }
        if( i < j ){
            // a[i] > key, 換到右邊
            a[j--] = a[i];
        }
    }

    int mid = i;
    a[mid] = key;
    return mid;
}

/*
以a[left]為中軸key, 把所有小于key的都放到它的左邊, 大的放到右邊。
中軸的位置就固定了。
再對左邊這一塊和右邊這一塊, 做同樣的處理。
*/
void quickSort( int left, int right ){
    if(left < right){
        int mid = partQuickSort(left, right);
        quickSort(left, mid - 1);
        quickSort(mid + 1, right);
    }
}

插入, 最好 O(n), 最壞 O(n^2)

// 升序
void insert_sort(int a[], int len){
    for(int i = 1; i < len; i++ ){
        int j = i;
        int key = a[j];
        // 把 key 插到正確的位置
        while( j > 0 && a[j-1] > key ){
            a[j] = a[j-1];
            j--;
        }
        a[j]=key;
    }
}

歸并, O(n^2)

二分, 序列必須有序

// 遞歸
int bsearch(int a[], int left, int right, int key){
    if( left <= right ){
        int mid = (left + right) / 2;
        if( key < a[mid] ){
            return bsearch(a, left, mid - 1, key);
        }
        else if( key > a[mid] ){
            return bsearch(a, mid + 1, right, key);
        }
        else{
            return mid;
        }
    }
    return -1;
}

// 非遞歸
int bsearch(int a[], int left, int right, int key){
    while( left <= right ){
        int mid = (left + right) / 2;
        if( key < a[mid] ){
            right = mid - 1;
        }
        else if( key > a[mid] ){
            left = mid + 1;
        }
        else{
            return mid;
        }
    }
    return -1;
}

KMP

BM

最大連續(xù)子列和

next_permutation

最大公因數(shù) gcd, 最小公倍數(shù) lcm

// PAT_B_1062, 1034, PAT_A_1081

// 最大公因數(shù), the Greatest Common Divisor
int get_gcd(int a, int b){
    if( b == 0 ){
        return a;
    }
    else{
        return get_gcd(b, a % b);
    }
}

// 最小公倍數(shù), the Lowest Common Multiple
int get_lcm(int a, int b){
    int gcd = get_gcd(a, b);
    if( gcd != 0 ){
        return a * b / gcd;
    }
    else{
        return 0;
    }
}

素數(shù)

Fib

數(shù)據(jù)庫事務(wù)(Transaction)的 ACID 特性

原子性(Atomicity), 一致性(Consistency), 隔離型(Isolation), 持久性(Durability)

原子性(A)是指事務(wù)中的操作不可拆分, 只允許全部執(zhí)行或者全部不執(zhí)行

一致性(C)指事務(wù)的執(zhí)行不能破壞數(shù)據(jù)庫的一致性, 一致性也稱為完整性。一個事務(wù)在執(zhí)行后, 數(shù)據(jù)庫必須從一個一致性狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€一致性狀態(tài)

隔離性(I)指并發(fā)的事務(wù)相互隔離, 不能互相干擾

持久性(D)指事務(wù)一旦提交, 對數(shù)據(jù)的狀態(tài)變更應(yīng)該被永久保存

數(shù)據(jù)庫事務(wù)隔離級別有4個

# 由低到高依次為
Read uncommitted, 讀到了未提交的事物, 只是 add 還沒有 commit
Read committed, 讀到了上一次的commit, 也就是說還沒有更新 最新的commit
Repeatable read, 保證讀取最新的 commit, 為此, 讀取的時候不允許提交
Serializable, 要求有很高的實時同步性
# 這四個級別可以逐個解決臟讀 、不可重復(fù)讀 、幻讀 這幾類問題

鎖（并發(fā)控制的手段）

關(guān)系數(shù)據(jù)模型的三個組成部分

數(shù)據(jù)結(jié)構(gòu), 對數(shù)據(jù)的操作, 完整性約束

參考鏈接

數(shù)據(jù)庫事務(wù)、隔離級別、鎖的理解與整理

CRUD

Create, Read, Update, and Delete

過程

1.首先連接到數(shù)據(jù)庫
  conn = sqlite.connect("test.db")
2.建立游標(biāo) cursor
  cursor = conn.cursor()
3.建立表
  create table user (id int, name varchar(20), score int )
4.insert into 插入數(shù)據(jù), 注意占位符是 ?
  insert into user (id, name) values(1, "Alice", 88)
  insert into user (id, name) values(2, "Bob", 89)
  insert into user (id, name) values(3, "Cindy", 88)
5.select * from user where 查找數(shù)據(jù)
  select * from user where id between 1 and 3 order by score asc
6.cursor.close()
7.conn.commit()
8.conn.close()

column, 列, 字段

select * from user
select col1, col2 from user

下面以這個表格 customers 為例, 展示 SQL 的語法

where 條件選擇

select * from customers where country="Germany" and city="Berlin"

order by 排序

select * from customers order by country

插入

insert into customers (name, age, city, postalcode, country) values ("Bart", 10, "LA", "4006", "USA")

更新

update customers set name = "Smith", city = "Paris" where id = 5

刪除

delete from customers where name = "Berglunds"

limit/top 不返回全部結(jié)果, 只返回有限數(shù)量的記錄

# SQL
select top 3 from customers
# MySQL
select * from customers limit 3

最大最小值

select min(age) from customers

統(tǒng)計 count, distinct

# 統(tǒng)計有多少個不同的國家
select count(distinct country) from customers

平均值

select avg(age) from customers

求和

select sum(age) from customers

通配符

# SQL
select * from customers where name like "B%"
# sqlite
select * from customers where name like "B*"

選擇范圍

# 離散
select * from customers where country in ("Germany", "France")
# 連續(xù)
select * from customers where age between 10 and 20

連接表格

inner join, (A ∩ B)
left join, (A ∩ B) U A
right join, (A ∩ B) U B
full outer join, (A U B)

參考資料

2xx: Successful responses

200 OK

3xx: Redirection messages

301 Moved Permanently, 永久轉(zhuǎn)移

This response code means that the URI of the requested resource has been changed permanently. Probably, the new URI would be given in the response.

307 Internal Redicrection, 瀏覽器自動重定向, HSTS 會用到

4xx: Client error responses

400 Bad Request, 非法請求

This response means that server could not understand the request due to invalid syntax.

403 Forbidden, 未認(rèn)證, 權(quán)限不夠

The client does not have access rights to the content, i.e. they are unauthorized, so server is rejecting to give proper response. Unlike 401, the client"s identity is known to the server.

404 Not Found, 沒有相應(yīng)的資源, 路徑不對

The server can not find requested resource. In the browser, this means the URL is not recognized. In an API, this can also mean that the endpoint is valid but the resource itself does not exist. Servers may also send this response instead of 403 to hide the existence of a resource from an unauthorized client. This response code is probably the most famous one due to its frequent occurence on the web.

405 Method Not Allowed, 非法的請求方式

The request method is known by the server but has been disabled and cannot be used. For example, an API may forbid DELETE-ing a resource. The two mandatory methods, GET and HEAD, must never be disabled and should not return this error code.

5xx: Server error responses

500 Internal Server Error, 服務(wù)器內(nèi)部錯誤

The server has encountered a situation it doesn"t know how to handle.

501 Not Implemented, 請求方法未實現(xiàn)

The request method is not supported by the server and cannot be handled. The only methods that servers are required to support (and therefore that must not return this code) are GET and HEAD.

參考資料

https://developer.mozilla.org...

冪等

GET為請求數(shù)據(jù), 沒有副作用, 每次請求的效果都相同。

POST為修改數(shù)據(jù), 相對GET來講沒有那么安全（因為要修改數(shù)據(jù)）。

安全性

GET 通過 URL 傳輸數(shù)據(jù), 容易在日志記錄中留下私密數(shù)據(jù), 隱蔽性沒有POST好。

長度限制。

一般通過GET方式傳輸數(shù)據(jù), 由于Web Server和瀏覽器限制, URL長度限制傳輸?shù)臄?shù)據(jù)有限(根據(jù)Web Server配置和瀏覽器不同, 一般為2kB~8kB)

而POST通?？梢院雎韵拗?實際上根據(jù)Web Server配置也還是有限制的, 一般是2G)

http://stackoverflow.com/ques...

三次握手

過程

服務(wù)器 B 處于 LISTEN 狀態(tài), 監(jiān)聽端口, 等待請求

客戶端 A 的 TCP 進程首先創(chuàng)建 TCB (傳輸控制塊, 存儲了每一個連接中的重要信息, srcPort, dstPort, srcIP, destIP, seq, ack)。 然后向 B 發(fā)出連接請求報文段(傳輸層是段, 網(wǎng)絡(luò)層是包, 鏈路層是幀)。 此時 【 SYN=1, seq=x 】, 不攜帶數(shù)據(jù), 但是消耗一個序號。接著進入 SYN-SENT狀態(tài)。

B 收到連接請求后, 如果同意連接, 則向A發(fā)送確認(rèn)(ACK), 此時 【 SYN=1, ACK=1, ack=x+1, seq=y 】, ACK是確認(rèn)標(biāo)志, ack是確認(rèn)號。這個報文段不帶數(shù)據(jù), 但是消耗一個序號。服務(wù)器進入 SYN-RCVD 狀態(tài)

A 收到 B 的確認(rèn)后, 還要向 B 確認(rèn)自己收到了。此時 【 ACK=1, ack=y+1, seq=x+1 】, 這個ACK報文段可以帶數(shù)據(jù)。接著 A 進入ESTABLISHED 狀態(tài)。

B 收到 A 的確認(rèn)后, 也進入 ESTABLISHED 狀態(tài)。

為什么三次握手, 而不是兩次？也就是說, B 在第一次收到 A 的 SYN 之后, 沒有立刻進入 ESTABLISHED, 而是等到 A 再來一次 ACK 才建立連接, 為什么要這樣設(shè)計？

答：防止已經(jīng)失效的連接請求(比如在某個網(wǎng)絡(luò)滯留了很久), 突然又傳到了 B , 從而產(chǎn)生錯誤, 造成 B 的資源浪費.

考慮這樣一種情況: A 的第一次 SYN 被攔截了。然后 A 又發(fā)了一次 SYN, B 收到, 并且完成后續(xù)的 握手 --- 數(shù)據(jù)傳輸 --- 揮手。

此時 A 的第一次 SYN 又被放了出來, 并傳到 B, 如果只需要 2 次握手, 那么此時 B 就會直接進入 ESTABLISHED

而這個時候 A 都已經(jīng)關(guān)機了, 不會發(fā)數(shù)據(jù)過來了, B 就在 ESTABLISHED 中苦苦等待 A, 浪費很多資源。

如果是3次握手, 那么 B 只會進入 SYN-RCVD 狀態(tài), 一段時間后 (比 ESTABLISHED 要短, 而且不會占用那么多資源), 會自動取消連接

SYN Flood

SYN Flood 是一種廣為人知的 DoS (拒絕服務(wù)攻擊) , 是 DDoS (分布式拒絕服務(wù)攻擊) 的方式之一, 這是一種利用 TCP 協(xié)議缺陷, 發(fā)送大量偽造的 TCP 連接請求, 從而使得被攻擊方資源耗盡 (CPU滿負(fù)荷或內(nèi)存不足) 的攻擊方式。

假設(shè)一個用戶向服務(wù)器發(fā)送了 SYN 報文后突然死機或掉線, 那么服務(wù)器在發(fā)出 SYN+ACK 應(yīng)答報文后是無法收到客戶端的 ACK 報文的 (第三次握手無法完成) ,

這種情況下服務(wù)器端一般會重試 (再次發(fā)送 SYN+ACK 給客戶端) 并等待一段時間后丟棄這個未完成的連接, 這段時間的長度我們稱為 SYN Timeout, 一般來說這個時間是分鐘的數(shù)量級 (大約為30秒 - 2分鐘).

一個用戶出現(xiàn)異常導(dǎo)致服務(wù)器的一個線程等待1分鐘并不是什么很大的問題, 但是, 如果有一個惡意的攻擊者大量模擬偽造這種情況, 服務(wù)器端將會維護一個非常大的半連接列表, 從而消耗非常多的資源

數(shù)以萬計的半連接, 即使是簡單的保存并遍歷也會消耗非常多的 CPU 時間和內(nèi)存, 何況還要不斷對這個列表中的 IP 進行 SYN+ACK 的重試

實際上如果服務(wù)器的 TCP/IP 棧不夠強大, 最后的結(jié)果往往是堆棧溢出崩潰,

即使服務(wù)器端的系統(tǒng)足夠強大, 服務(wù)器端也將忙于處理攻擊者偽造的 TCP 連接請求而無暇理睬客戶的正常請求 (畢竟客戶端的正常請求比率非常之小) , 此時從正?？蛻舻慕嵌瓤磥? 服務(wù)器失去響應(yīng), 無法對正?？蛻暨M行服務(wù)

這就是 SYN Flood 攻擊

防御措施: 縮短 SYN Timeout, 增加 IP 黑名單, 使用 CDN

斷開, 4次揮手 (4-way handshake, connection termination)

MSL, Maximum Segment Lifetime, 最長報文段壽命

A 發(fā)出的最后一個 ACK 可能會丟失. 而此時 B 還在等待這個 ACK, 如果 B 一直沒有收到, 則會給 A 發(fā)一個 FIN + ACK, 通知 A 剛才那個沒收到, 從 A 發(fā)出 ACK 到 B 發(fā)出 FIN + ACK 需要 2MSL, 如果 2MSL 時間里面 A 都沒有收到 B 的回復(fù), 就認(rèn)為自己的 ACK 已經(jīng)送達 B, 所以 A 可以安心關(guān)閉了

而且, 2MSL 后, 可以使本次連接所產(chǎn)生的所有報文段都從網(wǎng)絡(luò)上消失 (TTL, Time To Live), 以后建立新的連接, 就不會和舊的連接混淆

網(wǎng)絡(luò)請求具體過程, 步驟, 代碼

用了異步嗎, 為什么（網(wǎng)絡(luò)慢的時候不會卡界面）

MainActivity, 點擊, 進入新的 Activity 這中間發(fā)生了什么, 怎么傳遞的消息？

Intent

為什么選 Flask, 什么叫做輕？其他框架有看過嗎？

為什么要做這個網(wǎng)站？

把 vue 和 echarts 放到 html-body 前面

https 有什么作用, https具體連接過程是怎么樣的

交互圖

HTTPS加密過程和TLS證書驗證

深入理解 https 通信加密過程

HTTPS為什么安全 &分析 HTTPS 連接建立全過程

http://www.ruanyifeng.com/blo...

1). Client 給出協(xié)議版本號、一個的隨機數(shù)（Client random），以及客戶端支持的加密方法。
2). Server 確認(rèn)雙方使用的加密方法，并給出數(shù)字證書，以及一個服務(wù)器生成的隨機數(shù)
3). Client 確認(rèn)數(shù)字證書有效，然后生成一個新的隨機數(shù)(Premaster secret), 并使用數(shù)字證書中的公鑰，加密 Premaster secret, 發(fā)給 Server
4). Server 使用自己的私鑰，獲取愛麗絲發(fā)來的隨機數(shù) Premaster secret
5). Client 和 Server 根據(jù)約定的加密方法，使用前面的三個隨機數(shù)，生成"對話密鑰"（session key），用來加密接下來的整個對話過程。

生成對話密鑰一共需要三個隨機數(shù)。

握手之后的對話使用"對話密鑰"加密（對稱加密），服務(wù)器的公鑰和私鑰只用于加密和解密"對話密鑰"（非對稱加密），無其他作用。

服務(wù)器公鑰放在服務(wù)器的數(shù)字證書之中。

用 let"s encrypt 的 https 證書需要注意哪些事情？有什么限制嗎？為什么設(shè)置 60 天的有效期, 過期了要重新延長？證書有效期是什么概念？有效期過了會導(dǎo)致什么問題？

最重要的原因在于吊銷。當(dāng)網(wǎng)站的私鑰丟失時，網(wǎng)站應(yīng)該向證書頒發(fā)機構(gòu)（CA）申請將他們的證書加入到證書吊銷列表（CRL）里。當(dāng)用戶訪問https站點時，瀏覽器會自動向CA請求吊銷列表，如果用戶訪問的站點提供的證書在CRL里，瀏覽器就不信任這個證書，因為攻擊者可能擁有同樣的證書。所以如果證書永久有效，隨著越來越多的私鑰丟失，吊銷列表也越來越大（因為只有加進去的，沒有剔出去的），這既給CA增加流量壓力，也會增加瀏覽器的流量。而一旦有效期只有幾年，那么CA就可以將那些已經(jīng)過期了的證書從CRL里剔除，因為反正瀏覽器也不信任過期證書。

輸入 URL 到頁面展示, 中間發(fā)生了什么？授權(quán)解析服務(wù)器

https://segmentfault.com/a/11...

拿到端口號后, 誰跟誰之間建立了什么連接？

有哪些 request 的方法？GET, POST, PUT, DELETE 還有嗎？RESTful API？

GET 和 POST 有什么區(qū)別？

GET對URL的限制是哪里限制的？(Server 和 瀏覽器 都有限制)

HTTP headers的作用, 比如 Connection: keep-alive 是干什么用的？重用是什么概念, 是誰的重用？

客戶端和服務(wù)器之間用于傳輸HTTP數(shù)據(jù)的TCP連接不會關(guān)閉, 如果客戶端再次訪問這個服務(wù)器上的網(wǎng)頁, 會繼續(xù)使用這一條已經(jīng)建立的連接

HSTS？

javascript, setTimeout() 的用法

console.log(1)
for( let i = 0; i < 5; i++ ){
    setTimeout(function(){console.log(2);}, 1000);
}
console.log(3);

輸出是什么（1 3 2 2 2 2 2）

異步, 不會等

https://www.liaoxuefeng.com/w...

前端怎么向后端發(fā)起請求

axios, jQuery, AJAX 是怎么寫的

基礎(chǔ)要扎實

體系結(jié)構(gòu), 操作系統(tǒng), 網(wǎng)絡(luò), 語言, 數(shù)據(jù)結(jié)構(gòu)算法, 框架, 應(yīng)用

集中, 專攻, 而且要體現(xiàn)在簡歷上, 讓面試官知道問什么

如果要做 Java 就專攻 Java, SSM/SSH 實踐好, 理解好

Python 如果要做, 也要深入, 不要皮毛

牛客網(wǎng)面試經(jīng)歷 (視頻面試)

項目經(jīng)歷

自我介紹(中英文)