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

Commit232acfa

Browse files
authored
SriHari: Batch-3/Neetcode-All/Added articles (neetcode-gh#3760)
* small changes* Batch-3/Neetcode-All/Added-articles* Batch-3/Neetcode-All/Added-articles* Batch-3/Neetcode-All/Added-articles* Batch-3/Neetcode-All/Added-articles* Batch-3/Neetcode-All/Added-articles* Batch-3/Neetcode-All/Added-articles* Batch-3/Neetcode-All/Added-articles
1 parenta0098a6 commit232acfa

File tree

43 files changed

+16586
-13
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

43 files changed

+16586
-13
lines changed

‎articles/best-time-to-buy-and-sell-stock-ii.md

Lines changed: 458 additions & 0 deletions
Large diffs are not rendered by default.

‎articles/brick-wall.md

Lines changed: 245 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,245 @@
1+
##1. Brute Force
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defleastBricks(self,wall: List[List[int]]) ->int:
8+
n=len(wall)
9+
m=0
10+
for brickin wall[0]:
11+
m+= brick
12+
13+
gaps= [[]for _inrange(n)]
14+
for iinrange(n):
15+
gap=0
16+
for brickin wall[i]:
17+
gap+= brick
18+
gaps[i].append(gap)
19+
20+
res= n
21+
for lineinrange(1, m):
22+
cuts=0
23+
for iinrange(n):
24+
if linenotin gaps[i]:
25+
cuts+=1
26+
27+
res=min(res, cuts)
28+
return res
29+
```
30+
31+
```java
32+
publicclassSolution {
33+
publicintleastBricks(List<List<Integer>>wall) {
34+
int n= wall.size();
35+
int m=0;
36+
for (int brick: wall.get(0)) {
37+
m+= brick;
38+
}
39+
40+
List<List<Integer>> gaps=newArrayList<>();
41+
for (int i=0; i< n; i++) {
42+
gaps.add(newArrayList<>());
43+
int gap=0;
44+
for (int brick: wall.get(i)) {
45+
gap+= brick;
46+
gaps.get(i).add(gap);
47+
}
48+
}
49+
50+
int res= n;
51+
for (int line=1; line< m; line++) {
52+
int cuts=0;
53+
for (int i=0; i< n; i++) {
54+
if (!gaps.get(i).contains(line)) {
55+
cuts++;
56+
}
57+
}
58+
res=Math.min(res, cuts);
59+
}
60+
61+
return res;
62+
}
63+
}
64+
```
65+
66+
```cpp
67+
classSolution {
68+
public:
69+
int leastBricks(vector<vector<int>>& wall) {
70+
int n = wall.size();
71+
int m = 0;
72+
for (int brick : wall[0]) {
73+
m += brick;
74+
}
75+
76+
vector<vector<int>> gaps(n);
77+
for (int i = 0; i < n; i++) {
78+
int gap = 0;
79+
for (int brick : wall[i]) {
80+
gap += brick;
81+
gaps[i].push_back(gap);
82+
}
83+
}
84+
85+
int res = n;
86+
for (int line =1; line < m; line++) {
87+
int cuts = 0;
88+
for (int i = 0; i < n; i++) {
89+
if (find(gaps[i].begin(), gaps[i].end(), line) == gaps[i].end()) {
90+
cuts++;
91+
}
92+
}
93+
res = min(res, cuts);
94+
}
95+
96+
return res;
97+
}
98+
};
99+
```
100+
101+
```javascript
102+
classSolution {
103+
/**
104+
*@param{number[][]}wall
105+
*@return{number}
106+
*/
107+
leastBricks(wall) {
108+
constn=wall.length;
109+
let m=0;
110+
for (constbrickof wall[0]) {
111+
m+= brick;
112+
}
113+
114+
constgaps=Array.from({ length: n }, ()=> []);
115+
for (let i=0; i< n; i++) {
116+
let gap=0;
117+
for (constbrickof wall[i]) {
118+
gap+= brick;
119+
gaps[i].push(gap);
120+
}
121+
}
122+
123+
let res= n;
124+
for (let line=1; line< m; line++) {
125+
let cuts=0;
126+
for (let i=0; i< n; i++) {
127+
if (!gaps[i].includes(line)) {
128+
cuts++;
129+
}
130+
}
131+
res=Math.min(res, cuts);
132+
}
133+
134+
return res;
135+
}
136+
}
137+
```
138+
139+
::tabs-end
140+
141+
###Time & Space Complexity
142+
143+
* Time complexity: $O(m * n * g)$
144+
* Space complexity: $O(n * g)$
145+
146+
>Where $m$ is the sum of widths of the bricks in the first row, $n$ is the number of rows and $g$ is the average number of gaps in each row.
147+
148+
---
149+
150+
##2. Hash Map
151+
152+
::tabs-start
153+
154+
```python
155+
classSolution:
156+
defleastBricks(self,wall: List[List[int]]) ->int:
157+
countGap= {0:0}
158+
159+
for rin wall:
160+
total=0
161+
for iinrange(len(r)-1):
162+
total+= r[i]
163+
countGap[total]=1+ countGap.get(total,0)
164+
165+
returnlen(wall)-max(countGap.values())
166+
```
167+
168+
```java
169+
publicclassSolution {
170+
publicintleastBricks(List<List<Integer>>wall) {
171+
HashMap<Integer,Integer> countGap=newHashMap<>();
172+
countGap.put(0,0);
173+
174+
for (List<Integer> row: wall) {
175+
int total=0;
176+
for (int i=0; i< row.size()-1; i++) {
177+
total+= row.get(i);
178+
countGap.put(total, countGap.getOrDefault(total,0)+1);
179+
}
180+
}
181+
182+
int maxGaps=0;
183+
for (int count: countGap.values()) {
184+
maxGaps=Math.max(maxGaps, count);
185+
}
186+
187+
return wall.size()- maxGaps;
188+
}
189+
}
190+
```
191+
192+
```cpp
193+
classSolution {
194+
public:
195+
int leastBricks(vector<vector<int>>& wall) {
196+
unordered_map<int, int> countGap;
197+
countGap[0] = 0;
198+
199+
for (const auto& row : wall) {
200+
int total = 0;
201+
for (size_t i = 0; i < row.size() - 1; ++i) {
202+
total += row[i];
203+
countGap[total]++;
204+
}
205+
}
206+
207+
int maxGaps =0;
208+
for (constauto& [key, value] : countGap) {
209+
maxGaps = max(maxGaps, value);
210+
}
211+
212+
return wall.size() - maxGaps;
213+
}
214+
};
215+
```
216+
217+
```javascript
218+
classSolution {
219+
/**
220+
*@param{number[][]}wall
221+
*@return{number}
222+
*/
223+
leastBricks(wall) {
224+
constcountGap=newMap();
225+
countGap.set(0,0);
226+
for (constrowof wall) {
227+
let total=0;
228+
for (let i=0; i<row.length-1; i++) {
229+
total+= row[i];
230+
countGap.set(total, (countGap.get(total)||0)+1);
231+
}
232+
}
233+
returnwall.length-Math.max(...countGap.values());
234+
}
235+
}
236+
```
237+
238+
::tabs-end
239+
240+
###Time & Space Complexity
241+
242+
* Time complexity: $O(N)$
243+
* Space complexity: $O(g)$
244+
245+
>Where $N$ is the total number of bricks in the wall and $g$ is the total number of gaps in all the rows.

0 commit comments

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