华为OD机试真题 - 求满足条件的最长子 (D卷,100分)
题目描述
给定一个字符串,只包含字母和数字,按要求找出字符串中的最长(连续)子串的长度,字符串本身是其最长的子串,子串要求:
1、 只包含1个字母(a~z, A~Z),其余必须是数字;
2、 字母可以在子串中的任意位置;
如果找不到满足要求的子串,如全是字母或全是数字,则返回-1。
输入描述
字符串(只包含字母和数字)
输出描述
子串的长度
用例
题目解析
- 遍历字符串,记录当前连续的字母和数字的数量。
- 如果遇到一个字母,将字母计数器加1;如果遇到一个数字,将数字计数器加1。
- 如果字母计数器大于1,说明当前子串不满足条件,需要重新开始计算子串长度。
- 如果数字计数器为0,说明当前子串不满足条件,需要重新开始计算子串长度。
- 如果字母计数器为1且数字计数器大于0,说明当前子串满足条件,更新最长子串长度。
- 遍历结束后,返回最长子串长度。如果没有找到满足条件的子串,返回-1。
JS算法源码
const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on("line", (line) => { console.log(getResult(line)); }); function getResult(s) { let maxLen = -1; let l = 0, r = 0; const letterIdx = []; const isLetter = new Array(256).fill(false); for (let i = 'a'.charCodeAt(0); i <= 'z'.charCodeAt(0); i++) isLetter[i] = true; for (let i = 'A'.charCodeAt(0); i <= 'Z'.charCodeAt(0); i++) isLetter[i] = true; while (r < s.length) { if (isLetter[s.charCodeAt(r)]) { letterIdx.push(r); if (letterIdx.length > 1) { l = letterIdx.shift() + 1; } if (r == l) { r++; continue; } } maxLen = Math.max(maxLen, r - l + 1); r++; } return maxLen; }
Java算法源码
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(getResult(sc.next())); } private static int getResult(String str) { int maxLen = -1; boolean hasLetter = false; int l = 0, r = 0; while (r < str.length()) { char c = str.charAt(r); if (Character.isLetter(c)) { hasLetter = true; if (r > l) { l++; } else { r++; } } else {
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试题库D卷 文章被收录于专栏
2024年5-11月份考的D卷,不用再看AB卷,CD卷题目一样。多种语言解法,欢迎提供更好的解法。