8000 refactor 554 · puperfused/Leetcode@3977b5a · GitHub
[go: up one dir, main page]

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

Appearance settings

Commit 3977b5a

Browse files
refactor 554
1 parent 1dbc03f commit 3977b5a

File tree

2 files changed

+36
-34
lines changed

2 files changed

+36
-34
lines changed

src/main/java/com/fishercoder/solutions/_554.java

Lines changed: 34 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -34,41 +34,43 @@
3434
The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.
3535
*/
3636
public class _554 {
37-
//credit to: https://leetcode.com/articles/brick-wall/
37+
public static class Solution1 {
38+
/**
39+
* credit: https://leetcode.com/articles/brick-wall/
40+
*
41+
* we make use of a HashMap
42+
* map which is used to store entries in the form:
43+
* (sum,count). Here,
44+
* sum refers to the cumulative sum of the bricks' widths encountered in the current row, and
45+
* count refers to the number of times the corresponding sum is obtained. Thus,
46+
* sum in a way, represents the positions of the bricks's boundaries relative to the leftmost boundary.
47+
*
48+
* This is done based on the following observation:
49+
* We will never obtain the same value of sum twice while traversing over a particular row.
50+
* Thus, if the sum value is repeated while traversing over the rows, it means some row's brick boundary coincides with some previous row's brick boundary.
51+
* This fact is accounted for by incrementing the corresponding count value.
52+
* But, for every row, we consider the sum only upto the second last brick, since the last boundary isn't a valid boundary for the solution.
53+
*/
3854

39-
/**we make use of a HashMap
40-
map which is used to store entries in the form:
41-
(sum,count). Here,
42-
sum refers to the cumulative sum of the bricks' widths encountered in the current row, and
43-
count refers to the number of times the corresponding sum is obtained. Thus,
44-
sum in a way, represents the positions of the bricks's boundaries relative to the leftmost boundary.
45-
46-
This is done based on the following observation:
47-
We will never obtain the same value of sum twice while traversing over a particular row.
48-
Thus, if the sum value is repeated while traversing over the rows, it means some row's brick boundary coincides with some previous row's brick boundary.
49-
This fact is accounted for by incrementing the corresponding count value.
50-
51-
But, for every row, we consider the sum only upto the second last brick, since the last boundary isn't a valid boundary for the solution.*/
52-
53-
public int leastBricks(List<List<Integer>> wall) {
54-
Map<Integer, Integer> map = new HashMap();
55-
for (List<Integer> row : wall) {
56-
int sum = 0;
57-
for (int i = 0; i < row.size() - 1; i++) {
58-
//NOTE: i < row.size()-1
59-
sum += row.get(i);
60-
if (map.containsKey(sum)) {
61-
map.put(sum, map.get(sum) + 1);
62-
} else {
63-
map.put(sum, 1);
55+
public int leastBricks(List<List<Integer>> wall) {
56 8000 +
Map<Integer, Integer> map = new HashMap();
57+
for (List<Integer> row : wall) {
58+
int sum = 0;
59+
for (int i = 0; i < row.size() - 1; i++) {
60+
//NOTE: i < row.size()-1
61+
sum += row.get(i);
62+
if (map.containsKey(sum)) {
63+
map.put(sum, map.get(sum) + 1);
64+
} else {
65+
map.put(sum, 1);
66+
}
6467
}
6568
}
69+
int result = wall.size();
70+
for (int key : map.keySet()) {
71+
result = Math.min(result, wall.size() - map.get(key));
72+
}
73+
return result;
6674
}
67-
int result = wall.size();
68-
for (int key : map.keySet()) {
69-
result = Math.min(result, wall.size() - map.get(key));
70-
}
71-
return result;
7275
}
73-
7476
}

src/test/java/com/fishercoder/_554Test.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,14 +12,14 @@
1212
import static junit.framework.Assert.assertEquals;
1313

1414
public class _554Test {
15-
private static _554 test;
15+
private static _554.Solution1 test;
1616
private static int expected;
1717
private static int actual;
1818
private static List<List<Integer>> wall;
1919

2020
@BeforeClass
2121
public static void setup() {
22-
test = new _554();
22+
test = new _554.Solution1();
2323
}
2424

2525
@Before

0 commit comments

Comments
 (0)
0