K倍区间——JAVA解法(蓝桥杯)

简介: K倍区间——JAVA解法(蓝桥杯)

 题目链接:

 

题目描述

给定一个长度为 N 的数列,A1, A2, AN,A1,A2,⋯AN,如果其中一段连续的子序列 Ai,Ai+1,  Aj,Ai,Ai+1,⋯Aj ( i≤j ) 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗?

输入描述

第一行包含两个整数 N 和 K

以下 N 行每行包含一个整数 Ai

输出描述

输出一个整数,代表 K 倍区间的数目。

输入输出样例

示例

输入

5 2
1
2
3
4
5

image.gif

image.gif编辑

输出

6

image.gif

运行限制

    • 最大运行时间:2s
    • 最大运行内存: 256M

    解法一:

    import java.util.Scanner;
    public class k倍区间 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(), k = sc.nextInt();
            // 初始化桶
            int[] bucket = new int[k];
            bucket[0] = 1;
            long sum = 0; // 记录计数结果
            int preSum = 0; // 记录前缀和取 k 的余数的结果
            for (int i = 0; i < n; i++) {
                int num = sc.nextInt();
                preSum = (preSum + num) % k;
                // 特判负数的情况
                if (preSum < 0) {
                    preSum += k;
                }
                sum += bucket[preSum];
                bucket[preSum]++;
            }
            System.out.println(sum);
            sc.close();
        }
    }

    image.gif

    解法二:

    import java.util.Scanner;
    public class k倍区间 {
          public static void main(String[] args) {
                Scanner scan = new Scanner(System.in);
                int N = scan.nextInt();
                int k = scan.nextInt();
                int[] sums = new int[N+1];
                long[] cnt = new long[k];
                sums[0] = 0;
                cnt[0] = 1;
                int t;
                for (int i = 1; i <= N; ++i) {
                    t = scan.nextInt();
                    sums[i] = (sums[i-1] + t) % k;
                    cnt[sums[i]]++;
                }
                long ans = 0;
                for (int i = 0; i < k; ++i) {
                    ans += (cnt[i] * (cnt[i] -1)/2);
                }
                System.out.println(ans);
                scan.close();
            }
    }

    image.gif


    相关文章
    |
    3月前
    |
    算法 Java
    LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
    LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
    52 6
    |
    3月前
    |
    人工智能 算法 Java
    LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
    LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
    50 1
    |
    3月前
    |
    存储 算法 Java
    LeetCode经典算法题:预测赢家+香槟塔java解法
    LeetCode经典算法题:预测赢家+香槟塔java解法
    61 1
    |
    3月前
    |
    算法 Java
    LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
    LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
    54 0
    |
    3月前
    |
    存储 算法 Java
    LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
    LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
    39 0
    |
    5月前
    |
    Java
    2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
    2016届蓝桥杯大赛软件类国赛Java大学B组 愤怒小鸟 数学模拟
    52 4
    |
    5月前
    |
    Java
    蓝桥杯Java组暴力递归搜图
    蓝桥杯Java组暴力递归搜图
    33 4
    |
    5月前
    |
    Java
    2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
    2022蓝桥杯大赛软件类国赛Java大学B组 左移右移 空间换时间+双指针
    44 3
    |
    5月前
    |
    Java
    2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
    2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
    50 2
    |
    5月前
    |
    Java
    2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
    2023届蓝桥杯大赛软件类国赛Java大学B组 互质 数论
    37 1
    下一篇
    无影云桌面