前端算法小白日刷三题10

今天的内容主要是复习 ，第一题会有点难，可以从后往前看，循序渐进

第一题先来做一下青训营的题目：括号匹配策略 

function solution(s) {
    const n = s.length;
    if (n % 2 !== 0) return -1; 
    const ls = ['()', '[]', '{}', '<>'];
    const f = Array.from({ length: n }, () => Array(n).fill(Number.MAX_VALUE));

    function value(cl, cr) {
        let k = 2; 
        for (const [dl, dr] of ls) {
            k = Math.min(k, (cl !== dl ? 1 : 0) + (cr !== dr ? 1 : 0)); 
        }
        return k;
    }

    
    for (let i = 0; i < n - 1; i++) {
        f[i][i + 1] = value(s[i], s[i + 1]);
    }

    
    for (let m = 4; m <= n; m += 2) {
        for (let l = 0; l <= n - m; l++) {
            let r = l + m - 1;
            f[l][r] = f[l + 1][r - 1] + value(s[l], s[r]);
            for (let k = l; k < r; k++) {
                f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r]); 
            }
        }
    }

    return f[0][n - 1]; 
}


console.log(solution("[(]}") === 2);  
console.log(solution("<{[]}>") === 0); 
console.log(solution("<>>{(})]") === 3); 

• 这题做的我真的要破防了，写了一个半小时，思路我就不说了，我是参考了别人的python代码改的，思路勉强理顺了，本来是下面的解法，但是一直显示错误

function solution(s) {
    const stack = [];
    let num = 0;
    const match = {
        '>': '<',
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (let item of s) {
        if (item === '<' || item === '(' || item === '[' || item === '{') {
            stack.push(item);
        } else {
            if (stack.length === 0) {
                num++; // 对应的左括号缺失
            } else {
                let end = stack.pop();
                if (match[item] !== end) {
                    num++; // 括号不匹配，需要修改
                }
            }
        }
    }

    // 返回栈中剩余的左括号和不匹配的括号总数
    return stack.length + num; 
}

function main() {
    console.log(solution("[()]") === 2); // 示例1
    console.log(solution("<<[]>>") === 0); // 示例2
    console.log(solution("<>{()}") === 3); // 示例3
}

main();

第二题还是青训营：组成字符串ku的最大次数

function solution(s) {
    // write code here
    s = s.toLowerCase();
    const map = new Map([['k', 0], ['u', 0]])
    for (let item of s) {
        if (map.has(item) && (item == 'k' || item == 'u')) {
            map.set(item, map.get(item) + 1)
        } 
    }
    return Math.min(map.get('k'), map.get('u'));
}

function main() {
    console.log(solution("AUBTMKAxfuu") === 1);
    console.log(solution("KKuuUuUuKKKKkkkkKK") === 6);
    console.log(solution("abcdefgh") === 0);
}

main();

•  这题里面比较巧妙的地方就是我先将字符串全部变成小写，这样子统计就方便很多
• 这题是关于哈希表的

最后一题双指针：最长的神奇序列

function solution(inp) {
    // Edit your code here
    let maxLength = 0;
    let maxStart = 0;
    let currentLength = 1;
    let currentStart = 0;

    for (let i = 1; i < inp.length; i++) {
        if (inp[i] !== inp[i - 1]) {
            currentLength++;
        } else {
            if (currentLength >= 3) {
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                    maxStart = currentStart;
                }
            }
            currentLength = 1;
            currentStart = i;
        }
    }

    // Check the last segment
    if (currentLength >= 3 && currentLength > maxLength) {
        maxLength = currentLength;
        maxStart = currentStart;
    }

    return inp.substring(maxStart, maxStart + maxLength);
}

function main() {
    // Add your test cases here
    console.log(solution("0101011101") === "010101");
    console.log(solution("1110101010000") === "10101010");
    console.log(solution("1010101010101010") === "1010101010101010");
}

main();

 非常开心哈，前几天就发现青训营可以提交js的代码了

今天就练习到这里啦