[已解决]Python：每日一题 300

zltzlt

Stubborn 发表于 2020-1-5 20:41
我补个 if not len(pages):retrun 0

return 写成了 retrun，帮你改了

TJBEST

Croper 发表于 2020-1-5 18:49
恩。。怎么说呢。。
我说说我的理解把

明白了，明白了。相当于 不加nolocal，在内部函数 的page和 外部的page都指向一块内存 但是二者不是一个
，当内部让 page指向其他空间后，其和外部的page就是两个东西 。也就是说 用o.page表示外部的page, i.page表示内部的page  那么在执行内部函数时会隐藏一部 i.page = o.page 实际上是两个标签。

Stubborn

TJBEST 发表于 2020-1-5 20:45
明白了，明白了。相当于 不加nolocal，在内部函数 的page和 外部的page都指向一块内存 但是二者不是一个
...

1. def func(a, b=[]): # NO ！！！
   
2.     return b
   
3. x = func(1)
   
4. print(x) # -> []
   
5. x.append(10)
   
6. x.append("Alex")
   
7. print(x) # -> [10, 'Alex']
   
8. c = func(5)
   
9. print(c) # -> [10, 'Alex']

复制代码

理解下这个，希望会助于理解，Python变量标签问题

塔利班

Stubborn 发表于 2020-1-5 20:21

可以

阴阳神万物主

zltzlt 发表于 2020-1-5 17:51
k 可能超过 len(pages)。

嗯？也就是说，有人可以偷懒？
还是书可以撕开？

Stubborn

塔利班 发表于 2020-1-5 20:53
可以

来自班利塔大神的夸奖

塔利班

Stubborn 发表于 2020-1-5 21:09
来自班利塔大神的夸奖

不是大神，我都没听过minmax，，

Stubborn

阴阳神万物主 发表于 2020-1-5 21:00
嗯？也就是说，有人可以偷懒？
还是书可以撕开？

思考如果给定N本书，我们限定时间不超过T，需要多少复印员？

复印员 即 k 是 不限制，题目需要求到是时间！

就和1个人盖房子，30个人盖房子，300人盖房子，他们同样是盖一个房子，人多了而已。但是 完成的时间会不一样

TJBEST

Stubborn 发表于 2020-1-5 20:52
理解下这个，希望会助于理解，Python变量标签问题

谢谢啦

Stubborn

塔利班 发表于 2020-1-5 21:11
不是大神，我都没听过minmax，，

对了 ，班利塔，还有可亲可爱可敬的版主大人。请教一代码。用来素数求和的，有点看不懂过程，为什么，能帮忙解答下吗

1. def P10(n=100):
   
2.     r = int(n ** 0.5)
   
3.     V = [n // i for i in range(1, r + 1)]
   
4.     V += list(range(V[-1] - 1, 0, -1))
   
5.     S = {i: i * (i + 1) // 2 - 1 for i in V}
   
6.     for p in range(2, r + 1):
   
7.         if S[p] > S[p - 1]:  
   
8.             sp = S[p - 1]  
   
9.             p2 = p * p
   
10.             for v in V:
    
11.                 if v < p2: break
    
12.                 S[v] -= p * (S[v // p] - sp)
    
13.     return S[n]

复制代码

Unicorn#

终于写了俩，尽力优化了
第一个比较省空间，因为最早用DP做直接就超过深度限制了，所以卡得比较死，但是效率稍低
第二个比较浪费空间，但似乎更快
累死

1. # -*- coding: utf-8 -*-
   
2. def solve(pages, k):
   
3.     n = len(pages)
   
4.     k = n if k > n else k
   
5.     for people in range(k):
   
6.         new_ = []
   
7.         for page_from in range(n):
   
8.             new_.append([])
   
9.             for page_length in range(n-page_from+1):
   
10.                 if people == 0 or page_length <= 1:
    
11.                     new_[page_from].append(sum(pages[page_from:page_from+page_length]))
    
12.                 else:
    
13.                     new_[page_from].append(min(max(sum(pages[page_from:page_from+sep_length]), record[page_from+sep_length][page_length-sep_length])for sep_length in range(1, page_length)))
    
14.         record = new_.copy()
    
15.     return record[0][n]

复制代码

1. # -*- coding: utf-8 -*-
   
2. def solve(pages, k):
   
3.     n = len(pages)
   
4.     k = n if k > n else k
   
5.     record = []
   
6.     for people in range(k):
   
7.         record.append([])
   
8.         for page_from in range(n):
   
9.             record[people].append([])
   
10.             for page_length in range(n-page_from+1):
    
11.                 if people == 0 or page_length <= 1:
    
12.                     record[people][page_from].append(sum(pages[page_from:page_from+page_length]))
    
13.                 else:
    
14.                     record[people][page_from].append(min(max(record[0][page_from][sep_length], record[people-1][page_from+sep_length][page_length-sep_length])for sep_length in range(1, page_length)))
    
15.     return record[k-1][0][n]

复制代码

阴阳神万物主

Stubborn 发表于 2020-1-5 21:12
思考如果给定N本书，我们限定时间不超过T，需要多少复印员？

复印员 即 k 是 不限制，题目需要求到是 ...

我原先以为的是：k 为多少，就要把 pages 分成多少个部分。

阴阳神万物主

我已经不知道怎样优化效率了，反正我是模拟我自己分配的思路。人只要够，就不断二分……
我是不会求这个的时间复杂度了。

1. def solve(pages:'list of int',k:int)->int:
   
2.     t = [sum(pages)]
   
3.     p = [pages[:]]
   
4.     while len(p) < k and len(p)<len(pages):
   
5.         m = max(t)
   
6.         i = t.index(m)
   
7.         if len(p[i])==1:
   
8.             break
   
9.         each = []
   
10.         l = 0
    
11.         while l < m:
    
12.             m -= p[i][0]
    
13.             l += p[i][0]
    
14.             each.append(p[i].pop(0))
    
15.         else:
    
16.             if max(l-each[-1],m+each[-1]) < max(l,m):
    
17.                 l -= each[-1]
    
18.                 p[i].insert(0,each.pop())
    
19.         p.insert(i,each)
    
20.         t[i] -= l
    
21.         t.insert(i,l)
    
22.     return max(t)
    
23. if __name__ == '__main__':
    
24.     print('示例1 输出：',solve([3,2,4],2))
    
25.     print('示例2 输出：',solve([3,2,4],3))
    

复制代码

塔利班

Stubborn 发表于 2020-1-5 22:31
对了 ，班利塔，还有可亲可爱可敬的版主大人。请教一代码。用来素数求和的，有点看不懂过程，为什么，能 ...

从和里逐步剔除合数，你可以每次打印下v//p,p,S,v

fan1993423

我就看你们神仙打架

溯影

这个算法真的不好整哦，整了好长时间没有整出来，看来要努力补习算法了。

zltzlt

阴阳神万物主 发表于 2020-1-5 21:00
嗯？也就是说，有人可以偷懒？
还是书可以撕开？

有人可以不复印。

zltzlt

阴阳神万物主 发表于 2020-1-6 00:00
我已经不知道怎样优化效率了，反正我是模拟我自己分配的思路。人只要够，就不断二分……
我是不会求这个的 ...

解答错误

输入：pages = [1,9,7,3,4,7], k = 3
输出：14
预期结果：11

zltzlt

Unicorn# 发表于 2020-1-5 23:03
终于写了俩，尽力优化了
第一个比较省空间，因为最早用DP做直接就超过深度限制了，所以卡得比较死，但是效 ...

输入 pages = []，k = 1 ；两个都会出错。

阴阳神万物主

zltzlt 发表于 2020-1-6 19:33
解答错误

输入：pages = [1,9,7,3,4,7], k = 3

让我看看还有什么数据能错。

1. def solve(pages:'list of int',k:int)->int:
   
2.     t = [sum(pages)]
   
3.     p = [pages[:]]
   
4.     while len(p) < k and len(p)<len(pages):
   
5.         m = max(t)
   
6.         i = t.index(m)
   
7.         if len(p[i])==1:
   
8.             break
   
9.         each = []
   
10.         l = 0
    
11.         while l < m:
    
12.             m -= p[i][0]
    
13.             l += p[i][0]
    
14.             each.append(p[i].pop(0))
    
15.         else:
    
16.             if max(l-each[-1],m+each[-1]) < max(l,m):
    
17.                 l -= each[-1]
    
18.                 p[i].insert(0,each.pop())
    
19.         p.insert(i,each)
    
20.         t[i] -= l
    
21.         t.insert(i,l)
    
22.     else:
    
23.         m = max(t)
    
24.         i = t.index(m)
    
25.         if i:
    
26.             if max(t[i-1]+p[i][0],m-p[i][0]) < max(t[i-1],m):
    
27.                 t[i-1] += p[i][0]
    
28.                 t[i] -= p[i][0]
    
29.                 p[i-1].append(p[i].pop(0))
    
30.     #print('调试',t,p)
    
31.     return max(t)
    
32. if __name__ == '__main__':
    
33.     print('示例1 输出：',solve([3,2,4],2))
    
34.     print('示例2 输出：',solve([3,2,4],3))
    

复制代码