day16(力扣)自然数(python描述)

ゞ浴缸里的玫瑰 2021-11-05 05:50 226阅读 0赞

题目描述：给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。  
示例 1:

输入: [1, 2, 2, 3, 1]
    输出: 2
    解释: 
    输入数组的度是2，因为元素1和2的出现频数最大，均为2.
    连续子数组里面拥有相同度的有如下所示:
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    最短连续子数组[2, 2]的长度为2，所以返回2.

示例 2:

输入: [1,2,2,3,1,4,2]
    输出: 6

注意:

nums.length 在1到50,000区间范围内。
    nums[i] 是一个在0到49,999范围内的整数。

分析：朴素的想法就是对范围内的数字进行循环遍历，然后看每一个数是否符合要求，符合的就把他放到一个新列表，不符合就进行下一个数字的判断，直到判断完所有数字。然后大家可能就会写出如下代码，然后你会发现一个神奇的事情发生了，运行时间超出限制。（此处省略苦笑。。。。）  
超时代码：这里面我们要注意，在判断是否满足题意得if语句哪里，如果你先将a\[i\] % m == 0 这个表达式写在前面，你会发现程序报错，原因是除数有可能为0，所以你需要将判断除数得语句放在前面。

class Solution:
        def selfDividingNumbers(self, left: int, right: int) -> List[int]:
            a = list(set())
            c = list(set())
            for i in range(left, right, 1):
                a.append(i)         #把所有的数字添加到数组中
            for i in range(len(a)):
                while a[i] != 0:
                    n = a[i] % 10       #取余数
                    m = a[i] - n        #相减，得到的就是取出来的余数
                    if m != 0 and a[i] % m == 0:        #如果满足题意
                        c.append(m)     #添加到列表中
                i +=  1

正确代码如下：我们可以将每一个输入的数字转变为字符串，找出字符串 中的每一个字符，然后将字符串转换成整数进行取余运算，将满足条件的放入到一个空数组中，其实整体思路和上面的没有太大的差异，但是不知道为啥上面的就超时了，应该是循环的太多，因此大家在写代码的时候要注意这一点：**高效性**

class Solution(object):
        def selfDividingNumbers(self, left, right):
            
       #     :type left: int
        #    :type right: int
         #   :rtype: List[int]
            
            L = []
            for i in range(left, right + 1):
                flag = 0				#设置一个哨兵
                for j in str(i):        #直接找出字符串中的每个字符
                    if int(j) == 0 or int(i) % int(j)!= 0:      #将上一部找出来的字符与初始数字进行取余
                        flag = 1
                        break
                if flag == 0:
                    L.append(i)
            return L

本题其实也没有什么知识点，就是优化你的算法，让他满足题目要求，唯一注意的就是我们对不要把数字一直当作数字用，必要的时候可以把它当作字符串。