一八秃、稀疏數(shù)組
1、是什么计技？
比如有一個(gè) 11 * 11 的五子棋盤喜德，我們要用程序模擬，那肯定就是二維數(shù)組垮媒。然后用1表示黑子舍悯，2表示白子，假如現(xiàn)在棋盤上只有一個(gè)黑子一個(gè)白子睡雇，那么也就是這個(gè)二維數(shù)組中只有一個(gè)1萌衬，一個(gè)2，其他都是無意義并不代表任何棋子的0它抱，如下：
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
……
當(dāng)一個(gè)數(shù)組中大部分元素是0時(shí)秕豫，或者為同一個(gè)值時(shí)，就可以用稀疏數(shù)組來保存該數(shù)組观蓄。為什么要這么做混移？因?yàn)榭梢怨?jié)省空間。
2侮穿、怎么用歌径？
- 記錄原數(shù)組有幾行幾列，有多少個(gè)不同的值
- 把具有不同值的元素的行列及值記錄在一個(gè)小規(guī)模的數(shù)組中亲茅，這個(gè)小規(guī)模的數(shù)組就叫稀疏數(shù)組
歡迎大家關(guān)注我的公眾號(hào) javawebkf回铛，目前正在慢慢地將簡書文章搬到公眾號(hào)，以后簡書和公眾號(hào)文章將同步更新克锣，且簡書上的付費(fèi)文章在公眾號(hào)上將免費(fèi)茵肃。
3、案例：
現(xiàn)有如下的 6 * 7 的原始數(shù)組：
0 0 0 22 0 0 15
0 11 0 0 0 17 0
0 0 0 -6 0 0 0
0 0 0 0 0 39 0
91 0 0 0 0 0 0
0 0 28 0 0 0 0
首先稀疏數(shù)組第一行第一列是記錄元素?cái)?shù)組有幾行袭祟，第一行第二列是記錄原始數(shù)組有幾列验残，第一行第三列是記錄原始數(shù)組有幾個(gè)不同的值(除了0)。所以稀疏數(shù)組一行應(yīng)該是：
行 列 值
6 7 8
稀疏數(shù)組第二行開始巾乳，每行記錄的是胚膊，原始數(shù)組中非0值所在的行故俐、所在的列、值的大小紊婉。比如第二行要記錄22在原始數(shù)組中的行、列辑舷、值喻犁，那么稀疏數(shù)組第二行就是：
行 列 值
0 3 22
然后用此方法記錄15、11何缓、17肢础、-6、39碌廓、91传轰、28的相關(guān)信息，所以最終由該原始數(shù)組轉(zhuǎn)化出來的稀疏數(shù)組就是：
行 列 值
6 7 8
0 3 22
0 6 15
1 1 11
1 5 17
2 3 -6
3 5 39
4 0 91
5 2 28
這樣就把一個(gè) 6 * 7 的數(shù)組變成了一個(gè) 9 * 3 的數(shù)組谷婆，達(dá)到了壓縮的效果慨蛙。
4、原始數(shù)組與稀疏數(shù)組相互轉(zhuǎn)換思路：
原始數(shù)組轉(zhuǎn)稀疏數(shù)組：
- 遍歷二維數(shù)組得到有效數(shù)組的個(gè)數(shù)count纪挎；
- 根據(jù)count就可以創(chuàng)建稀疏數(shù)組
int[count + 1][3]; - 將有效數(shù)組存入稀疏數(shù)組
稀疏數(shù)組轉(zhuǎn)原始數(shù)組：
- 讀取稀疏數(shù)組第一行期贫，根據(jù)第一行數(shù)組可以知道原始數(shù)組有幾行幾列，然后創(chuàng)建原始數(shù)組异袄；
- 讀取稀疏數(shù)組后幾行的數(shù)組通砍，賦值給原始數(shù)組即可
5、代碼實(shí)操：
public class SparseArray {
public static void main(String[] args){
// 創(chuàng)建一個(gè) 11 * 11的原始數(shù)組
int[][] arr1 = new int[11][11];
arr1[1][2] = 1;
arr1[2][3] = 2;
// 原始數(shù)組轉(zhuǎn)稀疏數(shù)組
// 1. 遍歷烤蜕，得到非0數(shù)據(jù)的個(gè)數(shù)以及所在的行列
int count = 0;
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[i].length; j++) {
if (arr1[i][j] != 0){
count ++;
map.put(i+ "," + j, arr1[i][j]);
}
}
}
// 2. 創(chuàng)建稀疏數(shù)組
int[][] sparseArr = new int[count + 1][3];
sparseArr[0][0] = arr1.length;
sparseArr[0][1] = arr1[0].length;
sparseArr[0][2] = count;
// 3. 給稀疏數(shù)組賦值
int row = 1;
for (String key : map.keySet()){
String[] ij = key.split(",");
int i = Integer.parseInt(ij[0]);
int j = Integer.parseInt(ij[1]);
sparseArr[row][0] = i;
sparseArr[row][1] = j;
sparseArr[row][2] = map.get(key);
row ++;
}
// 4. 遍歷稀疏數(shù)組
for (int i = 0; i < sparseArr.length; i++) {
for (int j = 0; j < sparseArr[i].length; j++) {
System.out.print(sparseArr[i][j] + " ");
}
System.out.println("\r\n");
}
// 稀疏數(shù)組恢復(fù)原始數(shù)組
// 1. 根據(jù)第一行第一列第二列創(chuàng)建出原始數(shù)組
int i = sparseArr[0][0];
int j = sparseArr[0][1];
int[][] arr2 = new int[i][j];
// 2. 給原始數(shù)組賦值
for (int k = 1; k < sparseArr.length; k++) {
int x = sparseArr[k][0];
int y = sparseArr[k][1];
int val = sparseArr[k][2];
arr2[x][y] = val;
}
// 3. 遍歷轉(zhuǎn)換的數(shù)組
for (int a = 0; a < arr2.length; a++) {
for (int b = 0; b < arr2[a].length; b++) {
System.out.print(arr2[a][b] + " ");
}
System.out.println("\r\n");
}
}
}
上面的代碼就實(shí)現(xiàn)了原始數(shù)組與稀疏數(shù)組的相互轉(zhuǎn)換封孙，靈活運(yùn)用稀疏數(shù)組，可以節(jié)省運(yùn)行內(nèi)存讽营，提高程序性能虎忌。
二、環(huán)形隊(duì)列
1斑匪、普通隊(duì)列存在什么問題呐籽？
隊(duì)列大家都知道，有幾個(gè)重要的屬性：
- rear：指向隊(duì)列的尾巴蚀瘸，即最后一個(gè)元素所在的位置狡蝶，初始值為-1
- front：指向隊(duì)列的頭部的前一個(gè)位置，初始值也為-1
- capacity：隊(duì)列的容量
空隊(duì)列的rear和front都等于-1贮勃，入隊(duì)時(shí)贪惹，front不動(dòng)，rear++寂嘉，當(dāng) rear == capacity - 1時(shí)奏瞬，隊(duì)列已滿枫绅；出隊(duì)時(shí)，rear不動(dòng)硼端，front++并淋，當(dāng)front == rear時(shí)，隊(duì)列為空珍昨∠氐ⅲ看起來很完美，但實(shí)際上有問題镣典。假如一個(gè)隊(duì)列capacity = 3兔毙，入隊(duì)了三個(gè)元素，此時(shí)front = -1; rear = 2兄春，然后再將三個(gè)元素都出隊(duì)澎剥，此時(shí)front = 2, rear = 2。這時(shí)隊(duì)列明明是空的赶舆，但是卻不能再入隊(duì)元素的哑姚，因?yàn)闈M足rear = capacity - 1，也就是相當(dāng)于這隊(duì)列是一次性的涌乳，用過之后就不能再用了蜻懦，即使為空也不能再入隊(duì)了，造成空間的浪費(fèi)夕晓，所以環(huán)形隊(duì)列就出現(xiàn)了宛乃。
2、環(huán)形隊(duì)列實(shí)現(xiàn)思路：
環(huán)形隊(duì)列中的幾個(gè)重要屬性：
- rear：指向隊(duì)列尾巴的后一個(gè)位置蒸辆，初始值為0
- front：指向隊(duì)列的頭部征炼，即第一個(gè)元素所在的位置，初始值為0
- capacity：隊(duì)列的容量
下面是環(huán)形隊(duì)列的一些算法：
- 隊(duì)列為空時(shí)：
front == rear - 隊(duì)列已滿時(shí)：
(rear + 1) % capacity == front - 獲取隊(duì)列元素個(gè)數(shù)：
(rear + capacity - front) % capacity - 入隊(duì)操作時(shí)：
rear = (rear + 1) % capacity - 出隊(duì)操作時(shí)：
front = (front + 1) % capacity;
判斷隊(duì)列是否已滿是環(huán)形隊(duì)列中最重要也是最難理解的地方躬贡。假如有一個(gè)隊(duì)列capacity = 3谆奥，入隊(duì)操作如下：
- 第一個(gè)元素入隊(duì)：
front = 0，因?yàn)?code>(rear + 1) % capacity = 1 % 3 != front拂玻，所以元素可以入隊(duì)酸些，元素入隊(duì)后rear = 1； - 第二個(gè)元素入隊(duì)：
front = 0檐蚜，因?yàn)?code>(rear + 1) % capacity = 2 % 3 != front魄懂，所以元素可以入隊(duì)，元素入隊(duì)后rear = 2闯第； - 第三個(gè)元素入隊(duì)：
front = 0市栗，因?yàn)?code>(rear + 1) % capacity = 3 % 3 == front，所以元素不能入隊(duì)，隊(duì)列已滿填帽；
隊(duì)列容量明明是3蛛淋，只入隊(duì)了兩個(gè)元素就告訴我隊(duì)列滿了？沒錯(cuò)篡腌，這種判斷隊(duì)列是否已滿的算法需要犧牲數(shù)組的一個(gè)空間褐荷。
現(xiàn)在進(jìn)行出隊(duì)操作：
- 第一個(gè)元素出隊(duì)：
front = 1，rear = 2哀蘑，(rear + 1) % capacity = 3 % 3 = 0 != front诚卸。
可以發(fā)現(xiàn)，當(dāng)一個(gè)元素出隊(duì)后绘迁，又滿足入隊(duì)條件了，所以數(shù)組空間就可以重復(fù)利用了卒密。
3缀台、代碼實(shí)操：
public class CircleQueue<E> {
private int capacity;
private int front;
private int rear;
private Object[] arr;
public CircleQueue(int capacity){
this.capacity = capacity;
this.arr = new Object[capacity];
this.front = 0;
this.rear = 0;
}
public boolean isFull(){
return (rear + 1) % capacity == front;
}
public boolean isEmpty(){
return rear == front;
}
public void addQueue(E e){
if (isFull()){
throw new RuntimeException("隊(duì)列已滿，入隊(duì)失敗");
}
arr[rear] = e;
// rear指針后移
rear = (rear + 1) % capacity;
}
public E getQueue(){
if (isEmpty()){
throw new RuntimeException("隊(duì)列為空哮奇，出隊(duì)失敗");
}
E val = (E) arr[front];
front = (front + 1) % capacity;
return val;
}
public int getSize(){
return (rear + capacity - front) % capacity;
}
// 遍歷
public void showQueue(){
if (isEmpty()){
return;
}
for (int i = front; i < front + getSize(); i++) {
System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);
}
}
public static void main(String[] args){
CircleQueue<Integer> queue = new CircleQueue<>(3);
queue.addQueue(1);
queue.addQueue(2);
queue.showQueue();
//queue.addQueue(3);
System.out.println(queue.getSize());
System.out.println(queue.getQueue());;
queue.addQueue(3);
queue.showQueue();
}
}
