Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2022-05-19:给定一个数组arr,给定一个正数M, 如果arr[i] + arr[j]可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。 返

2022-05-19:给定一个数组arr,给定一个正数M, 如果arr[i] + arr[j]可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。 返

原创
作者头像
福大大架构师每日一题
发布于 2022-05-19 11:41:30
发布于 2022-05-19 11:41:30
2150
举报

2022-05-19:给定一个数组arr,给定一个正数M,

如果arri + arrj可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。

返回arr中M整除对的总数量。

来自微软。

答案2022-05-19:

求余,答案叠加,次数叠加。

时间复杂度:O(N)。

空间复杂度:O(M)。

代码用rust编写。代码如下:

代码语言:rust
AI代码解释
复制
fn main() {
    let arr: Vec<isize> = vec![5, 5, 5];
    let ans = num2(&arr, 5);
    println!("ans = {}", ans);
}

fn num2(arr: &Vec<isize>, m: isize) -> isize {
    let n = arr.len() as isize;
    let mut cnts: Vec<isize> = vec![];
    for _i in 0..m {
        cnts.push(0);
    }
    let mut ans: isize = 0;
    let mut i: isize = n - 1;
    while i >= 0 {
        let cur = (arr[i as usize] % m + m) % m;
        ans += cnts[((m - cur) % m) as usize];
        cnts[cur as usize] += 1;
        i -= 1;
    }
    return ans;
}

执行结果如下:

在这里插入图片描述
在这里插入图片描述

左神java代码

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
2022-05-19:给定一个数组arr,给定一个正数M, 如果arr[i] + arr[j]可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。
如果arr[i] + arr[j]可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。
福大大架构师每日一题
2022/06/04
1770
2022-05-19:给定一个数组arr,给定一个正数M, 如果arr[i] + arr[j]可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。
2022-05-07:返回一个数组中,所有降序三元组的数量。
2022-05-07:返回一个数组中,所有降序三元组的数量。 比如 : {5, 3, 4, 2, 1}, 所有降序三元组为 : {5, 3, 2}、{5, 3, 1}、{5, 4, 2}、{5, 4, 1}、 {5, 2, 1}、{3, 2, 1}、{4, 2, 1}。 所以返回数量7。 答案2022-05-07: 利用index tree。 时间复杂度:O(N * logN)。 空间复杂度:O(N)。 代码用rust编写。代码如下: fn main() { let mut arr: Vec<is
福大大架构师每日一题
2022/05/07
7120
2022-05-02:给定一个数组arr,一个正数num,一个正数k, 可以把arr中的某些数字拿出来组成一组,要求该组中的最大值减去最小值<=num, 且该组
2022-05-02:给定一个数组arr,一个正数num,一个正数k, 可以把arr中的某些数字拿出来组成一组,要求该组中的最大值减去最小值<=num, 且该组数字的个数一定要正好等于k, 每个数字只能选择进某一组,不能进多个组。 返回arr中最多有多少组。 来自微软。 答案2022-05-02: 排序+动态规划。滑动窗口有陷阱,不一定行,可能可以。 第一种情况,包含i,dpi跟dpi-k相关。 第二种情况,不包含i,dpi=dpi-1。 时间复杂度O(N * logN)。 代码用rust编写。代码如下:
福大大架构师每日一题
2022/05/02
9620
2022-05-21:给定一个数组arr,长度为n, 表示n个服务员,每个人服务一个人的时间。 给定一个正数m,表示有m个人等位。 如果你是刚来的人,请问你需要
2022-05-21:给定一个数组arr,长度为n, 表示n个服务员,每个人服务一个人的时间。 给定一个正数m,表示有m个人等位。 如果你是刚来的人,请问你需要等多久? 假设:m远远大于n,比如n<=1000, m <= 10的9次方,该怎么做? 来自谷歌。 答案2022-05-21: 方法一:小根堆。时间复杂度:O(m*logN)。 方法二:二分法。时间复杂度:O(N*logm)。 代码用rust编写。代码如下: use rand::Rng; fn main() { let len: i32 =
福大大架构师每日一题
2022/05/21
3030
2022-05-21:给定一个数组arr,长度为n, 表示n个服务员,每个人服务一个人的时间。 给定一个正数m,表示有m个人等位。 如果你是刚来的人,请问你需要
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线, 给定一个有序数组arr,表示现在哪些树已经没了,arr[i]一定在[1,n]
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线,
福大大架构师每日一题
2022/06/05
2140
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线, 给定一个有序数组arr,表示现在哪些树已经没了,arr[i]一定在[1,n]
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。 每一步,你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。
福大大架构师每日一题
2022/07/13
7630
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。 每一步,你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j
2022-11-03:给定一个数组arr,和一个正数k 如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号, 而且可以涂上1~k每一种颜色 如果
2022-11-03:给定一个数组arr,和一个正数k如果arri == 0,表示i这里既可以是左括号也可以是右括号,而且可以涂上1~k每一种颜色如果arri != 0,表示i这里已经确定是左括号,颜色就是arri的值那么arr整体就可以变成某个括号字符串,并且每个括号字符都带有颜色。返回在括号字符串合法的前提下,有多少种不同的染色方案。不管是排列、还是颜色,括号字符串任何一点不一样,就算不同的染色方案最后的结果%10001,为了方便,我们不处理mod,就管核心思路。2 <= arr长度 <= 50001
福大大架构师每日一题
2022/11/03
3160
2022-11-03:给定一个数组arr,和一个正数k 如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号, 而且可以涂上1~k每一种颜色 如果
2022-04-17:给定一个数组arr,其中的值有可能正、负、0, 给定一个正数k。 返回累加和>=k的所有子数组中,最短的子数组长度。 来自字节跳动。力扣8
2022-04-17:给定一个数组arr,其中的值有可能正、负、0, 给定一个正数k。 返回累加和>=k的所有子数组中,最短的子数组长度。 来自字节跳动。力扣862。 答案2022-04-17: 看到子数组,联想到结尾怎么样,开头怎么样。 预处理前缀和,单调栈。 达标的前缀和,哪一个离k最近? 单调栈+二分。复杂度是O(N*logN)。 双端队列。 时间复杂度:O(N)。 代码用rust编写。代码如下: fn main() { let arr: Vec<isize> = vec![2, -1, 2]
福大大架构师每日一题
2022/04/17
1.6K0
2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0
2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher :
福大大架构师每日一题
2022/04/27
8570
2023-03-18:给定一个长度n的数组,每次可以选择一个数x, 让这个数组中所有的x都变成x+1,问你最少的操作次数, 使得这个数组变成一个非降数组。 n
本题可以用多种算法来解决,下面我们将介绍四种常见的做法,分别是暴力枚举、动态规划、单调栈和差分。
福大大架构师每日一题
2023/03/18
1K0
2023-03-18:给定一个长度n的数组,每次可以选择一个数x, 让这个数组中所有的x都变成x+1,问你最少的操作次数, 使得这个数组变成一个非降数组。 n
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩, 一共有n个小兵,这n个小兵拍成一列, 第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列, 一共
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩,一共有n个小兵,这n个小兵拍成一列,第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列,一共进行m次操作,二狗每次操作选择一个数k,将前k个小兵战斗力从小到大排列,大胖每次操作选择一个数k,将前k个小兵战斗力从大到小排列,问所有操作结束后,排列顺序什么样,给定一个长度为n的数组arr,表示每个小兵的战斗力,给定一个长度为m的数组op, opi = { k , 0 }, 表示对前k个士兵执行从小到大的操作,opi = { k , 1 }, 表示对前
福大大架构师每日一题
2022/12/20
1910
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩, 一共有n个小兵,这n个小兵拍成一列, 第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列, 一共
2022-12-06:定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严格升序的情况下,得到的最大累加和
2022-12-06:定义一个概念叫"变序最大和" "变序最大和"是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严格升序的情况下,得到的最大累加和 比如,1,100,7变成1,6,7时,就有变序最大和为14 比如,5,4,9变成3,4,9时,就有变序最大和为16 比如,1,4,2变成0,1,2时,就有变序最大和为3 给定一个数组arr,其中所有的数字都是>=0的。 求arr所有子数组的变序最大和中,最大的那个并返回。 1 <= arr长度 <= 10^6, 0 <= arri <= 10^6。
福大大架构师每日一题
2022/12/06
6680
2022-12-06:定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严格升序的情况下,得到的最大累加和
2022-05-18:假设数组a和数组b为两组信号: 1) length(b) <= length(a); 2) 对于任意0<=i<length(b), 有b[
2) 对于任意0<=i<length(b), 有bi+1 - bi == ai+1 - ai。
福大大架构师每日一题
2022/05/18
3110
2022-05-18:假设数组a和数组b为两组信号: 1) length(b) <= length(a); 2) 对于任意0<=i<length(b), 有b[
2022-05-23:给定一个数组arr,你可以随意挑选其中的数字, 但是你挑选的数中,任何两个数a和b,必须Math.abs(a - b) > 1。 返回你最
let n: i32 = rand::thread_rng().gen_range(0, len) + 1;
福大大架构师每日一题
2022/05/23
5320
2022-05-23:给定一个数组arr,你可以随意挑选其中的数字, 但是你挑选的数中,任何两个数a和b,必须Math.abs(a - b) > 1。 返回你最
2022-11-03:给定一个数组arr,和一个正数k如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号,而且可
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_2_week/Code01_ParenthesesDye.java)
福大大架构师每日一题
2023/02/01
3760
2022-05-18:假设数组a和数组b为两组信号:1) length(b) <= length(a);2) 对于任意0<=i<
2) 对于任意0<=i<length(b), 有b[i+1] - b[i] == a[i+1] - a[i]。
福大大架构师每日一题
2022/06/04
2570
2022-05-18:假设数组a和数组b为两组信号:1) length(b) <= length(a);2) 对于任意0<=i<
2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组, 求剩下的数组,严格连续递增的子数组最大长度。 n <= 10^6。 来自字节。
2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组,求剩下的数组,严格连续递增的子数组最大长度。n <= 10^6。来自字节。5.6笔试。答案2022-08-22:动态规划+线段树。代码用rust编写。代码如下:use rand::Rng;fn main() { let n: i32 = 100; let v: i32 = 20; let test_time: i32 = 50000; println!("测试开始"); for _ in 0..te
福大大架构师每日一题
2022/08/22
5640
2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组, 求剩下的数组,严格连续递增的子数组最大长度。 n <= 10^6。 来自字节。
2022-04-15:给定一个非负数组arr,学生依次坐在0~N-1位置,每个值表示学生的安静值, 如果在i位置安置插班生,那么i位置的安静值变成0,同时任何同
2022-04-15:给定一个非负数组arr,学生依次坐在0~N-1位置,每个值表示学生的安静值,
福大大架构师每日一题
2022/04/15
3860
2022-05-25:最大子段和是 一个经典问题,即对于一个数组找出其和最大的子数组。 现在允许你在求解该问题之前翻转这个数組的连续一段, 如翻转(1,2,3,
如翻转(1,2,3,4,5,6)的第三个到第五个元素組成的子数组得到的是(1,2,5,4,3,6),
福大大架构师每日一题
2022/05/25
4470
2022-05-25:最大子段和是 一个经典问题,即对于一个数组找出其和最大的子数组。 现在允许你在求解该问题之前翻转这个数組的连续一段, 如翻转(1,2,3,
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线,给定一个有序数组arr,表示现在哪些树已经没了
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线,
福大大架构师每日一题
2023/06/08
1410
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线,给定一个有序数组arr,表示现在哪些树已经没了
推荐阅读
2022-05-19:给定一个数组arr,给定一个正数M, 如果arr[i] + arr[j]可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。
1770
2022-05-07:返回一个数组中,所有降序三元组的数量。
7120
2022-05-02:给定一个数组arr,一个正数num,一个正数k, 可以把arr中的某些数字拿出来组成一组,要求该组中的最大值减去最小值<=num, 且该组
9620
2022-05-21:给定一个数组arr,长度为n, 表示n个服务员,每个人服务一个人的时间。 给定一个正数m,表示有m个人等位。 如果你是刚来的人,请问你需要
3030
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线, 给定一个有序数组arr,表示现在哪些树已经没了,arr[i]一定在[1,n]
2140
2022-07-13:给你一个整数数组 arr ,你一开始在数组的第一个元素处(下标为 0)。 每一步,你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j
7630
2022-11-03:给定一个数组arr,和一个正数k 如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号, 而且可以涂上1~k每一种颜色 如果
3160
2022-04-17:给定一个数组arr,其中的值有可能正、负、0, 给定一个正数k。 返回累加和>=k的所有子数组中,最短的子数组长度。 来自字节跳动。力扣8
1.6K0
2022-04-27:Alice 有一个下标从 0 开始的数组 arr ,由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0
8570
2023-03-18:给定一个长度n的数组,每次可以选择一个数x, 让这个数组中所有的x都变成x+1,问你最少的操作次数, 使得这个数组变成一个非降数组。 n
1K0
2022-12-20:二狗买了一些小兵玩具,和大胖一起玩, 一共有n个小兵,这n个小兵拍成一列, 第i个小兵战斗力为hi,然后他们两个开始对小兵进行排列, 一共
1910
2022-12-06:定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严格升序的情况下,得到的最大累加和
6680
2022-05-18:假设数组a和数组b为两组信号: 1) length(b) <= length(a); 2) 对于任意0<=i<length(b), 有b[
3110
2022-05-23:给定一个数组arr,你可以随意挑选其中的数字, 但是你挑选的数中,任何两个数a和b,必须Math.abs(a - b) > 1。 返回你最
5320
2022-11-03:给定一个数组arr,和一个正数k如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号,而且可
3760
2022-05-18:假设数组a和数组b为两组信号:1) length(b) <= length(a);2) 对于任意0<=i<
2570
2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组, 求剩下的数组,严格连续递增的子数组最大长度。 n <= 10^6。 来自字节。
5640
2022-04-15:给定一个非负数组arr,学生依次坐在0~N-1位置,每个值表示学生的安静值, 如果在i位置安置插班生,那么i位置的安静值变成0,同时任何同
3860
2022-05-25:最大子段和是 一个经典问题,即对于一个数组找出其和最大的子数组。 现在允许你在求解该问题之前翻转这个数組的连续一段, 如翻转(1,2,3,
4470
2022-06-04:给定一个数字n,表示一开始有编号1~n的树木,列成一条直线,给定一个有序数组arr,表示现在哪些树已经没了
1410
相关推荐
2022-05-19:给定一个数组arr,给定一个正数M, 如果arr[i] + arr[j]可以被M整除,并且i < j,那么(i,j)叫做一个M整除对。
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档