题解 | #最大值#
最大值
http://www.nowcoder.com/practice/c0a95c1c30e94dc190e6acc42cb06930
题意理解
输入一个字符串s(由1~9组成)和一个整数k,我们从s中获取连续的长度为k的子串,求所有子串对应的数字中最大值为多少。
方法一
枚举
因为子串长度固定,且是从s中连续的位置提取,所以遍历一遍字符串,每次取连续的k个字符即可。每次取出后直接使用字符串比较大小。最后将最大的字符串转为数字。
具体代码如下:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int maxValue(string s, int k) {
// write code here
string maxm = "0";
//注意不能遍历到字符串的结尾
for (int i=0;i<s.size()-k+1;i++)
{
string ss = s.substr(i,k);
if (ss > maxm)
maxm = ss;
}
return stoi(maxm);
}
};
时间复杂度: 。遍历一遍长度为N字符串,每次比较时要遍历一遍长度为k的子串。
空间复杂度: 。***和maxm记录子串和最大子串,长度均为k。
方法二
方法一在比较两个子串的大小时耗时较多,可以将子串转化为数字比大小。但是直接转化也要加一重循环。我们观察到,新的子串对应的数字,只要将前一个子串对应的数字对取模,再乘以10,最后加上新子串的最后一个字符对应的数字即可。
示意图如下:
具体代码如下:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串
* @param k int整型
* @return int整型
*/
int maxValue(string s, int k) {
// write code here
string ss = s.substr(0,k);
int num = stoi(ss);
int maxm = num, t=1;
for (int i=1;i<k;i++)
t = t * 10;
for (int i=1;i<s.size()-k+1;i++)
{
//更新滑动后的数值
num = num % t * 10 + (s[i+k-1] - '0');
if (num>maxm) maxm = num;
}
return maxm;
}
};
时间复杂度: 。遍历一遍长度为N字符串。
空间复杂度: 。只使用了3个整型变量。