百度春招实习笔试

2022-03-22

题目类型为20题选择题+3题编程题，选择题记不清了，编程题如下。

题目一

图片像素扩展，输入数据中，第一行有两个数，第一个数为N，表示矩阵的宽高，第二个数为K，表示每个像素点的扩展倍速，接下来的[1, N - 1]行，每行分别有N个数，即为输入数组，输出扩展后的数组。示例如下：

输入:
2 2 // N K
0 1 
1 0 // [[0, 1], [1, 0]]
预期输出:
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0

解题思路及个人代码：

思路：模拟扩展过程

代码：

let first = readline().split(' '); //acm模式需处理输入输出
let n = first[0], k = first[1];
let base = [];
for(let i = 0; i < n; i++) {
  base.push(readline().split(' '));
}

//此时的base即为力扣模式的输入数组[[0, 1], [1, 0]]
function extend(arr, n, k) {
  let res = [];
  for(let i = 0; i < n; i++) {
    let tmp = [];
    for(let j = 0; j < n; j++) {
      //一次性塞k个
      let times = k;
    	while(times > 0) {
        tmp.push(arr[i][j]);
        times--;
      }
    }
    let times = k;
    while(times > 0) {
      res.push(tmp);
      times--;
    }
  }
  return res;
}
//执行过程为:
// res: [], tmp: []
// res: [], tmp: [0, 0, 1, 1]
// res: [[0, 0, 1, 1], [0, 0, 1, 1]] ...

//处理输出
let res = extend(base, n, k); 
for(let i = 0; i < res.length; i++) {
  let str = "";
  for(let j = 0; j < res[i].length; j++) {
    str += res[i][j];
    if(j < res[i].length - 1) str += " ";
  }
  console.log(str);
}

题目二

输入数据为一个字符串，其中仅包含0或1，找出两个字串，使得这两个字串中1和0的数量相同且最大，字串可以部分重叠但不能完全相同，题目保证输入有解，请输出两个字串的开始位置和结束位置(字符串起始位置为1)。示例如下：

输入:
11011
预期输出:
1 4 2 5 //两个字串为[0, 3]和[1, 4]

解题思路及个人代码：

思路：滑动窗口，哈希表保存过程状态(结果还是timeout了，只能跑到84%的用例结束)

代码：

let str = readline();
function findsubstr(str, start, end) {
  let x = 0, y = 0;
  for(let i = start; i < end; i++) {
    if(Number(str[i]) === 0) x++;
    else y++;
  }
  return [x, y];
}
function find(str) {
  let sub = 1;
  let table = new Map();
  let rtable = new Map();
  while(sub < str.length) {
    const len = str.length - sub;
    for(let i = 0; i <= sub; i++) {
      let x, y;
      //只需计算第一个,即上例中的[0, 3],其他都可以通过第一个推出
      if(i === 0 && len === str.length - 1) {
        [x, y] = findsubstr(str, i, i + len);
      }
      //窗口左移
      else if(i - 1 >= 0 && rtable.has(`${i - 1},${i + len - 1}`)) {
        [x, y] = rtable.get(`${i - 1},${i + len - 1}`).split(',');
        if(Number(str[i - 1]) === 0) x--;
        else y--;
        if(Number(str[i + len]) === 0) x++;
        else y++;
      }
      //窗口左扩
      else if(i - 1 >= 0 && rtable.has(`${i - 1},${i + len}`)) {
        [x, y] = rtable.get(`${i - 1},${i + len}`).split(',');
        if(Number(str[i - 1]) === 0) x--;
        else y--;
      }
      //窗口右扩
      else if(i + len + 1 < str.length && rtable.has(`${i},${i + len + 1}`)) {
        [x, y] = rtable.get(`${i},${i + len + 1}`).split(',');
        if(Number(str[i + len + 1]) === 0) x--;
        else y--;
      } 
      let k = `${x},${y}`, v = `${i},${i + len}`
      if(table.has(k)) {
        return table.get(k) + "," + v;
      }
      else {
        table.set(k, v);
        rtable.set(v, k);
      }
    }
  }
}
let arr = find(str).split(",");
let res = "";
for(let i = 0; i < arr.length; i++) {
  res += arr[i];
  if(i < arr.length - 1) res += " ";
}
console.log(res);

题目三

小熊在道路上捡金币。输入数据中，第一行有两个数，第一个数为N，表示道路的长度(单位米)，第二个数为K，表示小熊的起始位置，第二行有N个数，分别表示每个位置上的金币数量。小熊每次可以移动1米或者不移动，在停留在某个格子时，每次捡起1金币，当某个位置金币为0时，小熊无法到达那个位置也无法跳过那个位置，小熊从起始位置出发时可以不捡起始位置的金币，求小熊最终可以获得最多的金币数量，要求小熊从起点K出发最终回到起点K。示例如下：

输入:
4 1
3 2 2 1
预期输出:
8 // 小熊行动路线: 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 1

解题思路及个人代码：

思路：动态规划(应该是吧)

代码：

let first = readline().split(" ");
let n = first[0], k = first[1] - 1;
let arr = readline().split(" ");
function count(n, k, arr) {
  // 当起始位置的金币数为0时,无法在离开当前位置后回到原位,即无法捡到金币
  if(arr[k] === 0) return 0;
  let left = arr[k], right = arr[k]; // 分别计算小熊从起始位置往左和往右走所能获得的金币
  for(let i = k; i < arr.length - 1;) {
    right += arr[i + 1];
    // 当下一个格子金币数为0或者1时跳出循环,否则该位置上的所有金币都可获得
    if(arr[i + 1] > 1) i++
    else break; 
  }
  for(let i = k; i > 0;) {
    left += arr[i - 1];
    // 同上
    if(arr[i - 1] > 1) i--;
    else break;
  }
  // 当起始位置的金币数为1时,只能经过起始位置一次,此时所能获得的最大金币为向左或向右拿到的金币中较大者
  if(arr[k] === 1) {
    return left > right ? left : right;
  }
  // 否则可以拿到所有向左或向右所能拿到的金币,起始位置被重复计算了所以需要减掉
  else {
    return left + right - arr[k];
  }
}
console.log(count(n, k, arr));