备战菊厂笔试3

15.三数之和

15. 三数之和

1.DFS组合

注意：在threeSum里面的dfs里更新ans值，不是global，因为global是用来声明一个变量在模块级别（全局作用域）

这里我们只是修改该嵌套函数的外层函数的变量，用的是nonlocal（这个变量并不是全局变量）

而且其实这道题不用声明，因为append是对本身内容修改，而不是赋值

class Solution:def threeSum(self, nums):l=len(nums)vis=[0]*lans=[]def dfs(step):#global ansif sum(vis)==3:lis=[]for i in range(l):if vis[i]:lis.append(nums[i])lis.sort()if lis not in ans:if not sum(lis):ans.append(lis)returnif step==l:returnvis[step]=1dfs(step+1)vis[step]=0dfs(step+1)dfs(0)return ans
if __name__=='__main__':nums = [-1,0,1,2,-1,-4]sol=Solution()ans=sol.threeSum(nums)print(ans)

但是TLE了 

2.用combinations

注意是从 itertools（迭代器）里面导入

from itertools import combinations

这道题有一个难点就是去重，第一个想法就是set

那么怎么调整元组的顺序来实现set去重呢？可以先转为 list 然后 sort 接着再转为 tuple 进行add（因为 set 不能接受 list）

from itertools import combinationsclass Solution:def threeSum(self, nums):ans=set()l=combinations(nums,3)for i in l:if sum(i)==0:i=list(i)i.sort()i=tuple(i)ans.add(i)lis=[]for i in ans:lis.append(list(i))return lis
'''
if __name__=='__main__':nums = [-1,0,1,2,-1,-4]sol=Solution()ans=sol.threeSum(nums)lis=[]for i in ans:lis.append(list(i))print(lis)
'''

其实这里不用sort方法，可以直接sorted元组从而避免list（）

虽然比DFS快，但还是在最后几个TLE了

3.双指针-去重剪枝

让我们好好再利用一下“不重复”

将这道题的选择用DFS树形结构展开的话，这颗树从左往右的选择是变少的，是一颗左偏树

那么既然后面的比前面的选择少，那么如果我在前面已经判断过元素 i 了，后面又碰到 i ，那么我是不是不用判断 i 了？，因为后面 i 的所有情况都被前面的 i 所包含了

后面两个元素的选择也是同理，需要跳过重复的 left 和 right

结构和二分查找类似，如果和小了，就让 l 变大

class Solution:def threeSum(self, nums):nums.sort()#排序，方便后面去重lenn=len(nums)ans=[]for i in range(lenn-2):#-2:得给后面两个元素留位置if i>0 and nums[i]==nums[i-1]:#注意得去掉i=0的情况，否则就0-1了continue#后面的和前面的相同l=i+1r=lenn-1while l<r:#双指针经典循环条件total=nums[i]+nums[l]+nums[r]#每一次判断if total==0:ans.append([nums[i],nums[l],nums[r]])#得在前一次为0的基础上才能跳过重复的l和rwhile l<r and nums[l]==nums[l+1]:l+=1while l<r and nums[r]==nums[r-1]:r-=1l+=1r-=1elif total<0:#和小了：l变大l+=1else:r-=1return ans

可以注意到，我们只在total==0的时候才进行去重，是因为只有total为0的时候才可能影响ans、违反题意；而且如果在total不为0的情况也进行去重，会导致跳过组合

17.电话号码的字母组合

17. 电话号码的字母组合

注意：样例中可能存在特判（要先每一个跑一下）

比如这题刚开始要特判空

class Solution:def letterCombinations(self, digits):if not digits:return []d={'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}s=list(digits)ans=[]l=len(s)def dfs(step,b):if step==l:ans.append(b)returnfor j in d[s[step]]:b2=bb2+=jdfs(step+1,b2)dfs(0,'')return ansif __name__=='__main__':digits='23'sol=Solution()ans=sol.letterCombinations(digits)print(ans)

而且这题根本不用b2来占用内存

直接 b+j 而不改变 b

            if step == len(digits):ans.append(b)returnfor j in d[digits[step]]:dfs(step + 1, b + j)

22.括号生成

有效：在）前必须有（

22. 括号生成

class Solution:def generateParenthesis(self, n):n1=nn2=nans=[]def dfs(step,b,N1):#N1存活的 ( 数if step==2*n:ans.append(b)returnif N1==0:dfs(step+1,b+'(',1)else:if b.count('(')<n:dfs(step+1,b+'(',N1+1)dfs(step+1,b+')',N1-1)dfs(0,'',0)return ans

用N1和N2两个变量维护，消去count优化时间复杂度 

class Solution:def generateParenthesis(self, n):n1=nn2=nans=[]def dfs(step,b,N1,N2):#N1:(数；N2:)数             #N1存活的 ( 数if step==2*n:ans.append(b)returnif N1-N2<0:returnelif N1-N2==0:dfs(step+1,b+'(',N1+1,N2)else:if N1<n:dfs(step+1,b+'(',N1+1,N2)dfs(step+1,b+')',N1,N2+1)dfs(0,'',0,0)return ans
if __name__=='__main__':n=3sol=Solution()ans=sol.generateParenthesis(n)print(ans)

动态规划

参考22. 括号生成 - 力扣（LeetCode）

反思：
首先，面向小白：什么是动态规划？在此题中，动态规划的思想类似于数学归纳法，当知道所有 i<n 的情况时，我们可以通过某种算法推算出 i=n 的情况。
本题最核心的思想是，考虑 i=n 时相比 n-1 组括号增加的那一组括号的位置。

思路：
当我们清楚所有 i<n 时括号的可能生成排列后，对与 i=n 的情况，我们考虑整个括号排列中最左边的括号。
它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号 "( )"，我们认为这一组是相比 n-1 增加进来的括号。

那么，剩下 n-1 组括号有可能在哪呢？

【这里是重点，请着重理解】

剩下的括号要么在这一组新增的括号内部，要么在这一组新增括号的外部（右侧）。

既然知道了 i<n 的情况，那我们就可以对所有情况进行遍历：

"(" + 【i=p时所有括号的排列组合】 + ")" + 【i=q时所有括号的排列组合】

其中 p + q = n-1，且 p q 均为非负整数。

事实上，当上述 p 从 0 取到 n-1，q 从 n-1 取到 0 后，所有情况就遍历完了。

注：上述遍历是没有重复情况出现的，即当 (p1,q1)≠(p2,q2) 时，按上述方式取的括号组合一定不同。

class Solution:def generateParenthesis(self, n: int) -> List[str]:if n == 0:return []total_l = []total_l.append([None])    # 0组括号时记为Nonetotal_l.append(["()"])    # 1组括号只有一种情况for i in range(2,n+1):    # 开始计算i组括号时的括号组合l = []        for j in range(i):    # 开始遍历 p q ，其中p+q=i-1 , j 作为索引now_list1 = total_l[j]    # p = j 时的括号组合情况now_list2 = total_l[i-1-j]    # q = (i-1) - j 时的括号组合情况for k1 in now_list1:  for k2 in now_list2:if k1 == None:k1 = ""if k2 == None:k2 = ""el = "(" + k1 + ")" + k2l.append(el)    # 把所有可能的情况添加到 l 中total_l.append(l)    # l这个list就是i组括号的所有情况，添加到total_l中，继续求解i=i+1的情况return total_l[n]

1224.最大相等频率

1224. 最大相等频率

按照题目要求有两种可能：

1.现存数*k + 1 == 总数

2.现存中有一个是 k+1 个，其他都是 k 个

那么我们用一个一个字典维护

用 collections 的 Counter 初始化各出现次数

然后对于每种情况设置两个flag，其中一个是判断独特的那个出现次数，一个是判断是否有可能

注意特判：dn-1：dn>1 如果dn为1：必符合条件return

from collections import Counter
class Solution:def maxEqualFreq(self, nums):su=len(nums)d=Counter(nums)dn=len(d)#现在存活数字的数量for i in range(su-1,0,-1):if dn==1:#特判！！！return i+1k1=(sum(d.values())-1)/(dn-1)k2=(sum(d.values())-1)/dn'''print(d)print(k)'''if int(k1)==k1:#可能1flag1=1flag2=1for j in d:if d[j]!=k1:if flag2:#只能有一次1flag2=0else:flag1=0breakif flag1:return i+1if int(k2)==k2:#可能2！！flag1=1flag2=1for j in d:if d[j]!=k2:if d[j]!=(k2+1):flag1=0breakelse:if flag2:flag2=0else:flag1=0breakif flag1:return i+1d[nums[i]]-=1if d[nums[i]]==0:del d[nums[i]]dn-=1if __name__=='__main__':nums=[1,1,1,2,2,2]'''d=Counter(nums)print(d)print(sum(d.values()))'''sol=Solution()ans=sol.maxEqualFreq(nums)print(ans)