冒泡排序
原理：比較兩個(gè)相鄰的元素，將值大的元素交換至右端集灌。
思路：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面肺樟。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)凫佛，將小數(shù)放前芙扎，大數(shù)放后负乡。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)榜田，將小數(shù)放前，大數(shù)放后锻梳，如此繼續(xù)箭券，直至比較最后兩個(gè)數(shù)，將小數(shù)放前疑枯，大數(shù)放后辩块。重復(fù)第一趟步驟，直至全部排序完成荆永。
for (int e = arr.length - 1; e > 0; e--) {
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
使用python實(shí)現(xiàn)废亭，每一趟的長度都應(yīng)該減少1，第一趟時(shí)要對(duì)比所有的數(shù)據(jù)具钥，從arr[0]到arr[-1]進(jìn)行對(duì)比豆村，最后一次的arr[j+1]就是arr[-1],以后依次減少對(duì)比的長度。
for i in range(len(arr))[::-1]:
for j in range(i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j + 1], arr[j]
插入排序
直接插入排序(Straight Insertion Sort)的基本思想是：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無序表骂删。開始時(shí)有序表中只包含1個(gè)元素掌动，無序表中包含有n-1個(gè)元素，排序過程中每次從無序表中取出第一個(gè)元素宁玫，將它插入到有序表中的適當(dāng)位置粗恢，使之成為新的有序表，重復(fù)n-1次可完成排序過程撬统。
從后面的無序表中拿出一個(gè)數(shù)，先與最后有序表最后一個(gè)元素進(jìn)行對(duì)比敦迄，如果arr[j] > arr[j + 1]恋追，就進(jìn)行插入，否則不進(jìn)行操作罚屋。
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
python實(shí)現(xiàn)苦囱，每次有序長度加1或者說每次都需要從無序列表中拿一個(gè)數(shù)據(jù)，進(jìn)行插入對(duì)比是在有序里面進(jìn)行的脾猛，第一次開始的時(shí)arr[j+1]就是最新加入的數(shù)據(jù)
for i in range(1, len(arr)):
for j in range( i-1)[::-1]:
if arr[j] > arr[j+1]:
arr[j] , arr[j+1] = arr[j+1] , arr[j]
選擇排序
原理：每一趟從待排序的記錄中選出最小的元素撕彤，順序放在已排好序的序列最后，直到全部記錄排序完畢猛拴。
給定數(shù)組：int[] arr={里面n個(gè)數(shù)據(jù)}羹铅；第1趟排序，在待排序數(shù)據(jù)arr[1]~ arr[n]中選出最小的數(shù)據(jù)愉昆，將它與arrr[1]交換职员；第2趟，在待排序數(shù)據(jù)arr[2]~ arr[n]中選出最小的數(shù)據(jù)跛溉，將它與r[2]交換焊切；以此類推扮授，第i趟在待排序數(shù)據(jù)arr[i]~ arr[n]中選出最小的數(shù)據(jù)，將它與r[i]交換专肪，直到全部排序完成刹勃。
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
二分法使用遞歸查找最大值
使用堆的壓棧和出棧理解遞歸函數(shù)，每次調(diào)用一次自己嚎尤，就會(huì)把一個(gè)getmax(arr, L, R)的信息壓入棧荔仁，這時(shí)會(huì)有多個(gè)getmax(arr, L, R)函數(shù)被壓入棧，每個(gè)getmax(arr, L, R)有自己的獨(dú)立信息诺苹，當(dāng)L == R時(shí)咕晋，就會(huì)執(zhí)行出棧操作，從上往下進(jìn)行出棧操作收奔。
getmax：是通過二分法取得左側(cè)和右側(cè)的最大值掌呜，之后進(jìn)最大值之間的比較。
getmax(int [] arr, int L, int R){
if (L == R){
return arr[L];
}
int mid = (L + R) / 2;
int maxLeft = getmax(arr, L, mid);
int maxRight = getmax(arr, mid, R);
return Math.max(maxLeft, maxRight)
}
并歸排序
使用遞歸進(jìn)行二分法進(jìn)行排序坪哄，把左側(cè)和右側(cè)單獨(dú)排序质蕉，之后通過外派進(jìn)行進(jìn)行排序。外排就是使用兩個(gè)指針翩肌，新建一個(gè)新數(shù)組模暗，一個(gè)指向左側(cè)第一個(gè)，一個(gè)指向右側(cè)第一個(gè)念祭，把兩個(gè)指針的小值填入新數(shù)組兑宇，填入的指針加一。
解釋:void mergeSort(int[] arr, int l, int r)就是二分法的遞歸函數(shù)把左側(cè)和右側(cè)進(jìn)行排序
使用merge(int[] arr, int l, int m, int r)進(jìn)行外派合并粱坤，每次壓棧只對(duì)arr的[l, r]進(jìn)行操作隶糕，其他地方不變。
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
荷蘭國旗問題
輸入一個(gè)數(shù)組arr和一個(gè)數(shù)字p站玄，把小于p的數(shù)放左邊枚驻，大于p的數(shù)據(jù)放右邊，相等的放中間株旷。
思路：設(shè)置一個(gè)less指針和more指針再登。less指向arr[0]，more指向arr[-1],l從0-length滑動(dòng)晾剖。如果arr[l] < p就 交換arr[less+1]和arr[l], 之后i = i +1锉矢，如果arr[l] > p就交換arr[more-1]和arr[l],重新判斷i位置，相等時(shí)直接 i = i +1.
less + 1, more - 1 是arr[l] == p區(qū)間的位置
public static int[] partition(int[] arr, int l, int r, int p) {
int less = l - 1;
int more = r + 1;
while (l < more) {
if (arr[l] < p) {
swap(arr, ++less, l++);
} else if (arr[l] > p) {
swap(arr, --more, l);
} else {
l++;
}
}
return new int[] { less + 1, more - 1 };
}
int[] res = partition(test, 0, test.length - 1, 1);
python 實(shí)現(xiàn)荷蘭國旗問題齿尽，這里與四個(gè)指針沈撞，left，right時(shí)原始的數(shù)組開始和結(jié)尾指針雕什，less和more是在arr中小于和大于num的邊界缠俺，less和more中間的值就是等于num的值显晶。在排序過程中，less左右邊的值必為小于num的值壹士，在more右的值必為大于num的值磷雇，指針left每次都加1，但如果遇到大于num時(shí)躏救，會(huì)把當(dāng)前的值和一個(gè)未知大小的值arr[more-1]進(jìn)行交換唯笙，所以需要重新判斷一次arr[left]。
arr = [1,4,1,5,3,2,3,6]
def partition(arr, left, right, num):
less = left - 1
more = right + 1
while (left < more):
if arr[left] < num:
less += 1
arr[less],arr[left] = arr[left],arr[less]
left += 1
elif arr[left] > num:
more -= 1
arr[more],arr[left] = arr[left],arr[more]
else:
left += 1
print(arr)
return less + 1, more - 1
partition(arr,0, len(arr) - 1, 3)
快排
使用遞歸劃分子集盒使，給定一個(gè)arr崩掘，首先arr取中的最后一個(gè)數(shù)arr[-1]。把a(bǔ)rr[l] < arr[-1]的數(shù)放左邊少办，arr[l] > arr[-1]的數(shù)放右邊苞慢，arr[l] == arr[-1]的數(shù)放中間。得到arr[l] == arr[-1]的邊界p英妓，p[0] - 1就是arr[l] < arr[-1]的數(shù)表挽放，p[1] + 1就是arr[l] > arr[-1]的數(shù)表,繼續(xù)進(jìn)遞歸，中間arr[l] == arr[-1]的不需要?jiǎng)勇溃f歸操作的是l-r辑畦， 遞歸返回的條件就是arr[-1]就是整數(shù)組的最大值，這時(shí)l和p[0]相等腿倚，p[1]和r相等纯出，或者p[0]==p[1]相等。
隨機(jī)快排敷燎，由于數(shù)組本身就是有序數(shù)據(jù)暂筝，這時(shí)復(fù)雜度為最大，隨機(jī)選取一個(gè)數(shù)放在arr[-1]懈叹，就可以以隨機(jī)概率在大概率情況下取得較小復(fù)雜度乖杠。
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
//swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r); // 由于最后一個(gè)數(shù)不參與劃分直接分扎，需要把r放入等于區(qū)間
return new int[] { less + 1, more };
}
通過把每個(gè)子數(shù)組的進(jìn)行二分澄成，把小于arr[-1]放左邊，把大于arr[-1]的放右邊,當(dāng)數(shù)組中被切分的[left, right]最大值被放到最左邊時(shí),就可進(jìn)行返回了畏吓。
import random
arr = [1,4,1,6,3,2,3,5,1]
def partition(arr, left, right):
less = left - 1
more = right
num = arr[right]
while (left < more):
if arr[left] < num:
less += 1
arr[less],arr[left] = arr[left],arr[less]
left += 1
elif arr[left] > num:
more -= 1
arr[more],arr[left] = arr[left],arr[more]
else:
left += 1
arr[more],arr[right] = arr[right],arr[more]
return arr,[less + 1, more]
def quiksort(arr, left, right):
if left < right:
rand = left + int(random.random() *(right - left + 1))
arr[rand],arr[right] = arr[right],arr[rand]
arr,equl = partition(arr,left, right, )
arr = quiksort(arr, left, equl[0]-1)
arr = quiksort(arr, equl[1]+1, right)
return arr
print(quiksort(arr,0, len(arr) - 1))
堆結(jié)構(gòu)
把一個(gè)數(shù)組建一個(gè)大根堆結(jié)構(gòu)墨状。
i 左節(jié)點(diǎn)：2 * i + 1
i 右節(jié)點(diǎn): 2 * i + 1
父結(jié)構(gòu)： (i - 1) / 2
所有節(jié)點(diǎn)都不能越界。
完全二叉樹：先補(bǔ)左節(jié)點(diǎn)菲饼，再補(bǔ)右節(jié)點(diǎn)
大根堆：完全二叉樹肾砂，任何一個(gè)子樹的最大值為子樹頭部。
小根堆：完全二叉樹宏悦，任何一個(gè)子樹的最小值為子樹頭部镐确。對(duì)數(shù)組arr包吝，每次添加一個(gè)數(shù)到堆里。
heapInsert(int[] arr, int index) 第index個(gè)數(shù)加到堆的操作：找到index的父節(jié)點(diǎn)源葫，對(duì)比其中的最大值诗越，如果arr[index] > arr[(index - 1) / 2]，第index個(gè)數(shù)比父節(jié)點(diǎn)大息堂，進(jìn)行交換嚷狞，之后與父父節(jié)點(diǎn)對(duì)比，直到index=0或者arr[index] <= arr[(index - 1) / 2].
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
- 如果堆的值發(fā)生改變:
需要改變堆的結(jié)構(gòu)荣堰，把小值進(jìn)行下沉床未。
在一個(gè)數(shù)組中index的值發(fā)生改變，arr中size為堆的長度振坚。
找到index的兩個(gè)子節(jié)點(diǎn)中最大值largest薇搁，比較largest和index的小，如果largest <= index返回屡拨，否則交換swap(arr, largest, index)只酥，進(jìn)入下一個(gè)子節(jié)點(diǎn)的比較
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
- 怎么進(jìn)行減堆操作:
1.刪掉最后值，2.彈出第一個(gè)值呀狼，把最后一個(gè)值放到第一個(gè)值裂允，調(diào)整堆結(jié)構(gòu)
對(duì)一個(gè)動(dòng)態(tài)的數(shù)組建立一個(gè)堆，注意：數(shù)組的長度不固定哥艇，通過添加值的同時(shí)就可以保持?jǐn)?shù)據(jù)的有序性绝编。
通過建立一個(gè)大根堆和一個(gè)小根堆，兩個(gè)堆列的size不能超過1貌踏，如果某一個(gè)num <= big[0]進(jìn)行入大根堆十饥，否則進(jìn)入小根堆,size相差超過1，彈出頭部祖乳，這時(shí)大根堆的頭部為中位數(shù)逗堵。
堆排序
基于大根堆進(jìn)行排序，因?yàn)槊總€(gè)大根堆的頭部最大值是整個(gè)堆的最大值眷昆，通過把頭部與尾部進(jìn)行交換蜒秤，size-1，進(jìn)行對(duì)調(diào)整亚斋，循環(huán)調(diào)整作媚。
首先建堆，把數(shù)組arr堆成堆a(bǔ)rr帅刊，通過交換頭部與尾部纸泡，再調(diào)整堆結(jié)構(gòu)。
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
棧結(jié)構(gòu)
- 先入后出的一種數(shù)據(jù)結(jié)構(gòu)赖瞒，有push女揭，pop蚤假，peek操作。
push:往棧結(jié)構(gòu)中加入數(shù)據(jù)
pop:從棧結(jié)構(gòu)中彈出數(shù)據(jù)吧兔，只彈出最新的數(shù)據(jù),彈出的數(shù)據(jù)不屬于棧結(jié)構(gòu)
peek:返回棧的最后一個(gè)數(shù)據(jù)勤哗，并不刪除數(shù)據(jù)
- 固定數(shù)組的棧實(shí)現(xiàn)：
public ArrayStack(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
size = 0;
}
public Integer peek() {
if (size == 0) {
return null;
}
return arr[size - 1];
}
public void push(int obj) {
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
arr[size++] = obj;
}
public Integer pop() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
return arr[--size];
}
}
- 隊(duì)列結(jié)構(gòu)，先入先出掩驱。
使用數(shù)組設(shè)計(jì)一個(gè)固定長度的隊(duì)列結(jié)構(gòu)芒划，隊(duì)列有固定長度的size，設(shè)計(jì)兩個(gè)指針first,last欧穴。
last:最新添加的數(shù)據(jù)的位置
first:彈出的數(shù)據(jù)的位置
push:往隊(duì)列結(jié)構(gòu)中加入數(shù)據(jù)
poll:從隊(duì)列頭中彈出數(shù)據(jù)民逼，只彈出最早入隊(duì)列的數(shù)據(jù),彈出的數(shù)據(jù)不屬于結(jié)構(gòu)
peek:返回隊(duì)列的第一個(gè)數(shù)據(jù)，并不刪除數(shù)據(jù)
- 固定數(shù)組實(shí)現(xiàn)隊(duì)列
public static class ArrayQueue {
private Integer[] arr;
private Integer size;
private Integer first;
private Integer last;
public ArrayQueue(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
size = 0;
first = 0;
last = 0;
}
public Integer peek() {
if (size == 0) {
return null;
}
return arr[first];
}
public void push(int obj) {
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
size++;
arr[last] = obj;
last = last == arr.length - 1 ? 0 : last + 1;
}
public Integer poll() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
size--;
int tmp = first;
first = first == arr.length - 1 ? 0 : first + 1;
return arr[tmp];
}
}
例子：實(shí)現(xiàn)一個(gè)特殊的棧涮帘，在實(shí)現(xiàn)棧的結(jié)構(gòu)拼苍，返回棧中的最小值
使用兩個(gè)棧實(shí)現(xiàn)：
Data：正常的數(shù)據(jù)入棧
Min:第一次入棧數(shù)據(jù)和Data一樣，之后调缨，比較Min的棧頂與新數(shù)據(jù)的大小疮鲫，把最小值放入min中，Min和Data的長度一樣弦叶，Min和Data同步彈出俊犯，Min的棧頂就是Data中的最小值。例子：使用隊(duì)列替換棧結(jié)構(gòu)
隊(duì)列是先進(jìn)先出結(jié)構(gòu)伤哺，棧是先進(jìn)后出結(jié)構(gòu)燕侠。
方法：使用時(shí)兩個(gè)隊(duì)列Queue1和Queue2，正常入棧放到Queue1立莉，當(dāng)要出棧绢彤，就把Queue1最后一個(gè)之前的數(shù)據(jù)放入Queue2，把最后一個(gè)數(shù)據(jù)彈出蜓耻，彈出之后,新數(shù)據(jù)直接放到Queue2茫舶，這樣交替進(jìn)行，swap指向隊(duì)列的指針刹淌。
public static class TwoQueuesStack {
private Queue<Integer> queue;
private Queue<Integer> help;
public TwoQueuesStack() {
queue = new LinkedList<Integer>();
help = new LinkedList<Integer>();
}
public void push(int pushInt) {
queue.add(pushInt);
}
public int peek() {
if (queue.isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
while (queue.size() != 1) {
help.add(queue.poll());
}
int res = queue.poll();
help.add(res);
swap();
return res;
}
public int pop() {
if (queue.isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
while (queue.size() > 1) {
help.add(queue.poll());
}
int res = queue.poll();
swap();
return res;
}
private void swap() {
Queue<Integer> tmp = help;
help = queue;
queue = tmp;
}
}
- 例子：使用棧替換隊(duì)列結(jié)構(gòu)
隊(duì)列是先進(jìn)先出結(jié)構(gòu)饶氏，棧是先進(jìn)后出結(jié)構(gòu)。
同樣使用兩個(gè)棧結(jié)構(gòu)Stack1和Stack2芦鳍，使用時(shí)往Stack1添加數(shù)據(jù)嚷往，第一次彈數(shù)據(jù)時(shí)葛账，把Stack1數(shù)據(jù)全部放入Stack2柠衅，從Stack2彈出數(shù)據(jù)，之后把添加數(shù)據(jù)放入Stack1籍琳，Stack2一直彈數(shù)據(jù)菲宴，直到Stack2為空時(shí)再把Stack1倒入Stack2贷祈，所以Stack1一直是添加數(shù)據(jù)棧，Stack2存儲(chǔ)的是最先入隊(duì)的數(shù)據(jù)喝峦。
public static class TwoStacksQueue {
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
public void push(int pushInt) {
stackPush.push(pushInt);
}
public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
} else if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
} else if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
二叉樹結(jié)構(gòu)
有左右兩個(gè)子節(jié)點(diǎn)left势誊， right，同時(shí)函數(shù)有數(shù)據(jù)data
實(shí)現(xiàn)二叉樹結(jié)構(gòu)：
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
二叉樹遍歷一顆樹每個(gè)節(jié)點(diǎn)會(huì)訪問三次谣蠢。
- 先序遍歷
先打印節(jié)點(diǎn)粟耻，再打印左子樹，之后為右子樹
- 先序遍歷
- 中序遍歷
先打印左子樹眉踱，再打印節(jié)點(diǎn)挤忙，之后為右子樹
- 中序遍歷
- 后序遍歷
先打印左子樹，在打印為右子樹谈喳，之后打印節(jié)點(diǎn)
遞歸函數(shù)：
- 后序遍歷
public static void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
public static void inOrderRecur(Node head) {
if (head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}
public static void posOrderRecur(Node head) {
if (head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.value + " ");
}
解遞歸函數(shù):
- 前序遍歷册烈，可以通過棧實(shí)現(xiàn)，先把頭部壓棧婿禽，先彈打印當(dāng)前節(jié)點(diǎn)赏僧，先壓右節(jié)點(diǎn)，再壓左節(jié)點(diǎn)扭倾，如果無子節(jié)點(diǎn)淀零，進(jìn)行彈出，彈出左節(jié)點(diǎn)進(jìn)行打印膛壹，之后右節(jié)點(diǎn)窑滞。
public static void preOrderUnRecur(Node head) {
System.out.print("pre-order: ");
if (head != null) {
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
System.out.println();
}
2.中序遍歷把每個(gè)節(jié)點(diǎn)的左節(jié)點(diǎn)壓棧，直到遇到空恢筝，進(jìn)行出棧進(jìn)行彈出打印哀卫，找到同一節(jié)點(diǎn)的右節(jié)點(diǎn)，進(jìn)行左節(jié)點(diǎn)壓棧撬槽，循環(huán)此改。。侄柔。共啃。
public static void inOrderUnRecur(Node head) {
System.out.print("in-order: ");
if (head != null) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
- 后序遍歷
使用前序遍歷的逆序，使用兩個(gè)棧暂题，一個(gè)棧存頭部移剪，一個(gè)棧存打印節(jié)點(diǎn)，先壓左節(jié)點(diǎn)薪者，不進(jìn)行打印而是進(jìn)行壓棧纵苛，再壓右節(jié)點(diǎn)，不進(jìn)行打印而是進(jìn)行壓棧。完全遍歷之后進(jìn)行打印攻人。
public static void posOrderUnRecur1(Node head) {
System.out.print("pos-order: ");
if (head != null) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null) {
s1.push(head.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
- 樹的序列化
前序的序列化
對(duì)每個(gè)子節(jié)點(diǎn)取试，先返回左節(jié)點(diǎn)，在返回右節(jié)點(diǎn)怀吻，如果遇到null瞬浓，以"#!"代替
public static String serialByPre(Node head) {
if (head == null) {
return "#!";
}
String res = head.value + "!";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
- 判斷一個(gè)二叉樹是否是平衡二叉樹
平衡二叉樹，左右兩個(gè)邊的高度相差不超過1蓬坡。
- 左樹平衡猿棉，右樹平衡
- 左樹的高度，右樹的高度
遞歸函數(shù)每次返回?cái)?shù)據(jù)結(jié)構(gòu)是一樣的屑咳，通過先判度是否平衡铺根，再判斷右樹高度。
public static boolean isBalance(Node head) {
boolean[] res = new boolean[1];
res[0] = true;
getHeight(head, 1, res);
return res[0];
}
public static int getHeight(Node head, int level, boolean[] res) {
if (head == null) {
return level;
}
int lH = getHeight(head.left, level + 1, res);
if (!res[0]) {
return level;
}
int rH = getHeight(head.right, level + 1, res);
if (!res[0]) {
return level;
}
if (Math.abs(lH - rH) > 1) {
res[0] = false;
}
return Math.max(lH, rH);
}
- 搜索二叉樹
對(duì)一顆樹乔宿，左子節(jié)點(diǎn)的值比右子節(jié)點(diǎn)大位迂。在中序遍歷中，通過判斷先前節(jié)點(diǎn)==當(dāng)前節(jié)點(diǎn)详瑞。
- 判斷完全二叉樹
- 判斷有右節(jié)點(diǎn)掂林，無節(jié)點(diǎn)，為false
- 同一層中間層有缺節(jié)點(diǎn)
public static boolean isCBT(Node head) {
if (head == null) {
return true;
}
Queue<Node> queue = new LinkedList<Node>();
boolean leaf = false;
Node l = null;
Node r = null;
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
return false;
}
if (l != null) {
queue.offer(l);
}
if (r != null) {
queue.offer(r);
} else {
leaf = true;
}
}
return true;
}
- 一知一顆完全二叉樹坝橡，求其節(jié)點(diǎn)的個(gè)數(shù)
曼兒叉樹節(jié)點(diǎn)個(gè)數(shù)L泻帮，h(高度)：L = 2^(h) - 1
hash 函數(shù)
- hash（散列、雜湊）函數(shù)计寇，是將任意長度的數(shù)據(jù)映射到有限長度的域上锣杂。直觀解釋起來，就是對(duì)一串?dāng)?shù)據(jù)m進(jìn)行雜糅番宁，輸出另一段固定長度的數(shù)據(jù)h元莫，作為這段數(shù)據(jù)的特征（指紋）。
- input ==無窮
- output == 有限
- input same == out same
- input not same == out same 蝶押， hash碰撞
- input 無窮 == output 均勻分布
hash函數(shù)的輸出值踱蠢，每個(gè)位置上的值均是獨(dú)立的。
- hash 表
一個(gè)矩陣中只有0棋电，1兩種值茎截，每個(gè)位置都可以和自己的上下左右，四個(gè)位置相連赶盔，如果有一片1連在一起企锌，這個(gè)部分叫做一個(gè)島，求矩陣中有多少個(gè)島于未。
| 0 | 1 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
使用感染函數(shù)撕攒，把已經(jīng)感染的值1的上下左右變成2陡鹃，島的數(shù)量加1，繼續(xù)繼續(xù)重新遍歷打却，跳過0和2，循環(huán)遍歷谎倔。
public static int countIslands(int[][] m) {
if (m == null || m[0] == null) {
return 0;
}
int N = m.length;
int M = m[0].length;
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (m[i][j] == 1) {
res++;
infect(m, i, j, N, M);
}
}
}
return res;
}
public static void infect(int[][] m, int i, int j, int N, int M) {
if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
return;
}
m[i][j] = 2;
infect(m, i + 1, j, N, M);
infect(m, i - 1, j, N, M);
infect(m, i, j + 1, N, M);
infect(m, i, j - 1, N, M);
}
集合
- 查找兩個(gè)數(shù)是不是同一個(gè)集合：
通過進(jìn)行集合的合并柳击，給一個(gè)[1,2,3,4],每個(gè)數(shù)是自己的集合，[[1,], [2,], [3,], [4,]],如下片习，當(dāng)把[1]和[2]進(jìn)行合并時(shí)捌肴，把[2] 掛到[1]的集合上。
前綴樹
在進(jìn)行建樹的過程中藕咏，把字母依次在樹的路徑上進(jìn)行標(biāo)記状知，如果某一條路徑不存在，就建立一條路徑孽查。
使用前綴樹進(jìn)行字符的查找饥悴，構(gòu)建方法insert, delete,search進(jìn)前綴樹的構(gòu)建。
insert:是在數(shù)據(jù)樹中插入數(shù)據(jù)盲再，delete:刪除數(shù)據(jù)西设，search：在樹查找字符。
insert:沿著路徑進(jìn)行查找答朋，當(dāng)路徑不存在時(shí)構(gòu)建路徑贷揽，如果以及存在path++
delete：刪除路徑上的數(shù)據(jù)蓖柔，如果path==0,可以直接刪除之后的結(jié)果僚害，如果path！=0侣肄，需要?jiǎng)h除對(duì)應(yīng)數(shù)據(jù)洪规。
search：通過word進(jìn)行數(shù)據(jù)查找印屁。
public static class TrieNode {
public int path;
public int end;
public TrieNode[] nexts;
public TrieNode() {
path = 0;
end = 0;
nexts = new TrieNode[26];
}
}
public static class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
if (word == null) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
node.path++;
}
node.end++;
}
public void delete(String word) {
if (search(word) != 0) {
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (--node.nexts[index].path == 0) {
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.end--;
}
}
public int search(String word) {
if (word == null) {
return 0;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.end;
}
public int prefixNumber(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.path;
}
}
貪心算法的排序
if str1 + str2 < str2 + str1，str2 > str1
切分金條
子節(jié)點(diǎn)合并在一起的是葉節(jié)點(diǎn)的和斩例，怎么加最經(jīng)濟(jì)库车。
最大收益
有初始資金==w=10 ，有一組項(xiàng)目[[10,2],[12,3],[7,5],[,5,3],[13,10]]
[10, 2]:10為本金樱拴，2為利潤
家里兩個(gè)堆：
小根堆：按本金進(jìn)行排放柠衍，最小自放在最上面，都是現(xiàn)在無法完成的項(xiàng)目晶乔，沒錢
大根堆：按利潤進(jìn)行排放珍坊，最大的放上面，都是可以做的項(xiàng)目正罢。
從大根堆開始做項(xiàng)目阵漏，每次做最上的一個(gè)項(xiàng)目，做完之后把小根堆可以做的項(xiàng)目添加到大根堆上，直到k次或者大根堆已經(jīng)沒有項(xiàng)目可做結(jié)束履怯。
public static class MinCostComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.c - o2.c;
}
}
public static class MaxProfitComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o2.p - o1.p;
}
}
public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
Node[] nodes = new Node[Profits.length];
for (int i = 0; i < Profits.length; i++) {
nodes[i] = new Node(Profits[i], Capital[i]);
}
PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
for (int i = 0; i < nodes.length; i++) {
minCostQ.add(nodes[i]);
}
for (int i = 0; i < k; i++) {
while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
maxProfitQ.add(minCostQ.poll());
}
if (maxProfitQ.isEmpty()) {
return W;
}
W += maxProfitQ.poll().p;
}
return W;
}
動(dòng)態(tài)規(guī)劃
n回还！
同過解依賴問題n! = n * (n-1)! = n*(n-1)...1!
通過
'abc'
打印‘a(chǎn)bc’，打印所有字符組合叹洲。有三個(gè)位置柠硕，要a，不要a,要b运提，不要b,要c蝗柔，不要c。2x2x2=8種
public static void printAllSubsquence(String str) {
char[] chs = str.toCharArray();
process(chs, 0);
}
public static void process(char[] chs, int i) {
if (i == chs.length) {
System.out.println(String.valueOf(chs));
return;
}
process(chs, i + 1);
char tmp = chs[i];
chs[i] = 0;
process(chs, i + 1);
chs[i] = tmp;
}
- 母牛每年生一只母牛民泵，新出生的母牛成長三年后也能每年生一只 母牛癣丧，假設(shè)不會(huì)死。求N年后栈妆，母牛的數(shù)胁编。
n-1年和n-3年的牛綜合滿足第n年的類型，需要列出所有的牛的總數(shù)鳞尔，寫出所有的初始項(xiàng)掏呼。
F(n) = F(n-1) + F(n-3)
public static int cowNumber1(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
return cowNumber1(n - 1) + cowNumber1(n - 3);
}
- 給你一個(gè)二維數(shù)組，二維數(shù)組中的每個(gè)數(shù)都是正數(shù)铅檩，要求從左上 角走到右下角憎夷，每一步只能向右或者向下。沿途經(jīng)過的數(shù)字要累 加起來昧旨。返回最小的路徑和
public static int process1(int[][] matrix, int i, int j) {
int res = matrix[i][j];
if (i == 0 && j == 0) {
return res;
}
if (i == 0 && j != 0) {
return res + process1(matrix, i, j - 1);
}
if (i != 0 && j == 0) {
return res + process1(matrix, i - 1, j);
}
return res + Math.min(process1(matrix, i, j - 1), process1(matrix, i - 1, j));
}
通過構(gòu)建dp表拾给，因?yàn)閺?i,j)點(diǎn)到(n,n)的值固定，所以通過構(gòu)建dp樹可以進(jìn)行dp通過解所有的dp表就可以解出最小值.
| 3 | 1 | 0 | 2 |
|---|---|---|---|
| 4 | 3 | 2 | 1 |
| 5 | 2 | 1 | 0 |
bp表：
| (i,j) | (i,j+1) | * | 3 |
|---|---|---|---|
| (i+1,j) | * | * | 1 |
| 8 | 3 | 1 | 0 |
通過化解遞歸兔沃，使用動(dòng)態(tài)規(guī)劃：
public static int minPath2(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
int row = m.length;
int col = m[0].length;
int[][] dp = new int[row][col];
dp[0][0] = m[0][0];
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + m[i][0];
}
for (int j = 1; j < col; j++) {
dp[0][j] = dp[0][j - 1] + m[0][j];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
}
}
return dp[row - 1][col - 1];
}
- 給你一個(gè)數(shù)組arr蒋得，和一個(gè)整數(shù)aim。如果可以任意選擇arr中的 數(shù)字乒疏，能不能累加得到aim额衙，返回true或者false2
在數(shù)組中，一個(gè)數(shù)字怕吴，有要和不要窍侧，如果要就加上這個(gè)數(shù)組，如果得到aim转绷，返回true伟件。
public static boolean money1(int[] arr, int aim) {
return process1(arr, 0, 0, aim);
}
public static boolean process1(int[] arr, int i, int sum, int aim) {
if (sum == aim) {
return true;
}
// sum != aim
if (i == arr.length) {
return false;
}
return process1(arr, i + 1, sum, aim) || process1(arr, i + 1, sum + arr[i], aim);
}
