往届刷题总结

计算机基础

存储一个 32 位的数据 0x9876521 到地址 4000h~4003h，小端方式存储，则 4000h 地址中存放的数据是 ( )。科大讯飞 24 秋招

0x09
0x87
0x65
0x21

以下代码的执行结果是：京东 24 秋招字符串拼接不相加

JavaScript

var obj = {"key":"1","value":"2"};
var newObj = obj;
newObj.value += obj.key;
alert(obj.value);

编程

对于一个序列的中位数判定，若是奇数长度的序列不解释，若是偶数长度的序列选择中间两个数字里的较小者。现给定一个序列，排序以后每次取出中位数，并从序列剔除该数得到一个新的序列，最后输出整个序列按照取中位数顺序得到的结果。科大讯飞 24 秋招超时

🔍 展开代码

1.js

// 暴力拆解中位数并做字符串拼接或者数组push会超时
const rl = require("readline").createInterface({ input: process.stdin });
const inputs = [];
rl.on("line", (line) => {
  inputs.push(line);
});
rl.on("close", () => {
  deal(inputs);
});

class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  update(i, delta) {
    while (i <= this.size) {
      this.tree[i] += delta;
      i += i & -i;
    }
  }

  query(i) {
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= i & -i;
    }
    return sum;
  }

  findKth(k) {
    let pos = 0;
    let bitMask = 1 << 20;
    while (bitMask > 0) {
      let nextPos = pos + bitMask;
      if (nextPos <= this.size && this.tree[nextPos] < k) {
        k -= this.tree[nextPos];
        pos = nextPos;
      }
      bitMask >>= 1;
    }
    return pos + 1;
  }
}

function deal(inputs) {
  const n = +inputs[0];
  const arr = inputs[1].split(" ").map(Number);

  const sortedUniqueArr = Array.from(new Set(arr)).sort((a, b) => a - b);
  const rankMap = new Map();
  sortedUniqueArr.forEach((value, index) => {
    rankMap.set(value, index + 1);
  });

  const ft = new FenwickTree(sortedUniqueArr.length);
  const res = [];
  let length = n;

  for (let v of arr) {
    ft.update(rankMap.get(v), 1);
  }

  while (length) {
    const k = length % 2 === 0 ? length / 2 : Math.floor(length / 2) + 1;
    const discreteVal = ft.findKth(k);
    const realVal = sortedUniqueArr[discreteVal - 1];
    res.push(realVal);
    ft.update(discreteVal, -1);
    length--;
  }
  console.log(res.join(" "));
}

解析可参考二叉索引树。

如图科大讯飞 24 秋招以为很难放弃实则暴力

🔍 展开代码

2.js

const rl = require("readline").createInterface({
  input: process.stdin,
});
const lines = [];
rl.on("line", (line) => lines.push(line.trim()));
rl.on("close", () => deal(lines));

function deal(inputs) {
  const n = +inputs[0];
  const cases = inputs.slice(1).map(Number);

  // 预处理所有不超过 1e9 的幂乘积格式的数字
  const powers = [];
  const LIMIT = 1e9;
  const seen = new Set();

  for (let x = 1; x <= LIMIT; x *= 2) {
    for (let y = x; y <= LIMIT; y *= 3) {
      if (!seen.has(y)) {
        seen.add(y);
        powers.push(y);
      }
    }
  }

  powers.sort((a, b) => a - b);

  for (let i = 0; i < n; i++) {
    let cur = cases[i];
    const result = [];
    for (const val of powers) {
      if (val <= cur) {
        result.push(val);
        cur -= val;
        if (cur === 0) break;
      }
    }
    console.log(result.length);
    console.log(result.join(" "));
  }
}

如图京东 24 秋招this 指向

🔍 展开代码

3.js

const rl = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", (line) => deal(line));

class Walk {
  constructor() {
    // 0 1 2 3 分别代表 上 左 下 右
    this.direction = 0;
    this.x = 0;
    this.y = 0;
    // this.choices = [
    //   function () { this.y++; },
    //   function () { this.x--; },
    //   function () { this.y--; },
    //   function () { this.x++; },
    // ];
    this.choices = [
      () => this.y++,
      () => this.x--,
      () => this.y--,
      () => this.x++,
    ];
  }

  do() {
    this.choices[this.direction]();
  }
  left() {
    this.direction = (this.direction + 1) % 4;
  }
  right() {
    this.direction = (this.direction + 3) % 4;
  }
  out() {
    console.log(`${this.x} ${this.y}`);
  }
}

function deal(str) {
  const main = new Walk();
  str.split("").forEach((s) => {
    if (s === "W") main.do();
    else if (s === "A") main.left();
    else if (s === "D") main.right();
  });
  main.out();
}

如图京东 24 秋招不难但脑子抽了

🔍 展开代码

4.js

const rl = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => deal(inputs));

function deal(inputs) {
  const [n, k] = inputs[0].split(" ").map(Number);
  const choices = inputs[1].split(" ").map(Number);

  let res = 0;
  const map = new Map();
  for (const num of choices) {
    map.set(num, 1 + map.get(num) || 1);
  }
  for (const num of choices) {
    res += map.get(k - num) || 0;
  }
  console.log(res);
}

如图京东 24 秋招区间化处理不只是输出最小值

🔍 展开代码

5.js

const rl = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => deal(inputs));

function deal(inputs) {
  const [_t, ...cases] = inputs;
  const t = +_t;
  for (let i = 0; i < t; i++) {
    const curCase = cases[i * 2 + 1].split(" ").map(Number);
    const length = +cases[i * 2];
    const dp = new Array(length).fill(0);

    // curCase -1 or /2 ===> [0,0,0,...,0] min times
    // odd -1 even /2
    for (let j = 0; j < length; j++) {
      let curNum = curCase[j];
      while (curNum) {
        curNum = curNum % 2 === 0 ? curNum / 2 : curNum - 1;
        dp[j]++;
      }
    }
    console.log(Math.min(...dp)); 
    let res = dp[0];
    for (let k = 1; k < dp.length; k++) {
      if (dp[k] > dp[k - 1]) {
        res += dp[k] - dp[k - 1];
      }
    }
    console.log(res);
  }
}

如图虾皮 24 秋招数组的预处理和双指针思想

🔍 展开代码

6.js

const rl = require("readline").createInterface({
  input: process.stdin,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => deal(inputs));

const preDeal = (s, flag = false) => {
  const a = s.split(" ").map(Number);
  const b = a
    .slice()
    .map((value, index) => [value, index])
    .sort((a, b) => a[0] - b[0]);
  return flag ? b : a;
};

function deal(inputs) {
  const [m, n, x] = preDeal(inputs[0]);
  const a = preDeal(inputs[1], true);
  const b = preDeal(inputs[2], true);

  let i = 0;
  let j = n - 1;

  let diff = Infinity;
  let pairs = [Infinity, Infinity];

  const flag = (localDiff, localX, localY) => {
    if (localDiff < diff) return true;
    if (localDiff === diff) {
      if (localX < pairs[0]) return true;
      if (localX === pairs[0] && localY < pairs[1]) return true;
    }
    return false;
  };

  while (i < m && j >= 0) {
    const sum = a[i][0] + b[j][0];
    const localDiff = Math.abs(sum - x);

    if (flag(localDiff, a[i][1], b[j][1])) {
      diff = localDiff;
      pairs = [a[i][1], b[j][1]];
    }

    if (sum < x) {
      i++;
    } else {
      j--;
    }
  }

  console.log(pairs.join(" "));
}

如图虾皮 24 秋招背包问题不熟练

🔍 展开代码

7.js

const rl = require("readline").createInterface({
  input: process.stdin,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => deal(inputs));

function deal(inputs) {
  const preDeal = (s) => s.split(" ").map(Number);
  const [v, length] = preDeal(inputs[0]);
  const arr = preDeal(inputs[1]);

  // dp[i] 体积为 i 能装多少
  const dp = new Array(v + 1).fill(0);
  // 遍历所有物品
  for (let i = 0; i < length; i++) {
    // 逆序遍历背包容量，防止一个物品被重复使用
    for (let j = v; j >= arr[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
    }
  }

  // 最终 dp[v] 就是最大能装的体积
  console.log(v - dp[v]);
}

给出一个仅由大写字母 A 和 B 构成的字符串 s，请你求出 s 中包含 A 和 B 个数相同的连续区间的最长长度。京东 2024 春招暴力双循环超时

🔍 展开代码

8.js

const rl = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  let diff = 0;
  let max = 0;
  const m = new Map();
  m.set(0, -1);

  for (let i = 0; i < line.length; i++) {
    diff = line[i] === "A" ? diff + 1 : diff - 1;
    if (!m.has(diff)) m.set(diff, i);
    else max = Math.max(max, i - m.get(diff));
  }
  console.log(max);
});

如图快手 2024 秋招注意递归和 memo 位置不写错

🔍 展开代码

9.js

const rl = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => deal(inputs));

function deal(inputs) {
  const [r, c] = inputs[0].split(" ").map(Number);
  const matrix = [];
  for (let i = 0; i < r; i++) {
    matrix.push(inputs[i + 1].split(" ").map(Number));
  }
  const memo = Array.from({ length: r }, () =>
    Array.from({ length: c }, () => 0),
  );
  // matrix 里找到最长路径
  // 从当前节点出发 找到升高的最长路径 dfs
  let max = -Infinity;
  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      const cur = dfs(matrix, i, j, memo);
      max = Math.max(cur, max);
    }
  }

  console.log(max);
}

function dfs(grid, x, y, memo) {
  const [r, c] = [grid.length, grid[0].length];
  if (x < 0 || y < 0 || x >= r || y >= c) return 0;
  if (memo[x][y]) return memo[x][y];
  let max_len = 1;

  const choices = [
    [x - 1, y],
    [x + 1, y],
    [x, y - 1],
    [x, y + 1],
  ];
  for (const [d1, d2] of choices) {
    if (d1 >= 0 && d1 < r && d2 >= 0 && d2 < c && grid[d1][d2] > grid[x][y]) {
      max_len = Math.max(max_len, 1 + dfs(grid, d1, d2, memo));
    }
  }

  memo[x][y] = max_len;

  return max_len;
}

如图滴滴 2024 秋招

🔍 展开代码

10.js

const rl = require("readline").createInterface({
  input: process.stdin,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const [n, m] = inputs[0].split(" ").map(Number);
  const cases = inputs.slice(1).map((c) => c.split(" ").map(Number));
  const result = deal(n, m, cases);
  console.log(result);
});

function deal(n, m, cases) {
  const min = new Array(m).fill(Infinity);
  min[0] = Math.min(...cases.map((c) => c[0]));
  for (let i = 1; i < m; i++) {
    for (const c of cases) {
      min[i] = Math.min(min[i], c[i] - c[i - 1]);
    }
  }
  const result = min.reduce((pre, cur) => pre + cur, 0);
  return result;
}

如图滴滴 2024 秋招

🔍 展开代码

11.js

const rl = require("readline").createInterface({
  input: process.stdin,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  let res = "";
  const times = +inputs[0];
  for (let i = 1; i <= times; i++) {
    const [n, m] = inputs[i].split(" ").map(Number);
    const _res = deal(n, m);
    res += `${_res} `;
  }
  console.log(res.trimEnd());
});

function deal(n, m) {
  if (n === 1) return 0;
  if (n === 2) return m;
  return 2 * m;
}

如图滴滴 2024 春招

🔍 展开代码

12.js

// 超时
const rl = require("readline").createInterface({
  input: process.stdin,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const [N, M] = inputs[0].split(" ").map(Number);
  const lefts = inputs[1].split(" ").map(Number);
  const rights = inputs[2].split(" ").map(Number);
  const times = +inputs[3];
  const queries = inputs[4].split(" ").map(Number);

  const result = deal(N, M, lefts, rights);
  const answer = [];
  for (let i = 0; i < times; i++) {
    const q = queries[i];
    answer.push(result[q]);
  }

  console.log(answer.join(" "));
});

function deal(n, m, lefts, rights) {
  const records = new Array(n + 1).fill(0);
  for (let i = 0; i < m; i++) {
    j = lefts[i];
    while (j <= rights[i]) {
      records[j++]++;
    }
  }
  return records;
}
// 优化
function deal(n, m, lefts, rights) {
  const records = new Array(n + 1).fill(0);

  // 差分数组更新区间
  for (let i = 0; i < m; i++) {
    const left = lefts[i];
    const right = rights[i];
    records[left]++; // 开始加一
    records[right + 1]--; // 结束减一
  }

  // 计算前缀和得到最终的记录数组
  for (let i = 1; i <= n; i++) {
    records[i] += records[i - 1];
  }

  // 记录数组存储了每个位置上的最终结果
  return records;
}

往届刷题总结 ​

计算机基础 ​

编程 ​

往届刷题总结

计算机基础

编程