科大讯飞秋招笔试

给定一个字母字符串，并给定操作次数 $k$ ，每次可以将该字符串中的一个字符进行大小写反转。求经过 $k$ 次操作之后最多有几个大写字母？

🔍 展开代码

1.js

const rl = require("readline").createInterface({ input: process.stdin });
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const [n, k] = inputs[0].split(" ").map(Number);
  const str = inputs[1];
  console.log(maxUppercase(n, k, str));
});

function maxUppercase(n, k, str) {
  let lowercaseCount = 0;
  for (let i = 0; i < n; i++) {
    if (str[i] >= "a" && str[i] <= "z") {
      lowercaseCount++;
    }
  }

  let uppercaseCount = n - lowercaseCount;

  // 贪心 优先将小写字母转换为大写字母
  const convert = Math.min(lowercaseCount, k);
  uppercaseCount += convert;
  k -= convert;

  // 有剩余次数
  // 剩下奇数次 大写 -1
  // 剩下偶数次 不影响结果
  if (k > 0 && k % 2 === 1) {
    uppercaseCount--;
  }
  return uppercaseCount;
}

给定一个数组，可以将这个数组分为左右两个子数组，对于左右两侧不重复数字，怎么分割能使两侧的规模和最大？

🔍 展开代码

2.js

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

function deal(n, arr) {
  if (n === 0) return 0;

  const leftCount = new Array(n).fill(0);
  const leftSet = new Set();

  const rightCount = new Array(n).fill(0);
  const rightSet = new Set();

  for (let i = 0; i < n; i++) {
    leftSet.add(arr[i]);
    leftCount[i] = leftSet.size;
  }
  for (let i = n - 1; i >= 0; i--) {
    rightSet.add(arr[i]);
    rightCount[i] = rightSet.size;
  }

  let max = 0;
  for (let i = 0; i < n; i++) {
    const current = leftCount[i] + (i + 1 < n ? rightCount[i + 1] : 0);
    max = Math.max(max, current);
  }
  return max;
}

有 n 个生命区间，每个区间用 [s, e] 表示（s 为开始时间，e 为结束时间）。现有 m 个查询，每个查询用 [left, right] 表示一个时间范围。对于每个查询，请需要统计有多少个生命区间完全落在查询范围内（即 s ≥ left 且 e ≤ right）。

🔍 展开代码

3.js

const rl = require("readline").createInterface({ input: process.stdin });
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  // 1. 解析输入数据
  const [n, m] = inputs[0].split(" ").map(Number);
  const lives = [];
  for (let i = 1; i <= n; i++) {
    const [s, e] = inputs[i].split(" ").map(Number);
    lives.push({ s, e });
  }
  const queries = [];
  for (let i = n + 1; i <= n + m; i++) {
    const [left, right] = inputs[i].split(" ").map(Number);
    queries.push({ left, right });
  }

  // 2. 预处理：按结束时间e分组，且每组的s排序（用于后续二分查找）
  // 动态计算最大结束时间，避免固定值浪费空间
  const maxE = lives.length ? Math.max(...lives.map((l) => l.e)) : 0;
  const eGroup = Array.from({ length: maxE + 2 }, () => []); // e的范围：0 ~ maxE +2防止越界
  for (const { s, e } of lives) {
    eGroup[e].push(s);
  }
  // 对每个e对应的s数组排序
  for (let e = 0; e <= maxE; e++) {
    eGroup[e].sort((a, b) => a - b);
  }

  // 3. 处理每个查询，直接输出结果
  for (const { left, right } of queries) {
    let count = 0;
    // 仅遍历结束时间≤right的分组（超过right的e无需考虑）
    const targetE = Math.min(right, maxE); // 避免超出eGroup的范围
    for (let e = 0; e <= targetE; e++) {
      const sList = eGroup[e];
      if (sList.length === 0) continue;

      // 二分查找：找到s≥left的元素个数（排序数组特性）
      let low = 0,
        high = sList.length;
      while (low < high) {
        const mid = (low + high) >> 1;
        if (sList[mid] >= left) {
          high = mid;
        } else {
          low = mid + 1;
        }
      }
      count += sList.length - low; // 大于等于left的元素数量
    }
    // 直接输出当前查询的结果（按输入顺序）
    console.log(count);
  }
});

科大讯飞秋招笔试 ​

科大讯飞秋招笔试