Java數(shù)據(jù)結(jié)構(gòu)與算法初級(jí)篇之?dāng)?shù)組、集合和散列表> 數(shù)據(jù)是基礎(chǔ)，算法是靈魂
本文出自門心叼龍的博客，屬于原創(chuàng)類容，轉(zhuǎn)載請(qǐng)注明出處。https://blog.csdn.net/geduo_83/article/details/86385566
源碼下載地址：https://download.csdn.net/download/geduo_83/10913510
初級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法初級(jí)篇之?dāng)?shù)組、集合和散列表
中級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法中級(jí)篇之棧、隊(duì)列、鏈表
高級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法高級(jí)篇之樹、圖
理論篇：Java數(shù)組、集合、散列表常見算法淺析
理論篇：Java棧、隊(duì)列、鏈表常見算法淺析
理論篇：Java樹、圖常見算法淺析
1. 前言
2. 數(shù)組
2.1 概念
2.2 特點(diǎn)
2.3 存儲(chǔ)結(jié)構(gòu)
2.4 使用場(chǎng)景
2.5 相關(guān)算法
3. 集合
3.1 概念
3.2 特點(diǎn)
3.3 適用場(chǎng)景
3.4 相關(guān)算法
3.5 性能分析
4. 散列表
4.1 概念
4.2 哈希算法
4.3 哈希沖突
4.4 存儲(chǔ)結(jié)構(gòu)
4.5 特點(diǎn)
4.6 適用場(chǎng)景
4.7 性能分析
5. 小結(jié)
****1. 前言****
之前沒有寫過關(guān)于數(shù)據(jù)結(jié)構(gòu)的文章，那么今天我們將在本文中介紹最基礎(chǔ)、最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。
數(shù)組，作為數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的一個(gè)存儲(chǔ)方式，是我們學(xué)習(xí)一切數(shù)據(jù)結(jié)構(gòu)、算法的基石。大部分的數(shù)據(jù)結(jié)構(gòu)可以用數(shù)組來實(shí)現(xiàn)。接下來我們會(huì)介紹數(shù)組的概念、存儲(chǔ)結(jié)構(gòu)、特點(diǎn)和使用場(chǎng)景。
集合算是升級(jí)版的數(shù)組，在本文當(dāng)中我們會(huì)介紹集合的概念、特點(diǎn)、實(shí)現(xiàn)以及的它的適用場(chǎng)景。
散列表又叫哈希表，在很多語言中都是在數(shù)組的基礎(chǔ)上實(shí)現(xiàn)的，當(dāng)然散列表也有其他的實(shí)現(xiàn)形式，本文我們會(huì)介紹散列表的基本概念、特點(diǎn)、實(shí)現(xiàn)方式等。
****2. 數(shù)組****
****2.1 概念****
數(shù)組是內(nèi)存中有序的元素序列
****2.2 特點(diǎn)****
定長(zhǎng)、按順序訪問、索引快、插入刪除慢
****2.3 存儲(chǔ)結(jié)構(gòu)****
[圖片上傳失敗...(image-f51670-1553424312385)]
?[圖片上傳失敗...(image-1f1cb-1553424312387)]
?
****2.4 使用場(chǎng)景****
數(shù)組其實(shí)是非常簡(jiǎn)單的一個(gè)數(shù)據(jù)結(jié)構(gòu)，用起來也比較簡(jiǎn)單，他是其他所有數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，所以只有掌握好數(shù)組，才能學(xué)習(xí)好其他的數(shù)據(jù)結(jié)構(gòu)和算法。
什么時(shí)候使用數(shù)組，通過數(shù)據(jù)的特點(diǎn)我們就可以想到，數(shù)據(jù)的長(zhǎng)度是固定的，所以不會(huì)出現(xiàn)長(zhǎng)度變化的業(yè)務(wù)上比較適合使用數(shù)組
如果我們?cè)赼pp開發(fā)中非常常見的菜單按鈕，它的個(gè)數(shù)一般都是固定的不會(huì)發(fā)生變化，如下圖這個(gè)界面有首頁、報(bào)表、消息、我的，我們就可以用數(shù)組來存儲(chǔ)。
[圖片上傳失敗...(image-c4b201-1553424312385)]
?[圖片上傳失敗...(image-fa42a-1553424312387)]
?
****2.5 相關(guān)算法****
****2.5.1 冒泡排序****
通過相鄰的兩個(gè)數(shù)兩兩相比來進(jìn)行排序，其中有兩個(gè)循環(huán)，第一個(gè)循環(huán)控制循環(huán)的輪次，第二個(gè)循環(huán)控制每一個(gè)輪次循環(huán)的次數(shù)，第一輪循環(huán)確定的最后一個(gè)元素，第二輪循環(huán)確定的是倒數(shù)第二個(gè)元素，照這樣下去，直到確定了第一個(gè)元素，則循環(huán)排序完畢。
需要注意的是，第一個(gè)循環(huán)它的結(jié)束條件是i < len-1; 第二個(gè)循環(huán)的結(jié)束條件是j < len - i - 1;
package A數(shù)組.A001冒泡排序;
/**
* Description: <冒泡排序><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
sortBubbling(arr);
int i = 0;
while (i < arr.length) {
System.out.println(arr[i]);
i++;
}
}
// 冒泡排序：兩個(gè)循環(huán)，通過兩兩相比，進(jìn)行排序
private static void sortBubbling(int[] arr) {
// 第一輪確定最后一個(gè)，第二輪確定倒數(shù)第二個(gè)...
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
// 兩兩相比，就像魚吐水泡一樣...
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
}
****2.5.2 選擇排序****
第一步拿出第一個(gè)元素和剩余的元素進(jìn)行比較，確定了第一個(gè)元素，第二步拿出第二個(gè)元素和剩余元素進(jìn)行比較，確定了第二個(gè)元素，照這樣下去，直到確定了最后一個(gè)元素，則循環(huán)排序完畢。和冒泡排序一樣，也是通過兩個(gè)循環(huán)來完成的，第一個(gè)循環(huán)是控制循環(huán)的輪次，第二個(gè)循環(huán)是控制每一輪循環(huán)的次數(shù)。
需要注意的是，第一個(gè)循環(huán)它的結(jié)束條件是i < len-1和冒泡排序一樣，第二個(gè)循環(huán)的開始條件是j = i + 1; 結(jié)束條件是j < len 。
通過分析我們不難得出結(jié)論，無論是冒泡排序還是選擇排序，第一個(gè)控制輪次的循環(huán)的結(jié)束條件都是一樣的都是len - 1; 第二個(gè)控制每一輪循環(huán)次數(shù)的條件是相反的，冒泡排序控制的是結(jié)束條件j < len - i - 1，而選擇排序控制的是開始條件j = i + i。
這是我們哲學(xué)中講的矛盾，而冒泡和選擇就是我們矛盾的兩個(gè)方面。
package A數(shù)組.A002選擇排序;
/**
* Description: <選擇排序><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
sortChange(arr);
int i = 0;
while (i < arr.length) {
System.out.println(arr[i]);
i++;
}
}
// 選擇排序，選擇第一個(gè)元素和剩下的n-1個(gè)比較
private static void sortChange(int[] arr) {
// 第一輪確定第一個(gè)元素，第二輪確定第二個(gè)元素
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
// 選擇第一i個(gè)元素和剩余的元素進(jìn)行比較
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
}
****2.5.3 桶排序****
桶排序的核心思想就是以源數(shù)組的值作為新數(shù)組的下標(biāo)找到這個(gè)新元素，然后對(duì)該元素進(jìn)行加1賦值。通過遍歷源數(shù)組對(duì)新數(shù)組進(jìn)行加1操作，一輪循環(huán)完，排序也就確定了，然后對(duì)新數(shù)組進(jìn)行遍歷只要發(fā)現(xiàn)值大于0的元素就打印它的下標(biāo)，而打印的值就是我們想要的結(jié)果。
需要我們注意的是桶排序是有前提條件的必須要知道源數(shù)組中的最大元素才行，因?yàn)橹挥兄雷畲笤夭拍艽_定新數(shù)組的長(zhǎng)度。
桶排序的效率是非常高的，但是如果源數(shù)組的值是不均勻的那么勢(shì)必會(huì)造成空間的浪費(fèi)，桶排序就是典型的以空間換時(shí)間的最佳范例。
package A數(shù)組.A003桶排序;
/**
* Description: <桶排序><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
sortBucket(arr);
// int i = 0;
// while (i < arr.length) {
// System.out.println(arr[i]);
// i++;
// }
}
// 桶排序，聲明一個(gè)以 最大元素+1 為長(zhǎng)度的數(shù)組，遍歷原數(shù)組，桶數(shù)組計(jì)數(shù)
private static void sortBucket(int[] arr) {
int[] arr1 = new int[34 + 1];
for (int i = 0; i < arr.length; i++) {
arr1[arr[i]]++;
}
for (int i = 0; i < arr1.length; i++) {
int count = arr1[i];
while (count > 0) {
System.out.println(i);
count--;
}
}
}
}
****2.5.4 數(shù)組中是否有重復(fù)元素****
說到元素重復(fù)我們自然會(huì)想到數(shù)組、集合，這兩種數(shù)據(jù)結(jié)構(gòu)都是允許重復(fù)數(shù)據(jù)的，而散列表是不允許有重復(fù)數(shù)據(jù)的。
我們想了如果我們遍歷數(shù)組中的元素，把這些元素存儲(chǔ)在散列表當(dāng)中將會(huì)何如？有的人會(huì)說去重復(fù)了，是的沒有錯(cuò)，但更重要的是我們?cè)趯?shù)組的元素往散列表里面存入的時(shí)候加一個(gè)是否該元素在散列表中是否存在的判斷不就完了嗎？如果散列表中沒有耶就直接存儲(chǔ)了，如果有也就直接返回了，就這么簡(jiǎn)單。
這一招需要我們對(duì)散列表的知識(shí)非常的了解，其實(shí)對(duì)于集合和散列表都有contains這個(gè)方法。
package A數(shù)組.A004數(shù)組是否有重復(fù)元素;
import java.util.HashSet;
/**
* Description: <數(shù)組是否有重復(fù)元素><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
int[] arr = {11, 3, 10, 11, 34, 5, 21};
System.out.println(checkRepeat(arr));
}
// 查找一個(gè)數(shù)組里面有沒有重復(fù)元素
private static boolean checkRepeat(int[] arr) {
// 1.聲明一個(gè)散列表表
// 2.遍歷這個(gè)數(shù)組
// 3.對(duì)遍歷的元素依次進(jìn)行判斷，如果散列表里面沒有就往散列表里面塞，有就直接退出了
HashSet<Integer> hashSet = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
if (hashSet.contains(arr[i])) {
return true;
} else {
hashSet.add(arr[i]);
}
}
return false;
}
}
****2.5.5 刪除數(shù)組中的重復(fù)元素****
通過我們對(duì)上面判斷一個(gè)數(shù)組中是否有重復(fù)元素的分析，再做這個(gè)題就非常的簡(jiǎn)單了，直接用用一個(gè)散列表就ok了。
有沒有其他的解決方案？有沒有不借助其他的數(shù)據(jù)結(jié)構(gòu)直接就能實(shí)現(xiàn)的方案？有，其實(shí)方案的中心思想就是選擇排序有點(diǎn)像，就是取出當(dāng)前元素和其他剩余的元素進(jìn)行對(duì)比，如果有相等的則將后面的所有元素往前移動(dòng)一個(gè)位置，移動(dòng)完畢在對(duì)源數(shù)組的長(zhǎng)度進(jìn)行減1的壓縮處理，壓縮完畢在從頭開始循環(huán)判斷。
這個(gè)方法就注意兩點(diǎn)，首先只要相等就把后面的所有元素往前移位，然后移動(dòng)完畢在對(duì)源數(shù)組長(zhǎng)度進(jìn)行減1的壓縮處理，壓縮完畢重新開始循環(huán)。
package A數(shù)組.A005刪除數(shù)組重復(fù)元素;
import java.util.Arrays;
/**
* Description: <刪除數(shù)組重復(fù)元素><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAgorithm {
public static void main(String[] arg) {
int[] arr = {1, 3, 10, 1, 34, 5, 21};
arr = removeRepeat(arr);
int i = 0;
while (i < arr.length) {
System.out.println(arr[i]);
i++;
}
}
// 查找一個(gè)數(shù)組里面有沒有重復(fù)元素，如果有則刪除重復(fù)元素
private static int[] removeRepeat(int[] arr) {
// 取出第一個(gè)元素和剩余的其他元素進(jìn)行對(duì)比
// 一旦發(fā)現(xiàn)相等，則后面的元素都往前移動(dòng)一個(gè)，移動(dòng)完畢數(shù)組
loop: for (int i = 0; i < arr.length; i++) {
for (int k = i + 1; k < arr.length; k++) {
// 如果相等則后面的元素同意往前移動(dòng)
if (arr[i] == arr[k]) {
int head = k;
while (head < arr.length - 1) {
arr[head] = arr[head + 1];
head++;
}
// 對(duì)數(shù)組進(jìn)行壓縮處理
arr = Arrays.copyOf(arr, arr.length - 1);
i = 0;
// 壓縮完畢，重頭開始執(zhí)行
continue loop;
}
}
}
return arr;
}
}
****2.5.6 兩數(shù)求和****
說到兩數(shù)之和，那么就會(huì)想到數(shù)組中的任意兩個(gè)元素都會(huì)碰一下求和和我們的目標(biāo)數(shù)對(duì)比一下如果相等就把這兩個(gè)元素的下標(biāo)返回，這就把問題解決了。
任意兩個(gè)元素都要碰一下，此時(shí)我們又想到了選擇排序，通過這個(gè)算法我們就能實(shí)現(xiàn)兩兩相碰。兩個(gè)循環(huán)一個(gè)判斷就能問題解決。
還有另外一種算法，首先我們可以新建一個(gè)新的數(shù)據(jù)對(duì)象，還對(duì)象有兩個(gè)字段，一個(gè)存下標(biāo)，一個(gè)存元素的值，接著通過源數(shù)組建立一個(gè)以新數(shù)據(jù)對(duì)象為元素的數(shù)組并對(duì)該數(shù)組進(jìn)行排序，然后聲明兩個(gè)指針，一個(gè)頭指針，一個(gè)尾指針，這兩個(gè)指針分別從數(shù)組的頭和尾進(jìn)行前進(jìn)移動(dòng)和回退移動(dòng)，每移動(dòng)一步求和，和目標(biāo)數(shù)進(jìn)行對(duì)比，如果小于目標(biāo)數(shù)則頭指針往前移動(dòng)，然后再求和對(duì)比，如果大于目標(biāo)數(shù)則尾指針回退移動(dòng)再求和對(duì)比，直到相等就將兩個(gè)對(duì)象的下標(biāo)返回就解決問題了。
這兩種算法各有優(yōu)劣，方案1當(dāng)然代碼量最少是最簡(jiǎn)單的，方案2讓我們感受到了指針在運(yùn)算中神奇作用，雖然代碼量有些大，但是思路還是很清晰的。
package A數(shù)組.A006兩數(shù)求和;
import java.util.Arrays;
/**
* Description: <><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
int[] arr = {1, 23, 12, 2, 11, 22};
int[] res = get(arr, 33);
System.out.println(Arrays.toString(res));
}
static class Data implements Comparable<Data>{
int index;
int data;
public Data(int index, int data) {
this.index = index;
this.data = data;
}
@Override
public int compareTo(Data o) {
return data - o.data;
}
@Override
public String toString() {
return "Data{" + "index=" + index + ", data=" + data + '}';
}
}
// 指定一個(gè)目標(biāo)數(shù)，查找其中兩個(gè)數(shù)之和等于目標(biāo)數(shù)的下標(biāo)
public static int[] get(int[] arr, int sum) {
int[] result = {0, 0};
// 1.首先對(duì)原數(shù)組排序
Data[] arr1 = new Data[arr.length];
int i = 0;
while( i < arr.length){
arr1[i] = new Data(i,arr[i]);
i++;
}
Arrays.sort(arr1);
System.out.println(Arrays.toString(arr1));
// 2.聲明兩個(gè)指針，head，tail
int head = 0;
int tail = arr.length - 1;
while (head < tail) {
if ((arr1[head].data + arr1[tail].data) == sum) {
result[0] = arr1[head].index;
result[1] = arr1[tail].index;
return result;
} else if ((arr1[head].data + arr1[tail].data) < sum) {
head++;
} else {
tail--;
}
}
return null;
}
}
****2.5.7 求從左上到右下的路徑數(shù)****
這道題大意是這樣的，已知給定了一個(gè)m*n的二維數(shù)組，以第一個(gè)元素作為開始點(diǎn)，以最后一個(gè)元素作為結(jié)束點(diǎn)，然后開始點(diǎn)開始移動(dòng)，并且只能往右往下移動(dòng)直到到達(dá)結(jié)束點(diǎn)，求一共有多少條路徑數(shù)？
看到這道算法題想必有很多人都會(huì)懵圈，真是老虎吃天無從下手，這背后到底有什么樣的邏輯關(guān)系？會(huì)用到哪些數(shù)據(jù)結(jié)構(gòu)？用到什么樣的循環(huán)？用到什么樣的判斷？
其實(shí)具體的思路是這樣的，聲明一個(gè)m*n的二維數(shù)組，初始化賦值都為0，接著給數(shù)組的第一行賦值為1，然后給數(shù)組的第一列賦值為1，最后一步給數(shù)組中剩余的其他所有元素賦值，其他元素的值為它正上方元素的值和它正左方元素的值之和，賦值完成之后最后一個(gè)元素arr[m-1][n-1]的值就是我們所要計(jì)算的路徑數(shù)，一臉懵逼，為什么？為什么通過這樣的賦值就是我們想要的計(jì)算結(jié)果路徑數(shù)？其實(shí)這就是算法中動(dòng)態(tài)規(guī)劃的問題。
我們把第一行個(gè)第一列都賦值為1，為什么？，如果只有一行或只有一列這兩種情況都只有一條路，因此賦值為1沒毛病，這是合乎邏輯的，然后我們開始移動(dòng)，每走一步無外乎有兩種方案，要么往前走，要么往下走，那么走到當(dāng)前格子就有兩種方案，而這個(gè)值正是它正上方元素和正左方元素的和，那么同樣道理其他格子的值以此類推，而最后一個(gè)元素arr[m-1][n-1]的值就是我們所要計(jì)算的路徑數(shù)。
這就是動(dòng)態(tài)規(guī)劃其中的奧妙之處，通過三個(gè)循環(huán)簡(jiǎn)簡(jiǎn)單單的解決了我們的問題。
package A數(shù)組.A007左上到右下路徑數(shù);
/**
* Description: <在一個(gè)m*n的矩形方格中， 機(jī)器人在最左上的格子里，一次只能挪動(dòng)一步，只能往右往下移動(dòng) 目標(biāo)地點(diǎn)在最右下方的方格里，問共有幾條路徑 ><br>
* Author: 門心叼龍<br>
* Date: 2018/11/23<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
int path = getPath(3, 3);
System.out.println(path);
int[][] arr = new int[2][3];
System.out.println("length:"+arr.length);
}
// 動(dòng)態(tài)規(guī)劃問題
public static int getPath(int m, int n) {
int[][] arr = new int[m][n];
// 將第一行都賦值為1
for (int i = 0; i < n; i++) {
arr[0][i] = 1;
}
// 將第一列都賦值為1
for (int i = 0; i < m; i++) {
arr[i][0] = 1;
}
// 給其他單元格賦值
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
}
}
return arr[m - 1][n - 1];
}
}
****2.5.8 求左上到右下的路徑最小值****
這個(gè)問題是上面求路徑數(shù)問題的擴(kuò)展，求最小路徑數(shù)，不同的是現(xiàn)在還是一個(gè)m*n的二維數(shù)組，不過這個(gè)數(shù)組每個(gè)元素都已經(jīng)賦值了，讓你求路徑上所有元素的和的最小值，從左上到右下的路徑有n多條，但是肯定有一條的和值是最小的。其實(shí)這還是一個(gè)動(dòng)態(tài)規(guī)劃的問題。
具體解決思路如下，首先聲明一個(gè)大小完全相同二維數(shù)組，現(xiàn)在要給其賦值，賦值完畢我們要的結(jié)果也就出來了，第一個(gè)元素的值就是源數(shù)組第一個(gè)元素的值，第一行其他元素的值就是當(dāng)前元素的前導(dǎo)元素的值和源數(shù)組這個(gè)位置元素的值的和，第一列其他元素的值就是他的前導(dǎo)元素的值與源數(shù)組這個(gè)位置元素的值的和，然后其他元素的值就是當(dāng)前元素上方元素和左方元素取最小值和源數(shù)組這個(gè)位置元素的值求和，其他元素得計(jì)算方式以此類推，直到賦值完成，而最后一個(gè)元素的值就是我們要計(jì)算的左上到右下路徑的最小值。
通過分析我們不難發(fā)現(xiàn)，不管是求路徑數(shù)，還是求路徑的最小值，其背后的核心思想都是動(dòng)態(tài)規(guī)劃。通過對(duì)數(shù)組的動(dòng)態(tài)的賦值計(jì)算，從而得到我們要計(jì)算的結(jié)果。
package A數(shù)組.A008左上到右下路徑中的最小值;
/**
* Description: <在一個(gè)m*n的矩形方格中， 機(jī)器人在最左上的格子里，一次只能挪動(dòng)一步，只能往右往下移動(dòng) 目標(biāo)地點(diǎn)在最右下方的方格里，問共有幾條路徑，求路徑中的最小值><br>
* Author: 門心叼龍<br>
* Date: 2018/11/23<br>
* Version: V1.0.2<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
int[][] grid = new int[][] {{1, 1, 8}, {3, 1, 4}, {6, 2, 1}};
int minvalue = getMinvalue(grid);
System.out.println(minvalue);
}
private static int getMinvalue(int[][] grid) {
int[][] result = new int[grid.length][grid[0].length];
// 給result[0][0]賦值
result[0][0] = grid[0][0];
// 給第一行賦值
for (int i = 1; i < result[0].length; i++) {
result[0][i] = result[0][i - 1] + grid[0][i];
}
// 給第一列賦值
for (int i = 1; i < result.length; i++) {
result[i][0] = result[i - 1][0] + grid[i][0];
}
// 給其他元素賦值
for (int i = 1; i < result.length; i++) {
for (int j = 1; j < result[0].length; j++) {
result[i][j] = Math.min(result[i - 1][j], result[i][j - 1]) + grid[i][j];
}
}
return result[result.length - 1][result[0].length - 1];
}
}
****3. 集合****
****3.1 概念****
大家知道數(shù)據(jù)的致命缺點(diǎn)就是長(zhǎng)度固定，如果我們要存儲(chǔ)的數(shù)據(jù)長(zhǎng)度不固定，該怎么辦？這時(shí)候就要用集合了，其實(shí)集合也是基于數(shù)組實(shí)現(xiàn)的，不過它是一個(gè)變長(zhǎng)數(shù)組，想放入多少就可以放入多少。集合就是一個(gè)變長(zhǎng)數(shù)組或者叫做動(dòng)態(tài)數(shù)組。
****3.2 特點(diǎn)****
1.它的長(zhǎng)度是可變的
2.他會(huì)浪費(fèi)一定內(nèi)存空間
3.數(shù)據(jù)的拷貝會(huì)浪費(fèi)一定的時(shí)間
****3.3 適用場(chǎng)景****
集合的適用場(chǎng)景非常多，如果博客的文章列表、評(píng)論列表等，只要有列表就有集合的身影。
?
****3.4 常見的算法****
****3.4.1 自定義實(shí)現(xiàn)一個(gè)集合****
集合我們知道他是一個(gè)變長(zhǎng)數(shù)組，只有變長(zhǎng)才能源源不斷的往里面存放數(shù)據(jù)，通過集合元素添加流程圖我們也能看到，首先需要初始化一個(gè)數(shù)組，然后在添加元素的時(shí)候如果源數(shù)組滿了就需要擴(kuò)容了，當(dāng)然擴(kuò)容的系數(shù)有的是2倍，有的是0.75倍，這由自己定，不管是數(shù)組的擴(kuò)容還是壓縮都用到了數(shù)組工具類中非常重要的一個(gè)方法Arrays.copy(),有了添加的方法，必然少不了刪除方法，刪除的思路也很簡(jiǎn)單，就是把要?jiǎng)h除的元素之后的元素都往回移動(dòng)一位，然后再把最后一個(gè)元素賦值為0再退出循環(huán)就ok了。
現(xiàn)在我們不妨畫個(gè)流程圖方便大家理解集合的工作原理：
?
代碼實(shí)現(xiàn)如下：
package B集合.A001自定義實(shí)現(xiàn)一個(gè)ArrayList;
import java.util.Arrays;
/**
* Description: <自定義實(shí)現(xiàn)一個(gè)ArrayList><br>
* Author: 門心叼龍<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyArrayList {
private int[] arr;
private int initsize = 5;
private int size = 0;
public MyArrayList() {
arr = new int[initsize];
}
public int get(int index) {
return arr[index];
}
public boolean add(int value) {
// 說明此時(shí)數(shù)組已經(jīng)滿了，要擴(kuò)容了
if (size == arr.length) {
System.out.println("數(shù)組要擴(kuò)容了...");
arr = Arrays.copyOf(arr, size * 2);
}
arr[size++] = value;
return true;
}
public boolean remove(int value) {
if (arr.length > 0) {
loop: for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
int temp = i;
while (temp < arr.length - 1) {
arr[temp] = arr[temp + 1];
temp++;
}
arr[--size] = 0;
break loop;
}
}
}
return true;
}
public int size() {
return size;
}
}
****3.4.2 刪除集合中的偶數(shù)****
很多初學(xué)者看到這個(gè)問題都覺的太簡(jiǎn)單了，不就一個(gè)循環(huán)就解決問題了嗎？其實(shí)這是有大問題的，問什么？你想了循環(huán)開始的時(shí)候循環(huán)結(jié)束的條件就已經(jīng)確定了，如果你在循環(huán)的過程中刪除了一個(gè)元素，那么數(shù)組長(zhǎng)度就變短了，而我們循環(huán)并沒有停止，當(dāng)循環(huán)走到最后的時(shí)候勢(shì)必會(huì)造成數(shù)組下標(biāo)越界的空指針異常，怎么辦？其實(shí)我們通過集合迭代器來做這個(gè)刪除的工作就可以完美的規(guī)避這個(gè)問題。因?yàn)榈鞑恍枰聵?biāo)，也就不存在數(shù)組下標(biāo)越界的問題。
package B集合.A002刪除集合中的偶數(shù);
import java.util.ArrayList;
import java.util.Iterator;
/**
* Description: <刪除集合中的偶數(shù)><br>
* Author: 門心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] arg) {
ArrayList<Integer> list = new ArrayList() {
{
add(1);
add(2);
add(3);
add(4);
}
};
removeEvenNumber(list);
int i = 0;
while (i < list.size()) {
System.out.println(list.get(i));
i++;
}
}
// 刪除集合中的偶數(shù)元素
private static void removeEvenNumber(ArrayList<Integer> myArrayList) {
Iterator<Integer> iterator = myArrayList.iterator();
while (iterator.hasNext()) {
Integer next = iterator.next();
if (next % 2 == 0) {
iterator.remove();
}
}
}
}
****3.5 性能分析****
在算法中，每種算法的性能指標(biāo)一般都有兩個(gè)，即時(shí)間復(fù)雜度和空間復(fù)雜度。
時(shí)間復(fù)雜度：它定量的描述了該算法的運(yùn)行時(shí)間。常常用大寫的O表示。
空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間大小的度量。
雖然集合這個(gè)變長(zhǎng)數(shù)組比普通的數(shù)組高級(jí)一些，但是本質(zhì)上它還是基于數(shù)組實(shí)現(xiàn)的，所以它和數(shù)組的性能差不多。
對(duì)于數(shù)組的操作，并不像我們看到的那么直觀，計(jì)算機(jī)需要根據(jù)我們具體操作的位置，從頭到尾一個(gè)一個(gè)地尋找到指定的位置，所以我們?cè)跀?shù)組中增加元素、修改元素、獲取元素等操作的時(shí)間復(fù)雜度都為O(n)。
變長(zhǎng)數(shù)據(jù)也有性能損耗的問題，如果插入的元素發(fā)現(xiàn)其中固定的數(shù)組的長(zhǎng)度不夠，則需要建立一個(gè)新的更長(zhǎng)的數(shù)組，還要拷貝元素到新的數(shù)組，這都會(huì)造成性能損耗。
****4. 散列表****
****4.1 概念****
前面我們講了數(shù)組和集合，他們都有一個(gè)共同的特點(diǎn)，他們?cè)趦?nèi)存中的存儲(chǔ)順序是有序的，如果數(shù)據(jù)量很大我們需要在數(shù)組或者集合中查找一個(gè)元素，或者在數(shù)組或集合的頭部添加或者刪除一個(gè)元素，它的性能就會(huì)大大降低。
此時(shí)散列表就應(yīng)運(yùn)而生了，散列表是一種以空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)。
讓我們想一下，若在手機(jī)的通信錄中查找一個(gè)人，那我們應(yīng)該不會(huì)從第1個(gè)人一直的查找下去，因?yàn)檫@樣實(shí)在是太慢了。我們其實(shí)是這樣做的：首先看這個(gè)人的名字的首字母是什么，比如姓趙，那么我們會(huì)點(diǎn)擊字母z，列表里以字母z開始的人名都會(huì)迅速的查找出來，就很快的查找到我們要查找的那個(gè)人。
還有我們?cè)诓樽值涞臅r(shí)候，需要查找一個(gè)單詞，肯定不會(huì)從頭翻到尾，而是通過這字的首字母，查找到對(duì)應(yīng)的那一頁，這樣可以速度的跳到那個(gè)字所在的頁面。
其實(shí)這里就用到了散列表的思想。
散列表又叫哈希表，能通過給定的關(guān)鍵字的值直接訪問到具體對(duì)應(yīng)的值的一個(gè)數(shù)據(jù)結(jié)構(gòu)。也就是說，通過關(guān)鍵字映射到一個(gè)表中的位置來直接訪問記錄，以加速訪問的速度。
而這個(gè)關(guān)鍵字就是我通常所說的key，把對(duì)應(yīng)的記錄稱為value，所以可以說也是通過這個(gè)key訪問一個(gè)映射表來得到value的值，而這個(gè)映射表就是所說的散列表，也叫哈希表。
****4.2 哈希算法****
剛才我們說到，通過關(guān)鍵字映射到一個(gè)表中的位置來直接訪問記錄，這個(gè)映射到表中的位置就是通過哈希算法來實(shí)現(xiàn)的，目前這個(gè)哈希算法的實(shí)現(xiàn)的方法比較多，主要有以下一種：
1.直接尋址法
2.數(shù)字分析法
3.平方取中法
4.隨機(jī)數(shù)法
5.除留取余法
****4.3 哈希沖突****
會(huì)有這樣一種情況，有多個(gè)不同的Key通過哈希函數(shù)可能會(huì)得到相同的地址，這樣就會(huì)造成對(duì)數(shù)據(jù)的覆蓋、丟失。那么解決哈希沖突的處理方式也有很多種，主要有以下幾種方法：
1.開放地址法
2.再哈希法
3.鏈接地址法
****4.4 存儲(chǔ)結(jié)構(gòu)****
一個(gè)好的散列表設(shè)計(jì)，除了需要選擇一個(gè)性能較好的哈希函數(shù)，還要選擇一個(gè)好的沖突解決方式。這里我們選擇除留取余法作為哈希算法，選擇鏈接地址法作為沖突的處理方式。
?
****4.5 特點(diǎn)****
散列表有兩種用法，一種是key的值和Value的值一樣，一般我們稱這種數(shù)據(jù)結(jié)構(gòu)為Set集合；如果Key的值和Value的值不一樣，我們稱這種情況為Map。
1.增啥改查的速度都很快
2.無序
****4.6 適用場(chǎng)景****
1.數(shù)據(jù)緩存
2.快速查找
****4.7 性能分析****
散列表的訪問，如果沒有碰撞，那么我們完全可以認(rèn)為對(duì)元素的訪問的時(shí)間復(fù)雜度為O(1)
但是實(shí)際上不可能沒有碰撞，Java中使用鏈表來解決，而碰撞之后的訪問需要遍歷鏈表，所以時(shí)間的復(fù)雜度將變?yōu)镺(L),其中L為鏈表的長(zhǎng)度。
****5. 小結(jié)****
數(shù)組，作為數(shù)據(jù)結(jié)構(gòu)中最為基礎(chǔ)的、常用的一個(gè)結(jié)構(gòu)。而集合與散列表他們都是在數(shù)組的基礎(chǔ)上進(jìn)行稍微高級(jí)點(diǎn)的擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)，通過對(duì)比這三種數(shù)據(jù)結(jié)構(gòu)，我們更加清楚他們之間的區(qū)別和應(yīng)用場(chǎng)景了，對(duì)數(shù)組的應(yīng)用有了更加深入的理解。
源碼下載地址：https://download.csdn.net/download/geduo_83/10913510
初級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法初級(jí)篇之?dāng)?shù)組、集合和散列表
中級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法中級(jí)篇之棧、隊(duì)列、鏈表
高級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法高級(jí)篇之樹、圖
理論篇：Java數(shù)組、集合、散列表常見算法淺析
理論篇：Java棧、隊(duì)列、鏈表常見算法淺析
理論篇：Java樹、圖常見算法淺析
問題反饋
有任何問題，請(qǐng)?jiān)谖恼孪路搅粞浴?/p>
關(guān)于作者
var geduo_83 = {
nickName : "門心叼龍",
site : "http://www.weibo.com/geduo83"
}
