首页 > 3.27网易实习笔试(前端)
头像
Red_Ferrari
编辑于 2021-04-17 11:10
+ 关注

3.27网易实习笔试(前端)

只讲编程题,意向前端,我用的javascript
第1题,一组数据,判断能组成三角形最多的数,如果有多个,都写下来
思路,从小到大排序,三重循环暴力,通过70%案例
let n = parseInt(readline());
let arr = readline().split(' ').map((a) => parseInt(a)).sort((a, b) => a - b);
let canComTri = new Array(n).fill(0);
for (let i = 0; i < n - 2; i++) {
    for (let j = i + 1; j < n - 1; j++) {
        for (let k = j + 1; k < n; k++) {
            if (arr[k] < arr[i] + arr[j]) {
                canComTri[i]++;
                canComTri[j]++;
                canComTri[k]++;
            } else {
                break;
            }
        } 
    }
}
let res = [];
let max = Math.max(...canComTri);
for (let i = 0; i < n; i++) {
    if (canComTri[i] === max) res.push(arr[i]);
}
console.log(res.join(' '))
优化方案更新,两次三重循环,三重循环优化后时间复杂度由O(N^3)降为O(N^2),第3重循环的数k与第2重j相关,因此降低了时间复杂度


let n = parseInt(readline());
let arr = readline()
  .split(" ")
  .map((a) => parseInt(a))
  .sort((a, b) => a - b);
let canComTri = new Array(n).fill(0);
for (let i = 0; i < n - 2; i++) {
  let k = i + 2;
  for (let j = i + 1; j < n - 1; j++) {
    for (k = k > j ? k : j + 1; k < n && arr[k] < arr[i] + arr[j]; k++) {}
    canComTri[i] += k - j - 1;
    canComTri[j] += k - j - 1;
  }
}

for (let i = n - 1; i >= 2; i--) {
  let k = i - 2;
  for (let j = i - 1; j >= 1; j--) {
    for (k = k < j ? k : j - 1; k >= 0 && arr[i] < arr[j] + arr[k]; k--) {}
    canComTri[i] += k - j - 1;
  }
}
let res = [];
let max = Math.max(...canComTri);
for (let i = 0; i < n; i++) {
  if (canComTri[i] === max) res.push(arr[i]);
}
console.log(res.join(" "));
第2题,给你一个二叉树,实现固定值和的路径,优先层数低的,排在左边的


思路:BFS,由于输入是数组,进行字符串切割,进行BFS遍历各点的和,和为想要的固定值,倒推路径,通过70%案例
let arr = readline().split('[')[1].split(']')[0].split(',').map((a) => parseInt(a));
const sum = parseInt(readline());
const n = arr.length;
let index;
let res = [...arr];
for (let i = 1; i < n; i++) {
    if (isNaN(res[i])) {
        continue;
    } else {
        res[i] += res[((i - 1) >> 1)];
        if (res[i] === sum) {
            index = i;
            break;
        }
    }
}
if (index) {
    let path = [arr[index]];
    while (index) {
        index = ((index - 1) >> 1);
        path.unshift(arr[index]);
    }
    console.log('[' + path.join(',') + ']');
} else {
    console.log([]);
}
优化方案
let arr = readline().split('[')[1].split(']')[0].split(',').map((a) => parseInt(a));
const sum = parseInt(readline());
const n = arr.length;
let index;
let res = [...arr];
let queue = [];
if (!isNaN(res[0])) {
    queue.push(0);
}
while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
        let cur = queue.shift();
        if (!isNaN(res[cur * 2 + 1])) {
            queue.push(cur * 2 + 1);
            res[cur * 2 + 1] += res[cur];
            if (res[cur * 2 + 1] === sum) {
                index = cur * 2 + 1;
                break;
            }
        }
        if (!isNaN(res[cur * 2 + 2])) {
            queue.push(cur * 2 + 2);
            res[cur * 2 + 2] += res[cur];
            if (res[cur * 2 + 2] === sum) {
                index = cur * 2 + 2;
                break;
            }
        }
    }
    if (index) break;
}
if (index) {
    let path = [arr[index]];
    while (index) {
        index = ((index - 1) >> 1);
        path.unshift(arr[index]);
    }
    console.log('[' + path.join(',') + ']');
} else {
    console.log([]);
}
第3题,一组数据,找出能组成和被6整除的最大值对应的集合
思路:想到DFS暴力,觉得不对,pass了,做问答题时想到了按模6分组,每组排序,回来想写,发现写不了,无语了,问答题也写不了,只能提前交卷
其实应该用动态规划,dp[i][n]表示前i个数模6余n的最大值,先求出最大和再经过反向遍历求出该集合

第4题,编辑距离变种,定义了编辑距离和两组字符串长度的比值,参考 https://leetcode-cn.com/problems/edit-distance/ ,只不过增删距离为1,改距离为2
思路:动态规划,dp[i][j]为字符串前i个字符子串到字符串前j个字符子串的编辑距离,可以压缩空间,笔试就不装逼了,面试被问到的话打算写好后口述优化思路,终于A了1道,感觉自己好菜
let str0Arr = readline().split('');
let str1Arr = readline().split('');
const len0 = str0Arr.length;
const len1 = str1Arr.length;
const dp = new Array(len0 + 1);
dp[0] = new Array(len1 + 1);
for (let j = 0; j <= len1; j++) {
    dp[0][j] = j;
}
for (let i = 1; i <= len0; i++) {
    dp[i] = new Array(len1 + 1).fill(Number.MAX_SAFE_INTEGER);
    dp[i][0] = i;
}
for (let i = 1; i <= len0; i++) {
    for (let j = 1; j <= len1; j++) {
        if (str0Arr[i - 1] === str1Arr[j - 1]) {
            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
        } else {
            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
        }
    }
}
let sim = (len0 + len1 - dp[len0][len1]) / (len0 + len1);
console.log(sim.toFixed(2));

优化空间,从O(MN)降至O(N)
let str0Arr = readline().split('');
let str1Arr = readline().split('');
const len0 = str0Arr.length;
const len1 = str1Arr.length;
// const dp = new Array(len0 + 1);
// dp[0] = new Array(len1 + 1);
const dp = new Array(len1 + 1);
for (let j = 0; j <= len1; j++) {
    // dp[0][j] = j;
    dp[j] = j;
}
// for (let i = 1; i <= len0; i++) {
//     dp[i] = new Array(len1 + 1).fill(Number.MAX_SAFE_INTEGER);
//     dp[i][0] = i;
// }
for (let i = 1; i <= len0; i++) {
    let pre = dp[0];
    dp[0] = i;
    for (let j = 1; j <= len1; j++) {
        let temp = dp[j];
        if (str0Arr[i - 1] === str1Arr[j - 1]) {
            // dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            dp[j] = Math.min(pre, dp[j] + 1, dp[j - 1] + 1);
        } else {
            // dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            dp[j] = Math.min(dp[j] + 1, dp[j - 1] + 1);
        }
        pre = temp;
    }
}
let sim = (len0 + len1 - dp[len1]) / (len0 + len1);
console.log(sim.toFixed(2));

自己水平有限,希望对大家有用。
前两题已更新优化方案,求大佬们指点。

全部评论

(4) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐