网易笔试 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));
  }
}

#网易笔试##网易##笔经#