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

Commitd908bc0

Browse files
authored
Batch-5/Neetcode-Courses/Added-articles (neetcode-gh#3808)
1 parent3891fdd commitd908bc0

10 files changed

+4422
-3
lines changed

‎articles/build-a-matrix-with-conditions.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -489,7 +489,7 @@ class Solution {
489489
indegree[v]++;
490490
}
491491

492-
constqueue=[];
492+
constqueue=newQueue();
493493
constorder= [];
494494

495495
for (let i=1; i<= k; i++) {
@@ -498,8 +498,8 @@ class Solution {
498498
}
499499
}
500500

501-
while (queue.length) {
502-
constnode=queue.shift();
501+
while (!queue.isEmpty()) {
502+
constnode=queue.pop();
503503
order.push(node);
504504
for (constneiof adj[node]) {
505505
indegree[nei]--;

‎articles/first-bad-version.md

Lines changed: 373 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,373 @@
1+
##1. Brute Force (Linear Search)
2+
3+
::tabs-start
4+
5+
```python
6+
# The isBadVersion API is already defined for you.
7+
# def isBadVersion(version: int) -> bool:
8+
9+
classSolution:
10+
deffirstBadVersion(self,n:int) ->int:
11+
for iinrange(1, n):
12+
if isBadVersion(i):
13+
return i
14+
return n
15+
```
16+
17+
```java
18+
/* The isBadVersion API is defined in the parent class VersionControl.
19+
boolean isBadVersion(int version);*/
20+
21+
publicclassSolutionextendsVersionControl {
22+
publicintfirstBadVersion(intn) {
23+
for (int i=1; i< n; i++) {
24+
if (isBadVersion(i)) {
25+
return i;
26+
}
27+
}
28+
return n;
29+
}
30+
}
31+
```
32+
33+
```cpp
34+
// The API isBadVersion is defined for you.
35+
// bool isBadVersion(int version);
36+
37+
classSolution {
38+
public:
39+
int firstBadVersion(int n) {
40+
for (int i = 1; i < n; i++) {
41+
if (isBadVersion(i)) {
42+
return i;
43+
}
44+
}
45+
return n;
46+
}
47+
};
48+
```
49+
50+
```javascript
51+
// The isBadVersion API is already defined in the VersionControl class.
52+
// isBadVersion(version: number): boolean
53+
54+
class Solution extends VersionControl {
55+
/**
56+
* @param {number} n Total versions
57+
* @return {number} The first bad version
58+
*/
59+
firstBadVersion(n) {
60+
for (let i = 1; i < n; i++) {
61+
if (this.isBadVersion(i)) {
62+
return i;
63+
}
64+
}
65+
return n;
66+
}
67+
}
68+
```
69+
70+
::tabs-end
71+
72+
###Time & Space Complexity
73+
74+
* Time complexity: $O(n)$
75+
* Space complexity: $O(1)$ extra space.
76+
77+
---
78+
79+
##2. Recursive Binary Search
80+
81+
::tabs-start
82+
83+
```python
84+
# The isBadVersion API is already defined for you.
85+
# def isBadVersion(version: int) -> bool:
86+
87+
classSolution:
88+
deffirstBadVersion(self,n:int) ->int:
89+
defhelper(l,r):
90+
if l> r:
91+
return l
92+
m= l+ (r- l)//2
93+
if isBadVersion(m):
94+
return helper(l, m-1)
95+
else:
96+
return helper(m+1, r)
97+
98+
return helper(1, n)
99+
```
100+
101+
```java
102+
/* The isBadVersion API is defined in the parent class VersionControl.
103+
boolean isBadVersion(int version);*/
104+
105+
publicclassSolutionextendsVersionControl {
106+
publicintfirstBadVersion(intn) {
107+
return helper(1, n);
108+
}
109+
110+
privateinthelper(intl,intr) {
111+
if (l> r) {
112+
return l;
113+
}
114+
int m= l+ (r- l)/2;
115+
if (isBadVersion(m)) {
116+
return helper(l, m-1);
117+
}else {
118+
return helper(m+1, r);
119+
}
120+
}
121+
}
122+
```
123+
124+
```cpp
125+
// The API isBadVersion is defined for you.
126+
// bool isBadVersion(int version);
127+
128+
classSolution {
129+
public:
130+
int firstBadVersion(int n) {
131+
return helper(1, n);
132+
}
133+
134+
private:
135+
int helper(int l, int r) {
136+
if (l > r) {
137+
return l;
138+
}
139+
int m = l + (r - l) / 2;
140+
if (isBadVersion(m)) {
141+
return helper(l, m - 1);
142+
} else {
143+
return helper(m + 1, r);
144+
}
145+
}
146+
};
147+
```
148+
149+
```javascript
150+
// The isBadVersion API is already defined in the VersionControl class.
151+
// isBadVersion(version: number): boolean
152+
153+
class Solution extends VersionControl {
154+
/**
155+
* @param {number} n Total versions
156+
* @return {number} The first bad version
157+
*/
158+
firstBadVersion(n) {
159+
const helper = (l, r) => {
160+
if (l > r) {
161+
return l;
162+
}
163+
const m = Math.floor(l + (r - l) / 2);
164+
if (this.isBadVersion(m)) {
165+
return helper(l, m - 1);
166+
} else {
167+
return helper(m + 1, r);
168+
}
169+
};
170+
return helper(1, n);
171+
}
172+
}
173+
```
174+
175+
::tabs-end
176+
177+
###Time & Space Complexity
178+
179+
* Time complexity: $O(\log n)$
180+
* Space complexity: $O(\log n)$ for recursion stack.
181+
182+
---
183+
184+
##3. Iterative Binary Search
185+
186+
::tabs-start
187+
188+
```python
189+
# The isBadVersion API is already defined for you.
190+
# def isBadVersion(version: int) -> bool:
191+
192+
classSolution:
193+
deffirstBadVersion(self,n:int) ->int:
194+
l, r=1, n
195+
res=-1
196+
while l<= r:
197+
m= l+ (r- l)//2
198+
if isBadVersion(m):
199+
res= m
200+
r= m-1
201+
else:
202+
l= m+1
203+
return res
204+
```
205+
206+
```java
207+
/* The isBadVersion API is defined in the parent class VersionControl.
208+
boolean isBadVersion(int version);*/
209+
210+
publicclassSolutionextendsVersionControl {
211+
publicintfirstBadVersion(intn) {
212+
int l=1, r= n, res=-1;
213+
while (l<= r) {
214+
int m= l+ (r- l)/2;
215+
if (isBadVersion(m)) {
216+
res= m;
217+
r= m-1;
218+
}else {
219+
l= m+1;
220+
}
221+
}
222+
return res;
223+
}
224+
}
225+
```
226+
227+
```cpp
228+
// The API isBadVersion is defined for you.
229+
// bool isBadVersion(int version);
230+
231+
classSolution {
232+
public:
233+
int firstBadVersion(int n) {
234+
int l = 1, r = n, res = -1;
235+
while (l <= r) {
236+
int m = l + (r - l) / 2;
237+
if (isBadVersion(m)) {
238+
res = m;
239+
r = m - 1;
240+
} else {
241+
l = m + 1;
242+
}
243+
}
244+
return res;
245+
}
246+
};
247+
```
248+
249+
```javascript
250+
// The isBadVersion API is already defined in the VersionControl class.
251+
// isBadVersion(version: number): boolean
252+
253+
class Solution extends VersionControl {
254+
/**
255+
* @param {number} n Total versions
256+
* @return {number} The first bad version
257+
*/
258+
firstBadVersion(n) {
259+
let l = 1, r = n, res = -1;
260+
while (l <= r) {
261+
const m = Math.floor(l + (r - l) / 2);
262+
if (this.isBadVersion(m)) {
263+
res = m;
264+
r = m - 1;
265+
} else {
266+
l = m + 1;
267+
}
268+
}
269+
return res;
270+
}
271+
}
272+
```
273+
274+
::tabs-end
275+
276+
###Time & Space Complexity
277+
278+
* Time complexity: $O(\log n)$
279+
* Space complexity: $O(1)$
280+
281+
---
282+
283+
##4. Iterative Binary Search (Lower Bound)
284+
285+
::tabs-start
286+
287+
```python
288+
# The isBadVersion API is already defined for you.
289+
# def isBadVersion(version: int) -> bool:
290+
291+
classSolution:
292+
deffirstBadVersion(self,n:int) ->int:
293+
l, r=1, n
294+
while l< r:
295+
m= l+ (r- l)//2
296+
if isBadVersion(m):
297+
r= m
298+
else:
299+
l= m+1
300+
return l
301+
```
302+
303+
```java
304+
/* The isBadVersion API is defined in the parent class VersionControl.
305+
boolean isBadVersion(int version);*/
306+
307+
publicclassSolutionextendsVersionControl {
308+
publicintfirstBadVersion(intn) {
309+
int l=1, r= n;
310+
while (l< r) {
311+
int m= l+ (r- l)/2;
312+
if (isBadVersion(m)) {
313+
r= m;
314+
}else {
315+
l= m+1;
316+
}
317+
}
318+
return r;
319+
}
320+
}
321+
```
322+
323+
```cpp
324+
// The API isBadVersion is defined for you.
325+
// bool isBadVersion(int version);
326+
327+
classSolution {
328+
public:
329+
int firstBadVersion(int n) {
330+
int l = 1, r = n;
331+
while (l < r) {
332+
int m = l + (r - l) / 2;
333+
if (isBadVersion(m)) {
334+
r = m;
335+
} else {
336+
l = m + 1;
337+
}
338+
}
339+
return r;
340+
}
341+
};
342+
```
343+
344+
```javascript
345+
// The isBadVersion API is already defined in the VersionControl class.
346+
// isBadVersion(version: number): boolean
347+
348+
class Solution extends VersionControl {
349+
/**
350+
* @param {number} n Total versions
351+
* @return {number} The first bad version
352+
*/
353+
firstBadVersion(n) {
354+
let l = 1, r = n;
355+
while (l < r) {
356+
const m = Math.floor(l + (r - l) / 2);
357+
if (this.isBadVersion(m)) {
358+
r = m;
359+
} else {
360+
l = m + 1;
361+
}
362+
}
363+
return r;
364+
}
365+
}
366+
```
367+
368+
::tabs-end
369+
370+
###Time & Space Complexity
371+
372+
* Time complexity: $O(\log n)$
373+
* Space complexity: $O(1)$

0 commit comments

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