interview_preparation&backtrack

interview_preparation&backtrack_divided

1. subsets

 1 import copy
 2 class Solution:
 3     def subsets(self,nums):
 4         res=[[]]
 5         for n in nums:
 6             size=len(res)
 7             for i in range(size):
 8                 res.append(copy.deepcopy(res[i]))
 9                 res[-1].append(n)
10         return res
11 
12 nums=[1,2,3]
13 print(Solution().subsets(nums))

with same element

 1 import copy
 2 class Solution:
 3     def subsets(self,nums):
 4         res=[[]]
 5         for n in nums:
 6             size=len(res)
 7             for i in range(size):
 8                 res.append(copy.deepcopy(res[i]))
 9                 res[-1].append(n)
10         return res
11 
12 nums=[1,1,3]
13 res=Solution().subsets(nums)
14 res_=[tuple(tmp) for tmp in res]
15 res_=set(res_)
16 res=[list(tmp) for tmp in res_]
17 print(res)

bit op

___=000

__C=001

_B_=010

A__=100

_BC=011

AB_=110

A_C=101

ABC=111

1~2**n中哪些位为1，说明该位对应的元素在该子集中

 1 '''bit op'''
 2 class Solution:
 3     def subsets(self,nums):
 4         res=[]
 5         n=2**len(nums)
 6 
 7         for i in range(n):
 8             tmp=[]
 9             for j in range(len(nums)):
10                 if(i&(1<<j)):
11                     tmp.append(nums[j])
12             res.append(tmp)
13             
14         return res
15             
16 nums=[1,2,3]
17 res=Solution().subsets(nums)
18 print(res)

3. combination sum + same ele in nums

 1 class Solution:
 2     def dfs(self,nums,target,idx,path):
 3         if(sum(path)==target):
 4             self.res.append(path)
 5             return
 6 
 7         for i in range(idx,len(nums)):
 8             if i>idx and nums[i]==nums[idx]:
 9                 continue
10 
11             self.dfs(nums,target,i+1,path+[nums[i]])
12             
13 
14     def combSum(self,nums,target):
15         if(len(nums)==0):
16             return [[]]
17         nums.sort()
18         self.res=[]
19         self.dfs(nums,target,0,[])
20 
21         return self.res
22 
23 nums=[10,1,2,7,6,1,5]
24 print(Solution().combSum(nums,8))

4. generate valid parentheses

 1 class Solution:
 2     def dfs(self,n,left,right,path):
 3         if(right==n):
 4             self.res.append(path)
 5             return
 6         
 7         if(left<n):
 8             self.dfs(n,left+1,right,path+"(")
 9         
10         if(right<left):
11             self.dfs(n,left,right+1,path+")")
12 
13     def generateParenthesis(self,n):
14         if(n==0):
15             return []
16         self.res=[]
17         
18         self.dfs(n,0,0,"")
19 
20         return self.res
21 
22 n=3
23 s=Solution()
24 res=s.generateParenthesis(n)
25 print(res)

5. reversed pair in nums

 1 class Solution:
 2     def merge(self,nums,left,mid,right):
 3         i,j=left,mid+1
 4         new_nums=[]
 5         
 6         while(i<=mid and j<=right):
 7             if(nums[i]<=nums[j]):
 8                 new_nums.append(nums[i])
 9                 i+=1
10             else:
11                 self.res+=mid-i+1
12                 new_nums.append(nums[j])
13                 j+=1
14 
15         while(i<=mid):
16             new_nums.append(nums[i])
17             i+=1
18         
19         while(j<=right):
20             new_nums.append(nums[j])
21             j+=1
22 
23         for i in range(len(new_nums)):
24             nums[i+left]=new_nums[i]
25         
26 
27     def mergeSort(self,nums,left,right):
28 
29         self.res=0      
30 
31         if(left<right):
32             mid=left+(right-left)//2  
33             print(nums[left:mid+1],nums[mid+1:right+1])
34             self.mergeSort(nums,left,mid)
35             self.mergeSort(nums,mid+1,right)
36 
37             self.merge(nums,left,mid,right)
38         
39         print(self.res)
40         return nums
41 
42 
43 
44 nums=[1,2,7,82,2,3,5,1]
45 # nums=[5,1]
46 print(Solution().mergeSort(nums,0,len(nums)-1))

6. permuation s witth no duplicated elements

 1 class Solution(object):
 2     def permute(self, nums):
 3         res=[[]]
 4         for n in nums:
 5             res_tmp=[]
 6             for perm in res:
 7                 for i in range(len(perm)+1):
 8                     # res_tmp.append(perm[:i]+[n]+perm[i:])
 9                     perm.insert(i,n)
10                     res_tmp.append(perm[::-1])
11                     perm.pop(i)         
12             res=res_tmp
13         return res