题意:
有一个只由字符'1'到'9'组成的长度为 n 的字符串 s ,现在可以截取其中一段长度为 k 的子串并且将该子串当作十进制的正整数,如对于子串"123",其对应的十进制数字就是123 。
如果想让这个正整数尽可能的大的话,问该正整数最大能是多少。
方法一:
暴力枚举
思路:外层循环暴力遍历字符串,枚举起点;
内层循环计算区间长度为 k 的值,并且维护最大值。
class Solution {
public:
int maxValue(string s, int k) {
int len=s.size();
int res=0;
for(int i=0;i<len-k+1;i++){//枚举起点
int x=0;
for(int j=i;j<i+k;j++){//计算长度为k的数
x=x*10+s[j]-'0';
}
res=max(res,x);//维护最大值
}
return res;
}
};
时间复杂度:
空间复杂度:![]()
方法二:
滑动窗口
思路:首先,初始化长度为 k 的区间;
然后,利用滑动窗口,循环右移,并计算数值且维护最大值。
class Solution {
public:
int maxValue(string s, int k) {
int len=s.size();
int res=0,x=0;
int t=pow(10,k-1);//取余的数
int r=0;//右指针
while(r<len){
if(r<k){//初始化长度为k的区间
x=x*10+s[r++]-'0';
}else{
res=max(res,x);//维护最大值
x=x%t;
x=x*10+s[r++]-'0';
}
}
res=max(res,x);//维护最大值
return res;
}
};
时间复杂度:
空间复杂度:![]()



京公网安备 11010502036488号