2018.9.9字节跳动笔试题解（nodejs版）

1. 查找 最大 不含重复字符 子字符串AC, 思路：窗口遍历

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

rl.on('line', function (line) { // javascript每行数据的回调接口
    var str = line.trim();
    var tmp = '', maxSubStr = tmp, start = ;
    for(var i = ; i < str.length; i++){
        var j = tmp.search(str[i]);
        if(j === -){
            tmp += str[i];
        }else{
            if(tmp.length > maxSubStr.length){
                maxSubStr = tmp;
            }
            start += j + 
            tmp = str.slice(start, i + );
        }
        // console.log(tmp);
    }
    if(tmp.length > maxSubStr.length){
        maxSubStr = tmp;
    }
    console.log(maxSubStr.length);
    rl.close();
});
           

2.分几个部门未AC，笔试完后写的：

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

var M = ;
var curLine = ;
var input = [];

rl.on('line', function (line) { // javascript每行数据的回调接口
    if(curLine === ){
        M = parseInt(line.trim());
    }else{
        input.push(line.trim().split(' '));
        if(curLine === M){
            console.log(func(input));;
            rl.close();
        }
    }
    curLine++;
});

function func(input){
    var cnt = ;
    for(var i = ; i < input.length; i++){
        for(var j = ; j < input[].length; j++){
            if(input[i][j] == ){
                visit(input, i, j);
                cnt++;
            }
        }
    }
    return cnt;
}

function visit(input, i, j){
    input[i][j] = ;
    if(i- >=  && input[i-][j] == ){
        visit(input, i-, j);
    }
    if(i+ < input.length && input[i+][j] == ){
        visit(input, i+, j);
    }
    if(j- >=  && input[i][j-] == ){
        visit(input, i, j-);
    }
    if(j+ < input[].length && input[i][j+] == ){
        visit(input, i, j+);
    }
}
           

3.还原IP AC：暴力分段

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

rl.on('line', function (line) { // javascript每行数据的回调接口
    var str = line.trim();
    var ret = [], a, b, c, d;
    if(str.length > ){
        rl.close();
    }
    for(var i = ; i <= ; i++){
        if(str.length - i < ){
            break;
        }
        a = str.slice(, i);
        for(var j = ; j <= ; j++){
            if(str.length - i - j < ){
                break;
            }
            b = str.slice(i, i + j);
            for(var k = ; k <= ; k++){
                if(str.length - i - j - k < ){
                    break;
                }
                c = str.slice(i + j, i + j + k);
                d = str.slice(i + j + k);
                var tmp = [a, b, c, d].join('.');
                // console.log(tmp);
                if(/^(1\d{2,2}|2[0-4][0-9]|25[0-5]|[1-9][0-9]|[1-9])(\.(1\d{2,2}|2[0-4][0-9]|25[0-5]|[1-9][0-9]|[0-9])){3,3}$/.test(tmp)){
                    ret.push(tmp);
                }
            }
        }
    }
    console.log(ret.length);
    rl.close();
});
           

4.是否为合理utf-8码：比较每个字节是否在给定区间（比大小）40%，不知道为什么出错了，样例有点问题：

var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

var curLine = ;
var bytes = ;
var input = [];
rl.on('line', function (line) { // javascript每行数据的回调接口
    if(curLine === ){
        bytes = parseInt(line.trim());
        if(bytes > ){
            console.log();
            rl.close();
        }
    }else{
        input = line.trim().split(' ');
        for(var i = ; i < bytes; i++){
            input[i] = parseInt(input[i]);
        }
        if(bytes == ){
            if(input[] >  || input[] < ){
                console.log();
                rl.close();
            }else{
                console.log();
                rl.close();
            }
        }else if(bytes > ){
            var max = parseInt((new Array(bytes + )).join('1') + '0' + (new Array( - bytes)).join('1'), );
            var min = parseInt((new Array(bytes + )).join('1') + '0' + (new Array( - bytes)).join('0'), );
            // console.log(min, max);
            if(input[] > max || input[] < min){
                console.log();
                rl.close();
            }else{
                var max = ;
                var min = ;
                for(var i = ; i < bytes; i++){
                    if(input[i] > max || input[i] < min){
                        console.log();
                        rl.close();
                    }
                }
                console.log();
                rl.close();
            }
        }
    }
    curLine++;
});
           

5.抖音网红AC：反向建立有向图，逐个dfs，dfs返回路径等于人数，则计数加一

var Graph = (function () {
    function Graph(v) {
        this.vertices = v;
        this.edges = ;
        this.adj = [];
        this.marked = [];
        for (var i = ; i < this.vertices; i++) {
            this.adj[i] = [];
            this.marked[i] = false;
        }
    }

    Graph.prototype.addEdge = function (v, w) {
        this.adj[v].push(w);
        this.edges += ;
    }

    // search
    function _dfs(v, path) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) {
            path.push(v);
        }
        this.adj[v].forEach(element => {
            if (!this.marked[element]) {
                _dfs.call(this, element, path);
            }
        });
    }

    Graph.prototype.dfs = function (v) {
        for (var i = ; i < this.vertices; i++) {
            this.marked[i] = false;
        }
        var path = [];
        _dfs.call(this, v, path);
        return path;
    }

    return Graph;
})();

// 读取数据
var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

var N, M;
var curLine = ;
var g;

rl.on('line', function (line) {
    if (curLine === ) {
        N = parseInt(line.trim());
        g = new Graph(N + );
    } else if (curLine === ) {
        M = parseInt(line.trim());
    }else if(curLine === ){
        var arr = line.trim().split(' ');
        for (var i = ; i < M * ; i+=) {
            arr[i] = parseInt(arr[i]);
            arr[i + ] = parseInt(arr[i + ]);
            g.addEdge(arr[i + ], arr[i]);
        }

        var cnt = ;
        for (var i = ; i <= N; i++) {
            var tmp = g.dfs(i);
            if(tmp.length === N){
                cnt++;
            }
        }
        console.log(cnt);
        rl.close();
    }
    curLine++;
});