8.20 网易互联网前端笔试
前言：
- 已经过去好几天了，本来没想着写笔试贴的，一来过去蛮久了，可能没啥价值了；二来还有问题没有解决，对大家没啥帮助，也不好意思发出来。但是今天京东笔试竟然遇到相似的题目了，觉得这些过去的笔试还是有点价值的；再者哪怕仅仅把自己的思路发出来，有感兴趣的伙伴集思广益，说不定就能解决了。
- 一共4道编程题，没有选择题。笔试了这么多家，就网易的前端和其他的考一样的题目。我感觉这四道题目很像。说不出来哪里像
- 做题前理清思路很重要，比如“长城数”那题，我先是想的“长城两块砖，而且数据只能增加，那最终结果就是取原数组中第一大和第二大的数字”，但是这样想是不对的，比如“30、100、5、70”虽然前两个大的数是100、70，但是最终结果是“30、100、30、100”。正确的思路是分别取奇、偶数项的最大值！
- 笔试中，首先要尝试发现规律，简化操作；但若发现不了，也要先尝试暴力解法，暴力的代码量往往比较少；暴力解法不能AC，且有时间，就用正常的解法如“dp、回溯……”。【时间很重要！】
编程：
1. 删除数位求是否能整除
思路：
- 遍历：假设a有n位，b有m位，如果用遍历的话，最多有种可能（Cn1 + …… + Cn(n-1)）*（Cm1 + …… + Cm(m-1)）种可能性
- 从“贪心”的角度来说，应该从删除位数少向删除位数多遍历
- 从题意来看，a、b至少得留一位，不能全删除了
/*
参数a、b是数组的形式，因为数组才好操作删除位数。不知道纯数字怎么删除某一位的
*/
console.log(getRes([1, 2, 3, 4], [9, 9])); // 2
console.log(getRes([1, 2, 3, 4], [9, 9,9,9,9])); // 1
function getRes(a, b) {
// 直接整除，不用操作
if(isBase(a, b)) {
return 0
} else {
let alen = a.length, blen = b.length, bmap = new Map(), result = Number.MAX_VALUE
for(let i = 0; i <= alen - 1; ++i) {
let res1 = removeNum(i, a);
for(let j = 0; j <= blen - 1; ++j) {
if(!bmap.has(j)) {
let res = removeNum(j, b);
bmap.set(j, res)
}
let res2 = bmap.get(j);
if(gotyou(res1, res2)) {
result = Math.min(result, i + j);
}
}
}
return result === Number.MAX_VALUE ? -1 : result;
}
}
function isBase(a, b) {
let num1 = parseInt(a.join(''))
let num2 = parseInt(b.join(""));
if (num1 === 0|| num2 === 0) return true;
return num1 % num2 === 0 || num2 % num1 === 0;
}
/*
j是要删除的位数；b是数组
返回删除j位数后数组的组合
*/
function removeNum(j, b) {
let res = [], currentList = [];
// 删除j位，等价于从b中取出b.length - j位。
// 也就是从b.length位中取b.length - j位的组合，但是不能破坏原有的顺序，如1234只能取出123来，却不能取出321来————这里可以参考力扣46题全排列，用回溯！
let targetCount = b.length - j, used = new Array(b.length).fill(false);
backTrack(currentList, b, used, 0);
return res
function backTrack(currentList, nums, used, start) {
if(currentList.length === targetCount) {
// console.log(currentList);
// 注意复杂数据类型的赋值，这里浅拷贝下！
res.push(currentList.slice(0));
return
}
for(let i = start; i < nums.length; ++i) {
if(used[i] === true) {
continue
} else if (nums.length - i + 1 < targetCount - currentList.length) {
// 这种情况下，往后取肯定不够targetCount位，就直接返回吧，不要往下了
return;
} else {
currentList.push(nums[i]);
used[targetCount] === true;
// 为了保证顺序，从i+1往后取
backTrack(currentList, nums, used, i + 1);
currentList.pop(nums[i]);
used[targetCount] === true;
}
}
}
}
// 删除了某一位后拿来这里比较下，看能不能整除
function gotyou(arr1, arr2) {
for(let num1 of arr1) {
for(let num2 of arr2) {
if (isBase(num1, num2)) {
return true;
}
}
}
return false
}
2. 长城数
思路：
- 分别找到奇、偶数项的最大值。如果最大值相同就短的加一，即如果一共是偶数个数，随便哪个加1，如果一共是奇数个数，那就偶数位加1——>所以都让偶数位加1就够了
- 今天京东笔试也考到了长城数，但是有点差别。
console.log(getNum([1,1,4,5,1,4])); // 11 function getNum(arr) { let oddMax = 0, evenMax = 0, res = 0; for(let i = 0; i < arr.length; ++i) { if(i % 2 === 0) { oddMax = Math.max(oddMax, arr[i]); } else { evenMax = Math.max(evenMax, arr[i]); } } if(oddMax === evenMax) { evenMax += 1; } for (let i = 0; i < arr.length; ++i) { if (i % 2 === 0) { res += (oddMax - arr[i]); } else { res += (evenMax - arr[i]); } } return res; }
3. 百年好“e”
思路：
- 题干里说了两个限制条件，在'好e'`最多`的情况下，需要修改的`最少`位数。而当字符串位数已知的时候，'好e'的个数是可以预先求出来的，如3位、4位字符，最多一个'好e'；5位字符，最多两个好e。
- 我想的是求出来'好e'的个数，就知道其组合了，然后和原来的字符串比较即可。但是我这里想错了，如'reddee'最多有两个'好e'，最终应该是'rederd'或者'deredr'，但是'redred'也是两个'好e'呀，情况还有很多种，所以此路不通
- 暂无思路，也没看到好的解法。
4. 三元组数
- 思路：当时时间紧迫，我就用了暴力解法，过了60%。思路是，遍历数组，当arr[i] === arr[j]时，看i, j中间有几个符合要求的数。
function getNum(arr) {
let sum = 0
for(let i = 0; i < arr.length - 1; ++i) {
for(let j = i + 1; j < arr.length; ++j) {
if(arr[j] === arr[i]) {
sum += getPart(i, j);
}
}
}
return sum
function getPart(i, j) {
let res1 = 0
for(let z = i + 1; z < j; ++z) {
if(arr[z] < arr[i]) {
res1++;
}
}
return res1
}
}
console.log(getNum([3, 1, 3, 4, 3, 4])); // 3
- 优化思路，上面确实存在重复计算的情况，如[3,1,2,3,1,3]，算arr[0] 和arr[5]之间的三元组数时，可以用 arr[0] 和 arr[3] 加上 arr[3] 和arr[5]之间的三元组数，而前者是算过的，那就用个备忘录memo去记录一下，也就是用空间换时间啦，可以降低时间复杂度。
function getNum(arr) {
let sum = 0, memo = [-1,-1,-1];
for (let i = 0; i < arr.length - 1; ++i) {
for (let j = i + 1; j < arr.length; ++j) {
if (arr[j] === arr[i]) {
sum += getPart(i, j);
}
}
}
return sum;
function getPart(i, j) {
console.log(i,j);
let res1 = 0;
if (memo[0] !== i) {
// 这种情况下就是备忘录没用
for (let z = i + 1; z < j; ++z) {
if (arr[z] < arr[i]) {
res1++;
}
}
} else {
// 备忘录起作用了
for (let z = memo[1] + 1; z < j; ++z) {
if (arr[z] < arr[i]) {
res1++;
}
}
res1 += memo[2]
}
// memo记录了起点和终点，以及这个中间符合要求的三元组数！
memo = [i, j, res1];
return res1;
}
}
console.log(getNum([3, 1 ,3 ,4 ,3, 4])); // 3 - 但是这个memo还不够，还是有重复计算的情况，再优化吧！
