commit bca0cf9d05d7ff5f77d552eb6fb56bacff8190c3
parent d3f0506fd71be78dc95a09a173281783ec842c69
Author: Andrew Laack <andrew@laack.co>
Date: Sat, 14 Jun 2025 14:09:00 -0500
Finished a bunch more neetcode
Diffstat:
8 files changed, 371 insertions(+), 0 deletions(-)
diff --git a/linked-list-cycle/linked-list-cycle.py b/linked-list-cycle/linked-list-cycle.py
@@ -0,0 +1,23 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, x):
+# self.val = x
+# self.next = None
+
+class Solution:
+ def hasCycle(self, head: Optional[ListNode]) -> bool:
+
+ if head is None:
+ return False
+
+ head.val = None
+ current = head.next
+
+ while current is not None:
+ if current.val is None:
+ return True
+ else:
+ current.val = None
+ current = current.next
+
+ return False
diff --git a/linked-list-cycle/linked-list-cycleV2.py b/linked-list-cycle/linked-list-cycleV2.py
@@ -0,0 +1,31 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, x):
+# self.val = x
+# self.next = None
+
+class Solution:
+ def hasCycle(self, head: Optional[ListNode]) -> bool:
+
+ # two pointers, one fast, one slow
+ # if fast catches slow, issue
+ # if fast reaches end, success
+
+ if head is None:
+ return False
+
+ fast_ptr = head.next
+ slow_ptr = head
+
+ while fast_ptr is not None:
+ if fast_ptr == slow_ptr:
+ return True
+
+ fast_ptr = fast_ptr.next
+
+ if fast_ptr is not None:
+ fast_ptr = fast_ptr.next
+
+ slow_ptr = slow_ptr.next
+
+ return False
diff --git a/longest-repeating-character-replacement/longest-repeating.py b/longest-repeating-character-replacement/longest-repeating.py
@@ -0,0 +1,56 @@
+import numpy as np
+
+class Solution:
+ def characterReplacement(self, s: str, k: int) -> int:
+
+ # keep track of the most popular as we go through
+ # when adverserial examples are found, we add them to our hash_map
+ # and increment our counter for them.
+
+ # when adverserial > k, we move the left_ptr to the right, removing values each time.
+ # while we do this, we also need to check the most popular character in our
+ # substring.
+
+ longest = 0
+
+ counts = [0] * 26
+
+ left_ptr = 0
+ right_ptr = 0
+
+ converted = [char_to_int(i.lower()) for i in s]
+
+ while right_ptr < len(s):
+
+ counts[converted[right_ptr]] += 1
+ adv = count_adversaries(counts)
+
+ looped = False
+ while count_adversaries(counts) > k:
+ counts[converted[left_ptr]] -= 1
+ left_ptr += 1
+ looped = True
+
+ else:
+ current = (right_ptr - left_ptr) + 1
+ if current > longest:
+ longest = current
+ right_ptr += 1
+
+
+ return longest
+
+def char_to_int(char_input):
+ return ord(char_input) % 97
+
+def count_adversaries(counts):
+
+ adversaries = 0
+ max_index = np.argmax(counts)
+ for i in range(0, len(counts)):
+
+ if i == max_index:
+ continue
+ adversaries += counts[i]
+
+ return adversaries
diff --git a/maximum-difference-by-remapping-a-digit/max-diff.py b/maximum-difference-by-remapping-a-digit/max-diff.py
@@ -0,0 +1,46 @@
+class Solution:
+ def minMaxDifference(self, num: int) -> int:
+
+ num_ls = []
+ while num > 0:
+ lsb = num % 10
+ num = num // 10
+ num_ls.append(lsb)
+
+ num_ls.reverse()
+ num_ls_min = num_ls.copy()
+
+ # min = setting msb to 0 (since int, no leading 0's)
+
+ val_to_map = num_ls[0]
+
+ for i in range(0, len(num_ls)):
+ if num_ls[i] == val_to_map:
+ num_ls_min[i] = 0
+
+ # max = setting max non 9 value to be = 9 (or leaving as is when all 9's)
+
+ num_ls_max = num_ls.copy()
+ digit_to_change = 9
+
+ for i in range(0, len(num_ls_max)):
+ if num_ls_max[i] != 9:
+ digit_to_change = num_ls_max[i]
+ break
+
+ for i in range(0, len(num_ls_max)):
+ if num_ls_max[i] == digit_to_change:
+ num_ls_max[i] = 9
+
+
+ max_val = to_int(num_ls_max)
+ min_val = to_int(num_ls_min)
+
+ return max_val - min_val
+
+
+def to_int(num_ls) -> int:
+ num = 0
+ for i in range(len(num_ls) - 1, -1, -1):
+ num += num_ls[i] * 10**((len(num_ls) - 1) - i)
+ return num
diff --git a/merge-two-sorted-lists/merge-two-sorted-lists.py b/merge-two-sorted-lists/merge-two-sorted-lists.py
@@ -0,0 +1,44 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, val=0, next=None):
+# self.val = val
+# self.next = next
+class Solution:
+ # len(list1, list2) can be 0
+ def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
+
+ if list1 is None:
+ return list2
+ if list2 is None:
+ return list1
+
+ head = None
+
+ if list1.val < list2.val:
+ head = list1
+ list1 = list1.next
+ else:
+ head = list2
+ list2 = list2.next
+
+ assert(head is not None)
+
+ current = head
+
+ while list1 is not None and list2 is not None:
+
+ if list1.val < list2.val:
+ current.next = list1
+ list1 = list1.next
+ else:
+ current.next = list2
+ list2 = list2.next
+
+ current = current.next
+
+ if list1 is None:
+ current.next = list2
+ else:
+ current.next = list1
+
+ return head
diff --git a/permutation-in-string/perm-in-string.py b/permutation-in-string/perm-in-string.py
@@ -0,0 +1,68 @@
+class Solution:
+
+ # SLIDING WINDOW:
+
+ # CONSIDER:
+
+ # if s2 contains a permutation of s1 then
+ # there exists a contiguous string s1_x
+ # such that the count of each character
+ # in s1_x is the same s2
+
+ # Given this, we slide a window over s2,
+ # keeping track of character counts as we go
+ # if the characters match s1's characters, we return
+ # true.
+
+ # since we do at most 26 comparisons (one for each character)
+ # per window, we see this is O(n)
+
+ def checkInclusion(self, s1: str, s2: str) -> bool:
+
+ if len(s2) < len(s1):
+ return False
+
+ s1_counts = [0] * 26
+ s2_counts = [0] * 26
+
+ for char in s1:
+ s1_counts[to_int(char)] += 1
+
+ left_ptr = 0
+ right_ptr = len(s1) - 1
+
+ # initialize first window
+ for i in range(0, right_ptr + 1):
+ s2_counts[to_int(s2[i])] += 1
+
+ while right_ptr < len(s2):
+ # check count
+
+ if compare_lists(s2_counts, s1_counts):
+ return True
+ else:
+ s2_counts[to_int(s2[left_ptr])] -= 1
+ left_ptr += 1
+
+ right_ptr += 1
+
+ if right_ptr >= len(s2):
+ return False
+
+ s2_counts[to_int(s2[right_ptr])] += 1
+
+ return False
+
+
+def to_int(char):
+ return ord(char) % 97
+
+# assumes len(ls1) == len(ls2) which should
+# be true when initialized to represent lower case
+# characters.
+
+def compare_lists(ls1, ls2):
+ for i in range(0, len(ls1)):
+ if ls1[i] != ls2[i]:
+ return False
+ return True
diff --git a/reorder-list/reorder-list.py b/reorder-list/reorder-list.py
@@ -0,0 +1,77 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, val=0, next=None):
+# self.val = val
+# self.next = next
+
+# Do not return anything, modify head in-place instead.
+
+# IDEA:
+# first -> last, second -> second to last, inner most is at the end
+
+# IDEA 2:
+
+# Cut list in half O(n) time O(1)
+# interlace lists O(n)
+# return nothing
+
+class Solution:
+ def reorderList(self, head: Optional[ListNode]) -> None:
+
+ # count length
+
+ current = head
+ n = 0
+
+ while current is not None:
+ n += 1
+ current = current.next
+
+ if n == 1:
+ return None
+
+ # compute half
+
+ midpoint_index = n // 2
+
+ # split half
+
+ midpoint = head
+
+ for i in range(0, midpoint_index - 1):
+ midpoint = midpoint.next
+
+ midpoint_left = midpoint
+ midpoint = midpoint.next
+ midpoint_left.next = None
+
+
+ # reverse second half
+
+ iterations = n - midpoint_index
+ left = midpoint
+ right = midpoint.next
+ left.next = None
+
+ for i in range(0, iterations - 1):
+ temp_next = right.next
+ right.next = left
+ left = right
+ right = temp_next
+
+ head_of_reverse = left
+
+ # interlace
+
+ # current_left = head
+ # current_right = head_of_reverse
+
+ current = head
+ next_node = head_of_reverse
+
+ while next_node is not None:
+ temp_next = current.next
+ current.next = next_node
+
+ current = next_node
+ next_node = temp_next
diff --git a/reverse-linked-list/reverse-list.py b/reverse-linked-list/reverse-list.py
@@ -0,0 +1,26 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, val=0, next=None):
+# self.val = val
+# self.next = next
+class Solution:
+
+ # number of nodes is min == 0
+ def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
+
+ if head is None or head.next is None:
+ return head
+
+ left = head
+ right = head.next
+ head.next = None
+
+ while right is not None:
+ temp = right.next
+ right.next = left
+ left = right
+ right = temp
+
+ head = left
+
+ return head
