解题思路
这是一个字符串处理问题。需要找出字符串中最长的连续数字子串。
关键点:
- 识别连续的数字字符
- 记录最长数字串的位置和长度
- 处理多个相同长度的情况
- 考虑边界情况
算法步骤:
- 遍历字符串每个字符
- 识别并统计连续数字
- 更新最长数字串信息
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string solve(string str) {
string maxNum = ""; // 最长数字串
string curNum = ""; // 当前数字串
for (char c : str) {
if (isdigit(c)) {
curNum += c;
// 更新最长数字串
if (curNum.length() > maxNum.length()) {
maxNum = curNum;
}
} else {
curNum = ""; // 重置当前数字串
}
}
return maxNum;
}
};
int main() {
string str;
getline(cin, str);
Solution solution;
cout << solution.solve(str) << endl;
return 0;
}
import java.util.*;
public class Main {
static class Solution {
public String solve(String str) {
String maxNum = ""; // 最长数字串
StringBuilder curNum = new StringBuilder(); // 当前数字串
for (char c : str.toCharArray()) {
if (Character.isDigit(c)) {
curNum.append(c);
// 更新最长数字串
if (curNum.length() > maxNum.length()) {
maxNum = curNum.toString();
}
} else {
curNum = new StringBuilder(); // 重置当前数字串
}
}
return maxNum;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
Solution solution = new Solution();
System.out.println(solution.solve(str));
sc.close();
}
}
class Solution:
def solve(self, s):
max_num = "" # 最长数字串
cur_num = "" # 当前数字串
for c in s:
if c.isdigit():
cur_num += c
# 更新最长数字串
if len(cur_num) > len(max_num):
max_num = cur_num
else:
cur_num = "" # 重置当前数字串
return max_num
# 读取输入
s = input()
solution = Solution()
print(solution.solve(s))
算法及复杂度
- 算法:线性扫描
- 时间复杂度:,其中 是字符串长度
- 空间复杂度:,用于存储最长数字串