gpt4 book ai didi

1018. Binary Prefix Divisible By 5 可被 5 整除的二进制前缀

转载 作者:大佬之路 更新时间:2024-01-31 14:15:43 25 4
gpt4 key购买 nike

题目地址:https://leetcode.com/problems/binary-prefix-divisible-by-5/

题目描述

Given an array A of 0s and 1s, consider N_i: the i-th subarray from ```A[0]toA[i]`` interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: [0,1,1]
Output: [true,false,false]
Explanation: 
The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.  Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: [1,1,1]
Output: [false,false,false]

Example 3:

Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]

Example 4:

Input: [1,1,1,0,1]
Output: [false,false,false,false,false]

Note:

1、 1<=A.length<=30000
2、 A[i]is0or1

题目大意

给出一个数组,判断数组的每个位置构成的前缀能不能被5整除。

解题方法

这个题肯定不能蛮力求解,最简单的方法就是利用求余的性质。我们每次只用保存前缀对5的余数,在求下一个位置的时候把上一次的前缀×2 + 当前的数字再模5.

求余的性质:

((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p
(a×b) mod c=((a mod c) * (b mod c)) mod c
(a+b) mod c=((a mod c)+ (b mod c)) mod c
(a-b) mod c=((a mod c)- (b mod c)) mod c

所以,a扩大x倍之后模一个数字,等于((a % 5) * (x % 5)) % 5.

Python代码如下:

class Solution(object):
    def prefixesDivBy5(self, A):
        """
        :type A: List[int]
        :rtype: List[bool]
        """
        res = []
        prefix = 0
        for a in A:
            prefix = (prefix * 2 + a) % 5
            res.append(prefix == 0)
        return res

1 2 3 4 5 6 7 8 9 10 11 12

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com