广度优先搜索

ACM图论算法入门-广度优先搜索

小时候有没有玩过连连看的游戏？或者类俄罗斯方块之类的游戏？

怎么实现连通块的消除？（连通块是指颜色相同，在图中连通的方格）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

<html>
    <head>  
        <meta http-equiv="content-type" content="text/html;charset=utf-8">      
        <title>test</title>
        <style>
            #chart{
                width: 500px;
                height:500px;
            }
            table{
                width: 500px;
                height:500px;
            }
        </style>
    </head>
    <body>
        <div id="chart"></div>
        <script>
            var dir = [[1,0],[-1,0],[0,-1],[0,1],[-1,1],[-1,-1],[1,1],[1,-1]];//方向数组,分别表示上、下、左、右、左上、左下、右上、右下
            //g_search是广度优先搜索
            //d_search是深度优先搜索(下次再写)
            function g_search(tu,w,h,i,j){//tu是一个二维矩阵,width是矩阵的单位长度，h是单位高度,其中tu[0][0]=1表示图中（0,0）这个点是第1号颜色,i,j是起始点
                var next_i,
                    next_j,
                    nextPoint={},
                    nowPoint={},//现在要处理的点
                    flag = [],
                    isInQueue = [],//记录在进过队列的点
                    queue = [];//start_i是宽度的遍历索引,start_j是高度的遍历索引，其中i<w ,j<h,flag是标志图中每个点是否被访问的数组,queue是队列数组
                //初始化标记数组为未访问
                for(var x = 0;x < w; x++){
                    flag[x] = [];
                    for(var y = 0 ; y < h ; y++){
                        flag[x][y] = false;
                    }
                }
                var startPoint = {
                    x: i,
                    y: j,
                    color : tu[i][j]
                };
                
                flag[i][j] = true;//初始化开始点是被访问的
                queue.push(startPoint); //队列里面初始化一个点
                isInQueue.push(startPoint);
                while(queue.length !== 0){//队列为空则退出
                   nowPoint= queue.pop();
                   i = nowPoint.x;
                   j = nowPoint.y;
                   for(var ii=0; ii< dir.length; ii++){
                       next_i = i + dir[ii][0];
                       next_j = j+ dir[ii][1];
                       
                       if(isLegal(next_i,next_j,w,h)){//如果相邻点（方向数组里面的八个相邻点，点不超出图的边界）颜色相同，则放进队列
                            if(!flag[next_i][next_j]){
                                flag[next_i][next_j] = true;
                                if( tu[i][j] === tu[next_i][next_j]){
                                    nextPoint = {
                                        x: next_i,
                                        y: next_j,
                                        color: tu[next_i][next_j]
                                    }
                                    isInQueue.push(nextPoint);
                                    queue.push(nextPoint);
                                }   
                            }   
                       }
                   }
                }
                for(var i=0;i<isInQueue.length;i++){//如果在队列里面，说明是一个联通块，则变颜色
                    var obj = isInQueue[i];
                    tu[obj.x][obj.y] = 0;
                }
                return tu;
            }
            function isLegal(x,y,w,h){
                if(x>=0 && x<w && y>=0 && y<h){
                    return true
                }
                return false
            }
          
           //渲染成图
           function createTu(tuArr,id){//生成图,id是插入的dom的id
              var colorArr = ['#333333','#FFFAFA','#FFF68F','#FFEFD5','#FFE4E1','#FFDEAD','#FFC1C1'];//初始化六种颜色
              var html = "<table>"
              for(var i=0;i<tuArr.length;i++){
                html+="<tr>";
                for(var j=0;j<tuArr[i].length;j++){
                    html+="<td style='background-color:"+colorArr[tuArr[i][j]]+"' x='"+i+"' y='"+ j +"'></td>"
                }
                html+="</tr>";
              }
              html+= "</table>"
              var chart = document.getElementById("chart");
              chart.innerHTML = html;
              chart.onclick = clickHandler;
           }
           function clickHandler(e){//事件代理
                var tar = e.target||e.srcElement;
                var x = tar.getAttribute('x');
                var y = tar.getAttribute('y');
                x = !!x ? parseInt(x): null;
                y = !!y ? parseInt(y): null;
                if(x!=null && y!=null){
                    createTu(g_search(testArr,testArr.length,testArr[0].length,x,y));
                }
           }

            //测试数据
            var testArr = [[1,1,2,3,1],[1,3,5,1,1],[2,4,2,2,1]];
           createTu(testArr,"chart")
        </script>
    </body>
</html>

项目地址：

https://uking2016.github.io/g_search_demo/g_search_demo/test.html

postcss 2017/12/16

less转成acss，做支付宝小程序再也不用手动改样式啦（postcss,extract-text-webpack-plugin）

接到当前项目转成支付宝小程序的需求，你有没有这样做过？把原来的项目的样式（less，或者其他）拷贝到acss（支付宝小程序的样式），然后按支付宝小程序的规则把px转成rpx

其实这个拷贝修改的过程，可以变成自动转换的哦

extract-text-webpack-plugin该插件的主要是为了抽离css样式

postcss 把 CSS 解析成抽象语法树（AST）

首先在webpack的配置文件里面引入extract-text-webpack-plugin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
var webpack = require('webpack');
const ExtractTextPlugin = require("extract-text-webpack-plugin");
const extractLESS = new ExtractTextPlugin('output.css');

module.exports = {
    entry: './entry.js', //入口文件
    output: {
        //node.js中__dirname变量获取当前模块文件所在目录的完整绝对路径 
        path: __dirname, //输出位置
        filename: 'output.js' //输入文件
    },
    module: {
        loaders: [
            {
                test: /\.less$/,
                use: ExtractTextPlugin.extract({
                    fallback: "style-loader",
                    use: [{
                        loader: "css-loader",
                    // options: {
                    //     sourceMap: true
                    // }
                    }, {
                        loader: "less-loader"
                    }, {
                        loader: 'postcss-loader',
                        options: {
                            plugins: () => {
                                return [
                                    require("./myplugin.js")
                                ]
                            }
                        }
                    }
                    ],
                    publicPath: __dirname
                })
            }
        ]
    },
    //其他解决方案配置
    resolve: {
        extensions: ['.js', '.json', '.css', '.less'] //添加在此的后缀所对应的文件可以省略后缀
    },
    //插件
    plugins: [
        extractLESS
    ]
}

然后基于postcss写一个小插件，用来进行单位转换，就是把px转成rpx （如果项目进行了适配，输出的是rem，需要重新计算，根据适配前的规则）

1
2
3
4
5
6
7
8
9
10
var postcss = require('postcss');
module.exports = postcss.plugin('myplugin', function myplugin(options) {
    return function(css) {
        css.replaceValues(/\d+px/, {
            fast: 'px'
        }, string => {
            return parseInt(parseFloat(string)) + 'rpx';
        });
    }
});

最后我们看看打包出来的效果

index.less(打包之前)
1
2
3
4
5
6
7
8
.a{
	color:#fff;
	width:20px;
	.b{
		color:#333;
		width:30px;
	}
}
打包之后
1
2
3
4
5
6
7
8
.a {
  color: #fff;
  width: 20rpx;
}
.a .b {
  color: #333;
  width: 30rpx;
}

项目地址：

https://github.com/Uking2016/testPostcss

node前后端分离

node前后端分离

思考：前后端不分离有哪些缺点？

前后端分离的定义
就是前端和后端的分开嘛

前后端分离
啊，怎么分开，那我直接cx把前端代码弄走吗？

咦，请求不了了，
XMLHttpRequest cannot load https://s103.ggwan.com/mainlinghitv2/css/trends.css. No ‘Access-Control-Allow-Origin’ header is present on the requested resource. Origin ‘null’ is therefore not allowed access. The response had HTTP status code 404.
无法加载https://s103.ggwan.com/mainlinghitv2/css/trends.cs XMLHttpRequest。在所请求的资源上没有“访问控制允许源站点”报头。因此，不允许源站点“null”访问。响应具有HTTP状态代码404。

我们看看发送ajax的时候浏览器干了什么

站点null想访问https://s103.ggwan.com站点上的内容，结果报错。啊？为啥不能访问？
因为浏览器的同源策略

浏览器的同源策略

跨域处理的方法
1.CORS

跨域的处理方法
2.JSONP

跨域的处理方法
3.websocket
不受同源策略限制

跨域的处理方法
用一个代理服务器访问后端服务（就是避免让浏览器去请求不同的域，让我们的服务器去请求，就不存在同源策略啦）

node作为中间层实现跨域
接下来，我们一起用node（express）来创建一个服务器吧
var app = express();
App.listen(8080);
这个app就是我们的代理服务器啦，用它可以管理我们的静态资源（就是我们的前端代码啊，html,css,js）
app.use(express.static(path.join(__dirname, ‘/‘)));
就是这一句话！！就是表示静态资源就在当前目录，然后express就会自己去找index.html啦

结合webapack
A: Webpack除了用来打包，还能在开发环境下作为一个node的服务器（webpack-dev-server）哦。
B: 哇，那你的意思是，webpack-dev-server就可以跨域访问资源咯？
A: 没错噢，只要简单的配置啦，请看代码
在webpack.config.js里，我们这样配置

devServer:{
          historyApiFallback:true,
          hot:true,
          inline:true,
          progress:true,//报错无法识别，删除后也能正常刷新
          proxy: {//用devserver作跨域
            '/mainlinghitv2/css/trends.css': {
              target: 'https://s103.ggwan.com',//真正要请求的域名
              changeOrigin: true
            }
          }
      }

B: 就是说，我们在开发的时候，可以直接用webpack来调试接口就不用在本地搭建php(/java)的环境咯？
A: 是的哦
B: /哭笑 那为什么还要用node作中间层？
A: 因为webpack-dev-server是只能在开发环境运行的哦，webpack-dev-server生成的包并没有放在你的真实目录中,而是放在了内存中，就是说，webpack-dev-server不会生成html,js这些资源的目录里面，而这些静态文件在生产环境中是必须的，看下图
开发环境下

B: 也就是说，用了webpack-dev-server我们只是在开发环境下实现了前后端分离
A: 是的，生产环境下，我们其实也是同域访问的情况
B：就是说，上线的时候，又出现了前后端在一起的情况