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 = 0;for(var i = 0; i < str.length; i++){var j = tmp.search(str[i]);if(j === -1){tmp += str[i];}else{if(tmp.length > maxSubStr.length){maxSubStr = tmp;}start += j + 1tmp = str.slice(start, i + 1);}// 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 = 0;var curLine = 0;var input = [];rl.on('line', function (line) { // javascript每行数据的回调接口if(curLine === 0){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 = 0;for(var i = 0; i < input.length; i++){for(var j = 0; j < input[0].length; j++){if(input[i][j] == 1){visit(input, i, j);cnt++;}}}return cnt;}// 递归遍历上下左右节点，访问后直接置零function visit(input, i, j){input[i][j] = 0;if(i-1 >= 0 && input[i-1][j] == 1){visit(input, i-1, j);}if(i+1 < input.length && input[i+1][j] == 1){visit(input, i+1, j);}if(j-1 >= 0 && input[i][j-1] == 1){visit(input, i, j-1);}if(j+1 < input[0].length && input[i][j+1] == 1){visit(input, i, j+1);}}
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 > 12){rl.close();}for(var i = 1; i <= 3; i++){if(str.length - i < 3){break;}a = str.slice(0, i);for(var j = 1; j <= 3; j++){if(str.length - i - j < 2){break;}b = str.slice(i, i + j);for(var k = 1; k <= 3; k++){if(str.length - i - j - k < 1){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 = 0;var bytes = 0;var input = [];rl.on('line', function (line) { // javascript每行数据的回调接口if(curLine === 0){bytes = parseInt(line.trim());if(bytes > 4){console.log(0);rl.close();}}else{input = line.trim().split(' ');for(var i = 0; i < bytes; i++){input[i] = parseInt(input[i]);}if(bytes == 1){if(input[0] > 127 || input[0] < 0){console.log(0);rl.close();}else{console.log(1);rl.close();}}else if(bytes > 1){var max = parseInt((new Array(bytes + 1)).join('1') + '0' + (new Array(8 - bytes)).join('1'), 2);var min = parseInt((new Array(bytes + 1)).join('1') + '0' + (new Array(8 - bytes)).join('0'), 2);// console.log(min, max);if(input[0] > max || input[0] < min){console.log(0);rl.close();}else{var max = 191;var min = 127;for(var i = 1; i < bytes; i++){if(input[i] > max || input[i] < min){console.log(0);rl.close();}}console.log(1);rl.close();}}}curLine++;});
5.抖音网红AC：反向建立有向图，逐个dfs，dfs返回路径等于人数，则计数加一
var Graph = (function () {function Graph(v) {this.vertices = v;this.edges = 0;this.adj = [];this.marked = [];for (var i = 0; i < this.vertices; i++) {this.adj[i] = [];this.marked[i] = false;}}Graph.prototype.addEdge = function (v, w) {this.adj[v].push(w);this.edges += 1;}// searchfunction _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 = 0; 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 = 0;var g;rl.on('line', function (line) {if (curLine === 0) {N = parseInt(line.trim());g = new Graph(N + 1);} else if (curLine === 1) {M = parseInt(line.trim());}else if(curLine === 2){var arr = line.trim().split(' ');for (var i = 0; i < M * 2; i+=2) {arr[i] = parseInt(arr[i]);arr[i + 1] = parseInt(arr[i + 1]);g.addEdge(arr[i + 1], arr[i]);}var cnt = 0;for (var i = 1; i <= N; i++) {var tmp = g.dfs(i);if(tmp.length === N){cnt++;}}console.log(cnt);rl.close();}curLine++;});
#字节跳动##笔试题目#
得物app公司福利 402人发布
投递荣耀等公司10个岗位
