_我已经从中二毕业了

_我已经从中二毕业了 查看完整档案

广州编辑广东技术师范学院  |  计算机科学与技术 编辑  |  填写所在公司/组织 www.none.none 编辑
编辑

不搞前端会死星人。

个人动态

_我已经从中二毕业了 赞了文章 · 3月26日

剖析Vue原理&实现双向绑定MVVM

本文能帮你做什么?
1、了解vue的双向数据绑定原理以及核心代码模块
2、缓解好奇心的同时了解如何实现双向绑定
为了便于说明原理与实现,本文相关代码主要摘自vue源码, 并进行了简化改造,相对较简陋,并未考虑到数组的处理、数据的循环依赖等,也难免存在一些问题,欢迎大家指正。不过这些并不会影响大家的阅读和理解,相信看完本文后对大家在阅读vue源码的时候会更有帮助<
本文所有相关代码均在github上面可找到 https://github.com/DMQ/mvvm

相信大家对mvvm双向绑定应该都不陌生了,一言不合上代码,下面先看一个本文最终实现的效果吧,和vue一样的语法,如果还不了解双向绑定,猛戳Google

<div id="mvvm-app">
    <input type="text" v-model="word">
    <p>{{word}}</p>
    <button v-on:click="sayHi">change model</button>
</div>

<script data-original="./js/observer.js"></script>
<script data-original="./js/watcher.js"></script>
<script data-original="./js/compile.js"></script>
<script data-original="./js/mvvm.js"></script>
<script>
    var vm = new MVVM({
        el: '#mvvm-app',
        data: {
            word: 'Hello World!'
        },
        methods: {
            sayHi: function() {
                this.word = 'Hi, everybody!';
            }
        }
    });
</script>

效果:
图片描述

几种实现双向绑定的做法

目前几种主流的mvc(vm)框架都实现了单向数据绑定,而我所理解的双向数据绑定无非就是在单向绑定的基础上给可输入元素(input、textare等)添加了change(input)事件,来动态修改model和 view,并没有多高深。所以无需太过介怀是实现的单向或双向绑定。

实现数据绑定的做法有大致如下几种:

发布者-订阅者模式(backbone.js)

脏值检查(angular.js)

数据劫持(vue.js)

发布者-订阅者模式: 一般通过sub, pub的方式实现数据和视图的绑定监听,更新数据方式通常做法是 vm.set('property', value),这里有篇文章讲的比较详细,有兴趣可点这里

这种方式现在毕竟太low了,我们更希望通过 vm.property = value 这种方式更新数据,同时自动更新视图,于是有了下面两种方式

脏值检查: angular.js 是通过脏值检测的方式比对数据是否有变更,来决定是否更新视图,最简单的方式就是通过 setInterval() 定时轮询检测数据变动,当然Google不会这么low,angular只有在指定的事件触发时进入脏值检测,大致如下:

  • DOM事件,譬如用户输入文本,点击按钮等。( ng-click )
  • XHR响应事件 ( $http )
  • 浏览器Location变更事件 ( $location )
  • Timer事件( $timeout , $interval )
  • 执行 $digest() 或 $apply()

数据劫持: vue.js 则是采用数据劫持结合发布者-订阅者模式的方式,通过Object.defineProperty()来劫持各个属性的settergetter,在数据变动时发布消息给订阅者,触发相应的监听回调。

思路整理

已经了解到vue是通过数据劫持的方式来做数据绑定的,其中最核心的方法便是通过Object.defineProperty()来实现对属性的劫持,达到监听数据变动的目的,无疑这个方法是本文中最重要、最基础的内容之一,如果不熟悉defineProperty,猛戳这里
整理了一下,要实现mvvm的双向绑定,就必须要实现以下几点:
1、实现一个数据监听器Observer,能够对数据对象的所有属性进行监听,如有变动可拿到最新值并通知订阅者
2、实现一个指令解析器Compile,对每个元素节点的指令进行扫描和解析,根据指令模板替换数据,以及绑定相应的更新函数
3、实现一个Watcher,作为连接Observer和Compile的桥梁,能够订阅并收到每个属性变动的通知,执行指令绑定的相应回调函数,从而更新视图
4、mvvm入口函数,整合以上三者

上述流程如图所示:
图片描述

1、实现Observer

ok, 思路已经整理完毕,也已经比较明确相关逻辑和模块功能了,let's do it
我们知道可以利用Obeject.defineProperty()来监听属性变动
那么将需要observe的数据对象进行递归遍历,包括子属性对象的属性,都加上 settergetter
这样的话,给这个对象的某个值赋值,就会触发setter,那么就能监听到了数据变化。。相关代码可以是这样:

var data = {name: 'kindeng'};
observe(data);
data.name = 'dmq'; // 哈哈哈,监听到值变化了 kindeng --> dmq

function observe(data) {
    if (!data || typeof data !== 'object') {
        return;
    }
    // 取出所有属性遍历
    Object.keys(data).forEach(function(key) {
        defineReactive(data, key, data[key]);
    });
};

function defineReactive(data, key, val) {
    observe(val); // 监听子属性
    Object.defineProperty(data, key, {
        enumerable: true, // 可枚举
        configurable: false, // 不能再define
        get: function() {
            return val;
        },
        set: function(newVal) {
            console.log('哈哈哈,监听到值变化了 ', val, ' --> ', newVal);
            val = newVal;
        }
    });
}

这样我们已经可以监听每个数据的变化了,那么监听到变化之后就是怎么通知订阅者了,所以接下来我们需要实现一个消息订阅器,很简单,维护一个数组,用来收集订阅者,数据变动触发notify,再调用订阅者的update方法,代码改善之后是这样:

// ... 省略
function defineReactive(data, key, val) {
    var dep = new Dep();
    observe(val); // 监听子属性

    Object.defineProperty(data, key, {
        // ... 省略
        set: function(newVal) {
            if (val === newVal) return;
            console.log('哈哈哈,监听到值变化了 ', val, ' --> ', newVal);
            val = newVal;
            dep.notify(); // 通知所有订阅者
        }
    });
}

function Dep() {
    this.subs = [];
}
Dep.prototype = {
    addSub: function(sub) {
        this.subs.push(sub);
    },
    notify: function() {
        this.subs.forEach(function(sub) {
            sub.update();
        });
    }
};

那么问题来了,谁是订阅者?怎么往订阅器添加订阅者?
没错,上面的思路整理中我们已经明确订阅者应该是Watcher, 而且var dep = new Dep();是在 defineReactive方法内部定义的,所以想通过dep添加订阅者,就必须要在闭包内操作,所以我们可以在 getter里面动手脚:

// Observer.js
// ...省略
Object.defineProperty(data, key, {
    get: function() {
        // 由于需要在闭包内添加watcher,所以通过Dep定义一个全局target属性,暂存watcher, 添加完移除
        Dep.target && dep.addSub(Dep.target);
        return val;
    }
    // ... 省略
});

// Watcher.js
Watcher.prototype = {
    get: function(key) {
        Dep.target = this;
        this.value = data[key];    // 这里会触发属性的getter,从而添加订阅者
        Dep.target = null;
    }
}

这里已经实现了一个Observer了,已经具备了监听数据和数据变化通知订阅者的功能,完整代码。那么接下来就是实现Compile了

2、实现Compile

compile主要做的事情是解析模板指令,将模板中的变量替换成数据,然后初始化渲染页面视图,并将每个指令对应的节点绑定更新函数,添加监听数据的订阅者,一旦数据有变动,收到通知,更新视图,如图所示:
图片描述

因为遍历解析的过程有多次操作dom节点,为提高性能和效率,会先将跟节点el转换成文档碎片fragment进行解析编译操作,解析完成,再将fragment添加回原来的真实dom节点中

function Compile(el) {
    this.$el = this.isElementNode(el) ? el : document.querySelector(el);
    if (this.$el) {
        this.$fragment = this.node2Fragment(this.$el);
        this.init();
        this.$el.appendChild(this.$fragment);
    }
}
Compile.prototype = {
    init: function() { this.compileElement(this.$fragment); },
    node2Fragment: function(el) {
        var fragment = document.createDocumentFragment(), child;
        // 将原生节点拷贝到fragment
        while (child = el.firstChild) {
            fragment.appendChild(child);
        }
        return fragment;
    }
};

compileElement方法将遍历所有节点及其子节点,进行扫描解析编译,调用对应的指令渲染函数进行数据渲染,并调用对应的指令更新函数进行绑定,详看代码及注释说明:

Compile.prototype = {
    // ... 省略
    compileElement: function(el) {
        var childNodes = el.childNodes, me = this;
        [].slice.call(childNodes).forEach(function(node) {
            var text = node.textContent;
            var reg = /\{\{(.*)\}\}/;    // 表达式文本
            // 按元素节点方式编译
            if (me.isElementNode(node)) {
                me.compile(node);
            } else if (me.isTextNode(node) && reg.test(text)) {
                me.compileText(node, RegExp.$1);
            }
            // 遍历编译子节点
            if (node.childNodes && node.childNodes.length) {
                me.compileElement(node);
            }
        });
    },

    compile: function(node) {
        var nodeAttrs = node.attributes, me = this;
        [].slice.call(nodeAttrs).forEach(function(attr) {
            // 规定:指令以 v-xxx 命名
            // 如 <span v-text="content"></span> 中指令为 v-text
            var attrName = attr.name;    // v-text
            if (me.isDirective(attrName)) {
                var exp = attr.value; // content
                var dir = attrName.substring(2);    // text
                if (me.isEventDirective(dir)) {
                    // 事件指令, 如 v-on:click
                    compileUtil.eventHandler(node, me.$vm, exp, dir);
                } else {
                    // 普通指令
                    compileUtil[dir] && compileUtil[dir](node, me.$vm, exp);
                }
            }
        });
    }
};

// 指令处理集合
var compileUtil = {
    text: function(node, vm, exp) {
        this.bind(node, vm, exp, 'text');
    },
    // ...省略
    bind: function(node, vm, exp, dir) {
        var updaterFn = updater[dir + 'Updater'];
        // 第一次初始化视图
        updaterFn && updaterFn(node, vm[exp]);
        // 实例化订阅者,此操作会在对应的属性消息订阅器中添加了该订阅者watcher
        new Watcher(vm, exp, function(value, oldValue) {
            // 一旦属性值有变化,会收到通知执行此更新函数,更新视图
            updaterFn && updaterFn(node, value, oldValue);
        });
    }
};

// 更新函数
var updater = {
    textUpdater: function(node, value) {
        node.textContent = typeof value == 'undefined' ? '' : value;
    }
    // ...省略
};

这里通过递归遍历保证了每个节点及子节点都会解析编译到,包括了{{}}表达式声明的文本节点。指令的声明规定是通过特定前缀的节点属性来标记,如<span v-text="content" other-attrv-text便是指令,而other-attr不是指令,只是普通的属性。
监听数据、绑定更新函数的处理是在compileUtil.bind()这个方法中,通过new Watcher()添加回调来接收数据变化的通知

至此,一个简单的Compile就完成了,完整代码。接下来要看看Watcher这个订阅者的具体实现了

3、实现Watcher

Watcher订阅者作为Observer和Compile之间通信的桥梁,主要做的事情是:
1、在自身实例化时往属性订阅器(dep)里面添加自己
2、自身必须有一个update()方法
3、待属性变动dep.notice()通知时,能调用自身的update()方法,并触发Compile中绑定的回调,则功成身退。
如果有点乱,可以回顾下前面的思路整理

function Watcher(vm, exp, cb) {
    this.cb = cb;
    this.vm = vm;
    this.exp = exp;
    // 此处为了触发属性的getter,从而在dep添加自己,结合Observer更易理解
    this.value = this.get(); 
}
Watcher.prototype = {
    update: function() {
        this.run();    // 属性值变化收到通知
    },
    run: function() {
        var value = this.get(); // 取到最新值
        var oldVal = this.value;
        if (value !== oldVal) {
            this.value = value;
            this.cb.call(this.vm, value, oldVal); // 执行Compile中绑定的回调,更新视图
        }
    },
    get: function() {
        Dep.target = this;    // 将当前订阅者指向自己
        var value = this.vm[exp];    // 触发getter,添加自己到属性订阅器中
        Dep.target = null;    // 添加完毕,重置
        return value;
    }
};
// 这里再次列出Observer和Dep,方便理解
Object.defineProperty(data, key, {
    get: function() {
        // 由于需要在闭包内添加watcher,所以可以在Dep定义一个全局target属性,暂存watcher, 添加完移除
        Dep.target && dep.addDep(Dep.target);
        return val;
    }
    // ... 省略
});
Dep.prototype = {
    notify: function() {
        this.subs.forEach(function(sub) {
            sub.update(); // 调用订阅者的update方法,通知变化
        });
    }
};

实例化Watcher的时候,调用get()方法,通过Dep.target = watcherInstance标记订阅者是当前watcher实例,强行触发属性定义的getter方法,getter方法执行的时候,就会在属性的订阅器dep添加当前watcher实例,从而在属性值有变化的时候,watcherInstance就能收到更新通知。

ok, Watcher也已经实现了,完整代码
基本上vue中数据绑定相关比较核心的几个模块也是这几个,猛戳这里 , 在src 目录可找到vue源码。

最后来讲讲MVVM入口文件的相关逻辑和实现吧,相对就比较简单了~

4、实现MVVM

MVVM作为数据绑定的入口,整合Observer、Compile和Watcher三者,通过Observer来监听自己的model数据变化,通过Compile来解析编译模板指令,最终利用Watcher搭起Observer和Compile之间的通信桥梁,达到数据变化 -> 视图更新;视图交互变化(input) -> 数据model变更的双向绑定效果。

一个简单的MVVM构造器是这样子:

function MVVM(options) {
    this.$options = options;
    var data = this._data = this.$options.data;
    observe(data, this);
    this.$compile = new Compile(options.el || document.body, this)
}

但是这里有个问题,从代码中可看出监听的数据对象是options.data,每次需要更新视图,则必须通过var vm = new MVVM({data:{name: 'kindeng'}}); vm._data.name = 'dmq'; 这样的方式来改变数据。

显然不符合我们一开始的期望,我们所期望的调用方式应该是这样的:
var vm = new MVVM({data: {name: 'kindeng'}}); vm.name = 'dmq';

所以这里需要给MVVM实例添加一个属性代理的方法,使访问vm的属性代理为访问vm._data的属性,改造后的代码如下:

function MVVM(options) {
    this.$options = options;
    var data = this._data = this.$options.data, me = this;
    // 属性代理,实现 vm.xxx -> vm._data.xxx
    Object.keys(data).forEach(function(key) {
        me._proxy(key);
    });
    observe(data, this);
    this.$compile = new Compile(options.el || document.body, this)
}

MVVM.prototype = {
    _proxy: function(key) {
        var me = this;
        Object.defineProperty(me, key, {
            configurable: false,
            enumerable: true,
            get: function proxyGetter() {
                return me._data[key];
            },
            set: function proxySetter(newVal) {
                me._data[key] = newVal;
            }
        });
    }
};

这里主要还是利用了Object.defineProperty()这个方法来劫持了vm实例对象的属性的读写权,使读写vm实例的属性转成读写了vm._data的属性值,达到鱼目混珠的效果,哈哈

至此,全部模块和功能已经完成了,如本文开头所承诺的两点。一个简单的MVVM模块已经实现,其思想和原理大部分来自经过简化改造的vue源码,猛戳这里可以看到本文的所有相关代码。
由于本文内容偏实践,所以代码量较多,且不宜列出大篇幅代码,所以建议想深入了解的童鞋可以再次结合本文源代码来进行阅读,这样会更加容易理解和掌握。

总结

本文主要围绕“几种实现双向绑定的做法”、“实现Observer”、“实现Compile”、“实现Watcher”、“实现MVVM”这几个模块来阐述了双向绑定的原理和实现。并根据思路流程渐进梳理讲解了一些细节思路和比较关键的内容点,以及通过展示部分关键代码讲述了怎样一步步实现一个双向绑定MVVM。文中肯定会有一些不够严谨的思考和错误,欢迎大家指正,有兴趣欢迎一起探讨和改进~

最后,感谢您的阅读!

查看原文

赞 1297 收藏 1769 评论 152

_我已经从中二毕业了 发布了文章 · 2月9日

蓝桥杯2018决赛-第九届决赛-交换次数

题面

标题:交换次数

IT产业人才需求节节攀升。业内巨头百度、阿里巴巴、腾讯(简称BAT)在某海滩进行招聘活动。
招聘部门一字排开。由于是自由抢占席位,三大公司的席位随机交错在一起,形如:
ABABTATT,这使得应聘者十分别扭。
于是,管理部门要求招聘方进行必要的交换位置,使得每个集团的席位都挨在一起。即最后形如:
BBAAATTT 这样的形状,当然,也可能是:
AAABBTTT 等。

现在,假设每次只能交换2个席位,并且知道现在的席位分布,
你的任务是计算:要使每个集团的招聘席位都挨在一起需要至少进行多少次交换动作。

输入是一行n个字符(只含有字母B、A或T),表示现在的席位分布。
输出是一个整数,表示至少交换次数。

比如,输入:
TABTABBTTTT

程序应该输出:
3

再比如,输入:
TTAAABB

程序应该输出:
0

我们约定,输入字符串的长度n 不大于10万

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms

题解

首页通过题目可以知道,排序的方式有六种,分别是:

  • ABT
  • ATB
  • BAT
  • BTA
  • TAB
  • TBA

上面其实就是 ABT 的六种组合。我们要做的就是将输入的字符串,根据上面的每一种组合,每一个字符交换到正确的位置上。例如输入TABTAB,排序方式为ABT,就需要将两个AA交换到第 0 位和第 1 位,将两个BB交换到第 2 位和第 3 位,最后两个TT就是一定会在倒数第二位和第一位。由此可的,我们只需要根据每一种组合,知道ABT的先后排序顺序,依次交换直到符合条件,六组里最少交换次数的就是最后的答案。

使用对拍程序生成 10 万的数据,能够在本机 1 秒内执行。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <fstream>

using namespace std;

string s;
map<char, int> M;
// ABT 出现的组合情况
char per[6][3] = {
  {'A', 'B', 'T'},
  {'A', 'T', 'B'},
  {'B', 'A', 'T'},
  {'B', 'T', 'A'},
  {'T', 'A', 'B'},
  {'T', 'B', 'A'},
};

int minimumSwapCount (char com[]) {
  map<char, int> m1, m2, m3;
  char c1 = com[0], c2 = com[1], c3 = com[2];
  int l = 0;
  int r = M[c1];
  int res = 0;
  for (int i = l; i < r; i++)
    m1[s[i]]++;
  
  l = r;
  r = l + M[c2];
  for (int i = l; i < r; i++)
    m2[s[i]]++;
  
  l = r;
  r = s.length();
  for (int i = l; i < r; i++)
    m3[s[i]]++;
  
  // printf("A = %d, B = %d, T = %d\n", m1['A'], m1['B'], m1['T']);
  // printf("A = %d, B = %d, T = %d\n", m2['A'], m2['B'], m2['T']);
  // printf("A = %d, B = %d, T = %d\n", m3['A'], m3['B'], m3['T']);
  // cout << endl;

  // m1 只能有 c1 存在,c2 和 c3 都需要与 m2, m3 交换
  while (m1[c2]) {
    if (m2[c1]) {
      m1[c1]++;
      m2[c1]--;
      m1[c2]--;
      m2[c2]++;
      res++;
    } else if (m3[c1]) {
      m1[c1]++;
      m3[c1]--;
      m1[c2]--;
      m3[c2]++;
      res++;
    }
  }
  while (m1[c3]) {
    if (m2[c1]) {
      m1[c1]++;
      m2[c1]--;
      m1[c3]--;
      m2[c3]++;
      res++;
    } else if (m3[c1]) {
      m1[c1]++;
      m3[c1]--;
      m1[c3]--;
      m3[c3]++;
      res++;
    }
  }

  // m1 经过与 m2 和 m3 的交换后,m1 里只会保留 c1
  // m2 里可能还有 c2 和 c3 的值,与 m3 交换
  while (m2[c3]) {
    if (m3[c2]) {
      m2[c2]++;
      m3[c2]--;
      m2[c3]--;
      m3[c3]++;
      res++;
    }
  }

  // 经过上面的循环,m1 内只有 c1,m2 内只有 c2,由此 m3 内只会有 c3
  // 返回本次组合的交换次数
  return res;
}

int main () {
  cin >> s;

  // ifstream infile; 
  // infile.open("in.txt");
  // infile >> s;
  
  int n = s.length(), ans = 1 << 21;

  // 求出输入字符串中,A、B 和 T 的出现次数
  for (int i = 0; i < n; i++)
    M[s[i]]++;
  
  // 求每种组合最小的交换次数
  for (int i = 0; i < 6; i++)
    ans = min(ans, minimumSwapCount(per[i]));

  cout << ans << endl;

  return 0;
}

知识点

  • 排列组合;
  • 交换。
查看原文

赞 0 收藏 0 评论 0

_我已经从中二毕业了 发布了文章 · 2月1日

2020蓝桥杯校内赛-一带一路-图论-最小生成树

题面

问题描述
  2015年,全中国实现了户户通电。作为一名电力建设者,小明正在帮助一带一路上的国家通电。
  这一次,小明要帮助 n 个村庄通电,其中 1 号村庄正好可以建立一个发电站,所发的电足够所有村庄使用。
  现在,这 n 个村庄之间都没有电线相连,小明主要要做的是架设电线连接这些村庄,使得所有村庄都直接或间接的与发电站相通。
  小明测量了所有村庄的位置(坐标)和高度,如果要连接两个村庄,小明需要花费两个村庄之间的坐标距离加上高度差的平方,形式化描述为坐标为 (x_1, y_1) 高度为 h_1 的村庄与坐标为 (x_2, y_2) 高度为 h_2 的村庄之间连接的费用为
  sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2))+(h_1-h_2)*(h_1-h_2)。
  在上式中 sqrt 表示取括号内的平方根。请注意括号的位置,高度的计算方式与横纵坐标的计算方式不同。
  由于经费有限,请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。
输入格式
  输入的第一行包含一个整数 n ,表示村庄的数量。
  接下来 n 行,每个三个整数 x, y, h,分别表示一个村庄的横、纵坐标和高度,其中第一个村庄可以建立发电站。
输出格式
  输出一行,包含一个实数,四舍五入保留 2 位小数,表示答案。
样例输入
4
1 1 3
9 9 7
8 8 6
4 5 4
样例输出
17.41
评测用例规模与约定
  对于 30% 的评测用例,1 <= n <= 10;
  对于 60% 的评测用例,1 <= n <= 100;
  对于所有评测用例,1 <= n <= 1000,0 <= x, y, h <= 10000。

题解

通过阅读题面了解到是最小生成树的模板题。接收完数据后,需要通过题目给出的公式算出两点之间的权重,结果保存到一个邻接矩阵里(稠密图)。最后使用普里姆算法,设置第一个结点为起点,求出最小生成树。最后将所有边的权值加起来就是答案。输出可以使用printf("%.2f")格式化输出,最自动四舍五入。

代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define N 1001
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFTY 1 << 21

using namespace std;

double M[N][N], d[N];
int color[N], p[N], n;
struct Node {
  double x, y, h;
} arr[N];

void prim () {
  for (int i = 0; i < N; i++) {
    color[i] = WHITE;
    d[i] = INFTY;
  }

  d[0] = 0;
  p[0] = -1;

  int mincost, u;
  
  while (1) {
    mincost = INFTY;
    
    for (int i = 0; i < n; i++) {
      if (color[i] != BLACK && d[i] < mincost) {
        mincost = d[i];
        u = i;
      }
    }

    if (mincost == INFTY)
      break;

    color[u] = BLACK;

    for (int v = 0; v < n; v++) {
      if (color[v] != BLACK && M[u][v]) {
        d[v] = M[u][v];
        p[v] = u;
        color[v] = GRAY;
      }
    }
  }
}

int main () {
  cin >> n;

  double x, y, h;
  
  for (int i = 0; i < n; i++) {
    cin >> x >> y >> h;
    arr[i].x = x;
    arr[i].y = y;
    arr[i].h = h;
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j)
        M[i][j] = 0;
      else {
        x = (arr[i].x - arr[j].x) * (arr[i].x - arr[j].x);
        y = (arr[i].y - arr[j].y) * (arr[i].y - arr[j].y);
        h = (arr[i].h - arr[j].h) * (arr[i].h - arr[j].h);
        M[i][j] = sqrt(x + y) + h;
      }
    }
  }

  prim();

  double ans = 0;
  for (int i = 0; i < n; i++)
    ans += d[i];

  printf("%.2f", ans);

  return 0;
}

知识点

  • 图论;
  • 最小生成树;
  • 普里姆算法。
查看原文

赞 0 收藏 0 评论 0

_我已经从中二毕业了 发布了文章 · 2月1日

2020蓝桥杯校内赛-梅花桩-搜索

题面

问题描述
  小明每天都要练功,练功中的重要一项是梅花桩。
  小明练功的梅花桩排列成 n 行 m 列,相邻两行的距离为 1,相邻两列的距离也为 1。
  小明站在第 1 行第 1 列上,他要走到第 n 行第 m 列上。小明已经练了一段时间,他现在可以一步移动不超过 d 的距离(直线距离)。
  小明想知道,在不掉下梅花桩的情况下,自己最少要多少步可以移动到目标。
输入格式
  输入的第一行包含两个整数 n, m,分别表示梅花桩的行数和列数。
  第二行包含一个实数 d(最多包含一位小数),表示小明一步可以移动的距离。
输出格式
  输出一个整数,表示小明最少多少步可以到达目标。
样例输入
3 4
1.5
样例输出
3
评测用例规模与约定
  对于 30% 的评测用例,2 <= n, m <= 20,1 <= d <= 20。
  对于 60% 的评测用例,2 <= n, m <= 100,1 <= d <= 100。
  对于所有评测用例,2 <= n, m <= 1000,1 <= d <= 100。

题解 1

使用宽度优先搜索,从(1,1)开始搜索。用 x 表示行,用 y 表示列。d 为用户输入的可以移动的距离

  • 往下搜索(x + d, y);
  • 往右搜索(x, y + d)
  • 斜着搜索:从当前点 p1(从队头取出)出发,找另外一个点 p2,符合 p1p2 的距离的要小于 d*d 的点 p2 入队。

代码里使用了bool booked[N][N]二维数组用来表示已经走过的(x, y)点,避免重复的搜索。由于输入的步数 d 可能会很大,斜着走更加容易走到终点,把斜着走符合条件的点先入队,会避免走那些更远的点,从而达到节省时间的效果。

⚠️斜着走搜索可以访问的点时间复杂度太高,无法通过 100% 的数据。且部分答案错误,仅提供参考思路。

代码 1

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#define N 10001

using namespace std;

const double minDis = sqrt(2);
int n, m;
double d;
bool booked[N][N];
struct Point {
  int x, y, step;
};

void bfs () {
  // d1 横竖着走最大的移动距离
  // d2 斜着走最大的移动距离
  int d1 = (int)d;
  queue<struct Point> Q;

  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      booked[i][j] = false;

  struct Point p;
  p.x = 1;
  p.y = 1;
  p.step = 0;

  Q.push(p);
  while (Q.size()) {
    struct Point top = Q.front(); Q.pop();

    if (top.x >= n && top.y >= m) {
      cout << top.step << endl;
      break;
    }

    struct Point p1, p2, p3;

    // 斜着走
    // 斜着走最小都需要跟号 2 的长度
    if (d >= minDis) {
      for (int i = 1; i <= d; i++) {
        for (int j = 1; j <= d; j++) {
          int temp = j * j + i * i;
          if (temp <= d * d) {
            struct Point p3;
            p3.x = j + top.y;
            p3.y = i + top.x;
            
            if (!booked[p3.x][p3.y]) {
              booked[p3.x][p3.y] = true;
              p3.step = top.step + 1;
              Q.push(p3);
            }
          }
        }
      }
    }
    
    
    p1.x = top.x + d1;
    if (!booked[p1.x][top.y] && top.x < n) {
      // 向下走
      p1.y = top.y;
      p1.step = top.step + 1;
      booked[p1.x][p1.y] = true;
      Q.push(p1);
    }

    p2.y = top.y + d1;
    if (!booked[top.x][p2.y] && top.y < m) {
      // 向右走
      p2.x = top.x;
      p2.step = top.step + 1;
      booked[p2.x][p2.y] = true;
      Q.push(p2);
    }
  }
}

int main () {
  cin >> n >> m;
  cin >> d;

  bfs();

  return 0;
}

题解 2

由于第一个解题思路斜着走搜索时间复杂度太高,经过长时间的思考(熬夜)想到另外一种解题思路:

  • 先从右边至右下搜索:从头结点的ty = y + d >= m ? m : y + d开始搜索,头结点tx = x + ii 是从 0 递增到d,新的点(tx, ty)和头结点计算距离判断是否小于d*d,如果是则将新点入队;
  • 当新的点(tx, ty)入队后,进入第二个循环,开始往回走,寻找以d为半径内覆盖的最远的点(tx, ty - j),变量j从 1 开始递增,直到找到新点(tx, ty - j),或ty - j小于 0,则退出。
x为当前队列头结点的成员变量,y为当前队列头结点的成员变量,d为用户输入的浮点数向下取整。

代码里使用了bool booked[N][N]二维数组用来表示已经走过的(x, y)点,避免重复的搜索。

代码 2

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#define N 2000

using namespace std;

int n, m;
double d;
bool booked[N][N] = {false};
struct Point {
  int x, y, step;
};

void bfs () {
  int d1 = (int)d, tx, ty;
  queue<struct Point> Q;

  struct Point p;
  p.x = 1;
  p.y = 1;
  p.step = 0;

  Q.push(p);
  while (Q.size()) {
    struct Point top = Q.front(); Q.pop();

    if (top.x >= n && top.y >= m) {
      cout << top.step << endl;
      break;
    }

    // 向右和右下搜索
    for (int i = 0; i <= d1; i++) {
      tx = top.x + i;
      ty = top.y + d1 >= m ? m : top.y + d1;

      if ((tx - top.x) * (tx - top.x) + (ty - top.y) * (ty - top.y) <= d * d && !booked[tx][ty]) {
        struct Point p;
        p.x = tx;
        p.y = ty;
        p.step = top.step + 1;
        booked[tx][ty] = true;
        Q.push(p);
      }

      if (i > 0) {
        int j = 1;
        bool found = false;

        while (!found && ty - j - top.y >= 0) {
          if ((tx - top.x) * (tx - top.x) + (ty - j - top.y) * (ty - j - top.y) <= d * d && !booked[tx][ty - j]) {
            struct Point p;
            p.x = tx;
            p.y = ty - j;
            p.step = top.step + 1;
            booked[tx][ty - j] = true;
            found = true;
            break;
          } else {
            j++;
          }
        }
      }
    }
  }
}

int main () {
  cin >> n >> m;
  cin >> d;

  bfs();

  return 0;
}

知识点

  • 宽度优先搜索(bfs);
  • 两点之间的距离:d^2 = (x - x1)^2 + (y - y1)^2
查看原文

赞 0 收藏 0 评论 0

_我已经从中二毕业了 赞了文章 · 2018-03-14

Koa原理学习路径与设计哲学

Koa原理学习路径与设计哲学

本文基于Koa@2.5.0

Koa简介(废话篇)

Koa是基于Node.jsHTTP框架,由Express原班人马打造。是下一代的HTTP框架,更简洁,更高效。

我们来看一下下载量(2018.3.4)

Koa:471,451 downloads in the last month
Express:18,471,701 downloads in the last month

说好的Koa是下一代框架呢,为什么下载量差别有这么大呢,Express一定会说:你大爷还是你大爷!

确实,好多知名项目还是依赖Express的,比如webpack的dev-server就是使用的Express,所以还是看场景啦,如果你喜欢DIY,喜欢绝对的控制一个框架,那么这个框架就应该什么功能都不提供,只提供一个基础的运行环境,所有的功能由开发者自己实现。

正是由于Koa的高性能和简洁,好多知名项目都在基于Koa,比如阿里的eggjs,360奇舞团的thinkjs

所以,虽然从使用范围上来讲,Express对于Koa你大爷还是你大爷!,但是如果Express很好,为什么还要再造一个Koa呢?接下来我们来了解下Koa到底带给我们了什么,Koa到底做了什么。

如何着手分析Koa

先来看两段demo。

下面是Node官方给的一个HTTP的示例。

const http = require('http');

const hostname = '127.0.0.1';
const port = 3000;

const server = http.createServer((req, res) => {
  res.statusCode = 200;
  res.setHeader('Content-Type', 'text/plain');
  res.end('Hello World\n');
});

server.listen(port, hostname, () => {
  console.log(`Server running at http://${hostname}:${port}/`);
});

下面是最简单的一个Koa的官方实例。

const Koa = require('koa');
const app = new Koa();

app.use(async ctx => {
  ctx.body = 'Hello World';
});

app.listen(3000);

Koa是一个基于Node的框架,那么底层一定也是用了一些Node的API。

jQuery很好用,但是jQuery也是基于DOM,逃不过也会用element.appendChild这样的基础API。Koa也是一样,也是用一些Node的基础API,封装成了更好用的HTTP框架。

那么我们是不是应该看看Koahttp.createServer的代码在哪里,然后顺藤摸瓜,了解整个流程。

Koa核心流程分析

Koa的源码有四个文件

  • application.js // 核心逻辑
  • context.js // 上下文,每次请求都会生成一个
  • request.js // 对原生HTTP的req对象进行包装
  • response.js // 对原生HTTP的res对象进行包装

我们主要关心application.js中的内容,直接搜索http.createServer,会搜到

  listen(...args) {
    debug('listen');
    const server = http.createServer(this.callback());
    return server.listen(...args);
  }

刚好和Koa中的这行代码app.listen(3000);关联起来了。

找到源头,现在我们就可以梳理清楚主流程,大家对着源码看我写的这个流程

fn:listen
∨
fn:callback
∨
[fn:compose] // 组合中间件 会生成后面的 fnMiddleware
∨
fn:handleRequest // (@closure in callback)
∨
[fn(req, res):createContext] // 创建上下文 就是中间件中用的ctx
∨
fn(ctx, fnMiddleware):handleRequest // (@koa instance)
∨
code:fnMiddleware(ctx).then(handleResponse).catch(onerror);
∨
fn:handleResponse
∨
fn:respond
∨
code:res.end(body);

从上面可以看到最开始是listen方法,到最后HTTP的res.end方法。

listen可以理解为初始化的方法,每一个请求到来的时候,都会经过从callbackrespond的生命周期。

在每个请求的生命周期中,做了两件比较核心的事情:

  1. 将多个中间件组合
  2. 创建ctx对象

多个中间件组合后,会先后处理ctx对象,ctx对象中既包含的req,也包含了res,也就是每个中间件的对象都可以处理请求和响应。

这样,一次HTTP请求,接连经过各个中间件的处理,再到返回给客户端,就完成了一次完美的请求。

Koa中的ctx

app.use(async ctx => {
  ctx.body = 'Hello World';
});

上面的代码是一个最简单的中间件,每个中间件的第一个参数都是ctx,下面我们说一下这个ctx是什么。

创建ctx的代码:

  createContext(req, res) {
    const context = Object.create(this.context);
    const request = context.request = Object.create(this.request);
    const response = context.response = Object.create(this.response);
    context.app = request.app = response.app = this;
    context.req = request.req = response.req = req;
    context.res = request.res = response.res = res;
    request.ctx = response.ctx = context;
    request.response = response;
    response.request = request;
    context.originalUrl = request.originalUrl = req.url;
    context.cookies = new Cookies(req, res, {
      keys: this.keys,
      secure: request.secure
    });
    request.ip = request.ips[0] || req.socket.remoteAddress || '';
    context.accept = request.accept = accepts(req);
    context.state = {};
    return context;
  }

直接上代码,Koa每次请求都会创建这样一个ctx对象,以提供给每个中间件使用。

参数的req, res是Node原生的对象。

下面解释下这三个的含义:

  • context:Koa封装的带有一些和请求与相应相关的方法和属性
  • request:Koa封装的req对象,比如提了供原生没有的host属性。
  • response:Koa封装的res对象,对返回的bodyhook了getter和setter。

其中有几行一堆 xx = xx = xx,这样的代码。

是为了让ctx、request、response,能够互相引用。

举个例子,在中间件里会有这样的等式

ctx.request.ctx === ctx
ctx.response.ctx === ctx

ctx.request.app === ctx.app
ctx.response.app === ctx.app

ctx.req === ctx.response.req
// ...

为什么会有这么奇怪的写法?其实只是为了互相调用方便而已,其实最常用的就是ctx。

打开context.js,会发现里面写了一堆的delegate

/**
 * Response delegation.
 */

delegate(proto, 'response')
  .method('attachment')
  .method('redirect')
  .method('remove')
  .method('vary')
  .method('set')
  .method('append')
  .method('flushHeaders')
  .access('status')
  .access('message')
  .access('body')
  .access('length')
  .access('type')
  .access('lastModified')
  .access('etag')
  .getter('headerSent')
  .getter('writable');

/**
 * Request delegation.
 */

delegate(proto, 'request')
  .method('acceptsLanguages')
  .method('acceptsEncodings')
  .method('acceptsCharsets')
  .method('accepts')
  .method('get')
  .method('is')
  .access('querystring')
  .access('idempotent')
  .access('socket')
  .access('search')
  .access('method')
  .access('query')
  .access('path')
  .access('url')
  .getter('origin')
  .getter('href')
  .getter('subdomains')
  .getter('protocol')
  .getter('host')
  .getter('hostname')
  .getter('URL')
  .getter('header')
  .getter('headers')
  .getter('secure')
  .getter('stale')
  .getter('fresh')
  .getter('ips')
  .getter('ip');

是为了把大多数的requestresponse中的属性也挂在ctx下,我们为了拿到请求的路径需要ctx.request.path,但是由于代理过path这个属性,ctx.path也是可以的,即ctx.path === ctx.request.path

ctx模块大概就是这样,没有讲的特别细,这块是重点不是难点,大家有兴趣自己看看源码很方便。

一个小tip: 有时候我也会把context.js中最下面的那些delegate当成文档使用,会比直接看文档快一点。

Koa中间件机制

中间件函数的参数解释

  • ctx:上面讲过的在请求进来的时候会创建一个给中间件处理请求和响应的对象,比如读取请求头和设置响应头。
  • next:暂时可以理解为是下一个中间件,实际上是被包装过的下一个中间件。

一个小栗子

我们来看这样的代码:

// 第一个中间件
app.use(async(ctx, next) => {
  console.log('m1.1', ctx.path);
  ctx.body = 'Koa m1';
  ctx.set('m1', 'm1');
  next();
  console.log('m1.2', ctx.path);
});

// 第二个中间件
app.use(async(ctx, next) => {
  console.log('m2.1', ctx.path);
  ctx.body = 'Koa m2';
  ctx.set('m2', 'm2');
  next();
  debugger
  console.log('m2.2', ctx.path);
});

// 第三个中间件
app.use(async(ctx, next) => {
  console.log('m3.1', ctx.path);
  ctx.body = 'Koa m3';
  ctx.set('m3', 'm3');
  next();
  console.log('m3.2', ctx.path);
});

会输出什么呢?来看下面的输出:

m1.1 /
m2.1 /
m3.1 /
m3.2 /
m2.2 /
m1.2 /

来解释一下上面输出的现象,由于将next理解为是下一个中间件,在第一个中间件执行next的时候,第一个中间件就将执行权限给了第二个中间件,所以m1.1后输出的是m2.1,在之后是m3.1

那么为什么m3.1后面输出的是m3.2呢?第三个中间件之后已经没有中间件了,那么第三个中间件里的next又是什么?

我先偷偷告诉你,最后一个中间件的next是一个立刻resolve的Promise,即return Promise.resolve(),一会再告诉你这是为什么。

所以第三个中间件(即最后一个中间件)可以理解成是这样子的:

app.use(async (ctx, next) => {
    console.log('m3.1', ctx.path);
    ctx.body = 'Koa m3';
    ctx.set('m3', 'm3');
    new Promise.resolve(); // 原来是next
    console.log('m3.2', ctx.path);
});

从代码上看,m3.1后面就会输出m3.2

那为什么m3.2之后又会输出m2.2呢?,我们看下面的代码。

let f1 = () => {
  console.log(1.1);
  f2();
  console.log(1.2);
}

let f2 = () => {
  console.log(2.1);
  f3();
  console.log(2.2);
}

let f3 = () => {
  console.log(3.1);
  Promise.resolve();
  console.log(3.2);
}

f1();

/*
  outpout
  1.1
  2.1
  3.1
  3.2
  2.2
  1.2
*/

这段代码就是纯函数调用而已,从这段代码是不是发现,和上面一毛一样,对一毛一样,如果将next理解成是下一个中间件的意思,就是这样。

中间件组合的过程分析

用户使用中间件就是用app.use这个API,我们看看做了什么:

  // 精简后去掉非核心逻辑的代码
  use(fn) {
    this.middleware.push(fn);
    return this;
  }

可以看到,当我们应用中间件的时候,只是把中间件放到一个数组中,然后返回this,返回this是为了能够实现链式调用。

那么Koa对这个数组做了什么呢?看一下核心代码

const fn = compose(this.middleware); // @callback line1
// fn 即 fnMiddleware 
return fnMiddleware(ctx).then(handleResponse).catch(onerror); // @handleRequest line_last

可以看到用compose处理了middleware数组,得到函数fnMiddleware,然后在handleRequest返回的时候运行fnMiddleware,可以看到fnMiddleware是一个Promiseresolve的时候就会处理完请求,能猜到compose将多个中间件组合成了一个返回Promise的函数,这就是奇妙之处,接下来我们看看吧。

精简后的compose源码

// 精简后去掉非核心逻辑的代码
00    function compose (middleware) {
01      return function (context, next) { // fnMiddleware
02        return dispatch(0)
03        function dispatch (i) {
04          let fn = middleware[i] // app.use的middleware
05          if (!fn) return Promise.resolve()
06          return fn(context, function next () {
07            return dispatch(i + 1)
08          })
09        }
10      }
11    }

精简后代码只有十几行,但是我认为这是Koa最难理解、最核心、最优雅、最奇妙的地方。

看着各种function,各种return有点晕是吧,不慌,不慌啊,一行一行来。

compose返回了一个匿名函数,这个匿名函数就是fnMiddleware

刚才我们是有三个中间件,你们准备好啦,请求已经过来啦!

当请求过来的时候,fnMiddleware就运行了,即运行了componse返回的匿名函数,同时就会运行返回的dispatch(0),那我们看看dispatch(0)做了什么,仔细一看其实就是

// dispatch(0)的时候,fn即middleware[0]
return middleware[0](context, function next (){
  return dispatch(1);
})

// 上面的context和next即中间件的两个参数
// 第一个中间件
app.use(async(ctx, next) => {
  console.log('m1.1', ctx.path);
  ctx.body = 'Koa m1';
  ctx.set('m1', 'm1');
  next(); // 这个next就是dispatch(1)
  console.log('m1.2', ctx.path);
});

同理,在第二个中间件里面的next,就是dispatch(2),也就是用上面的方法被包裹一层的第三个中间件。

  • 现在来看第三个中间件里面的next是什么?

可以看到精简过的compose05行有个判断,如果fn不存在,会返回Promise.resolve(),第三个中间件的nextdispatch(3),而一共就有三个中间件,所以middleware[3]是undefined,触发了分支判断条件,就返回了Promise.resolve()

再来复盘一下:

  1. 请求到来的事情,运行fnMiddleware(),即会运行dispatch(0)调起第一个中间件。
  2. 第一个中间件的nextdispatch(1),运行next的时候就调起第二个中间件
  3. 第二个中间件的nextdispatch(2),运行next的时候就调起第三个中间件
  4. 第三个中间件的nextdispatch(3),运行next的时候就调起Promise.resolve()。可以把Promise.resolve()理解成一个空的什么都没有干的中间件。

到此,大概知道了多个中间件是如何被compose成一个大中间件的了吧。

中间件的类型

koa2中,支持三种类型的中间件:

  • common function:普通的函数,需要返回一个promise
  • generator function:需要被co包裹一下,就会返回一个promise
  • async function:直接使用,会直接返回promise

可以看到,无论哪种类型的中间件,只要返回一个promise就好了,因为这行关键代码return fnMiddleware(ctx).then(handleResponse).catch(onerror);,可以看到KoafnMiddleware的返回值认为是promise。如果传入的中间件运行后没有返回promise,那么会导致报错。

结语

Koa的原理就解析到这里啦,欢迎交流讨论。
为了更好地让大家学习Koa,我写了一个mini版本的Koa,大家可以看一下 https://github.com/geeknull/t...

查看原文

赞 54 收藏 79 评论 3

_我已经从中二毕业了 赞了问题 · 2018-03-03

解决关于CSS布局的问题,请问为什么这两个箱子不在同一行?

clipboard.png

 <!DOCTYPE html>
 <html lang="en">
 <head>
     <meta charset="UTF-8">
     <meta name="viewport" content="width=device-width, initial-scale=1.0">
     <meta http-equiv="X-UA-Compatible" content="ie=edge">
     <title>Document</title>
 </head>


 <style>
   .outer{
      width:500px;
      height: 500px;
      background: green;
   }

   .outer>div{
       display: inline-block;
   }

   .inner1{

       width:48%;
       height:48%;
       margin: 0 1%;
       background: powderblue;
   }

   .inner2{
       
       width: 48%;
       height: 48%;
       margin: 0 1%;
       background: blue;

   }
 
 
 
 </style>
 
 <body>


    <div class="outer">

           <div class="inner1"></div>
           <div class="inner2"></div>

    </div>
     
 </body>
 </html>

这样加起来不正好每个百分之50么,感觉应该在一行才对啊

关注 10 回答 9

_我已经从中二毕业了 关注了收藏夹 · 2018-02-05

你所需要知道的推荐系统知识及应用

尽量能让不懂技术的朋友能看得懂看得爽(白话逻辑、原理、业务场景),也希望能让搞技术的朋友看到的懂(给案例给代码)

关注 214

_我已经从中二毕业了 报名了讲座 · 2018-01-08

_我已经从中二毕业了 回答了问题 · 2017-12-09

解决使用VUE发现变量无法解析到href=""里

修改为:

<a :href="site.name">{{site.name}}</a>

关注 5 回答 4

_我已经从中二毕业了 赞了文章 · 2017-10-10

浅谈对CSRF的认识,以及一些应对措施

CSRF

CSRF(Cross Site Request Forgery, 跨站域请求伪造)的定义,相信大家都不陌生。它是指攻击者通过诱导用户,打开已精心设计好的页面后,发送请求到某个网站执行某个操作(修改数据)的过程。这里有以下三个前提:

1、用户已登录某可信网站(A站,以下所提到的A站都指这里的某可信网站)

2、A站存在某个请求,可以修改或保存信息(例如:/saveinfo)

3、用户在A站Session过期前打开攻击者设计好的的页面,并自动或触发发送请求(/saveinfo)

看起来要求听苛刻的,但的确存在这种情况。“即便是大名鼎鼎的 Gmail, 在 2007 年底也存在着 CSRF 漏洞,从而被黑客攻击而使 Gmail 的用户造成巨大的损失。”

想要了解怎么应对CSRF,先来看看攻击者干些什么。

攻击者能干什么

因为受同源策略限制,攻击者并不能拿到A站的任何信息(Cookies)和响应信息,他只能利用发送请求时,会带上cookies去校验登录信息或权限的特性,去修改用户的数据,来达到攻击目的。因此,一般用于获取信息而不涉及到修改信息的请求(Get)就不用担心会有CSRF危险了,重要的是能修改信息的请求。当然,如果你用Get去修改信息,那就需要考虑防范CSRF了。but这样做本身就违背了HTTP method设定的初衷,同时Get的攻击方式更为简单,一个Img标签加上JavaScript就能触发。所以不建议这么做

CRSF预防措施

正所谓兵来将挡,水来土掩。了解了攻击者利用的一些原理,就对应的可以找到一些对应措施

1、在服务端验证HTTP的Referer字段。

此方法成本较小,只需要在服务端拦截请求,判断Referer是否来自于同一域名,如果不是或者不存在CSRF的话,则认为有可能是CSRF攻击,直接过滤。但这种方法也有弊端,那就是当有些人会担心Referer会泄露个人信息时(毕竟像服务器发送了自己的来源地址)。这些人会尝试去关闭Referer。这样当这些用户发起请求时就不会带上Referer,这个请求就会被判成有可能的CSRF攻击,因为按照上述过滤规则,请求头中无Referer的有可能会是CSRF攻击。

2、在请求地址中添加 token 并验证

此方法的核心思想就是,构造成什么样的信息,来辨别请求是从用户手中发出,还是被攻击者利用而发出的,很显然Cookie不能做到,因为用户和攻击者都能将同样的Cookie带到服务器上。

答案就是token(令牌),它由服务端通过一定算法生成,每当用户请求页面的时候,则向用户返回的页面中带上一个全新的token。下次用户在发送请求的时候,就带上该token与服务器的token进行对比。但这token要放在哪里呢?

三种情况:
1 对于Get请求,在Url后面动态加上token。 此方法也有一定约束,页面有很多链接,一个一个加太麻烦,就需要在document加载完以后,通过js来辅助完成了。但这个方法对于动态生成的内容,就无能为力了。

2 Post请求 在form表带中加上
<pre>< input type=”hidden” name=token value=”tokenvalue”/></pre>

(查看PC淘宝的个人中心,其修改资料就是用的此方法)由于同源策略,攻击者是拿不到表单里的数据的。此方法也跟Get请求有同样的问题,那就是对于多链接和动态生成的内容,js批量加上token的办法就不行了,只能手动添加。

3、对于Ajax请求,如果跨域,则默认不会带上A站的cookie。因此,从某些方面来说,是相对安全的。但是根据w3c对Ajax的一个属性的描述

4.6.4 The withCredentials attribute

client . withCredentials

True when user credentials are to be included in a cross-origin request. False when they are to be excluded in a cross-origin request and when cookies are to be ignored in its response. Initially false.

大概说的意思是,如果withCredentials为true,则存在跨域请求的时候,用户的credentials(包括cookie,我是这么理解的,如有错欢迎指正)会被带上。

如果将withCredentials设为true,这样也会存在上述的安全问题,因为Cookies在发送请求的同时也被戴上了。

总结

1、攻击者是利用用户登录过信任网站后,在会话未过期之前诱导用户打开有问题的网站而达到攻击目的的

2、常见的防御措施有校验请求头的referer,以及新增攻击者无法获取的随机数token(令牌)来达到防御目的的。

3、token存放的地方有多种,对于POST请求,则构造hideen的input标签;对于Get则在链接后添加token;对于ajax,则在cookie中添加token。

4、个人觉得相对安全的做法就是既验证referer,同时也校验token。如涉及到更隐秘的操作,则需要通过验证码或者手动输入密码来做防范了。

参考文章:
https://www.w3.org/TR/2014/WD...
https://www.ibm.com/developer...
https://en.wikipedia.org/wiki...

第一次写Post,过程如此之多,小到markdown语法;大到发现问题、探索分析问题、查阅资料并自测验证。最后通篇检查,是否存在有问题的地方。整个过程虽然比较难,但这让自己对于CRSF有了更深刻的认识。在团队完成分享后不遗余力整理的一篇,相信以后会更好。

查看原文

赞 5 收藏 7 评论 1

认证与成就

  • 获得 350 次点赞
  • 获得 45 枚徽章 获得 4 枚金徽章, 获得 16 枚银徽章, 获得 25 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

  • Amaze UI 分页组件

    amazeui-pagination 是基于Amaze UI 和 jQuery 所造的轮子,因为妹子 UI 官方没有分页相关的 js 组件故自己造了一个。

注册于 2014-11-03
个人主页被 3.5k 人浏览