文簡介

點贊 + 收藏 + 關注 = 學會了

這次會使用css畫出一個格子背景。并且一步步分析如何實現~

思路

直接給答案：通過2個相等的直角三角形拼接，形成一個正方形。

三角形可以使用 background-image 的漸變來實現。

html,
body {
  margin: 0;
  width: 100%;
  height: 100%;
}
body {
  background-image: linear-gradient(45deg, #000 25%, transparent 0);
}

此時出來的效果如上圖所示。

做一個45度的線性漸變，第一個顏色是#000（黑色），占整個背景貼片的25%，其余部分都是紅色。

在上面的基礎上，用 background-size 來控制背景貼片的大小。

body {
  background-image: linear-gradient(45deg, #000 25%, transparent 0);
  background-size: 200px 200px;
}

開始有點想法了嗎？

此時如果我們再畫多一個反過來的黑色的直角三角形，拼在一起不就成了正方形了嗎？

反過來的三角形怎么畫呢？我嘗試將黑色從 25% 改成 75%，會得到以下效果

body {
  background-image: linear-gradient(45deg, #000 75%, transparent 0);
  background-size: 200px 200px;
}

可以看到紅色的三角形就是原本黑色三角形反過來的樣子。

把上圖的“白色三角形”變成黑色，原本的黑色三角形（25%）繼續保留。

于是我又加多層漸變~

body {
  background-image:
    linear-gradient(45deg, #000 25%, transparent 0),
    linear-gradient(45deg, transparent 75%, #000 0);
  background-size: 200px 200px;
}

簡化一下代碼：

body {
  background-image: linear-gradient(45deg, #000 25%, transparent 0, transparent 75%, #000 0);
  background-size: 200px 200px;   
}

最后再做多一層上面的效果，然后移動一下其中一層的位置，就可以合并成一個黑色正方形。

body {
  background-image:
    linear-gradient(45deg, #000 25%, transparent 0, transparent 75%, #000 0),
    linear-gradient(45deg, #000 25%, transparent 0, transparent 75%, #000 0);
  background-position: 0 0, 100px 100px;
  background-size: 200px 200px;
}

大功告成。

最后需要提醒的是，在本例中 background-position 第二個漸變的位移是 background-size 的一半，這樣就能實現這種格子背景了~

完整代碼

<style>
  html,
  body {
    margin: 0;
    width: 100%;
    height: 100%;
  }

  body {
    background-image:
      linear-gradient(45deg, #000 25%, transparent 0, transparent 75%, #000 0),
      linear-gradient(45deg, #000 25%, transparent 0, transparent 75%, #000 0);
    background-position: 0 0, 100px 100px;
    background-size: 200px 200px;
  }
</style>

這是做成背景的完整代碼。

近決定擼一下算法，然后想起來要過一下數據結構基礎，接下來就和大家一起復習一下數據結構吧。

下面貼出一張數據結構日常用途。

結尾會給大家一些算法示意圖網站，卷起來。

算法在計算機科學中扮演著重要的角色。它是任何正確定義的計算過程，該過程取某個值或值的集合作為輸入并產生輸出。

良好的算法設計能夠提高程序的執行效率、減少程序占用空間、提高程序的可讀性和可維護性。同時，解決同一個問題的各種不同算法的效率常常相差非常大，這種效率上的差距影響往往比硬件和軟件方面的差距還要大。

算法需要數據結構的支撐，所以學習前我們必須熟練掌握這些基本數據結構！

數組

數組是一種線性數據結構，它用一組連續的內存空間來存儲相同類型的數據。在數組中，每個元素都有一個唯一的索引，用于訪問和修改它們。數組的優點是易于理解和實現，但缺點是插入和刪除操作可能需要移動大量數據，導致效率較低。

鏈表

鏈表是一種非線性數據結構，由一系列節點組成，每個節點包含一個數據元素和一個指向下一個節點的指針。鏈表的優點是插入和刪除操作相對簡單，因為它們只需要修改指針。然而，鏈表的缺點是訪問單個元素的速度較慢，因為需要從頭節點開始遍歷。

鏈表的特點：

• 采用動態存儲分配，不會造成內存浪費和溢出。
• 鏈表執行插入和刪除操作十分方便，修改指針即可，不需要移動大量元素。
• 鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多。但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間復雜度分別是O(logn)和O(1)。

棧和隊列

棧是一種后進先出（LIFO）的數據結構，它只允許在一端（稱為棧頂）進行插入和刪除操作。棧的常用操作有push（壓入元素）、pop（彈出元素）和peek（查看棧頂元素）。棧常用于處理具有特定順序要求的問題，如函數調用和解謎游戲。

棧分為順序棧、鏈式棧、遞歸棧等

隊列是一種線性表，它只允許在表的一端進行插入，在表的另一端進行刪除。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列的主要特點就是先進先出（FIFO） 。

隊列有：順序隊列、鏈式隊列、循環隊列等

哈希表

哈希表提供了快速的插入操作和查找操作，無論哈希表總中有多少條數據，插入和查找的時間復雜度都是為O(1)，因為哈希表的查找速度非?？欤栽诤芏喑绦蛑卸加惺褂霉１?，例如拼音檢查器 。

哈希表的基本思想是將任意長度的二進制值通過一個特定的函數，變換成固定長度的字符串，用作數組的下標。比如說我們可以用一個短的字符串表示一個長的字符串，然后用這個短字符串作為數組的下標來存儲長字符串。這樣就可以通過短字符串來快速地查找到對應的長字符串了。

常見哈希表：

• 數組哈希表；
• 鏈式哈希表；
• 開放地址哈希表；
• 二叉哈希表；
• 壓縮哈希表；
• 位圖哈希表

樹

樹是一種非線性數據結構，由根節點、子節點和葉節點組成。樹的一個常見例子是二叉樹，其中每個節點最多有兩個子節點。樹的其他類型包括平衡樹（如AVL樹和紅黑樹）和非平衡樹（如二叉搜索樹）。樹結構常用于表示層級關系和組織數據。

常見樹的分類有 二叉樹、AVL樹、紅黑樹等

排序算法

將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。

分類：

非穩定排序算法：快速排序、希爾排序、堆排序、直接選擇排序 穩定的排序算法：基數排序、冒泡排序、直接插入排序、折半插入排序、歸并排序

搜索算法

利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。

分類：枚舉算法、深度優先搜索、廣度優先搜索、A*算法、回溯算法、蒙特卡洛樹搜索、散列函數等算法。

貪心算法

在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

典型例子：

0/1背包問題，馬踏棋盤，均分紙牌

分治算法

分治算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序算法，簡單問題可用二分法完成。

典型例子：

排序中：歸并排序、堆排序、快速排序；實例：找偽幣、求最值、棋盤覆蓋

動態規劃

這個感覺比較難，后面也得卷起來！

用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。

動態規劃一般可分為線性動規，區域動規，樹形動規，背包動規四類。

線性動規：攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等；

區域動規：石子合并， 加分二叉樹，統計單詞個數，炮兵布陣等；

樹形動規：貪吃的九頭龍，二分查找樹，聚會的歡樂，數字三角形等；

背包問題：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶（同濟）等

算法相關鏈接：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

https://visualgo.net/zh

https://algorithm-visualizer.org/

https://github.com/qiwsir/algorithm

因

又到深夜了，我按照以往在公眾號寫著數據結構！這占用了我大量的時間！我的超越妹妹嚴重缺乏陪伴而 怨氣滿滿！

超越妹妹時常埋怨，認為數據結構這么抽象難懂的東西沒啥作用，常會問道：天天寫這玩意，有啥作用。而我答道：能干事情多了，比如寫個小游戲啥的！

當我碼完字準備睡覺時：寫不好別睡覺！

分析

如果用數據結構與算法造出東西來呢？

• 什么東西簡單容易呢？我百度一下，我靠，這個鳥游戲原來不好搞啊，得接觸一堆不熟悉的東西，搞不來搞不來。

有了(靈光一閃)，寫個猜數字游戲，問他加減乘除等于幾。

• 超越妹妹又不是小孩子，糊弄不過去。

經過一番折騰，終于在半夜12點確定寫迷宮小游戲了。大概弄清楚其中的幾個步驟。

大概是：

• 畫線—>畫迷宮(擦線)—>方塊移動、移動約束(不出界不穿墻)—>完成游戲。

畫線(棋盤)

對于html+js(canvas)畫的東西，之前學過javaswing應該有點映像。在html中有個canvas 的畫布，可以在上面畫一些東西和聲明一些監聽(鍵盤監聽)。

對于迷宮來說，那些線條是沒有屬性的，只有位置x,y，你操作這個畫布時候，可能和我們習慣的面相對象思維不一樣。所以，在你設計的線或者點的時候，記得那個點、線在什么位置，在后續劃線還是擦線還是移動的時候根據這個位置進行操作。

 <!DOCTYPE html>
<html>
 <head>
 <title>MyHtml.html</title> 
 </head> 
 <body>
 <canvas id="mycanvas" width="600px" height="600px"></canvas>
 
 </body>
 <script type="text/javascript">

var aa=14;
 var chess = document.getElementById("mycanvas");
 var context = chess.getContext('2d');

 // var context2 = chess.getContext('2d');
 // context.strokeStyle = 'yellow';
 var tree = [];//存放是否聯通
 var isling=[];//判斷是否相連
 for(var i=0;i<aa;i++){
 tree[i]=[];
 for(var j=0;j<aa;j++){
 tree[i][j]=-1;//初始值為0
 }
 } for(var i=0;i<aa*aa;i++){
 isling[i]=[];
 for(var j=0;j<aa*aa;j++){
 isling[i][j]=-1;//初始值為0
 }
 }
 
 function drawChessBoard(){//繪畫
 for(var i=0;i<aa+1;i++){
 context.strokeStyle='gray';//可選區域
 context.moveTo(15+i*30,15);//垂直方向畫15根線，相距30px;
 context.lineTo(15+i*30,15+30*aa);
 context.stroke();
 context.moveTo(15,15+i*30);//水平方向畫15根線，相距30px;棋盤為14*14；
 context.lineTo(15+30*aa,15+i*30);
 context.stroke();
 }
 }
 drawChessBoard();//繪制棋盤
 
 // var mymap=new Array(36);
 // for(var i=0;i<36;i++)
 // {mymap[i]=-1;}


 </script>
</html>

實現效果

畫迷宮

隨機迷宮怎么生成？怎么搞？一臉懵逼。

• 因為我們想要迷宮，那么就需要這個迷宮出口和入口有連通路徑，你可能壓根不知道迷宮改怎么生成，用的什么算法。小聲BB：用并查集(不相交集合)。

迷宮和不相交集合有什么聯系呢？(規則)

• 之前筆者在前面數據結構與算法系列中曾經介紹過并查集(不相交集合)，它的主要功能是森林的合并，不聯通的通過并查集能夠快速將兩個森林合并，并且能夠快速查詢兩個節點是否在同一個森林中！

而我們的隨機迷宮：在每個方格都不聯通的情況下，是一個棋盤方格，這也是它的初始狀態。而這個節點可以跟鄰居可能相連，也可能不相連。我們可以通過并查集實現。

具體思路為：(主要理解并查集)

• 1：定義好不想交集合的基本類和方法（search,union等）
  2：數組初始化，每一個數組元素都是一個集合，值為-1
  3：隨機查找一個格子（一維數據要轉換成二維，有點麻煩），在隨機找一面墻（也就是找這個格子的上下左右），還要判斷找的格子出沒出界。
  具體在格子中找個隨機數m——>隨機數m在二維中的位置[m/長,m%長]——>這個二維的上下左右隨機找一個位置p[m/長+1,m%長]或[m/長-1,m%長]或[m/長,m%長+1]或[m/長,m%長-1]——>判斷是否越界
  4：判斷兩個格子(一維數組編號)是否在一個集合(并查集查找)。如果在，則重新找，如果不在，那么把墻挖去
  5：把墻挖去有點繁瑣，需要考慮奇偶判斷它那種墻(上下還是左右，還要考慮位置)，然后擦掉。（根據數組轉換成真實距離）。具體為找一個節點，根據位置關系找到一維數組的號位用并查集判斷是否在一個集合中。
  6：最終得到一個完整的迷宮。直到第一個(1,1)和(n,n)聯通停止。雖然采用隨機數找墻，但是效果并不是特別差。其中要搞清一維二維數組的關系。一維是真實數據，并查集操作。二維是位置。要搞懂轉化！

注意：避免混淆，搞清數組的地址和邏輯矩陣位置。數組從0開始的，邏輯上你自己判斷。別搞混淆！

主要邏輯為：

while(search(0)!=search(aa*aa-1))//主要思路
 {
 var num = parseInt(Math.random() * aa*aa );//產生一個小于196的隨機數
 var neihbour=getnei(num);
 if(search(num)==search(neihbour)){continue;}
 else//不在一個上
 {
 isling[num][neihbour]=1;isling[neihbour][num]=1;
 drawline(num,neihbour);//劃線
 union(num,neihbour);
 
 }
 }

那么在前面的代碼為

<!DOCTYPE html>
<html>
 <head>
 <title>MyHtml.html</title> 
 </head> 
 <body>
 <canvas id="mycanvas" width="600px" height="600px"></canvas>
 
 </body>
 <script type="text/javascript">
//自行添加上面代碼
 // var mymap=new Array(36);
 // for(var i=0;i<36;i++)
 // {mymap[i]=-1;}
 function getnei(a)//獲得鄰居號 random
 {
 var x=parseInt(a/aa);//要精確成整數
 var y=a%aa;
 var mynei=new Array();//儲存鄰居
 if(x-1>=0){mynei.push((x-1)*aa+y);}//上節點
 if(x+1<14){mynei.push((x+1)*aa+y);}//下節點
 if(y+1<14){mynei.push(x*aa+y+1);}//有節點
 if(y-1>=0){mynei.push(x*aa+y-1);}//下節點
 var ran=parseInt(Math.random() * mynei.length );
 return mynei[ran];

 }
 function search(a)//找到根節點
 {
 if(tree[parseInt(a/aa)][a%aa]>0)//說明是子節點
 {
 return search(tree[parseInt(a/aa)][a%aa]);//不能壓縮路徑路徑壓縮
 }
 else
 return a;
 }
 function value(a)//找到樹的大小
 {
 if(tree[parseInt(a/aa)][a%aa]>0)//說明是子節點
 {
 return tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路徑壓縮
 }
 else
 return -tree[parseInt(a/aa)][a%aa];
 }
 function union(a,b)//合并
 {
 var a1=search(a);//a根
 var b1=search(b);//b根
 if(a1==b1){}
 else
 {
 if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//這個是負數()，為了簡單減少計算，不在調用value函數
 {
 tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//個數相加 注意是負數相加
 tree[parseInt(b1/aa)][b1%aa]=a1; //b樹成為a樹的子樹，b的根b1直接指向a；
 }
 else
 {
 tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
 tree[parseInt(a1/aa)][a1%aa]=b1;//a所在樹成為b所在樹的子樹
 }
 }
 }

 function drawline(a,b)//劃線，要判斷是上下還是左右
 {

 var x1=parseInt(a/aa);
 var y1=a%aa;
 var x2=parseInt(b/aa);
 var y2=b%aa; 
 var x3=(x1+x2)/2;
 var y3=(y1+y2)/2;
 if(x1-x2==1||x1-x2==-1)//左右方向的點 需要上下劃線
 {
 //alert(x1);
 // context.beginPath();
 context.strokeStyle = 'white';
 // context.moveTo(30+x3*30,y3*30+15);//
 // context.lineTo(30+x3*30,y3*30+45);
 context.clearRect(29+x3*30, y3*30+16,2,28);
 // context.stroke();
 }
 else
 {
 // context.beginPath();
 context.strokeStyle = 'white';
 // context.moveTo(x3*30+15,30+y3*30);//
 // context.lineTo(45+x3*30,30+y3*30);
 context.clearRect(x3*30+16, 29+y3*30,28,2);
 // context.stroke();
 }
 }
 
 while(search(0)!=search(aa*aa-1))//主要思路
 {
 var num = parseInt(Math.random() * aa*aa );//產生一個小于196的隨機數
 var neihbour=getnei(num);
 if(search(num)==search(neihbour)){continue;}
 else//不在一個上
 {
 isling[num][neihbour]=1;isling[neihbour][num]=1;
 drawline(num,neihbour);//劃線
 union(num,neihbour);
 
 }
 }
 </script>
</html>

方塊移動

這部分我采用的方法不是動態真的移動，而是一格一格的跳躍。也就是當走到下一個格子將當前格子的方塊擦掉，在移動的那個格子中再畫一個方塊。選擇方塊是因為方塊更方便擦除，可以根據像素大小精準擦除。

另外，再移動中要注意不能穿墻、越界。那么怎么判斷呢？很好辦，我們再前面會判斷兩個格子是否聯通，如果不連通我們將把這個墻拆開。再拆的時候把這個墻的時候記錄這兩點拆墻可走即可(數組)

另外，事件的監聽上下左右查一查就可以得到，添加按鈕對一些事件監聽，這些不是最主要的。

為了豐富游戲可玩性，將方法封裝，可以設置關卡(只需改變迷宮大小)。這樣就可以實現通關了。另外，如果寫成動態存庫那就更好了。

結語

在線嘗試地址，代碼直接查看網頁源代碼即可！

筆者前端能力和算法能力有限，寫的可能不是特別好，還請見諒！當然，筆者歡迎和一起熱愛學習的人共同進步、學習！歡迎關注，如果感覺不錯，歡迎關注、點贊！蟹蟹！