腾讯前端特工解题报告

网站链接：腾讯前端攻略。本来早就有的了，但是自己一直很排斥任何有关做题闯关的，今天又不小心看到了于是试了一下发现非常有意思，考察前端的基础知识，很灵活，比发试卷那种做题方式有意思多了，还能巩固或提升自己的能力

第一关，抓包

提示要抓包，于是查看在chrome查看response header，提示说『请设置隐藏域的值』，于是查了下网页的html代码，发现有一个隐藏域

<input type="hidden" name="timestamp">

于是猜测是要设置timestamp的值，就用Javascript在Chrome控制台中试了一下，果然对了:)

document.getElementsByName('timestamp').value = new Date().getTime()

第二关，CSS绘图

考察用CSS绘制简单的椭圆、三角形。就是考察对border和border-radius的理解以及会用css3中的旋转，没什么可说的，查看w3schools上的文档。不过需要注意的是题目中三角形指出了一定要绕某个点旋转，所以必须指定transform-origin

// 椭圆
border-radius: 50%;
// 三角形
border-color: transparent black;
-webkit-transform-origin: top right;
-webkit-transform: rotate(-60deg);

第三关，坦克大战

这个。。。涉及到游戏，真的是没有兴趣也压根不会，所以果断去网上找了一个代码，涉及到版权，就不贴出来了。。。

第四关，JS基础

第四题是最简单的一道，就是javascript的一些基本的使用方法，也就是语法，分三道题全是填空，下面<>表示要填的空

/* 1. 数组克隆（数组元素非引用类型） */
var clone = function(arr){
    return <>
};
// 答案：arr.slice()

/* 2. 去除字符串首尾空格 */
var trim = function(s){
    return <>
};
// 答案：s.trim()

/* 3. 将Nodelist对象转换为数组对象 */
var arrify = function(list){
    return <>
};
// 答案：Array.prototype.slice.call(list)

第五关，求最大值

这是最有意思的一个题，综合了DOM操作、算法方面的知识。用动态规划，由于是求最值，设r[i][j]为第0层到第i层的第j个节点的数字和的最大值（i和j均从0开始计数），data[i][j]为第i行j列的数字值，则

r[i][j] = max(r[i-1][j-1], r[i-1][j]) + data[i][j]  // i > 0, i > j > 0,
r[i][j] = r[i-1][0] + data[i][j]                    // i > 0, j = 0
r[i][j] = r[i-1][i-1] + data[i][j]                  // i > 0, j = i

然后为了输出路径，倒序遍历r数组，倒序输出节点，并在图中选中节点。为了方便，引入jquery，方便对DOM树的操作。时间空间复杂度均为O(N)，N是节点数，如果不是因为要自动选中图中的节点，而选中节点是又必须是从第二层开始依次序逐层选中的话，空间复杂度可以是O(n)，n为最后一层的节点数。以下是代码实现

// 引入jquery，以便使用jquery操作DOM。贴代码是要先贴这一段再贴其他的，以免jquery库还未加载完毕
var s = document.createElement('script');
s.src = "http://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js";
document.body.appendChild(s);

var record = [[+$($('#box>div>span')[0]).text()]];
var $rows = $('#box>div');
// 行
for (var i = 1; i < $rows.length; i++) {
    var row = $rows[i]
    var $cols = $(row).children('span')
    record.push([])
    // 列
    for (var j = 0; j < $cols.length; j++) {
        var num = +$($cols[j]).text()
        switch (j) {
            case 0: record[i][j] = record[i-1][0] + num;break;
            case i: record[i][j] = record[i-1][i-1] + num;break;
            default: record[i][j] = Math.max(record[i-1][j-1], record[i-1][j]) + num;
        }
    }
}

// 找到产生最大值的路径中最深层次的节点的下标
var max = 0
for (var k = 1; k < record[i-1].length; k++) {
    if (record[i-1][k] > record[i-1][max]) {
        max = k
    }
}
var path = []
// 从第一层节点到当前层节点数字之和的最大值
var sum = record[i-1][max]

// 从倒数第二层开始往回遍历，倒序输出路径
for (var i = record.length-1; i--;) {
    var r = record[i]
    var a = max ? r[max-1] : -1
    var b = (max == i+1) ? -1 : r[max]
    var t = max
    // 最大值路径在当前层中的节点下标
    if (a > b) {
        max--;
    }
    // 实际存的是上一层的节点
    path.push([t, sum - r[max]])
    sum = r[max]
}
// 选中图中的节点
for (var i = 2; $rows.length; i++) {
    var node = path.pop()
    $($('#box').children('#row_' + i).children()[node[0]]).click()
    console.log('%d -> %d', i, node[1])
}