8月25日 奇安信前端工程师笔试
1.计算城市通路数目 DFS
判断从城市0到城市4有多少条路可以通
0和4城市之间的网络拓扑是有向无环图，计算0到4有多少条路可以走
function DagPathNum(nodes) {
// write code here
let n = nodes.length;
let map = Array.from(new Array(n), () => new Array(n).fill(false));
for (let i = 0; i < nodes.length; i++) {
for (let j = 0; j < nodes[i].length; j++) {
map[i][nodes[i][j]] = true;
}
}
console.log(map);
let count = 0;
function fun(i) {
console.log("i:", i);
if (i == n - 1) count++;
for (let j = 0; j < n; j++) {
if (map[i][j]) {
fun(j);
}
}
}
fun(0)
return count;
} 2. 查找直角坐标系内的两个点使他们与x轴围成的长方形面积最大 （暴力）
给定一个无符号整数数组，每个元素表示一个点，数组元素的索引作为直角坐标系的x坐标，元素作为y坐标,任意两个点:
x轴方向的距离作为长方形的长，y轴方向的最小值作为长方形的宽，找到两个点使长方形面积最大，输出面积。
例如 [4,1,2,7]代表4个点(0,4),(1,1),(2,2),(3,7),点(0,4),(1,1)表示的长方形：
长=(1-0),宽=min(4,1),面积=长*宽=1
function cfx(node) {
node = node.replace("[", "").replace("]", "").split(",");
let nums = [], max = 0;
for (let i = 0; i < node.length; i++) {
nums.push({
x: i,
y: parseInt(node[i])
})
}
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
let c = nums[j].x - nums[i].x;
let w = getMin(nums[i].y, nums[j].y);
max = Math.max(max, c * w)
}
}
function getMin(a, b) {
return a < b ? a : b;
}
return max
}
