首页 > 试题广场 >

小红的数字串

[编程题]小红的数字串
  • 热度指数:25 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小红拿到了一个数字串(由'1'~'9'组成,不含'0'),她准备截取一段连续子串,使得该子串表示的正整数小于k。你能帮她求出有多少种截取方案吗?

输入描述:
第一行输入一个数字串,长度不超过200000。
第二行输入一个正整数k
1\leq k \leq 10^9


输出描述:
小于k的截取方案数。
示例1

输入

1234
23

输出

5

说明

共有1,2,3,4,12这五种截取方法。
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int k = sc.nextInt();
        int left = 0;
        int right = 0;
        int res = 0;
        while (right < s.length()) {
            while (Long.parseLong(s.substring(left, right + 1)) >= k) {
                if (left == right) {
                    right++;
                }
                left++;
            }

            while (right < s.length() && Long.parseLong(s.substring(left, right + 1)) < k) {
                int curLength = right - left + 1;
                res += curLength;
                right++;
            }
        }
        System.out.println(res);
    }
}

发表于 2024-05-12 09:16:11 回复(0)