Commit83db1dd

committed

upd

1 parentf5488aa commit83db1ddCopy full SHA for 83db1dd

File tree

+142

-0

lines changed

+142

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1 @@`
	`1`	`+git aa&& git ci -m'upd'&& git push`

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+classSolution:`
	`2`	`+defcombinationSum2(self,candidates:List[int],target:int)->List[List[int]]:`
	`3`	`+res= []`
	`4`	`+candidates.sort()`
	`5`	`+`
	`6`	`+defdfs(i,cur,total):`
	`7`	`+iftotal==target:`
	`8`	`+res.append(cur.copy())`
	`9`	`+return`
	`10`	`+ifi>=len(candidates)ortotal>target:`
	`11`	`+return`
	`12`	`+`
	`13`	`+cur.append(candidates[i])`
	`14`	`+`
	`15`	`+# i+1, because same number can not be chosen again`
	`16`	`+dfs(i+1,cur,total+candidates[i])`
	`17`	`+cur.pop()`
	`18`	`+`
	`19`	`+# skip the same number`
	`20`	`+whilei+1<len(candidates)andcandidates[i+1]==candidates[i]:`
	`21`	`+i+=1`
	`22`	`+dfs(i+1,cur,total)`
	`23`	`+`
	`24`	`+dfs(0, [],0)`
	`25`	`+`
	`26`	`+returnres`

Lines changed: 54 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,54 @@`
	`1`	`+classSolution:`
	`2`	`+defrecursive_neetcode_github(self,nums:List[int])->List[List[int]]:`
	`3`	`+res= []`
	`4`	`+`
	`5`	`+# base case`
	`6`	`+iflen(nums)==1:`
	`7`	`+return [nums[:]]# nums[:] is a deep copy`
	`8`	`+`
	`9`	`+foriinrange(len(nums)):`
	`10`	`+n=nums.pop(0)`
	`11`	`+perms=self.permute(nums)`
	`12`	`+`
	`13`	`+forperminperms:`
	`14`	`+perm.append(n)`
	`15`	`+res.extend(perms)`
	`16`	`+nums.append(n)`
	`17`	`+returnres`
	`18`	`+`
	`19`	`+defrecursive_neetcode_youtube(self,nums:List[int])->List[List[int]]:`
	`20`	`+iflen(nums)==0:`
	`21`	`+return [[]]`
	`22`	`+`
	`23`	`+perms=self.permute(nums[1:])`
	`24`	`+res= []`
	`25`	`+`
	`26`	`+forpinperms:`
	`27`	`+foriinrange(len(p)+1):# may insert to tail: +1`
	`28`	`+p_copy=p.copy()`
	`29`	`+p_copy.insert(i,nums[0])`
	`30`	`+res.append(p_copy)`
	`31`	`+`
	`32`	`+returnres`
	`33`	`+`
	`34`	`+defnon_recursive(self,nums:List[int])->List[List[int]]:`
	`35`	`+perms= [[]]`
	`36`	`+`
	`37`	`+forninnums:`
	`38`	`+new_perms= []`
	`39`	`+forpinperms:`
	`40`	`+foriinrange(len(p)+1):`
	`41`	`+p_copy=p.copy()`
	`42`	`+p_copy.insert(i,n)`
	`43`	`+new_perms.append(p_copy)`
	`44`	`+perms=new_perms`
	`45`	`+`
	`46`	`+returnperms`
	`47`	`+`
	`48`	`+`
	`49`	`+defpermute(self,nums:List[int])->List[List[int]]:`
	`50`	`+# res = self.recursive_neetcode_github(nums)`
	`51`	`+# res = self.recursive_neetcode_youtube(nums)`
	`52`	`+res=self.non_recursive(nums)`
	`53`	`+`
	`54`	`+returnres`

Lines changed: 21 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,21 @@`
	`1`	`+classSolution:`
	`2`	`+defsubsetsWithDup(self,nums:List[int])->List[List[int]]:`
	`3`	`+res= []`
	`4`	`+nums.sort()`
	`5`	`+subset= []`
	`6`	`+`
	`7`	`+defdfs(i):`
	`8`	`+ifi>=len(nums):`
	`9`	`+res.append(subset.copy())`
	`10`	`+return`
	`11`	`+`
	`12`	`+subset.append(nums[i])`
	`13`	`+dfs(i+1)`
	`14`	`+subset.pop()`
	`15`	`+whilei+1<len(nums)andnums[i+1]==nums[i]:`
	`16`	`+i+=1`
	`17`	`+dfs(i+1)`
	`18`	`+`
	`19`	`+dfs(0)`
	`20`	`+returnres`
	`21`	`+`

Lines changed: 40 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,40 @@`
	`1`	`+classSolution:`
	`2`	`+"""`
	`3`	`+ @param rooms: m x n 2D grid`
	`4`	`+ @return: nothing`
	`5`	`+ """`
	`6`	`+`
	`7`	`+defwalls_and_gates(self,rooms:List[List[int]]):`
	`8`	`+ROWS,COLS=len(rooms),len(rooms[0])`
	`9`	`+q= []`
	`10`	`+visited=set()`
	`11`	`+`
	`12`	`+defvisit_room(r,c,dist):`
	`13`	`+if (`
	`14`	`+notrinrange(ROWS)or`
	`15`	`+notcinrange(COLS)or`
	`16`	`+ (r,c)invisitedor`
	`17`	`+rooms[r][c]==-1`
	`18`	`+ ):`
	`19`	`+return`
	`20`	`+`
	`21`	`+visited.add((r,c))`
	`22`	`+q.append((r,c))`
	`23`	`+rooms[r][c]=dist`
	`24`	`+`
	`25`	`+# get all gates`
	`26`	`+forrinrange(ROWS):`
	`27`	`+forcinrange(COLS):`
	`28`	`+ifrooms[r][c]==0:`
	`29`	`+q.append((r,c))`
	`30`	`+visited.add((r,c))`
	`31`	`+`
	`32`	`+dist=0`
	`33`	`+whileq:`
	`34`	`+qlength=len(q)`
	`35`	`+dist+=1`
	`36`	`+for_inrange(qlength):`
	`37`	`+r,c=q.pop(0)`
	`38`	`+fordr,dcin [[-1,0], [1,0], [0,-1], [0,1]]:`
	`39`	`+# visit each adjacent`
	`40`	`+visit_room(r+dr,c+dc,dist)`

Comments

(0)