algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit ee86843858c87fa3134aedcd2db76ecd953dfd61
parent f4b688c52ca2c96fd27253797d43384ea7c8d7b7
Author: Andrew Laack <andrew@laack.co>
Date:   Thu,  1 Oct 2026 12:39:34 -0500

More rnd leetcode problems

Diffstat:
Aleetcode/check-if-there-is-a-valid-parentheses-string-path/check-if-there-is-a-valid-parentheses-string-path-v1.py | 59+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aleetcode/check-if-there-is-a-valid-parentheses-string-path/check-if-there-is-a-valid-parentheses-string-path-v2.py | 58++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aleetcode/maximum-nesting-depth-of-the-parentheses/maximum-nesting-depth-of-the-parentheses.cpp | 17+++++++++++++++++
Aleetcode/reverse-substrings-between-each-pair-of-parentheses/reverse-substrings-between-each-pair-of-parentheses.cpp | 34++++++++++++++++++++++++++++++++++
Mplan.txt | 2--
5 files changed, 168 insertions(+), 2 deletions(-)

diff --git a/leetcode/check-if-there-is-a-valid-parentheses-string-path/check-if-there-is-a-valid-parentheses-string-path-v1.py b/leetcode/check-if-there-is-a-valid-parentheses-string-path/check-if-there-is-a-valid-parentheses-string-path-v1.py @@ -0,0 +1,59 @@ +class Solution: + def checkValid(self,hist): + stack = [] + for ch in hist: + if ch == '(': + stack.append('(') + if ch == ')': + if len(stack) > 0: + stack.pop() + else: + return False + return len(stack) == 0 + + + def recurse(self,pos_x,pos_y,hist,grid, oc, cc): + + if not self.memo.get(str(pos_x) + " " + str(pos_y) + " " + str(oc) + " " + str(cc)) is None or self.done: + return False # true would already be propogated up. + + if pos_y == len(grid)-1 and pos_x == len(grid[pos_y])-1: + return self.checkValid(hist + grid[pos_y][pos_x]) + + current = grid[pos_y][pos_x] + + on = oc + cn = cc + + if current == '(': + on += 1 + else: + cn += 1 + + if cn > on: + return False + + correct = False + + if(pos_y < len(grid)-1): + down_res = self.recurse(pos_x,pos_y+1,hist+current,grid,on,cn) + if down_res: + correct = True + if not correct and (pos_x < len(grid[pos_y])-1): + right_res = self.recurse(pos_x+1,pos_y,hist+current,grid,on,cn) + if right_res: + correct = True + + self.memo[str(pos_x) + " " + str(pos_y) + " " + str(oc) + " " + str(cc)] = correct + if correct: + self.done = True + return correct + + def hasValidPath(self, grid: list[list[str]]) -> bool: + # conditions: + # () + # AB where A is valid, B is valid + + self.memo = {} + self.done = False + return self.recurse(0,0,"",grid,0,0) diff --git a/leetcode/check-if-there-is-a-valid-parentheses-string-path/check-if-there-is-a-valid-parentheses-string-path-v2.py b/leetcode/check-if-there-is-a-valid-parentheses-string-path/check-if-there-is-a-valid-parentheses-string-path-v2.py @@ -0,0 +1,58 @@ +class Solution: + def checkValid(self,hist): + on = 0 + for ch in hist: + if ch == '(': + on += 1 + if ch == ')': + on -= 1 + if on < 0: + return False + return on == 0 + + + def recurse(self,pos_x,pos_y,hist,grid, oc, cc): + + if not self.memo.get(str(pos_x) + " " + str(pos_y) + " " + str(oc) + " " + str(cc)) is None or self.done: + return False # true would already be propogated up. + + if pos_y == len(grid)-1 and pos_x == len(grid[pos_y])-1: + return self.checkValid(hist + grid[pos_y][pos_x]) + + current = grid[pos_y][pos_x] + + on = oc + cn = cc + + if current == '(': + on += 1 + else: + cn += 1 + + if cn > on: + return False + + correct = False + + if(pos_y < len(grid)-1): + down_res = self.recurse(pos_x,pos_y+1,hist+current,grid,on,cn) + if down_res: + correct = True + if not correct and (pos_x < len(grid[pos_y])-1): + right_res = self.recurse(pos_x+1,pos_y,hist+current,grid,on,cn) + if right_res: + correct = True + + self.memo[str(pos_x) + " " + str(pos_y) + " " + str(oc) + " " + str(cc)] = correct + if correct: + self.done = True + return correct + + def hasValidPath(self, grid: list[list[str]]) -> bool: + # conditions: + # () + # AB where A is valid, B is valid + + self.memo = {} + self.done = False + return self.recurse(0,0,"",grid,0,0) diff --git a/leetcode/maximum-nesting-depth-of-the-parentheses/maximum-nesting-depth-of-the-parentheses.cpp b/leetcode/maximum-nesting-depth-of-the-parentheses/maximum-nesting-depth-of-the-parentheses.cpp @@ -0,0 +1,17 @@ +class Solution { +public: + int maxDepth(string s) { + int max = 0; + int current = 0; + for(int i = 0; i < s.size(); ++i) { + if(s[i] == '(') { + current += 1; + max = std::max(current,max); + } + if(s[i] == ')') { + current -= 1; + } + } + return max; + } +}; diff --git a/leetcode/reverse-substrings-between-each-pair-of-parentheses/reverse-substrings-between-each-pair-of-parentheses.cpp b/leetcode/reverse-substrings-between-each-pair-of-parentheses/reverse-substrings-between-each-pair-of-parentheses.cpp @@ -0,0 +1,34 @@ +class Solution { +public: + void reverseSubstring(string& s, int idxl, int idxr) { + for(int i = 0; i <= (idxr - idxl) / 2; ++i) { + auto temp = s[i + idxl]; + s[i + idxl] = s[idxr - i]; + s[idxr - i] = temp; + } + } + + string reverseParentheses(string s) { + vector<int> stack {}; + int idx = 0; + + for(char& ch : s) { + if(ch == '(') { + stack.push_back(idx); + } else if (ch == ')') { + auto idxFinal = stack[stack.size() - 1]; + stack.pop_back(); + reverseSubstring(s,idxFinal,idx); + } + idx += 1; + } + + string res = ""; + for(char& ch : s) { + if(ch != '(' && ch != ')') { + res += ch; + } + } + return res; + } +}; diff --git a/plan.txt b/plan.txt @@ -10,7 +10,5 @@ these are the things I want to learn, ordered - quickselect x lc 1 - lc 2 - - 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)