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

牛客算法简单题(JS版)

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

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 下,比较两个字符串中的所有子串。

  1. 设定滑动窗口的长度 len,从 1 到 min(s1.length, s2.length) 依次增大。
  2. 对每一个长度 len,从 s1s2 中分别提取所有可能的子串。
  3. 对于 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

相关文章:

  • Java 锁机制
  • [JAVAEE] 面试题(二) - CAS 和 原子类
  • 在数学中体验逻辑与创造的乐趣20241029
  • UI设计软件全景:13款工具助力创意实现
  • 【GPT模型的大小】GPT3模型到底多大,如果训练需要什么条件?
  • 美畅物联丨视频上云网关如何配置上级联网云平台
  • R语言在机器学习中的应用
  • unity中的材质(material)贴图(texture)着色器(shader)介绍
  • C++设计模式创建型模式———生成器模式
  • 【jvm】什么是TLAB
  • Ubuntu 22.04系统启动时自动运行ROS2节点
  • 【机器学习】Softmax 函数
  • GraphQL系列 - 第1讲 GraphQL语法入门
  • 计算机毕业设计——ssm基于HTML5的互动游戏新闻网站的设计与实现录像演示2021
  • R_机器学习——常用函数方法汇总
  • Java进阶篇设计模式之四 -----适配器模式和桥接模式
  • 会议录音转文字怎么转?有这6款视频语音转文字工具就够了!
  • 微信小程序时间弹窗——年月日时分
  • G2 基于生成对抗网络(GAN)人脸图像生成
  • Pytorch学习--神经网络--非线性激活
  • 【Unity基础】初识UI Toolkit - 运行时UI
  • 【项目复现】——DDoS-SDN Detection Project
  • Nginx + Lua + Redis:打造智能 IP 黑名单系统
  • 「Mac畅玩鸿蒙与硬件14」鸿蒙UI组件篇4 - Toggle 和 Checkbox 组件
  • Conditional DETR论文笔记
  • Java基础(4)之正则,异常与文件IO流