Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2327992

Browse files
authored
Sri Hari: Batch-4/Neetcode-All/Added-articles (neetcode-gh#3773)
* Batch-4/Neetcode-All/Added-articles* Batch-4/Neetcode-All/Added-articles* Batch-4/Neetcode-All/Added-articles* Batch-4/Neetcode-All/Added-articles
1 parentae946f1 commit2327992

18 files changed

+8905
-0
lines changed

‎articles/best-team-with-no-conflicts.md‎

Lines changed: 649 additions & 0 deletions
Large diffs are not rendered by default.
Lines changed: 283 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,283 @@
1+
##1. Recursion
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defcountGoodStrings(self,low:int,high:int,zero:int,one:int) ->int:
8+
mod=10**9+7
9+
10+
defdfs(length):
11+
if length> high:
12+
return0
13+
res=1if length>= lowelse0
14+
res+= dfs(length+ zero)+ dfs(length+ one)
15+
return res% mod
16+
17+
return dfs(0)
18+
```
19+
20+
```java
21+
publicclassSolution {
22+
finalint mod=1_000_000_007;
23+
24+
publicintcountGoodStrings(intlow,inthigh,intzero,intone) {
25+
return dfs(low, high, zero, one,0);
26+
}
27+
28+
privateintdfs(intlow,inthigh,intzero,intone,intlength) {
29+
if (length> high)return0;
30+
int res= (length>= low)?1:0;
31+
res= (res+ dfs(low, high, zero, one, length+ zero))% mod;
32+
res= (res+ dfs(low, high, zero, one, length+ one))% mod;
33+
return res;
34+
}
35+
}
36+
```
37+
38+
```cpp
39+
classSolution {
40+
public:
41+
int countGoodStrings(int low, int high, int zero, int one) {
42+
const int mod = 1e9 + 7;
43+
44+
function<int(int)> dfs = [&](int length) {
45+
if (length > high) return 0;
46+
int res = (length >= low) ? 1 : 0;
47+
res = (res + dfs(length + zero)) % mod;
48+
res = (res + dfs(length + one)) % mod;
49+
return res;
50+
};
51+
52+
return dfs(0);
53+
}
54+
};
55+
```
56+
57+
```javascript
58+
classSolution {
59+
/**
60+
*@param{number}low
61+
*@param{number}high
62+
*@param{number}zero
63+
*@param{number}one
64+
*@return{number}
65+
*/
66+
countGoodStrings(low,high,zero,one) {
67+
constmod=1e9+7;
68+
69+
constdfs=length=> {
70+
if (length> high)return0;
71+
let res= length>= low?1:0;
72+
res= (res+dfs(length+ zero))% mod;
73+
res= (res+dfs(length+ one))% mod;
74+
return res;
75+
};
76+
77+
returndfs(0);
78+
}
79+
}
80+
```
81+
82+
::tabs-end
83+
84+
###Time & Space Complexity
85+
86+
* Time complexity: $O(2 ^ n)$
87+
* Space complexity: $O(n)$
88+
89+
>Where $n$ is equal to the given $high$ value.
90+
91+
---
92+
93+
##2. Dynamic Programming (Top-Down)
94+
95+
::tabs-start
96+
97+
```python
98+
classSolution:
99+
defcountGoodStrings(self,low:int,high:int,zero:int,one:int) ->int:
100+
mod=10**9+7
101+
dp= {}
102+
103+
defdfs(length):
104+
if length> high:
105+
return0
106+
if lengthin dp:
107+
return dp[length]
108+
109+
dp[length]=1if length>= lowelse0
110+
dp[length]+= dfs(length+ zero)+ dfs(length+ one)
111+
return dp[length]% mod
112+
113+
return dfs(0)
114+
```
115+
116+
```java
117+
publicclassSolution {
118+
finalint mod=1_000_000_007;
119+
privateint[] dp;
120+
121+
publicintcountGoodStrings(intlow,inthigh,intzero,intone) {
122+
dp=newint[high+1];
123+
Arrays.fill(dp,-1);
124+
return dfs(low, high, zero, one,0);
125+
}
126+
127+
privateintdfs(intlow,inthigh,intzero,intone,intlength) {
128+
if (length> high)return0;
129+
if (dp[length]!=-1)return dp[length];
130+
131+
dp[length]= (length>= low)?1:0;
132+
dp[length]= (dp[length]+ dfs(low, high, zero, one, length+ zero))% mod;
133+
dp[length]= (dp[length]+ dfs(low, high, zero, one, length+ one))% mod;
134+
return dp[length];
135+
}
136+
}
137+
```
138+
139+
```cpp
140+
classSolution {
141+
const int mod = 1e9 + 7;
142+
vector<int> dp;
143+
144+
public:
145+
int countGoodStrings(int low, int high, int zero, int one) {
146+
dp.assign(high + 1, -1);
147+
return dfs(low, high, zero, one, 0);
148+
}
149+
150+
private:
151+
int dfs(int low, int high, int zero, int one, int length) {
152+
if (length > high) return 0;
153+
if (dp[length] != -1) return dp[length];
154+
dp[length] = (length >= low) ? 1 : 0;
155+
dp[length] = (dp[length] + dfs(low, high, zero, one, length + zero)) % mod;
156+
dp[length] = (dp[length] + dfs(low, high, zero, one, length + one)) % mod;
157+
return dp[length];
158+
}
159+
};
160+
```
161+
162+
```javascript
163+
class Solution {
164+
/**
165+
* @param {number} low
166+
* @param {number} high
167+
* @param {number} zero
168+
* @param {number} one
169+
* @return {number}
170+
*/
171+
countGoodStrings(low, high, zero, one) {
172+
const mod = 1e9 + 7;
173+
const dp = new Array(high + 1).fill(-1);
174+
175+
const dfs = length => {
176+
if (length > high) return 0;
177+
if (dp[length] !== -1) return dp[length];
178+
dp[length] = length >= low ? 1 : 0;
179+
dp[length] = (dp[length] + dfs(length + zero)) % mod;
180+
dp[length] = (dp[length] + dfs(length + one)) % mod;
181+
return dp[length];
182+
};
183+
184+
return dfs(0);
185+
}
186+
}
187+
```
188+
189+
::tabs-end
190+
191+
###Time & Space Complexity
192+
193+
* Time complexity: $O(n)$
194+
* Space complexity: $O(n)$
195+
196+
> Where $n$ is equal to the given $high$ value.
197+
198+
---
199+
200+
##3. DynamicProgramming (Bottom-Up)
201+
202+
::tabs-start
203+
204+
```python
205+
classSolution:
206+
defcountGoodStrings(self,low:int,high:int,zero:int,one:int) ->int:
207+
dp= {0 :1 }
208+
mod=10**9+7
209+
210+
for iinrange(1, high+1):
211+
dp[i]= (dp.get(i- one,0)+ dp.get(i- zero,0))% mod
212+
213+
returnsum(dp[i]for iinrange(low, high+1))% mod
214+
```
215+
216+
```java
217+
publicclassSolution {
218+
publicintcountGoodStrings(intlow,inthigh,intzero,intone) {
219+
int[] dp=newint[high+1];
220+
int mod=1_000_000_007, res=0;
221+
dp[0]=1;
222+
223+
for (int i=1; i<= high; i++) {
224+
if (i>= zero) dp[i]= (dp[i]+ dp[i- zero])% mod;
225+
if (i>= one) dp[i]= (dp[i]+ dp[i- one])% mod;
226+
if (i>= low) res= (res+ dp[i])% mod;
227+
}
228+
return res;
229+
}
230+
}
231+
```
232+
233+
```cpp
234+
classSolution {
235+
public:
236+
int countGoodStrings(int low, int high, int zero, int one) {
237+
vector<int> dp(high + 1);
238+
int mod = 1e9 + 7, res = 0;
239+
dp[0] = 1;
240+
241+
for (int i = 1; i <= high; i++) {
242+
if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % mod;
243+
if (i >= one) dp[i] = (dp[i] + dp[i - one]) % mod;
244+
if (i >= low) res = (res + dp[i]) % mod;
245+
}
246+
return res;
247+
}
248+
};
249+
```
250+
251+
```javascript
252+
classSolution {
253+
/**
254+
*@param{number}low
255+
*@param{number}high
256+
*@param{number}zero
257+
*@param{number}one
258+
*@return{number}
259+
*/
260+
countGoodStrings(low,high,zero,one) {
261+
constmod=1e9+7;
262+
constdp=newInt32Array(high+1);
263+
let res=0;
264+
dp[0]=1;
265+
266+
for (let i=1; i<= high; i++) {
267+
if (i>= zero) dp[i]= (dp[i]+ dp[i- zero])% mod;
268+
if (i>= one) dp[i]= (dp[i]+ dp[i- one])% mod;
269+
if (i>= low) res= (res+ dp[i])% mod;
270+
}
271+
return res;
272+
}
273+
}
274+
```
275+
276+
::tabs-end
277+
278+
###Time & Space Complexity
279+
280+
* Time complexity: $O(n)$
281+
* Space complexity: $O(n)$
282+
283+
>Where $n$ is equal to the given $high$ value.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp