aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-22 00:31:01 -0600
committerJack Sangdahl <[email protected]>2024-10-22 00:31:01 -0600
commitc6245c8eb0b1d8463bb3f5d2d1349c7de10a1c32 (patch)
treec8cd3df605224c2674457f0b83fb7f46494a5ca5
parent79945065d30539dc039f0e77cf8c9fc0058ec2c7 (diff)
downloadleetcode-c6245c8eb0b1d8463bb3f5d2d1349c7de10a1c32.tar.gz
leetcode-c6245c8eb0b1d8463bb3f5d2d1349c7de10a1c32.zip
554. brick wall
-rw-r--r--brick_wall.c85
-rw-r--r--brick_wall.py42
2 files changed, 127 insertions, 0 deletions
diff --git a/brick_wall.c b/brick_wall.c
new file mode 100644
index 0000000..be39306
--- /dev/null
+++ b/brick_wall.c
@@ -0,0 +1,85 @@
+// 554. Brick Wall
+#include "leetcode.h"
+
+/*
+ * there is a rectangular brick wall in front of you with 'n' rows of bricks.
+ * the i'throw has some number of bricks each of the same height (ie. one unit)
+ * butthey can be of different widths. the total width of each row is the same.
+ * draw a vertical line from the top to the bottom and cross the least bricks.
+ * if your line goes through the edge of a brick, then the brick is not
+ * considered as crossed. you cannot draw a line just along one of the two
+ * vertical edges of the wall, in which case the line will obviously cross no
+ * bricks. given the 2d array 'wall' that contains the information about the
+ * wall, return the minimum number of cross bricks after drawing such a vertical
+ * line
+ */
+
+#define MOD 1009
+
+struct item {
+ struct item *next;
+ int key;
+ int freq;
+};
+
+static struct item *hash[MOD];
+
+void hash_init(void) { memset((void *)hash, 0, sizeof(hash)); }
+
+int hash_get(int key, int *freq) {
+ int idx = key % MOD;
+ for (struct item *header = hash[idx]; header; header = header->next)
+ if (header->key == key) {
+ *freq = header->freq;
+ return 0;
+ }
+ return -1;
+}
+
+void hash_set(int key, int freq) {
+ struct item *i = (struct item *)malloc(sizeof(struct item));
+ i->key = key;
+ i->freq = freq;
+ i->next = hash[key % MOD];
+ hash[key % MOD] = i;
+}
+
+void hash_free(void) {
+ for (int i = 0; i < MOD; i++)
+ for (struct item *header = hash[i], *delete; header;) {
+ delete = header;
+ header = header->next;
+ free(delete);
+ }
+}
+
+int leastBricks(int **wall, int wallSize, int *wallColSize) {
+ int ans = 0, freq;
+ hash_init();
+ for (int i = 0; i < wallSize; i++)
+ for (int j = 0, end = 0; j < wallColSize[i] - 1; j++) {
+ end += wall[i][j];
+ if (hash_get(end, &freq) == -1)
+ freq = 1;
+ else
+ freq++;
+ hash_set(end, freq);
+ if (freq > ans)
+ ans = freq;
+ }
+ hash_free();
+ return wallSize - ans;
+}
+
+int main() {
+ int w1i[6][4] = {{1, 2, 2, 1}, {3, 1, 2}, {1, 3, 2},
+ {2, 4}, {3, 1, 2}, {1, 3, 1, 1}},
+ w2i[3][1] = {{1}, {1}, {1}};
+ struct two_d_arr w1, w2;
+ two_d_arr_init(&w1, 6, 4, w1i);
+ two_d_arr_init(&w2, 3, 1, w2i);
+ printf("%d\n", leastBricks(w1.arr, w1.row_size, w1.col_size)); // expect: 2
+ printf("%d\n", leastBricks(w2.arr, w2.row_size, w2.col_size)); // expect: 3
+ two_d_arr_free(&w1);
+ two_d_arr_free(&w2);
+}
diff --git a/brick_wall.py b/brick_wall.py
new file mode 100644
index 0000000..1f7953c
--- /dev/null
+++ b/brick_wall.py
@@ -0,0 +1,42 @@
+# 554. Brick Wall
+
+"""
+there is a rectangular brick wall in front of you with 'n' rows of bricks.
+the i'throw has some number of bricks each of the same height (ie. one unit)
+butthey can be of different widths. the total width of each row is the same.
+draw a vertical line from the top to the bottom and cross the least bricks.
+if your line goes through the edge of a brick, then the brick is not
+considered as crossed. you cannot draw a line just along one of the two
+vertical edges of the wall, in which case the line will obviously cross no
+bricks. given the 2d array 'wall' that contains the information about the
+wall, return the minimum number of cross bricks after drawing such a vertical
+line
+"""
+
+
+class Solution(object):
+ def leastBricks(self, wall):
+ """
+ :type wall: List[List[int]]
+ :rtype: int
+ """
+ edge_freq = {}
+ max_freq = 0
+ for row in range(len(wall)):
+ edge_pos = 0
+ for brick_num in range(len(wall[row]) - 1):
+ curr = wall[row][brick_num]
+ edge_pos += curr
+ edge_freq[edge_pos] = edge_freq.get(edge_pos, 0) + 1
+ max_freq = max(edge_freq[edge_pos], max_freq)
+ return len(wall) - max_freq
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.leastBricks(
+ wall=[[1, 2, 2, 1], [3, 1, 2], [1, 3, 2], [2, 4], [3, 1, 2], [1, 3, 1, 1]]
+ )
+ )
+ print(obj.leastBricks(wall=[[1], [1], [1]]))