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%案例
思路：想到DFS暴力，觉得不对，pass了，做问答题时想到了按模6分组，每组排序，回来想写，发现写不了，无语了，问答题也写不了，只能提前交卷
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整除的最大值对应的集合
其实应该用动态规划，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)); 
