Friedrich Ewald My Personal Website

Posts


  • Leetcode: Generate parentheses

    Given a strictly positive integer n, write a function that returns all possible combinations of well-formed parentheses. Parentheses can be nested and added one after the other. It is important that we don’t create invalid combinations, such as )(. The idea then becomes to start with a single set of parentheses (). We can add another set of parentheses at three possible places: 1(2)3. When looking closely, we see that 1 and 3 are the same position. We can then utilize Pythons string splitting capabilities which allow us to insert one or more characters at any place in the string. We do this by iterating over the string and inserting () at every possible position. This creates all valid pairs like (()) and ()() etc. To avoid the aforementioned duplicates we can add a memory to the function and store all the visited possible combinations. This allows us to speed the process up significantly. For example when we visit ()(), we don’t need to visit it again to form ()()() or ()(()) (for n=3) because they would already been visited.

    Continue reading

  • Leetcode: Word break

    Given a string s and a list of words, return True if the string can be constructed from any combination of the words and False otherwise. The alphabet contains only lowercase English characters. My initial idea was to replace all occurrences of a word in the string s. The problem with this approach is that a string aabb with the words ['ab'] is considered valid, while it is not. I then tried on adding breaking characters (.) to prevent this. It worked although very slowly.

    Continue reading

  • Leetcode: Maximum product subarray

    Given an array nums with integer values -10 <= x <= 10, calculate the maximum consecutive product. For example, the array [2,3,-1,4] produces the maximum product 6 because 2*3=6. The first obsveration that we can make is that whenever a 0 is encountered, it sets the whole product to 0. This means, if a 0 is somewhere in the middle of the array, we need to look at the left and right part individually because they cannot be connected. Secondly, an odd amount of negative numbers makes the whole product negative. Having 2, 4,, 6, … negative numbers will keep the product at the same amount (if all of them are -1) or increase it. Finally, since those numbers are all integers, the longer the chain of multiplied numbers, the higher to outcome.

    Continue reading

  • Leetcode: Sort list

    Given a single linked list, sort the values in ascending order.

    # Example
    Input: (4)->(3)->(1)->(2)
    Output: (1)->(2)->(3)-(4)

    Continue reading

  • Leetcode: Gas station

    Given two arrays, gas and cost and an infinite tank, it costs costs[i] to go from one index to the other. The most a car can get gas is gas[i]. The task is to determine whether a car can go a full round for any possible starting point. The program should return the starting index if it is possible and -1 if it is not possible to do so. Example:

    gas =  [1,1,2]
    cost = [2,1,1]
    # result: 2
    The result is 2, because we can start from index 2, get 2 units of gas, and it costs us 1 unit to go to 1, leaving us with 1 unit. Then we can get another unit which is exactly the required 2 units it takes us to get to 1 and from there we get 1 leaving us with 0 at 2 and completing the cycle.

    Continue reading

Page: 7 of 28