论坛 › Python交流 › Python：每日一题 313

zltzlt 发表于 2020-1-23 18:41:43

Python：每日一题 313

今天的题目：

给出一个整型数组，求这个数组的最小循环节的长度。

示例 1：

输入：
输出：2
解释：最小循环节为 ，长度为 2。
示例 2：

输入：
输出：2
解释：最小循环节为 ，长度为 2。最后一个 2 虽然没有给出，但是我们还是认为循环节是 。
示例 3：

输入：
输出：6
解释：最小循环节为 ，长度为 6。

{:10_298:}欢迎大家一起答题！{:10_298:}

Croper 发表于 2020-1-23 18:41:44

def solve(lst:'list of int >= 0',debug=False)->list:
    if lst:
      loop = 1
      for i in range(1,len(lst)-1):
            if lst != lst or lst != lst[(i+1)%loop]:
                if lst == lst:
                  r = loop+i
                  l = r//2
                  if lst[:l]==lst:
                        loop = l
                        continue
                loop = i+1 if lst == lst else i+2
                if debug:
                  print('调试',loop)
      return loop
    else:
      return 0
      
def fun313(l):
        p=0
        index=[-1,0]      
        for q in range(1,len(l)):
                while p!=-1 and l!=l:
                        p=index
                p+=1
                index.append(p)
        return q-p+1
      
l=
print(solve(l))
print(fun313(l))

结果:9
7

塔利班 发表于 2020-1-23 18:54:55

本帖最后由 塔利班 于 2020-1-23 19:00 编辑

def f313(x):
    l=len(x)
    z=len(set(x))
    for i in range(z,l+1):
      a,b=divmod(l,i)
      if x==x[:i]*a+x[:b]:
            return i
先写一个

zltzlt 发表于 2020-1-23 19:03:34

塔利班 发表于 2020-1-23 18:54
先写一个

输入 + * 5000 超时

Croper 发表于 2020-1-23 20:06:58

本帖最后由 Croper 于 2020-1-23 20:10 编辑

凭感觉写的，kmp算法改了下def func313(l:list):
    p=0
    index=[-1,0]
    for q in range(1,len(l)):
      while p!=-1 and l!=l:
            p=index
      p+=1
      index.append(p)
    return q-p+1

wanting-for 发表于 2020-1-23 20:07:33

如果多个循环节呢？例如 1212353535
这时候怎么处理呢？

zltzlt 发表于 2020-1-23 20:10:24

wanting-for 发表于 2020-1-23 20:07
如果多个循环节呢？例如 1212353535
这时候怎么处理呢？

把 1212353535 当做一整个循环节处理。

zltzlt 发表于 2020-1-23 20:12:06

塔利班 发表于 2020-1-23 18:54
先写一个

还是超时

塔利班 发表于 2020-1-23 20:19:25

zltzlt 发表于 2020-1-23 20:12
还是超时

我在想你@错了

Croper 发表于 2020-1-23 20:36:32

想了想，好像不需要kmp。。def func313(l:list):
    p=0
    for q in range(1,len(l)):
      if l!=l:
            p=0
      else:
            p+=1
    return q-p+1

wanting-for 发表于 2020-1-23 20:54:06

def solve_313(list1:list):
    length = 0
    for i in range(0,len(list1)):
      if length == 0 and list1 == list1:
            length = i-0
      elif length!=0 and list1 == list1:
            continue
      else:
            length = 0
    if length:
      return length
    else:
      return len(list1)

if __name__ == "__main__":
    print(solve_313())
给的测试点，都过了，可能还会有错误，
请楼主劳累测试一下，麻烦了！感谢，比心心

zltzlt 发表于 2020-1-23 20:56:19

Croper 发表于 2020-1-23 20:36
想了想，好像不需要kmp。。

输入 出错

zltzlt 发表于 2020-1-23 20:57:57

wanting-for 发表于 2020-1-23 20:54
给的测试点，都过了，可能还会有错误，
请楼主劳累测试一下，麻烦了！感谢，比心心

解答错误

输入：
输出：12
预期结果：11（循环节为 ）

Croper 发表于 2020-1-23 21:01:14

zltzlt 发表于 2020-1-23 20:56
输入 出错

好吧- -def func313(l:list):
    if (len(l)<2):
      return len(l)
    p=0
    for q in range(1,len(l)):
      if l!=l:
            p=0
      else:
            p+=1
    return q-p+1

zltzlt 发表于 2020-1-23 21:02:06

Croper 发表于 2020-1-23 21:01
好吧- -

解答错误

输入：
输出：12
预期结果：11（循环节为 ）

wanting-for 发表于 2020-1-23 21:06:55

zltzlt 发表于 2020-1-23 20:57
解答错误

输入：


def solve_313(list1:list):
    length = 0
    for i in range(0,len(list1)):
      if length == 0 and list1 == list1:
            length = i-0
      elif length!=0 and list1 == list1:
            continue
      elif list1 == list1:
            length = i-0
      else:
            length = 0
    if length:
      return length
    else:
      return len(list1)

if __name__ == "__main__":
    print(solve_313())
上一个代码没有更新最大长度，失算失算！

zltzlt 发表于 2020-1-23 21:08:21

wanting-for 发表于 2020-1-23 21:06
上一个代码没有更新最大长度，失算失算！

解答错误

输入：
输出：11
预期结果：6（循环节为 ）

Croper 发表于 2020-1-23 21:17:04

zltzlt 发表于 2020-1-23 21:08
解答错误

输入：


所以还是得kmp，但是kmp超时。。。这就很纠结了

wanting-for 发表于 2020-1-23 21:30:00

def solve_313(list1:list):
    length = 0
    for i in range(0,len(list1)):
      if length == 0 and list1 == list1:
            if list1 == list1:
                length = i-0
      elif length!=0 and list1 == list1:
            pass
      elif list1 == list1:
            length = i-0
      else:
            length = 0
    if length:
      return length
    else:
      return len(list1)
if __name__ == "__main__":
    print(solve_313())
太麻烦楼主了，我这一包茶，一包烟，一个bug改一天！{:9_240:}

zltzlt 发表于 2020-1-23 21:34:20

wanting-for 发表于 2020-1-23 21:30
太麻烦楼主了，我这一包茶，一包烟，一个bug改一天！

{:10_256:}

解答错误

输入：



输出：40007
预期结果：40003

查看完整版本: Python：每日一题 313