下面三个题做法一模一样:
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 表达式求值
解法:
- 定义两个栈,一个用来存储数字,一个用来存储符号。
- 定义 + - * / 的运算优先级(明显 * / 大于 + -),接着定义这四种符号的运算方式。
- 首先判断括号,因为括号中的运算优先级最高,识别到左括号,就将该字符串直接放入符号栈。
- 其次识别右括号,因为要将括号中的都计算完,然后将左括号弹出栈,进行后续运算。
- 要判断负号有三种情况:
- 第一个数就是负数,因此字符串[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 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);
})();