一脸秽，稀疏數(shù)組
一骂删，稀疏數(shù)組的應(yīng)用場(chǎng)景
當(dāng)一個(gè)數(shù)組中大部分元素為0掌动，或者為同一個(gè)值的數(shù)組時(shí)，可以使用稀疏數(shù)組來保
存該數(shù)組宁玫。
二粗恢，稀疏數(shù)組的處理方法
1)記錄數(shù)組一共有幾行幾列，有多少個(gè)不同的值
2)把具有不同值的元素的行列及值記錄在一個(gè)小規(guī)模的數(shù)組中撬统，從而縮小程序的規(guī)模
三适滓，二維數(shù)組和稀疏數(shù)組互相轉(zhuǎn)換的思路
二維數(shù)組轉(zhuǎn)為稀疏數(shù)組
1).遍歷原始的二維數(shù)組，得到有效數(shù)據(jù)的個(gè)數(shù)sum
2).根據(jù)sum就可以創(chuàng)建稀疏數(shù)組sparseArr int[sum+1][3]
3).將二維數(shù)組的有效數(shù)據(jù)存入到稀疏數(shù)組
稀疏數(shù)組轉(zhuǎn)為二維數(shù)組
1).先讀取稀疏數(shù)組的第一行恋追，根據(jù)第一行的數(shù)據(jù)凭迹，創(chuàng)建原始的二維數(shù)組
2).在讀取稀疏數(shù)組后幾行的數(shù)據(jù)，并賦給原始的二維數(shù)組即可
四苦囱，代碼實(shí)現(xiàn)
public class SparseArry {
public static void main(String[] args) {
int cheesArray1[][] = new int[11][11];
cheesArray1[1][2] = 1;
cheesArray1[2][3] = 2;
System.out.println("原始的二維數(shù)組為：");
for (int[] row : cheesArray1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
// 將原始的二維數(shù)組轉(zhuǎn)換成稀疏數(shù)組
int sum = 0;
for (int i = 0; i < cheesArray1.length; i++) {
for (int j = 0; j < cheesArray1[i].length; j++) {
if (cheesArray1[i][j] != 0) {
sum++;
}
}
}
int sparseArray[][] = new int[sum + 1][3];
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
int count = 0;
for (int i = 0; i < cheesArray1.length; i++) {
for (int j = 0; j < cheesArray1[i].length; j++) {
if (cheesArray1[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = cheesArray1[i][j];
}
}
}
System.out.println();
System.out.println("轉(zhuǎn)換后的稀疏數(shù)組為：");
for (int i = 0; i < sparseArray.length; i++) {
System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
}
// 將稀疏數(shù)組回復(fù)為原始二維數(shù)組
System.out.println("恢復(fù)后的原始二維數(shù)組為：");
// 1.創(chuàng)建一個(gè)新的數(shù)組
int cheesArray2[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++) {
cheesArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
for (int[] row : cheesArray2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
二嗅绸，隊(duì)列
一.隊(duì)列的介紹
隊(duì)列是一個(gè)有序列表，可以用數(shù)組或是鏈表來實(shí)現(xiàn)撕彤，遵循先入先出的原則鱼鸠，即：先存入隊(duì)列的數(shù)據(jù)要先取出猛拴，后存入的要后取出。
二.使用數(shù)組模擬隊(duì)列
隊(duì)列本身是有序列表蚀狰，若使用數(shù)組的結(jié)構(gòu)來存儲(chǔ)隊(duì)列的數(shù)據(jù)愉昆，其中maxSize是隊(duì)列的最大容量。
因?yàn)殛?duì)列的輸出麻蹋，輸入是分別從前后端來處理的跛溉，因此需要兩個(gè)變量front及rear分別記錄隊(duì)列前后端的下標(biāo)，front會(huì)隨著數(shù)據(jù)輸出而改變扮授，而rear則是隨著數(shù)據(jù)輸入而改變
隊(duì)列
數(shù)組模擬隊(duì)列
?當(dāng)我們將數(shù)據(jù)存 入隊(duì)列時(shí)稱為”addQueue", addQueue 的處理需要有兩個(gè)步
驟:思路分析
1)將尾指針往后移: rear+1, 當(dāng)front == rear
[空]
2)若尾指針rear小于隊(duì)列的最大下標(biāo)maxSize-1芳室，則將數(shù)據(jù)存入rear所指的數(shù)
組元素中，否則無法存入數(shù)據(jù)刹勃。rear == maxSize - 1[隊(duì)列滿]
class ArrayQueue(arrMaxSize: Int) { val
?代碼實(shí)現(xiàn)
maxSize: Int = arrMaxSize
?問題分析并優(yōu)化
val array = new Arryl[nt(arrMaxSize)
var front: Int =-1
1初始化
var rear: Int = -1
val queue = new ArrayQueue(3)|
2. front 是隊(duì)列最前元素[不含]
