Commitc3ef0ff

authored

Merge pull requestneetcode-gh#3239 from giggling-ginger/ginger

1397 solution

2 parents57ea8c1 +c2f6085 commitc3ef0ffCopy full SHA for c3ef0ff

File tree

+62

-0

lines changed

+62

-0

lines changed

Lines changed: 14 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,3 +8,17 @@ def countBits(self, n: int) -> List[int]:`
`8`	`8`	`offset=i`
`9`	`9`	`dp[i]=1+dp[i-offset]`
`10`	`10`	`returndp`
	`11`	`+`
	`12`	`+# Another dp solution`
	`13`	`+classSolution2:`
	`14`	`+defcountBits(self,n:int)->List[int]:`
	`15`	`+res= [0]* (n+1)`
	`16`	`+foriinrange(1,n+1):`
	`17`	`+ifi%2==1:`
	`18`	`+res[i]=res[i-1]+1`
	`19`	`+else:`
	`20`	`+res[i]=res[i//2]`
	`21`	`+returnres`
	`22`	`+# This solution is based on the division of odd and even numbers.`
	`23`	`+# I think it's easier to understand.`
	`24`	`+# This is my full solution, covering the details: https://leetcode.com/problems/counting-bits/solutions/4411054/odd-and-even-numbers-a-easier-to-understanding-way-of-dp/`

Lines changed: 48 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,48 @@`
	`1`	`+classSolution:`
	`2`	`+deffindGoodStrings(self,n:int,s1:str,s2:str,evil:str)->int:`
	`3`	`+a=ord('a')`
	`4`	`+z=ord('z')`
	`5`	`+`
	`6`	`+arr_e=list(map(ord,evil))`
	`7`	`+len_e=len(evil)`
	`8`	`+next= [0]*len_e`
	`9`	`+`
	`10`	`+foriinrange(1,len_e):`
	`11`	`+j=next[i-1]`
	`12`	`+whilej>0andevil[i]!=evil[j]:`
	`13`	`+j=next[j-1]`
	`14`	`+ifevil[i]==evil[j]:`
	`15`	`+next[i]=j+1`
	`16`	`+`
	`17`	`+defgood(s):`
	`18`	`+arr=list(map(ord,s))`
	`19`	`+len_a=len(arr)`
	`20`	`+`
	`21`	`+@cache`
	`22`	`+deff(i,skip,reach,e):`
	`23`	`+ife==len_e:`
	`24`	`+return0`
	`25`	`+ifi==len_a:`
	`26`	`+return0ifskipelse1`
	`27`	`+`
	`28`	`+limit=arr[i]ifreachelsez`
	`29`	`+ans=0`
	`30`	`+`
	`31`	`+ifskip:`
	`32`	`+ans+=f(i+1,True,False,0)`
	`33`	`+`
	`34`	`+forcinrange(a,limit+1):`
	`35`	`+ee=e`
	`36`	`+whileee>0andarr_e[ee]!=c:`
	`37`	`+ee=next[ee-1]`
	`38`	`+`
	`39`	`+ifarr_e[ee]==c:`
	`40`	`+ee+=1`
	`41`	`+`
	`42`	`+ans+=f(i+1,False,reachandc==limit,ee)`
	`43`	`+`
	`44`	`+returnans%int(1e9+7)`
	`45`	`+`
	`46`	`+returnf(0,True,True,0)`
	`47`	`+`
	`48`	`+return (good(s2)-good(s1)+int(evilnotins1))%int(1e9+7)`

Comments

(0)