commit 0bafcf643f45f7f8d8df3c3497831cc515ad0e5d
parent 7f56f71951c5d5e7916c1a3b2c38b423ade21431
Author: Andrew Laack <andrew@laack.co>
Date: Sun, 13 Sep 2026 11:27:07 -0500
Updated prim visualization, added merkle tree to plan, fixed readme, did subtree encoding lc problem, did dp problem, and graph translation problem
Diffstat:
7 files changed, 177 insertions(+), 36 deletions(-)
diff --git a/README b/README
@@ -1,3 +1,3 @@
Algorithms
-=========
+==========
This is a repo containing algorithm implementations.
diff --git a/leetcode/find-duplicate-subtrees/find-duplicate-subtrees.cpp b/leetcode/find-duplicate-subtrees/find-duplicate-subtrees.cpp
@@ -0,0 +1,46 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ * int val;
+ * TreeNode *left;
+ * TreeNode *right;
+ * TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+
+ unordered_map<string,int> subtrees {};
+ vector<TreeNode*> matching {};
+
+ string inOrder(TreeNode* root) {
+ if(root == nullptr) {
+ return "";
+ }
+ string current = "";
+ string left = "L" + inOrder(root->left);
+ current.append(left);
+ current.append(to_string(root->val));
+ current.append(", ");
+ string right = "R" + inOrder(root->right);
+ current.append(right);
+
+ if(subtrees[current] == 0) {
+ subtrees[current] += 1;
+ } else {
+ if (subtrees[current] == 1) {
+ subtrees[current] = 2; // won't be added to return again for multi-dupes
+ matching.push_back(root);
+ }
+ }
+
+ return current;
+ }
+
+ vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
+ inOrder(root);
+ return matching;
+ }
+};
diff --git a/leetcode/image-overlap/image-overlap.py b/leetcode/image-overlap/image-overlap.py
@@ -0,0 +1,27 @@
+class Solution:
+
+ def safe_read(self,img1,x,y):
+ if y >= len(img1) or x >= len(img1[y]) or x < 0 or y < 0:
+ return 0
+ return img1[y][x]
+
+ # we shift img1
+ def shift_and_check(self,img1,img2,shift_x,shift_y):
+ count = 0
+ for y in range(len(img2)):
+ for x in range(len(img2[y])):
+ if img2[y][x] == 1:
+ if self.safe_read(img1,x-shift_x, y-shift_y):
+ count += 1
+ return count
+
+ def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
+ best = 0
+
+ for y in range(len(img1)):
+ for mult_y in [-1,1]:
+ for x in range(len(img1[y])):
+ for mult_x in [-1,1]:
+ best = max(self.shift_and_check(img1,img2,x*mult_x,y*mult_y), best)
+
+ return best
diff --git a/leetcode/maximum-earnings-from-taxi/maximum-earnings-from-taxi-v1.py b/leetcode/maximum-earnings-from-taxi/maximum-earnings-from-taxi-v1.py
@@ -0,0 +1,35 @@
+def start(e):
+ return e[0]
+class Solution:
+ def best_from(self,current_ride_index,rides):
+
+ if current_ride_index in self.mem:
+ return self.mem[current_ride_index]
+
+ if current_ride_index >= len(rides):
+ return 0
+
+ ride = rides[current_ride_index]
+ ending = ride[1]
+ best_without = self.best_from(current_ride_index+1,rides)
+
+ n_idx = current_ride_index+1
+ for i in range(current_ride_index+1, len(rides) + 1):
+ if i >= len(rides):
+ n_idx = i
+ break
+ if rides[i][0] >= ending:
+ n_idx = i
+ break
+
+ best_with = self.best_from(n_idx, rides)
+
+ res = max(best_with + (ride[1] - ride[0]) + ride[2], best_without)
+ self.mem[current_ride_index] = res
+ return res
+
+
+ def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
+ rides.sort(key=start)
+ self.mem = {}
+ return self.best_from(0,rides)
diff --git a/leetcode/maximum-earnings-from-taxi/maximum-earnings-from-taxi-v2.py b/leetcode/maximum-earnings-from-taxi/maximum-earnings-from-taxi-v2.py
@@ -0,0 +1,40 @@
+def start(e):
+ return e[0]
+class Solution:
+
+ def binary_search_find(self, rides, left, right, target):
+ while left < right:
+ mid = left + (right - left) // 2
+ if rides[mid][0] < target:
+ left = mid + 1
+ else:
+ right = mid
+ if left < len(rides) and rides[left][0] >= target:
+ return left
+ return -1
+
+
+ def best_from(self,current_ride_index,rides):
+
+ if current_ride_index in self.mem:
+ return self.mem[current_ride_index]
+
+ if current_ride_index >= len(rides) or current_ride_index == -1:
+ return 0
+
+ ride = rides[current_ride_index]
+ ending = ride[1]
+ best_without = self.best_from(current_ride_index+1,rides)
+
+ n_idx = self.binary_search_find(rides,current_ride_index,len(rides)-1,ride[1])
+ best_with = self.best_from(n_idx, rides)
+
+ res = max(best_with + (ride[1] - ride[0]) + ride[2], best_without)
+ self.mem[current_ride_index] = res
+ return res
+
+
+ def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
+ rides.sort(key=start)
+ self.mem = {}
+ return self.best_from(0,rides)
diff --git a/plan.txt b/plan.txt
@@ -10,6 +10,7 @@ these are the things I want to learn, ordered
- quickselect
x lc 1
- lc 2
- - visualize
- perlin noise
- visualize
+ x merkle tree
+ x find duplicate subtrees (this isn't a merkle tree, but builds on the idea of encoding subtrees in a unique way)
diff --git a/visualizations/prim.py b/visualizations/prim.py
@@ -9,7 +9,7 @@ pygame.init()
display = pygame.display.set_mode((5120,1440))
VERTICES = 100
-EDGES = 200
+EDGES = 1000
white = (255, 255, 255)
red = (255, 0, 0)
@@ -71,6 +71,12 @@ while True:
mst = []
+ start = random.choice(list(graph.keys()))
+ start.visited = True
+ visited_vertices.add(start)
+ for edge in graph[start]:
+ heapq.heappush(edge_heap, edge)
+
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
@@ -78,46 +84,32 @@ while True:
quit()
display.fill(black)
-
for vertex in graph:
vertex.draw_vertex(display)
-
for edge in edge_list:
edge.draw_edge(display, light_grey)
-
for edge in mst:
edge.draw_edge(display, white)
+ item = None
+ while edge_heap:
+ candidate = heapq.heappop(edge_heap)
+ if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices):
+ item = candidate
+ break
- if len(edge_heap) == 0:
- start = random.choice(list(graph.keys()))
- visited_vertices.add(start)
- edges = graph[start]
- for edge in edges:
- heapq.heappush(edge_heap, edge)
- else:
- item = None
- while True:
- if len(edge_heap) > 0:
- item = heapq.heappop(edge_heap)
- v1_visited = item.v1 in visited_vertices
- v2_visited = item.v2 in visited_vertices
- if v1_visited != v2_visited:
- break
- else:
- item = None
- break
-
- if item != None:
- new_vertex = item.v2 if item.v1 in visited_vertices else item.v1
- visited_vertices.add(new_vertex)
- new_vertex.visited = True
- mst.append(item)
- edges = graph[new_vertex]
- for edge in edges:
- heapq.heappush(edge_heap, edge)
- else:
+ if item is None:
+ pygame.display.update()
+ if len(visited_vertices) == VERTICES:
pygame.image.save(display, "out.jpg")
- break
- time.sleep(.1)
+ break
+
+ new_vertex = item.v2 if item.v1 in visited_vertices else item.v1
+ visited_vertices.add(new_vertex)
+ new_vertex.visited = True
+ mst.append(item)
+ for edge in graph[new_vertex]:
+ heapq.heappush(edge_heap, edge)
+
+ time.sleep(.1)
pygame.display.update()
