当前位置：首页 > article >正文

牛客算法简单题（JS版）

article 2024/10/30 12:45:41

下面三个题做法一模一样：

HJ11 数字颠倒

HJ12 字符串反转

HJ106 字符逆序

解法：

定义一个结果值进行接收，反向遍历输入的字符串，拼接到结果字符串中即可。

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    while ((line = await readline())) {
        let input = line.split("");
        let reversed = "";

        for (let i = input.length - 1; i >= 0; i--) {
            reversed += input[i];
        }
        console.log(reversed);
    }
})();

HJ75 公共子串计算

解法一：

设 dp[i][j] 表示以 s1[i-1] 和 s2[j-1] 结尾的最长公共子串的长度。状态转移方程如下：

如果 s1[i-1] === s2[j-1]，则增加公共子串长度 dp[i][j] = dp[i-1][j-1] + 1。
如果不相等，则 dp[i][j] = 0。

最终结果就是 dp 数组中的最大值。

时间复杂度O(m*n)，空间复杂度O(m*n)

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    const s1 = await readline();
    const s2 = await readline();

    const dp = Array(s1.length + 1).fill(0).map(() => Array(s2.length + 1).fill(0));

    let maxLength = 0;

    for (let i = 1; i <= s1.length; i++) {
        for (let j = 1; j <= s2.length; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLength = Math.max(maxLength, dp[i][j]);
            } else {
                dp[i][j] = 0;
            }
        }
    }
    console.log(maxLength)
}()

解法二：

需要在每个长度 len 下，比较两个字符串中的所有子串。

设定滑动窗口的长度 len，从 1 到 min(s1.length, s2.length) 依次增大。
对每一个长度 len，从 s1 和 s2 中分别提取所有可能的子串。
对于 s1 的每一个子串，检查它是否存在于 s2 中。如果存在，更新最大公共子串长度。

时间复杂度O(n^3)，空间复杂度O(n)

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    const s1 = await readline();
    const s2 = await readline();

    let maxLength = 0;
    const minLen = Math.min(s1.length, s2.length);

    for (let len = 1; len <= minLen; len++) {
        let found = false;
        
        for (let i = 0; i <= s1.length - len; i++) {
            const subStr = s1.slice(i, i + len);

            if (s2.includes(subStr)) {
                maxLength = len;
                found = true;
            }
        }

        if (!found) break;
    }

    console.log(maxLength);
}();

HJ76 尼科彻斯定理

解法：

计算起始奇数：对于给定的整数 m，第一个奇数是 m^2 - m + 1；
输出 m 个连续奇数：从起始奇数开始，依次输出 m 个奇数。

因此对定义的res 只需要从第一个值按照 2n+1 的方式依次加 m 个值即可，并且在达到字符串最后一位之前，同时拼接 + 符号。

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    while(line = await readline()){
        let m = parseInt(line.trim());

        let first = m * m - m + 1;
        let res = '';

        for(let i = 0; i < m; i++) {
            res += (first + 2 * i) + (i === m - 1 ? '' : '+'); 
        }

        console.log(res);
    }
}()

HJ54 表达式求值

解法：

定义两个栈，一个用来存储数字，一个用来存储符号。
定义 + - * / 的运算优先级（明显 * / 大于 + -），接着定义这四种符号的运算方式。
首先判断括号，因为括号中的运算优先级最高，识别到左括号，就将该字符串直接放入符号栈。
其次识别右括号，因为要将括号中的都计算完，然后将左括号弹出栈，进行后续运算。
要判断负号有三种情况：
1. 第一个数就是负数，因此字符串[0]就是 -；
2. 在左括号后面紧跟 -，说明是在括号内存在负数；
3. 在 - 前面有其他运算符，说明是负数的运算；
其余的可以直接放入运算的方法进行运算即可（需要判断运算优先级）

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    const expression = await readline();
    console.log(evaluateExpression(expression));
}();

function evaluateExpression(expression) {
    const nums = [];  // 数字栈
    const ops = [];   // 操作符栈
    let i = 0;

    // 优先级定义
    const precedence = {
        '+': 1,
        '-': 1,
        '*': 2,
        '/': 2
    };

    // 运算函数
    const applyOperation = () => {
        const b = nums.pop();
        const a = nums.pop();
        const op = ops.pop();

        switch (op) {
            case '+': nums.push(a + b); break;
            case '-': nums.push(a - b); break;
            case '*': nums.push(a * b); break;
            case '/': nums.push(Math.trunc(a / b)); break; 
        }
    };

    while (i < expression.length) {
        const char = expression[i];

        if (char === '(') {
            ops.push(char);
        } else if (char === ')') {
            while (ops[ops.length - 1] !== '(') {
                applyOperation();
            }
            ops.pop(); // 弹出左括号
        } else if (char in precedence) {
            // 处理负号：检测是减法操作还是负数
            if (char === '-' && (i === 0 || expression[i - 1] === '(' || expression[i - 1] in precedence)) {
                // 解析负数
                let num = 0;
                i++;
                while (i < expression.length && !isNaN(expression[i])) {
                    num = num * 10 + Number(expression[i]);
                    i++;
                }
                nums.push(-num);
                i--; // 回退一位
            } else {
                while (
                    ops.length &&
                    ops[ops.length - 1] !== '(' &&
                    precedence[ops[ops.length - 1]] >= precedence[char]
                ) {
                    applyOperation();
                }
                ops.push(char);
            }
        } else if (!isNaN(char)) {
            let num = 0;
            while (i < expression.length && !isNaN(expression[i])) {
                num = num * 10 + Number(expression[i]);
                i++;
            }
            nums.push(num);
            i--; // 回退一位
        }
        i++;
    }

    // 计算剩余操作
    while (ops.length) {
        applyOperation();
    }

    return nums.pop();
}

HJ86 求最大连续bit数

解法：

将字符串转换为二进制，进行循环遍历，找到1就计数+1并更新最大值，碰到0就计数清0

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    const n = parseInt(await readline());
    const binaryStr = n.toString(2);

    let maxCount = 0;
    let currentCount = 0;

    for (let char of binaryStr) {
        if (char === "1") {
            currentCount++;
            maxCount = Math.max(maxCount, currentCount);
        } else {
            currentCount = 0;
        }
    }

    console.log(maxCount);
})();

查看全文

http://www.kler.cn/a/371559.html