牛客算法简单题（JS版）

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

HJ11 数字颠倒

HJ12 字符串反转

HJ106 字符逆序

解法：

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

javascript">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)

javascript">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)

javascript">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 个值即可，并且在达到字符串最后一位之前，同时拼接 + 符号。

javascript">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. 在 - 前面有其他运算符，说明是负数的运算；
其余的可以直接放入运算的方法进行运算即可（需要判断运算优先级）

javascript">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

javascript">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);
})();