Python 力扣系列:余数的三大定理
2021-09-03 09:28:39
7次阅读
0个评论
Python 力扣系列

今天忍不住更新一下力扣系列,再一次感受到了数学的强大,事情是这个样子的,有个题一直超时,然后就去看了答案,我去,数学好牛呀。我先来写下知识点。

余数的三大定理

1.余数的加法定理 a与b的和除以c的余数,等于a,b分别除以c的余数之和,或这个和除以c的余数。

例:18,21除以5的余数分别是1和3,而18+21=39除以5的余数等于4,即是两个余数的和1+3. 当余数的和比除数大时,所求的余数等于余数之和再除以c所得的余数。

2.余数的乘法定理
a与b的乘积除以c的余数,等于a,b分别除以c的余数的积,或者这个积除以c所得的余数。
例:18,21除以5的余数分别是1和3,而18×21=378除以5的余数等于3,即是两个余数的积1×3.  当余数的积比除数大时,所求的余数等于两个余数的积再除以c所得的余数。

3.同余定理
若两个整数a、b被自然数m除有相同的余数,那么称a、b对于模m同余。同余式读作:a同余于b,模m。由同余的性质我们可以得到一个非常重要的推论:若两个数a、b除以同一个数m,得到的余数相同,则a、b的差一定能被m整除。
例:18,33除以5的余数都是3,则33-18=15一定能被5整除。 

学完了余数的三大定理,主要是最后一个同余定理,然后来看题目。

连续的子数组和
  1. 连续的子数组和 给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:

子数组大小 至少为 2 ,且 子数组元素总和为 k 的倍数。如果存在,返回 true ;否则,返回 false 。

如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

这个题的第一思路是暴利法,来小二,上题解

<pre class="prettyprint lang-js">from typing import  List
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        if sum(nums)==0 and len(nums)>1:
            return True
        if len(nums)<=1:
            return False
        for i in range(len(nums)):
            for j in range(i+2,len(nums)+1):
                if sum(nums[i:j])%k==0:
                    return True
        else:
            return False </pre>

两个循环,把特殊条件摘出去,果然这是超时的解法。哎,我冥思苦想,看了看题解,妹的竟然是同余定理,于是我去百度了一下定理,嗯,好熟悉,上学一定学过,一看果然是初中学的,我不禁感叹了一下,怎么这么菜。啊,好了思路有了,再来一次.刷题就是这样,一次不行多来几次,慢慢的多来的次数就会越来越少,不要轻言放弃嘻嘻

<pre class="prettyprint lang-js">class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        a=set()
        b=0
        for i in nums:
            c=b
            b+=i
            b%=k
            if b in a:
                return True
            a.add(c)
        return False</pre>

执行结果:通过 执行用时:104 ms 内存消耗:28.7 MB

根据同余定理的思路,首先我定义了一个集合,初始化一个变量值为0,然后遍历nums里面的数值,把b的值赋值给c,b 等于 遍历值的和模除k,最后b就是个余数,b就是前n项和的余数,然后集合增加,如果b在集合里面,说明他俩余数是一样的并且长度一定大于等于2的,直接返回True就行了

再一次感叹是数学的魅力呀,数学真香,我爱数学。今天更新到这里了,美滋滋。同志们下期见!


收藏 0 0

登录 后评论。没有帐号? 注册 一个。

cspython

  • 0 回答
  • 0 粉丝
  • 0 关注