2022-2023 - Class 3

This class was about classes and sorting algorithms

Slides

Solution to problem on slide 3:

roman = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
z = 0
for i in range(0, len(s) - 1):
   if roman[s[i]] < roman[s[i+1]]:
      z -= roman[s[i]]
   else:
      z += roman[s[i]]
   return z + roman[s[-1]]

Solution to problem on slide 5:

# iterate through l1 and l2 if one head-value is less than the other head-value than it must be the smallest value in both of the current lists so add it to the list. At the end when one list is empty you can simply append the rest of the elements to the list. Here is a fast solution that uses that algorithm.
dummy = cur = ListNode(0)
while l1 and l2:
    if l1.val < l2.val:
        cur.next = l1
        l1 = l1.next
    else:
        cur.next = l2
        l2 = l2.next
    cur = cur.next
cur.next = l1 or l2
return dummy.next

Solution to problem on slide 7:

(I'm not sure whether this is a homework problem or not, if it is, look at the solution after attempting the problem yourself)

n = len(A)
m = len(B)if n>m:
    return self.findMedianSortedArrays(B,A)
k = (n+m-1)//2
l = 0
r = min(k,n)
while l<r:
    midA = (l+r)//2
    midB = (k-midA)
    if A[midA] < B[midB]:
        l = midA +1
    else:
        r = midA
#recursion splits combined array into 4 sections:
# A into A[0:midA] and A[midA:n]
# B into B[0:midB] and B[midB:m]
# since the total length is n+m and midA + midB = k = (m+l)//2 then
# midA and midB split the two arrays in half collectively. 
# so the median is between these 4 numbers: A[l-1], A[l], B[k-l], and B[k-l+1] 
# 2 of the smaller values could be A[l-1] and B[k-l]
m1 = max(A[l-1] if l > 0 else float(-1e6), B[k-l] if k-l >= 0 else float(-1e6))
# 2 of the greator values could be A[l] and B[k-l+1]
m2 = min(A[l] if l < n else float(1e6), B[k-l+1] if k-l+1 < m else float(1e6))
if (n+m) % 2 != 0:
    #if length is odd this is the answer
    return m1
else:
    #if length is even this is the answer
    return (m1+m2)/2.0

Let me know if you have any questions about the slides or code in this post or need help understanding a problem or its solution (discord is probably your best bet).