LeetCode 1018. 可被 5 整除的二进制前缀
发布日期:2021-07-01 03:24:32
浏览次数:2
分类:技术文章
本文共 1262 字,大约阅读时间需要 4 分钟。
1. 题目
给定由若干 0 和 1 组成的数组 A。
我们定义N_i
:从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数(从最高有效位到最低有效位)。 返回布尔值列表 answer,只有当 N_i
可以被 5 整除时,答案 answer[i] 为 true,否则为 false。
示例 1:输入:[0,1,1]输出:[true,false,false]解释:输入数字为 0, 01, 011;也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除,因此 answer[0] 为真。示例 2:输入:[1,1,1]输出:[false,false,false]示例 3:输入:[0,1,1,1,1,1]输出:[true,false,false,false,true,false]示例 4:输入:[1,1,1,0,1]输出:[false,false,false,false,false] 提示:1 <= A.length <= 30000A[i] 为 0 或 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-prefix-divisible-by-5 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
余数定理
(a+b)%q = (a % q + b % q) % q
(a*b)%p = (a % p * b % p) % p
class Solution { public: vectorprefixesDivBy5(vector & A) { int sum = 0; vector ans(A.size()); for(int i = 0; i < A.size(); ++i) { sum = sum*2+A[i]; ans[i] = (sum%5 == 0); sum %= 5;//防止溢出 } return ans; }};
class Solution { public: vectorprefixesDivBy5(vector & A) { int sum = 0; vector ans(A.size()); for(int i = 0; i < A.size(); ++i) { sum = ((sum<<1)+A[i])%5; ans[i] = (sum == 0); } return ans; }};
转载地址:https://michael.blog.csdn.net/article/details/105799833 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年05月03日 13时59分09秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Request_继承体系
2019-05-01
前端权限控制:获取用户信息接口构造数据
2019-05-01
有状态服务和无状态服务
2019-05-01
七牛云存储:断点续传
2019-05-01
字节流复制文本文件【应用】
2019-05-01
字节流复制图片
2019-05-01
私钥加密私钥解密
2019-05-01
锁的释放流程-ReentrantLock.unlock
2019-05-01
Java判断字符串是否为数字(浮点类型也包括)
2019-05-01
ubuntu opencv-python 安装很慢问题
2019-05-01
MySQL5.7版本修改了my.ini配置文件后mysql服务无法启动问题
2019-05-01
【大数据开发】Java基础 -总结21-Hashmap和HashTable的区别
2019-05-01
Azkaban体系结构
2019-05-01
机器学习之重头戏-特征预处理
2019-05-01
synchronized底层实现及锁的升级、降级
2019-05-01
PermGen space-永久区内存溢出
2019-05-01
Maven继承和聚合
2019-05-01