小红书前端笔试9.19

题型：选择20 编程3

总体：题真的不难啊...我该说我太渣呢？还是JS太渣呢？好吧...归根到底就是我太渣
我感觉思路都没啥问题，但就是一题没A...我不懂了...跪求各位大佬赐教！

烦恼ing...

编程1：零件（55%）

const [a1, a2, a3, a4, x] = [1, 3, 3, 2, 5]
const matrix = [
    [4],
    [7, 7, 9],
    [6, 3, 5],
    [2, 8],
]

let res = [];
for (let item of matrix) {
    let temp = item.filter(v => v > x);
    res.push([...temp]);
}

console.log(res)
res = res.map(item => item.length ? item.length : 0);
console.log(Math.min(...res));

编程2：最小花费（82%）

思路：动态规划

const n = 5, k = 2;
const heights = [1, 5, 3, 4, 2];

// 思路动态规划
function fn2(n, k, heights) {
    // 传送规则： 高-低不花钱，低到高花钱=高度差
    let dp = new Array(n).fill(0);

    for (let m = 1; m < k; m++) {
        dp[m] = heights[m] > heights[0] ? heights[m] - heights[0] : 0;
    }

    for (let i = k; i < n; i++) {
        let temp = Infinity;
        for (let j = 1; j <= k; j++) {
            let c = heights[i] < heights[i-j] ? 0 : Math.abs(heights[i-j] - heights[i]);   // 高-低不额外收费
            temp = Math.min(temp, dp[i-j] + c)
        }
        dp[i] = temp;
    }

    return dp[n-1];
}

console.log(fn2(n, k, heights))

编程3：支配数（72%）

思路：滑动窗口

const n = 5, k = 2;
const nums = [1, 2, 1, 2, 3];

// 思路：滑动窗口
function fn3(n, k, nums) {
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i+k; j <= nums.length; j++) {
            let temp = nums.slice(i, j);
            if (helper(temp, k)) {
                res += (n-j+1);
                break;
            } else {
                continue;
            }
        }
    }

    return res;
} 

function helper(arr, k) {
    let m = new Map();
    for (let item of arr) {
        if (!m.has(item)) {
            m.set(item, 1);
        } else {
            if (m.get(item) === k-1) {
                return true;
            }
        }
    }

    return false;
}

console.log(fn3(n, k, nums))