题目描述
输入一个字符串仅包含大小写字母和数字，求字符串中包含的最长的非严格递增连续数字序列的长度，（比如12234属于非严格递增连续数字序列）。
输入描述
输入一个字符串仅包含大小写字母和数字，输入的字符串最大不超过255个字符。
输出描述
最长的非严格递增连续数字序列的长度
用例
| 输入 | abc2234019A334bc |
| 输出 | 4 |
| 说明 | 2234为最长的非严格递增连续数字序列，所以长度为4。 |
双指针解法
简单的双指针题目。
双指针逻辑如下
当right指针移动遇到字母时，则right前面可能：
- 是一个空串
- 是一个符合题意的，且长度right-left的子串，
然后right++，left = right，即left,right同时移到字母后一个位置
当right指针移动遇到数字时，
- 若此时left、right在同一个位置，则可得一个长度为1的符合要求的子串
- 若此时left、right不在同一个位置，则检查right指向数值是否大于right-1指向的数值，
- 若是，则可得一个符合要求的，长度right-left+1的子串，然后right++
- 若不是，则可得一个符合要求的，长度right-left的子串，然后right++，left = right，即left,right同时移到字母后一个位置
Java算法源码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
System.out.println(getResult(s));
}
public static int getResult(String s) {
int l = 0;
int r = 0;
int maxLen = 0;
while (r < s.length()) {
char c = s.charAt(r);
if (c >= '0' && c <= '9') {
if (l != r) {
if (c >= s.charAt(r - 1)) {
maxLen = Math.max(maxLen, r - l + 1);
} else {
maxLen = Math.max(maxLen, r - l);
l = r;
}
r++;
} else {
maxLen = Math.max(maxLen, 1);
r++;
}
} else {
maxLen = Math.max(maxLen, r - l);
r++;
l = r;
}
}
return maxLen;
}
}
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", (line) => {
console.log(getMaxLen(line));
});
function getMaxLen(str) {
let L = 0;
let R = 0;
let maxLen = 0;
while (R < str.length) {
if (/d/.test(str[R])) {
if (L !== R) {
if (str[R] - 0 >= str[R - 1] - 0) {
maxLen = Math.max(maxLen, R - L + 1);
R++;
} else {
maxLen = Math.max(maxLen, R - L);
L = R;
R++;
}
} else {
maxLen = Math.max(maxLen, 1);
R++;
}
} else {
maxLen = Math.max(maxLen, R - L);
R++;
L = R;
}
}
return maxLen;
}
Python算法源码
# 输入获取
s = input()
# 算法入口
def getResult():
l = 0
r = 0
maxLen = 0
while r < len(s):
if '0' <= s[r] <= '9':
if l != r:
if s[r] >= s[r-1]:
maxLen = max(maxLen, r - l + 1)
r += 1
else:
maxLen = max(maxLen, r - l)
l = r
r += 1
else:
maxLen = max(maxLen, 1)
r += 1
else:
maxLen = max(maxLen, r - l)
r += 1
l = r
return maxLen
# 调用算法
print(getResult())
C算法源码
#include <stdio.h>
#include <string.h>
#define MAX(a,b) a > b ? a : b
int main() {
char s[255];
scanf("%s", s);
int l = 0;
int r = 0;
int maxLen = 0;
while(r < strlen(s)) {
char c = s[r];
if(c >= '0' && c <= '9') {
if(l != r) {
if(c >= s[r - 1]) {
maxLen = MAX(maxLen, r - l + 1);
} else {
maxLen = MAX(maxLen, r - l);
l = r;
}
r++;
} else {
maxLen = MAX(maxLen, 1);
r++;
}
} else {
maxLen = MAX(maxLen, r - l);
r++;
l = r;
}
}
printf("%dn", maxLen);
return 0;
}单指针解法
上面双指针解法略显繁琐，因为我们需要依赖于L，R来求解子串长度，但是其实我们可以只靠一个变量len来记录长度即可
for循环从左到右开始扫描字符串，
若遇到字母，则len=0，maxNum=0，表示符合题意的子串长度len为0，重置最大数字字符为0
若遇到数字，则看len是否为0，
若为0，则表示该数字是子串开头，此时子串长度len=1，最大数字字符maxNum就是当前数字curNum
若不为0，则表示该数字前面还有数字，且前面的数字必然是maxNum，此时需要判断curNum>=maxNum？，若是，则len++，否则len=1,然后maxNum=curNum
Java算法源码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
System.out.println(getResult(s));
}
public static int getResult(String s) {
int maxNum = 0;
int len = 0;
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
int curNum = c - '0';
if (len == 0) {
len = 1;
maxNum = curNum;
} else {
if (curNum >= maxNum) {
len++;
} else {
len = 1;
}
maxNum = curNum;
}
} else {
len = 0;
maxNum = 0;
}
maxLen = Math.max(maxLen, len);
}
return maxLen;
}
}
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", (line) => {
console.log(getMaxLen(line));
});
function getMaxLen(str) {
let maxLen = 0;
let len = 0;
let maxNum = 0;
for (let i = 0; i < str.length; i++) {
if (/d/.test(str[i])) {
let curNum = str[i] - 0;
if (len === 0) {
len = 1;
maxNum = curNum;
} else {
curNum >= maxNum ? len++ : (len = 1);
maxNum = curNum;
}
} else {
len = 0;
maxNum = 0;
}
maxLen = Math.max(maxLen, len);
}
return maxLen;
}
Python算法源码
# 输入获取
s = input()
# 算法入口
def getResult():
maxLen = 0
length = 0
maxNum = 0
for c in s:
if '0' <= c <= '9':
curNum = int(c)
if length == 0:
length = 1
maxNum = curNum
else:
if curNum >= maxNum:
length += 1
else:
length = 1
maxNum = curNum
else:
length = 0
maxNum = 0
maxLen = max(maxLen, length)
return maxLen
# 调用算法
print(getResult())
C算法源码
#include <stdio.h>
#include <string.h>
#define MAX(a, b) a > b ? a : b
int main() {
char s[255];
scanf("%s", s);
int maxNum = 0;
int len = 0;
int maxLen = 0;
for (int i = 0; i < strlen(s); i++) {
if (s[i] >= '0' && s[i] <= '9') {
int curNum = s[i] - '0';
if (len == 0) {
len = 1;
maxNum = curNum;
} else {
if (curNum >= maxNum) {
len++;
} else {
len = 1;
}
maxNum = curNum;
}
} else {
len = 0;
maxNum = 0;
}
maxLen = MAX(maxLen, len);
}
printf("%d", maxLen);
return 0;
}
免责声明：
1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0