题解 | #最大值#

最大值

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);
    }
};

时间复杂度: O(Nk)O(Nk)。遍历一遍长度为N字符串,每次比较时要遍历一遍长度为k的子串。
空间复杂度: O(k)O(k)。***和maxm记录子串和最大子串,长度均为k。

方法二

方法一在比较两个子串的大小时耗时较多,可以将子串转化为数字比大小。但是直接转化也要加一重循环。我们观察到,新的子串对应的数字,只要将前一个子串对应的数字对10k10^k取模,再乘以10,最后加上新子串的最后一个字符对应的数字即可。

示意图如下: alt

具体代码如下:

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;
    }
};

时间复杂度: O(N)O(N)。遍历一遍长度为N字符串。
空间复杂度: O(1)O(1)。只使用了3个整型变量。

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务