1. 需求：編寫五子棋程序务冕，有存盤和讀盤的功能血当。
當(dāng)一個數(shù)組中大部分元素是0，或者為同一個值時，可以使用稀疏數(shù)組來保存該數(shù)組臊旭。
稀疏數(shù)組的處理方法：
- 記錄數(shù)組一共有幾行幾列落恼，有多少個不同的值
-
把具有不同值的元素的行列以及值記錄在一個小規(guī)模的數(shù)組中，從而縮小程序的規(guī)模离熏。
例子：
image.png
6行7列變成了9行3列领跛，稀疏數(shù)組固定都是3列。
2. 應(yīng)用實例
使用稀疏數(shù)組來表示棋盤的二維數(shù)組來存盤撤奸，再將稀疏數(shù)組恢復(fù)成二維數(shù)組棋盤實現(xiàn)讀盤。
row? col? value
11?? 11?? 2 ? ? ?-- 11行11列喊括，2個有效數(shù)字
1??? 2??? 1? ? ? -- 第一行第二列胧瓜，值為1
2? ??3? ??2? ? ? -- 第二行第三列，值為2
二維數(shù)組轉(zhuǎn)稀疏數(shù)組思路：
- 遍歷二維數(shù)組郑什，得到有效值的個數(shù)sum
- 根據(jù)sum創(chuàng)建稀疏數(shù)組sparse-array int[sum + 1][3]
- 將二維數(shù)組的有效數(shù)據(jù)存入到稀疏數(shù)組
稀疏數(shù)組轉(zhuǎn)二維數(shù)組思路：
- 先讀取稀疏數(shù)組第一行府喳，根據(jù)第一行的數(shù)據(jù)創(chuàng)建原始的二維數(shù)組（第一行的前兩個值就是行數(shù)和列數(shù)）
- 再讀取稀疏數(shù)組后幾行的數(shù)據(jù)，并賦給原始的二維數(shù)組
3. 代碼
用vscode寫的蘑拯，文件是utf8的钝满，但是注釋卻是gbk的，不知道為什么申窘，就是javac的時候老報錯弯蚜，只能刪了注釋來運行。
-- 查了下資料剃法，“由于JDK是國際版的碎捺，我們在用javac編譯時，編譯程序首先會獲得我們操作系統(tǒng)默認(rèn)采用的編碼格式（GBK）贷洲，然后JDK就把Java源文件從GBK編碼格式轉(zhuǎn)換為Java內(nèi)部默認(rèn)的Unicode格式放入內(nèi)存中收厨，然后javac把轉(zhuǎn)換后的Unicode格式的文件編譯成class類文件，此時优构，class文件是Unicode編碼的诵叁，它暫存在內(nèi)存中，緊接著钦椭，JDK將此以Unicode格式編碼的class文件保存到操作系統(tǒng)中形成我們見到的class文件拧额。當(dāng)我們不加設(shè)置就編譯時，相當(dāng)于使用了參數(shù)：javac -encoding GBK Test.java玉凯，就會出現(xiàn)不兼容的情況势腮。”
https://github.com/toyranger/data_structure_algorithm.git
package com.ds.sparse.array;
public class SparseArray {
public static void main(String[] args) {
int[][] chessArray = genChessArray();
printArray(chessArray);
System.out.println("------------------------------");
int[][] trans2SparseArr = trans2SparseArr(chessArray);
printArray(trans2SparseArr);
System.out.println("------------------------------");
int[][] trans2ChessArr = trans2ChessArr(trans2SparseArr);
printArray(trans2ChessArr);
}
/***
* 生成原始的棋盤二維數(shù)組
* @return
*/
private static int[][] genChessArray() {
int[][] chessArray = new int[11][11];
chessArray[1][2] = 1;
chessArray[2][3] = 2;
return chessArray;
}
/***
* 遍歷打印數(shù)組
* @param array
*/
private static void printArray(int[][] array) {
for (int[] tmpArr : array) {
for (int value : tmpArr) {
System.out.printf("%d\t", value);
}
System.out.println();
}
}
/***
* 獲取二維數(shù)組中有效值個數(shù)
* @param array
* @return
*/
private static int getValidValueCnt(int[][] array) {
int cnt = 0;
for (int[] tmpArr : array) {
for (int tmpVal : tmpArr) {
if (0 != tmpVal) {
cnt++;
}
}
}
return cnt;
}
/***
* 二維數(shù)組轉(zhuǎn)成稀疏數(shù)組
* @param chessArr
* @return
*/
private static int[][] trans2SparseArr(int[][] chessArr) {
int valueCnt = getValidValueCnt(chessArr);
int[][] sparseArr = new int[valueCnt + 1][3];
// 第一行是原始二維數(shù)組的行數(shù)列數(shù)和有效值
int rowCnt = chessArr.length;
int colCnt = chessArr[0].length;
sparseArr[0][0] = rowCnt;
sparseArr[0][1] = colCnt;
sparseArr[0][2] = valueCnt;
// 遍歷棋盤數(shù)組漫仆，每找到一個有效值捎拯，對應(yīng)稀疏數(shù)組的行數(shù)加一，并且把有效值的行和列以及值存入該行
int sparseRow = 1;
for (int row = 0; row < rowCnt; row++) {
for (int col = 0; col < colCnt; col++) {
int value = chessArr[row][col];
if (0 != value) {
sparseArr[sparseRow][0] = row;
sparseArr[sparseRow][1] = col;
sparseArr[sparseRow][2] = value;
sparseRow++;
}
}
}
return sparseArr;
}
/***
* 稀疏數(shù)組還原成二維數(shù)組
* @param sparseArr
* @return
*/
private static int[][] trans2ChessArr(int[][] sparseArr) {
int rowCnt = sparseArr[0][0];
int colCnt = sparseArr[0][1];
int[][] chessArr = new int[rowCnt][colCnt];
// 從第二行開始遍歷稀疏數(shù)組，把有效值填入棋盤數(shù)組對應(yīng)的行和列位置
for (int rowNumOfSparse = 1; rowNumOfSparse < sparseArr.length; rowNumOfSparse++) {
int rowNum = sparseArr[rowNumOfSparse][0];
int colNum = sparseArr[rowNumOfSparse][1];
int value = sparseArr[rowNumOfSparse][2];
chessArr[rowNum][colNum] = value;
}
return chessArr;
}
}
