Writing
-
Leetcode: House robber
Continue readingGiven an array of
numsthat represent the loot of a house robber, return the maximum amount of money a robber can steal. The only rule is that a robber can not steal from two neighboring houses.When looking at this problem, we can see that we want to maximize the number of houses that we rob from. Consider the following array:
[0,1,0,1]. Our maximum profit is2, because we can rob the house at index1and index3. If we were to rob at index0and2, we would only gain0profit. We cannot however simply compare the even versus the odd indices because there could also be the following situation:[10,5,5,10]. Here, it is advantageous to skip2instead of just skipping1. We need to look at every step if we want to visit the one after the next or the one after this. We don’t need to look if we want to visit the one after this, because then we could also simply have visited the one after the next. -
Leetcode: Palindrome linked list
Continue readingGiven the
headof a linked list, determine if the linked list is a palindrome and returnTrueif it is,Falseotherwise. For added difficulty, find an algorithm that runs inO(n)and usesO(1)space. -
Leetcode: Intersection of two arrays II
Continue readingGiven two arrays,
nums1andnums2, return the intersection of those arrays in any order.The easiest way I was able to come up with was to sort the arrays first and then look at the beginning of the arrays. If both are equal, add the element to the output and pop the first element from each array. Otherwise, pop the smaller element of both arrays. Repeat this until one of the arrays is empty at which point there can be no more intersecting elements.
-
Leetcode: Power of three
Continue readingGiven a number
n, check if this number is a power of three, that is that it can be represented by3^x.A straightforward solution looks as follows. Multiply by
3until we reachn. If we’re greater thann, returnFalse, andTrueotherwise.class Solution: def isPowerOfThree(self, n: int) -> bool: if n <= 0: return False x = 1 while x < n: x *= 3 return x == n -
Leetcode: Kth smallest element in matrix
Continue readingGiven a
n*nmatrix, find thekthsmallest element. Each row in the matrix is sorted in ascending order and independent of the other rows. Do not useO(n*n)space when solving this. One example matrix looks like this:1 5 9 10 11 13 12 13 15 For k = 8 return 13 because 13 is the 8th smallest element.If we could use all the space we wanted, we could just perform an n-way merge sort on every row at once. This would work because the rows itself are sorted already. Afterwards, we would need to pick the kth element from the list and would be done.