leetcode

commit 23c7522d57d2b2ff672aa2dd06dc9064cb7bc7f6
Author: Martin Ashby <martin@ashbysoft.com>
Date:   Mon,  1 Jun 2026 22:29:43 +0100

Doing some leetcode for entertainment

Diffstat:
A
.gitignore
 | 
1
+
A
10.c
 | 
159
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2144.c
 | 
39
+++++++++++++++++++++++++++++++++++++++

3 files changed, 199 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+a.out
diff --git a/10.c b/10.c
@@ -0,0 +1,158 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+
+#define DEBUG 0
+#define PDEBUG(...) if (DEBUG) printf(__VA_ARGS__)
+
+#define HTLEN 3000
+
+static bool isMatchInternal(char* s, char* p, int depth) {
+	PDEBUG("isMatch [%s] [%s] depth %d\n", s, p, depth);
+	// fully recursive solution... 
+	// look ahead, how many characters could 
+	int pl = strlen(p);
+	int pn = -1;
+	if (pl > 1) {
+		pn = p[1];
+	}
+
+	if (s[0] == '\0') {
+		// if we're at the end of the pattern 
+		if (p[0] == '\0') {
+			return true;
+		}
+		// OR the next is * then recurse again..
+		if (pn == '*') {
+			return isMatchInternal(s, p+2, depth+1);
+		}
+		// otherwise there is remaining unmatched pattern, so we're not a match
+		return false;
+	} else if (pn == '*') {
+		// how many characters _could_ we match?
+		int n = 0;
+		while ((s[n] == p[0] || p[0] == '.') && s[n] != '\0') {
+			n++;
+		}
+		// try each option
+		for (int i=0; i<=n; i++) {
+			PDEBUG("trying i %d\n", n);
+			if (isMatchInternal(s+i, p+2, depth+1)) {
+				return true;
+			}
+		}
+		return false;
+	} else if (s[0] == p[0] || p[0] == '.') {
+		PDEBUG("s[0] [%c] p[0] [%c] incrementing\n", s[0], p[0]);
+		return isMatchInternal(s+1, p+1, depth+1);
+	} else {
+		return false;
+	}
+}
+
+bool isMatch(char* s, char* p) {
+	return isMatchInternal(s, p, 0);
+}
+
+// bool isMatch(char* s, char* p) {
+// 	PDEBUG("isMatch %s %s\n", s, p);
+// 	int sx = 0, px = 0;
+// 	int pl = strlen(p);
+// 	int sl = strlen(s);
+// 	while (s[sx] != '\0' && p[px] != '\0') {
+// 		int pn = -1;
+// 		if ((px+1) < pl) {
+// 			pn = p[px+1];
+// 		}
+// 		if (pn == '*') {
+// 			PDEBUG("s[sx] %c p[px] %c pn %c\n", s[sx], p[px], pn);
+
+// 			// is this the end of the pattern?
+// 			if ((px+2) == pl) {
+// 				PDEBUG("* at end of string\n");
+// 				// just check all the remaining characters match
+// 				bool res = true;
+// 				for (int i=sx; i<sl; i++) {
+// 					res = res && (s[i] == p[px] || p[px] == '.');
+// 				}
+// 				return res;
+// 			} else {
+// 				// how many characters _could_ we match??
+// 				int sxx = sx;
+// 				while ((s[sxx] == p[px] || p[px] == '.') && s[sxx] != '\0') {
+// 					sxx++;
+// 				}
+// 				// recursively match the remaining trying each possible number of matches. 
+// 				// god this could be slow.
+// 				for (int i=sx; i<(sxx+1); i++) {
+// 					if (isMatch(s+i, p+px+2)) {
+// 						return true;
+// 					}
+// 				}
+// 				return false;
+// 			}
+// 		} else {
+// 			PDEBUG("s[sx] %c p[px] %c\n", s[sx], p[px]);
+// 			if (s[sx] == p[px] || p[px] == '.') {
+// 				sx++;
+// 				px++;
+// 			} else {
+// 				return false;
+// 			}
+// 		}
+// 	}
+// 	// now verify we're at the end of both strings, OR we're at the last character of p and it's a *
+// 	bool res = s[sx] == '\0' && p[px] == '\0';
+// 	PDEBUG("isMatch %s\n", res ? "true": "false");
+// 	return res;
+// }
+
+void test(char* s, char* p, bool exp) {
+	bool act = isMatch(s, p);
+	if (act != exp) {
+		fprintf(stderr, "test s %s p %s failed, exp %s act %s\n", s, p, exp ? "true": "false", act ? "true" : "false");
+	}
+}
+
+int main() {
+	{
+		test("aa", "p", false);
+	}
+	{
+		test("aa", "a*", true);
+	}
+	{
+		test("ab", ".*", true);
+	}
+	{
+		test("aab", "a*", false);
+	}
+	{
+		test("aab", "a*b", true);
+	}
+	{
+		test("aaaaaab", "a*b", true);
+	}
+	{
+		test("aaaaaab", "a*b*", true);
+	}
+	{
+		test("aaaaaabc", "a*b*", false);
+	}
+	{
+		test("aaaaaabc", "a*b*.", true);
+	}	
+	{
+		test("aab", "c*a*b", true);
+	}
+	{
+		test("aaa", "a*a", true);
+	}
+	{
+		test("a", "ab*", true);
+	}
+	{
+		test("abcaaaaaaabaabcabac", ".*ab.a.*a*a*.*b*b*", true);
+	}
+}
+\ No newline at end of file
diff --git a/2144.c b/2144.c
@@ -0,0 +1,38 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int cmp(const void* a, const void* b) {
+	return *((int*)b)-*((int*)a);
+}
+
+int minimumCost(int* cost, int costSize) {
+    qsort(cost, costSize, sizeof(int), cmp);
+    int sum=0;
+    for (int i=0; i<costSize; i++) {
+    	if ((i+1)%3>0) {
+    		int cc = cost[i];
+    		sum+=cc;
+    	}
+    }
+    return sum;
+}
+
+void test(int* cost, int costSize, int exp) {
+	int act = minimumCost(cost, costSize);
+	if (act != exp) {
+		fprintf(stderr, "test failed! exp %d act %d\n", exp, act);
+	}
+}
+
+int main() {
+	{
+		int cost[] = {1, 2, 3};
+		int costSize = 3;
+		test(cost, costSize, 5);
+	}
+	{
+		int cost[] = {6,5,7,9,2,2};
+		int costSize = 6;
+		test(cost, 6, 23);
+	}
+}
+\ No newline at end of file