网易笔试 9.18 前端全A代码
1 这题的思路是遍历每个位,然后判断是否整除即可
const num = parseInt(readline()); let temp = num; let ret = 0; while (temp) { const e = temp % 10; if (num % e === 0) { ret += 1; } temp = Math.floor(temp / 10); } console.log(ret);
- 这题的思路是求前缀和,然后比较区间,选择距离 m 前缀和差最大的区间使用魔法键
const line = readline().split(' '); const s = line[0]; const m = parseInt(line[1]); const getLength = (s1, s2) => { const len1 = Math.abs(s1.charCodeAt(0) - s2.charCodeAt(0)); const len2 = Math.abs(26 + s1.charCodeAt(0) - s2.charCodeAt(0)); const len3 = Math.abs(26 + s2.charCodeAt(0) - s1.charCodeAt(0)); return Math.min(len1, len2, len3); } const dp = new Array(1e6 + 10); dp[0] = 0; for (let i = 1; i < s.length; i += 1) { dp[i] = dp[i - 1] + getLength(s[i], s[i - 1]); } const value = dp[s.length - 1]; let diff = 0; for (let i = m; i < s.length; i += 1) { if (dp[i] - dp[i - m] > m) { diff = Math.max(dp[i] - dp[i - m] - m, diff); } } console.log(value - diff + s.length);
3 这题因为题目说到可以是 全部 2^n 加 或者一个大 2^n 的减很多小的 2^n
即 num = 2^x1 + 2^x2 + 2^x3 + ... + 2^xn
或 num = 2^x1 - 2^x2 - 2^x3 - ... - 2^xn
我们发现等式二可以改写成 num = 2^x1 - (2^x2 + 2^x3 + ... + 2^xn)
因此
例如对 11100 这个二进制数字
其实可以看成 num = 2^2 + 2^3 + 2^4 其实就是求原先二进制的1的数量
也可以看成 num = 2^6 - (2^x2 + 2^x3 + ... + 2^xn)
移项,变成 (2^x2 + 2^x3 + ... + 2^xn) = 2^6 - num
因此变成了求左边这个二进制数的 1 的数量
const getCount = (num) => { let oneCount = 0; let zeroCount = 0; while (num) { if (num % 2 === 1) { oneCount += 1; } else { zeroCount += 1; } num = Math.floor(num / 2); } return [zeroCount, oneCount]; }; const num = parseInt(readline()); const [zero, v1] = getCount(num); const count = Math.pow(2, zero + v1); const [_, v2] = getCount(count - num); console.log(num === 0 ? -1 : Math.min(v1, v2 + 1));
4 这题是 dijsktra 模板题,因为 js 没提供优先队列,所以自己实现了一个
class Target { constructor(v, i, j) { this.v = v; this.i = i; this.j = j; } } class Heap { constructor(cmp) { this.cmp = cmp; this.data = []; } add(value) { this.data.push(value); this.siftUp(this.data.length - 1); } size() { return this.data.length; } empty() { return this.data.length === 0; } top() { return this.data[0]; } pop() { this.swap(0, this.data.length - 1); const value = this.data.pop(); this.siftDown(0); return value; } leftChild(index) { return index * 2 + 1; } rightChild(index) { return this.leftChild(index) + 1; } swap(index1, index2) { [this.data[index1], this.data[index2]] = [ this.data[index2], this.data[index1], ]; } parent(index) { return Math.floor((index - 1) / 2); } siftUp(index) { while ( this.parent(index) >= 0 && this.cmp(this.data[this.parent(index)], this.data[index]) < 0 ) { this.swap(index, this.parent(index)); index = this.parent(index); } } siftDown(index) { while (this.leftChild(index) < this.data.length) { const leftChildIndex = this.leftChild(index); const rightChildIndex = this.rightChild(index); let swapIndex = leftChildIndex; if ( rightChildIndex < this.data.length && this.cmp(this.data[rightChildIndex], this.data[leftChildIndex]) > 0 ) { swapIndex = rightChildIndex; } if (this.cmp(this.data[index], this.data[swapIndex]) > 0) { break; } this.swap(index, swapIndex); index = swapIndex; } } } const heap = new Heap((v1, v2) => v2.v - v1.v); const nums = readline().split(' ').map(v => parseInt(v)); const n = nums[0]; const [a, b] = [nums[1], nums[2]]; const lines = []; for (let i = 0; i < n; i += 1) { lines.push(readline()); } const graph = lines.map((line) => { return [...line]; }); const isHere = new Array(1e3 + 10); for (let i = 0; i < isHere.length; i += 1) { isHere[i] = new Array(1e3 + 10).fill(false); } let isFirst = true; let temp = -1; const MOD = 1e3 + 10; const map = new Map(); for (let i = 0; i < graph.length; i += 1) { for (let j = 0; j < graph[0].length; j += 1) { if (graph[i][j] === "*") { if (isFirst) { temp = i * MOD + j; } else { map.set(temp, i * MOD + j); map.set(i * MOD + j, temp); } isFirst = false; } } } heap.add(new Target(0, 0, 0)); isHere[0][0] = true; if (map.has(0)) { const pos = map.get(0); const x = Math.floor(pos / MOD); const y = pos % MOD; map.clear(); heap.add(new Target(0 + b, x, y)); } const dx = [1, 0, -1, 0]; const dy = [0, 1, 0, -1]; const getValue = (ch) => { if (ch === ".") return 0; if (ch === "#") return a; if (ch === "*") return 0; }; while (!heap.empty()) { const { i, j, v } = heap.pop(); if (i === n - 1 && j === n - 1) { console.log(v); break; } for (let k = 0; k < 4; k += 1) { const newX = i + dx[k]; const newY = j + dy[k]; if (newX < 0 || newX >= n) continue; if (newY < 0 || newY >= n) continue; if (isHere[newX][newY]) continue; isHere[newX][newY] = true; const ch = graph[newX][newY]; const value = newX * MOD + newY; if (map.has(value)) { const pos = map.get(value); const x = Math.floor(pos / MOD); const y = pos % MOD; map.clear(); heap.add(new Target(v + b, x, y)); } heap.add(new Target(v + getValue(ch), newX, newY)); } }#网易笔试##网易##笔经#