备战菊厂笔试4

目次
39.组合总和 
回溯（单向剪枝）
3102.最小化曼哈顿距离
利用曼哈顿距离的性子

3163.压缩字符串3
46.全分列
53.最大子数组和

---

39.组合总和 

39. 组合总和
注意：
set不能添加list得加元组
元组不可修改
sorted后得赋值

1. class Solution:
2.     def combinationSum(self, candidates,target):
4.         ans=set()
5.         def fenjie(num,se):
6.             if num==0:
7.                 se=tuple(sorted(se))
8.                 ans.add(se)
9.                 return
10.             if num<0:
11.                 return
12.             
13.             for i in candidates:
14.                 se2=tuple(list(se)+[i])
15.                 fenjie(num-i,se2)
17.         fenjie(target,())
18.         return [list(x) for x in ans]  # 转换为题目要求的格式
19. if __name__=='__main__':
20.     candidates = [2,3,6,7];target = 7
22.     sol=Solution()
23.     ans=sol.combinationSum(candidates,target)
24.     print(ans)

复制代码

固然过了，但这道题更好的办法是
回溯（单向剪枝）

回溯是一种 试探+撤销 的计谋
我们将这问题看成一颗搜索树，每个节点体现一种选择路径，那么我们从根节点开始一步步试探性地往下走，直到走到满足条件的叶子节点，那么就把路径参加答案
我们用start控制开始下标，单向（升序）地往后面选（注意同一个数字可以重复利用，那么下一层就是从当前start开始

1. start=0, path=[], remaining=7
2. ├── 选2 → path=[2], remaining=5
3. │   ├── 选2 → path=[2,2], remaining=3
4. │   │   ├── 选2 → path=[2,2,2], remaining=1
5. │   │   │   └── 选2 → path=[2,2,2,2], remaining=-1 ❌ 超了，返回
6. │   │   │   └── 选3 → path=[2,2,2,3], remaining=-2 ❌ 超了，返回
7. │   │   ├── 选3 → path=[2,2,3], remaining=0 ✅ 找到结果
8. │   │   └── ...
9. │   └── 选3 → path=[2,3], remaining=2
10. ├── 选3 → path=[3], remaining=4
11. │   ├── 选3 → path=[3,3], remaining=1
12. │   └── ...
13. ├── 选6 → path=[6], remaining=1
14. ├── 选7 → path=[7], remaining=0 ✅ 找到结果

复制代码

1. class Solution:
2.     def combinationSum(self, candidates, target):
3.         res = []
4.         candidates.sort()
6.         def backtrack(start, path, remaining):
7.             if remaining == 0:
8.                 res.append(path[:])  # 找到一个合法组合，加入结果
9.                 return
10.             if remaining < 0:
11.                 return  # 超过了目标值，剪枝
13.             for i in range(start, len(candidates)):
14.                 path.append(candidates[i])
15.                 backtrack(i, path, remaining - candidates[i])  # 可重复选，从 i 开始
16.                 path.pop()  # 撤销上一步选择，继续尝试下一个
17.                
18.         backtrack(0, [], target)
19.         return res

复制代码

此中 path,pop() 有点像 恢复vis[ ] = 0

3102.最小化曼哈顿距离

3102. 最小化曼哈顿距离
本来我想用一半的二维矩阵来优化空间复杂度，但是这样反而得不偿失了，太绕了连正确答案都跑不出来，还是正常用二维的
这题的主要思路的思路就是枚举删的点，然后再枚举所有点的所有边（撤除当时删的点的），进行体现

1. '''
2. class Solution:
3.     def minimumDistance(self, points):
4.         n=len(points)
5.         ma=[[0]*i for i in range(n-1,0,-1)]
6.         for i in range(n-1):
7.             for j in range(i+1,n):
8.                 dis=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])
9.                 ma[i][j-i-1]=dis
10.         print(ma)
12.         ans=float('inf')
13.         for i in range(n):#去掉的点
14.             now=-1
15.             for j in range(n):#除去掉的点外的点出发到其他点的距离
16.                 if j==i:
17.                     continue
18.                 else:
19.                     for a in range(n-j-1):
20.                         if a+1==i:continue
21.                         now=max(now,ma[j][a])
22.                     for b in range(j):
23.                         if b==i:continue
24.                         now=max(now,ma[b][j-b-1])
25.                     ans=min(ans,now)
26.         return ans
27. '''
28. class Solution:
29.     def minimumDistance(self, points):
30.         import itertools
31.         n = len(points)
32.         ans = float('inf')
33.         for skip in range(n):  # 枚举删除哪一个点
34.             max_dist = 0
35.             remaining = [points[i] for i in range(n) if i != skip]
36.             for i in range(len(remaining)):
37.                 for j in range(i + 1, len(remaining)):
38.                     x1, y1 = remaining[i]
39.                     x2, y2 = remaining[j]
40.                     dist = abs(x1 - x2) + abs(y1 - y2)
41.                     max_dist = max(max_dist, dist)
42.             ans = min(ans, max_dist)
43.         return ans
44. if __name__=='__main__':
45.     points=[[3,10],[5,15],[10,2],[4,4]]
47.     sol=Solution()
48.     ans=sol.minimumDistance(points)
49.     print(ans)
50.         

复制代码

但是这样暴力肯定会TLE
利用曼哈顿距离的性子

1. class Solution:
2.     def minimumDistance(self, points):
3.         n = len(points)
4.         vals = [[] for _ in range(4)]  # 保存四种变换
6.         for i, (x, y) in enumerate(points):
7.             vals[0].append((x + y, i))
8.             vals[1].append((x - y, i))
9.             vals[2].append((-x + y, i))
10.             vals[3].append((-x - y, i))
12.         candidates = set()
13.         for arr in vals:
14.             arr.sort()
15.             candidates.add(arr[0][1])     # 最小值对应点
16.             candidates.add(arr[-1][1])    # 最大值对应点
18.         def get_max_dist(skip):
19.             max_val = 0
20.             for arr in vals:
21.                 temp = [(val, idx) for val, idx in arr if idx != skip]
22.                 max_val = max(max_val, temp[-1][0] - temp[0][0])
23.             return max_val
25.         return min(get_max_dist(i) for i in candidates)

复制代码

3163.压缩字符串3

3163. 压缩字符串 III
主要用到 strip

1. class Solution:
2.     def compressedString(self, word: str) -> str:
3.         comp=''
4.         l=len(word)
5.         while word:
6.             '''
7.             i=0
8.             while word[i]==word[i+1]:#前缀
9.                 i+=1
10.             comp+=str(i+1)+word[i]
11.             '''
12.             c=word[0]
13.             
14.             word=word.lstrip(c)# lstrip :  删除左边连续子串直到碰到其他字符
15.             #print(word)
16.             l2=len(word)
17.             d=l-l2
18.             if d>9:
19.                 d1=d//9
20.                 d2=d%9
21.                 comp+=('9'+c)*d1
22.                 if d2:
23.                     comp+=str(d2)+c
24.             else:
25.                 comp+=str(d)+c
26.             l=l2
27.         return comp
29. if __name__=='__main__':
30.     word='abcde'
32.     sol=Solution()
33.     ans=sol.compressedString(word)
34.     print(ans)

复制代码

 灵神的代码
此中enumerate是同时提取索引和元素        （素数筛内里用的也是enumerate）
divmod( a,b )返回( a//b,a%b )

1. class Solution:
2.     def compressedString(self, word: str) -> str:
3.         t = []
4.         i0 = -1
5.         for i, c in enumerate(word):
6.             if i + 1 == len(word) or c != word[i + 1]:
7.                 k, rem = divmod(i - i0, 9)
8.                 t.append(("9" + c) * k)
9.                 if rem:
10.                     t.append(str(rem))
11.                     t.append(c)
12.                 i0 = i
13.         return ''.join(t)
15. 作者：灵茶山艾府
16. 链接：https://leetcode.cn/problems/string-compression-iii/solutions/2790666/mo-ni-pythonjavacgo-by-endlesscheng-3hk7/
17. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

46.全分列

 注意itertools.permutations出来的是元组，得list

1. from itertools import permutations
3. class Solution:
4.     def permute(self, nums):
5.         l=len(nums)
6.         ans=permutations(nums,l)
7.         lis=[]
8.         for i in ans:
9.             lis.append(list(i))
10.         return lis
12. if __name__=='__main__':
13.     nums=[1,2,3]
15.     sol=Solution()
16.     ans=sol.permute(nums)
17.     print(ans)

复制代码

53.最大子数组和

我的第一想法是用前缀和之差，于是我直接暴力体现了

1. class Solution:
2.     def maxSubArray(self, nums):
3.         pre=[[0,0]]
4.         l=len(nums)
6.         for i,k in enumerate(nums):
7.             #print(i,k)
8.             pre.append([pre[-1][0]+k,pre[-1][1]+1])
9.         
10.         #print(pre)
12.         ans=-float('inf')
13.         for su,n in pre:
14.             for j in range(n):
15.                 now=su-pre[j][0]
16.                 ans=max(ans,now)
17.         return ans
18.             
20. if __name__=='__main__':
21.     nums=[-2,1,-3,4,-1,2,1,-5,4]
23.     sol=Solution()
24.     ans=sol.maxSubArray(nums)
25.     print(ans)

复制代码

因为 最大值= -最小值，所以我们实在可以在一边遍历数组计算前缀和的同时一边维护前缀和的最小值
请注意，由于标题要求子数组不能为空，应当先计算前缀和-最小前缀和，再更新最小前缀和。相称于不能在同一天买入股票又卖出股票。假如先更新最小前缀和，再计算前缀和-最小前缀和，就会把空数组的元素和 0 算入答案。（来自灵神）

1. class Solution:
2.     def maxSubArray(self, nums: List[int]) -> int:
3.         ans = -inf
4.         min_pre_sum = pre_sum = 0
5.         for x in nums:
6.             pre_sum += x  # 当前的前缀和
7.             ans = max(ans, pre_sum - min_pre_sum)  # 减去前缀和的最小值
8.             min_pre_sum = min(min_pre_sum, pre_sum)  # 维护前缀和的最小值
9.         return ans

复制代码