题意:
有一个只由字符'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; } };
时间复杂度:空间复杂度: