2021京东前端笔试题目总结
总字数1.3K
阅读时长 ≈5 分钟
前言 🔗
太对了哥，哥实在是太对
两道编程题都做出来了，过不过不要紧，开心是真的开心
虫子爬井 🔗
这题理清思路的话还是没啥问题的，就是如果爬上去的时候已经高过井的高度了，那么直接算爬出井了，不用再休息滑下来了。
（答题前看了看系统的支持情况，es6及es6以上都是不支持的，所以全部都用var来定义）
javascript
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
javascript
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
javascript
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背包，也就是给出的东西，要么放进包里，要么不放进包里，
可以理解成部分背包每种物品只有一个的情况
javascript
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];
}完全背包 🔗
完全背包，也就是每件物品都不限制个数，只要总价值小于背包的价值
那么这件物品就可以无限放，就可以有更大的魅力值
可以理解成部分背包的物品有正无穷个的情况
javascript
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：
因为使用京东的题目来写，所以这里的价值就类似容量，而魅力值就对应原来的价值
上面的输入物品的数组的格式都是
javascript
[
[1, 2, 3], // 表示物品有1个，每个价值为2，每个魅力值的3
// ...
]后记 🔗
如果过了感觉面试还是会gg，哈哈哈哈
#JavaScript
#前端笔试题
哦呐该，如果没有评论的话，瓦达西...