文简介

点赞 + 收藏 + 关注 = 学会了

这次会使用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>

方块移动

这部分我采用的方法不是动态真的移动，而是一格一格的跳跃。也就是当走到下一个格子将当前格子的方块擦掉，在移动的那个格子中再画一个方块。选择方块是因为方块更方便擦除，可以根据像素大小精准擦除。

另外，再移动中要注意不能穿墙、越界。那么怎么判断呢？很好办，我们再前面会判断两个格子是否联通，如果不连通我们将把这个墙拆开。再拆的时候把这个墙的时候记录这两点拆墙可走即可(数组)

另外，事件的监听上下左右查一查就可以得到，添加按钮对一些事件监听，这些不是最主要的。

为了丰富游戏可玩性，将方法封装，可以设置关卡(只需改变迷宫大小)。这样就可以实现通关了。另外，如果写成动态存库那就更好了。

结语

在线尝试地址，代码直接查看网页源代码即可！

笔者前端能力和算法能力有限，写的可能不是特别好，还请见谅！当然，笔者欢迎和一起热爱学习的人共同进步、学习！欢迎关注，如果感觉不错，欢迎关注、点赞！蟹蟹！