得物秋招笔试

有一个迷宫，共有 $n$ 层，其中 $n >= 1$ ，每层都有 $n$ 个房间，每个房间里都有一定数量的金币。从第一层走到最后一层，最多能获得几个金币？约束条件如下：每一层的房间只能向右或者向下走，没有向上或者向左的回头路，同时不能斜向行走。最后一层的房间只能向下走，不能向左右或者上方走。动态规划

🔍 展开代码

1.js

const inputs = [];
while ((line = read_line()) !== "") {
  inputs.push(line);
}

const n = +inputs[0];
const coins = inputs.slice(1).map((line) => line.split(" ").map(Number));

// 对于一个n层房间应该计算0~n-2层的dp
// 最后一层只能由上面的房间向下走一步
const dp = Array.from({ length: n - 1 }, (_, index) =>
  Array.from({ length: index + 1 }, () => coins[0][0]),
);

for (let i = 1; i < n - 1; i++) {
  for (let j = 0; j < i + 1; j++) {
    const right = dp[i][j - 1] || 0;
    const down = dp[i - 1][j] || 0;
    dp[i][j] = Math.max(right, down) + coins[i][j];
  }
}

const resultDp = dp[n - 2].map(
  (beforeCoins, index) => beforeCoins + coins[n - 1][index],
);
const result = Math.max(...resultDp);
console.log(result);

总共有三行输入，经过这三行输入你可以构造出一棵树。第一行输入一个整数，代表节点的个数 $n$ ；第二行输入 $n$ 个整数，代表每个节点的颜色，其中 $1$ 对应红色， $0$ 对应蓝色；第三行输入 $n$ 个整数，代表每个节点的父节点编号，其中 $0$ 代表根节点。现在给出定义如下：对于红色节点，如果没有子节点或者子节点都是蓝色，则该节点是目标节点；对于蓝色节点，如果没有子节点或者子节点中至少一个节点是红色，则该节点是目标节点。请输出两种颜色节点各自是目标节点的个数。82% 用例应该是边界问题，反正 GPT 也没想到

🔍 展开代码

2.js

const inputs = [];
while ((line = read_line()) !== "") {
  inputs.push(line);
}

const nodesCount = +inputs[0];
const colorInfo = inputs[1].split(" ").map(Number);
const parentInfo = inputs[2].split(" ").map(Number);

class TreeNode {
  constructor(color, id) {
    this.color = color;
    this.id = id;
    this.children = [];
  }

  addChild(childIndex) {
    this.children.push(childIndex);
  }

  output() {
    console.log(this.color, this.children.length, this.id);
  }
}

const tree = [];

for (let i = 0; i < nodesCount; i++) {
  const color = colorInfo[i] ? "red" : "blue";
  const id = i + 1;
  const currentNode = new TreeNode(color, id);
  tree.push(currentNode);
}

for (let i = 0; i < nodesCount; i++) {
  const currentParentId = parentInfo[i];
  if (currentParentId) {
    const parentNode = tree.find((node) => node.id === currentParentId);
    parentNode.addChild(i + 1);
  }
}

let redCount = 0;
let blueCount = 0;
tree.forEach((node) => {
  if (node.color === "red") {
    const flag =
      node.children.length === 0 ||
      node.children.every((child) => tree[child - 1].color === "blue");
    if (flag) redCount++;
  } else {
    const flag =
      node.children.length === 0 ||
      node.children.some((child) => tree[child - 1].color === "red");
    if (flag) blueCount++;
  }
});

console.log(blueCount, redCount);

给定三行输入，第一行输入数组长度 $n$ ，余下两行代表两个数组 $A$ 和 $B$ ，长度均为 $n$ 。现在提供一个栈 C 和两种操作，操作一从 $A$ 中弹出下标最小的元素并压入栈 C，操作二读取栈 C 的栈顶元素 $x$ 以及当前栈容量 $i$ ，当前收益可计算为 $x * b_{i}$ ，然后将 $x$ 从栈 C 中弹出。直到数组 $A$ 为空，每一步收益的和可以表示为当前操作方案的收益。最后，请输出所有操作方案的收益总和。略显暴力但能通过

🔍 展开代码

3.js

const inputs = [];
while ((line = read_line()) !== "") {
  inputs.push(line);
}

const len = +inputs[0];
const [A, B] = inputs.slice(1).map((line) => line.split(" ").map(Number));

// len === 2： 0011 0101
// 0 是左括号 1 是右括号的有效对
const compos = [];

function gen(size, res) {
  function dfs(current, left, right) {
    if (current.length === 2 * size) {
      res.push(current);
      return;
    }
    if (left < size) dfs(current + "0", left + 1, right);
    if (right < left) dfs(current + "1", left, right + 1);
  }
  dfs("", 0, 0);
}

gen(len, compos);

const stack = [];

function into(origin) {
  const target = origin.shift();
  stack.push(target);
}

function out() {
  const stackSize = stack.length;
  const num1 = B[stackSize - 1];
  const num2 = stack.pop();
  return num1 * num2;
}
let result = 0;
for (const c of compos) {
  let localRes = 0;
  let origin = A.slice();
  for (const s of c) {
    if (s === "0") {
      into(origin);
    } else {
      localRes += out();
    }
  }
  result += localRes;
}

console.log(result);

得物秋招笔试 ​

得物秋招笔试