2021京东前端笔试题目总结

发表于 更新于 分类于

前言

太对了哥，哥实在是太对

两道编程题都做出来了，过不过不要紧，开心是真的开心

虫子爬井

这题理清思路的话还是没啥问题的，就是如果爬上去的时候已经高过井的高度了，那么直接算爬出井了，不用再休息滑下来了。

（答题前看了看系统的支持情况，es6及es6以上都是不支持的，所以全部都用var来定义）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function fn(n, m) {
  // m输入的是米，所以要转成厘米
  m = m * 100;
  // 使用的天数
  var day = 0;
  // 当前爬的高度
  var cur = 0;
  // 当前累计降低的高度
  var down = 0;
  while (cur < m) {
    // 高度累加
    cur += n;
    // 天数累加
    day++;
    // 爬的时候已经高于或等于井的高度了，直接返回天数
    if (cur >= m) {
      return day;
    }
    // 计算这一次休息下降的高度
    down += n / Math.pow(2, day);
    // 减掉这次下降的高度
    cur -= down;
  }
  return day;
}

背包问题

这个其实我忘的差不多了，但是最后还是凭借着自己的理解做出来了，还是相当的开心的，虽然在别人眼里就是流水账一样的写…

背包问题就是填一个表格的问题，23333

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function fn(n, p, items) {
  var dp = [];
  // 多少行，也就是多少个物品
  for (var i = 0; i < items.length + 1; i++) {
    dp[i] = [];
  }
  // 多少列，也就是有多少个价值
  for (var i = 0; i < items.length + 1; i++) {
    for (var j = 0; j < p + 1; j++) {
      dp[i][j] = 0;
    }
  }
  for (var i = 1; i < items.length + 1; i++) {
    for (var j = 1; j < p + 1; j++) {
      if (items[i - 1][1] <= j) {
        // 如果物品的价值小于当前的最大价值，才进入
        // 计算最多能放多少个
        var c = parseInt(j / items[i - 1][1] + '');
        // 要和它本身的数量比较，取最小
        var len = Math.min(c, items[i - 1][0]);
        // 遍历每一个，比如0个，1个，直到len个
        for (var l = 0; l <= len; l++) {
          // 状态转移
          dp[i][j] = Math.max(dp[i - 1][j - l * items[i - 1][1]] + l * items[i - 1][2], dp[i][j]);
        }
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][p];
}

这个代码还是可以进行空间上的优化的，使用一维数组来保存dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function fn(n, p, items) {
  var dp = [];
  for (var j = 0; j < p + 1; j++) {
    dp[j] = 0;
  }
  for (var i = 1; i < items.length + 1; i++) {
    // 从后往前遍历，因为从二维数组的版本来看
    // 我们需要上一层价值的数据
    // 如果从前往后，新的值会覆盖掉原来的值，导致不能计算正确
    for (var j = p; j >= 1; j--) {
      // 这里的计算和二位的基本一样
      if (items[i - 1][1] <= j) {
        var c = parseInt(j / items[i - 1][1] + '');
        var len = Math.min(c, items[i - 1][0]);
        for (var l = 0; l <= len; l++) {
          dp[j] = Math.max(dp[j - l * items[i - 1][1]] + l * items[i - 1][2], dp[j]);
        }
      }
    }
  }
  return dp[p];
}

除了这种部分背包问题，还有

  • 01背包
  • 完全背包

背包问题基本都是一个解体的思路

01背包

01背包，也就是给出的东西，要么放进包里，要么不放进包里，

可以理解成部分背包每种物品只有一个的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function fn2(n, p, items) {
  var dp = [];
  // 多少行，也就是多少个物品
  for (var i = 0; i < items.length + 1; i++) {
    dp[i] = [];
  }
  // 多少列，也就是有多少个价值
  for (var i = 0; i < items.length + 1; i++) {
    for (var j = 0; j < p + 1; j++) {
      dp[i][j] = 0;
    }
  }
  for (var i = 1; i < items.length + 1; i++) {
    for (var j = 1; j < p + 1; j++) {
      // 这里已经不需要计算多少个了，只有一个，要么放入，要么不放
      if (items[i - 1][1] <= j) {
        // 状态转移
        // dp[i - 1][j - items[i - 1][1]] + items[i - 1][2] 表示把这件物品放入的魅力值
        // dp[i - 1][j] 表示不放入这件物品的魅力值
        dp[i][j] = Math.max(dp[i - 1][j - items[i - 1][1]] + items[i - 1][2], dp[i - 1][j]);
      } else {
        // 如果这件物品的价值已经比当前的价值j要大，那么肯定是放不进的
        // 直接写入放入i-1物品价值为j的最大魅力值的数据即可
        // 如果没这个判断那么会产生计算的错误
        // 在上个if中 [j - item[i - 1][1]] 会产生负数索引
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][p];
}

完全背包

完全背包，也就是每件物品都不限制个数，只要总价值小于背包的价值

那么这件物品就可以无限放，就可以有更大的魅力值

可以理解成部分背包的物品有正无穷个的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function fn(n, p, items) {
  var dp = [];
  // 多少行，也就是多少个物品
  for (var i = 0; i < items.length + 1; i++) {
    dp[i] = [];
  }
  // 多少列，也就是有多少个价值
  for (var i = 0; i < items.length + 1; i++) {
    for (var j = 0; j < p + 1; j++) {
      dp[i][j] = 0;
    }
  }
  for (var i = 1; i < items.length + 1; i++) {
    for (var j = 1; j < p + 1; j++) {
      if (items[i - 1][1] <= j) {
        // 如果物品的价值小于当前的最大价值，才进入
        // 理论上可以有无数个，但是物品有价值，个数产生的价值不能超过背包的价值，超过了没有意义
        // 计算最多能放多少个
        var c = parseInt(j / items[i - 1][1] + '');
        // 遍历每一个，比如0个，1个，直到len个
        for (var l = 0; l <= c; l++) {
          dp[i][j] = Math.max(dp[i - 1][j - l * items[i - 1][1]] + l * items[i - 1][2], dp[i][j]);
        }
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][p];
}

Tips：

因为使用京东的题目来写，所以这里的价值就类似容量，而魅力值就对应原来的价值

上面的输入物品的数组的格式都是

1
2
3
4
[
  [1, 2, 3], // 表示物品有1个，每个价值为2，每个魅力值的3
  // ... 
]

后记

如果过了感觉面试还是会gg，哈哈哈哈