Preparation For Quantitative Trader/Researcher Job – Page 3

Question 392 Is Subsequence

The code is in the following link:

https://leetcode.com/problems/is-subsequence/

My code:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0:
            return True
        elif len(t) == 1:
            if s[0] == t[0]:
                return True
            else:
                return False
        else:
            i = 0
            CheckNum = 0
            while i< len(t):
                if s[CheckNum] == t[i]:
                    CheckNum +=1
                if CheckNum == len(s):
                    return True
                i+=1
            return False

Explanation:

Check one by one, if one element is confirmed, then we check next element in the string s. If the total all the element in the string s occur in string t, then we return true, otherwise we return false.

Question 746 Min costing climbing stairs

Description of the question can be found in the following link:

My code

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) == 2:
            return min(cost[0],cost[1])
        else:
            cost.append(0)
            TotalCostList = [0]*len(cost)
            TotalCostList[0] = cost[0]
            TotalCostList[1] = cost[1]
            for i in range(2,len(cost)):
                TotalCostList[i] = min(TotalCostList[i-1],TotalCostList[i-2])+ cost[i]
            return TotalCostList[len(cost)-1]

Explanation:

We just need to compare the cost of going from one step below or two steps below. One extra element appended to the cost is due to the final stage we need to check. Then we just need to take the final element of the total cost list to get the minimum to go to the top.

Question 256 Paint House

The description of the question is in the following link:

https://leetcode.com/problems/paint-house/

My code

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        if len(costs) == 0:
            return 0
        else:
            RedList = [0]*len(costs)
            BlueList = [0]*len(costs)
            GreenList = [0]*len(costs)
            RedList[0] = costs[0][0];
            BlueList[0] = costs[0][1];
            GreenList[0] = costs[0][2];
            for i in range(1,len(costs)):
                RedList[i]  = min(BlueList[i-1]+costs[i][0], GreenList[i-1]+costs[i][0])
                BlueList[i] = min(RedList[i-1]+costs[i][1], GreenList[i-1]+costs[i][1])
                GreenList[i]= min(RedList[i-1]+costs[i][2], BlueList[i-1]+costs[i][2])
            Min1 = min(RedList[-1],BlueList[-1])
            Min2 = min(Min1, GreenList[-1])
            return Min2

Explanation:

Here for each house, we have three choices: blue, green or the red, for each choice, we have different minimum costs that we can have in order to choose that specific color (green, red or blue). We do not know which one would provide the best choice, so we can have three different routines: Red List gives the minimum cost for choosing red this time, and similar for other lists. For the best answer, we just need to find the minimum cost on choosing three different colors at the end of the list.

Question 1025 Divisor Game

The description of the question is in the following link:

https://leetcode.com/problems/divisor-game/

My Code:

def divisorGame(self, N: int) -> bool:
        if N ==1:
            return False
        else:
            ResultList = [0]*(N+1)
            ResultList[0] = "Empty"
            ResultList[1] = "Lose"
            ResultList[2] = "Win" #Here win means that whoever takes this number has a strategy to win with 100%
            for i in range(3,N+1):
                LoseIndicator = 0
                TestNumber = math.ceil(i/2)
                for j in range(1,TestNumber+1):
                    if i/j == i//j:
                        if ResultList[i-j] == "Lose":
                            LoseIndicator +=1

                if LoseIndicator == 0:
                    ResultList[i] = "Lose"
                else:
                    ResultList[i] = "Win"
            if ResultList[N] =="Win":
                return True
            else:
                return False

Explanation: The win and lose here denotes if the one who chooses this number may win or not. As they are all optimal player, the only time they can win is that under all the situation (with all divisor x), the only choice for the other guy is win, otherwise they may choose the one that lead the opponent to lose.

Question 647 palindromic substrings

Description:

https://leetcode.com/problems/palindromic-substrings/

My Code

class Solution:
    def countSubstrings(self, s: str) -> int:
        InputList = [[s[i] for i in range(len(s))]]
        TotalNum = len(s)
        for i in range(len(s)-1):
            OldList = InputList[i]
            NewList = []
            for j in range(i+1,len(s)):
                NewString = OldList[j-i-1]+ s[j]
                NewList.append(NewString)
                if NewString  == NewString[::-1]:
                    TotalNum +=1
            InputList.append(NewList)
        return TotalNum

Explain:

Take all possible out and then test one by one. Saving time by using extra storage space.

Question 13 Roman to Integer

The description of the question is in the following link:

https://leetcode.com/problems/roman-to-integer/

My Code:

class Solution:
    def romanToInt(self, s: str) -> int:
        RomanToIntegerDict = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }
        if len(s) ==1:
            return RomanToIntegerDict[s[0]]
        else:
            OutputNum = 0
            i = 0
            while i< len(s):
                if i == len(s) -1:
                    OutputNum += RomanToIntegerDict[s[i]]
                    return OutputNum
                else:
                    KeyThis = s[i]
                    KeyNext = s[i+1]
                    if RomanToIntegerDict[KeyThis]< RomanToIntegerDict[KeyNext]:
                        OutputNum += RomanToIntegerDict[KeyNext]-RomanToIntegerDict[KeyThis]
                        i+=1
                    else:
                        OutputNum += RomanToIntegerDict[KeyThis]
                    i+=1
            return OutputNum

Explanation: the key point is to know how to read the roman number. Whenever the number behind you is larger than the value you have now, it means that you need to take the subtraction between the number later and the number you have now. Next point is to be careful with the last element in the string.

Question 523 Continuous SubArray Sum

The description of the code is in the following link

My Code

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        if len(nums) <2:
            return False
        else:
            if k == 0:
                InputList= nums[0:2]
                if sum(InputList)  == 0:
                    return True
                else:
                    SumList = [[sum(InputList[i:len(InputList)]) for i in range(len(InputList))]]
                    SumList = [[0],[0]]+SumList # To get the save for the list with length 2
                    for i in range(2, len(nums)):
                        NewList = []
                        for j in range(i):
                            NewSum = nums[i]+SumList[i][j]
                            if NewSum == 0:
                                return True
                            NewList.append(NewSum)
                        NewList.append(nums[i])
                        SumList.append(NewList)
                    return False
            else:
                InputList = nums[0:2];
                if sum(InputList) % k ==0:
                    return True
                else:
                    SumList = [[sum(InputList[i:len(InputList)]) for i in range(len(InputList))]]
                    SumList = [[0],[0]]+SumList # To get the save for the list with length 2
                    for i in range(2, len(nums)):
                        NewList = []
                        for j in range(i):
                            NewSum = nums[i]+SumList[i][j]
                            if NewSum %k  == 0:
                                return True
                            NewList.append(NewSum)
                        NewList.append(nums[i])
                        SumList.append(NewList)
                return False

Explanation: The key point is still doing it brutally. We check all the possible sum and whenever we encounter find there is a full division, we return true, otherwise we return false. Here we use one extra array to improve the time complexity, otherwise it is going to be n^3, now it is n^2

Another Approach: Using Hash Table (The Solution is not clearly clarified, need to do some further reading)

Question 122. Best Time to Buy and Sell Stock II

the description of the question is in the following link

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

My code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) ==0 or len(prices) ==1:
            return 0
        else:
            TotalProfit = 0
            i = 0
            while i < len(prices)-1:
                Buy = prices[i]
                Sell = prices[i+1]
                PriceDiff = Sell - Buy 
                TotalProfit  += max(PriceDiff,0)
                i+=1
            return TotalProfit

We can see the total profit as a cumulative daily return, the only difference is that whenever we encounter a negative daily return, we ignore the loss part. Hence we just need to add all the positive returns.

Question 121 Best Time to Buy and Sell Stock

The description of the question is given in the following link:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

My code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        else:
            Maximum = 0
            Buy = prices[0]
            Index = 1
            i= 1
            while(i<len(prices)):
                Sell = prices[i]
                profit = Sell-Buy
                if profit< 0:
                    Buy = Sell
                Maximum = max(profit, Maximum)
                i +=1
            return Maximum

Explanation:

This code is straightforward: We start from first element as buy in . Whenever we have a negative profit, it means that we have a lower price later, hence for any profit we have later, buy in with the lower price will definitely give the larger profit, that’s why we substitute the buy with sell here. Then for each time we compare the profit we have with the previous profit, which gives the maximum.

Question 96. Unique Binary Search Trees

The description of the question is in the following link:

My code:

class Solution:
    def numTrees(self, n: int) -> int:
        if n ==1:
            return 1
        elif n ==2 :
            return 2
        else:
            TotalNumberList = [1]*(1+n)
            for Length in range(2,n+1):
                TotalSum = 0
                for Index in range(Length):
                    NumberDevideByThisIndex = TotalNumberList[Index]*TotalNumberList[Length-1-Index]
                    TotalSum += NumberDevideByThisIndex
                TotalNumberList[Length] = TotalSum
            return TotalNumberList[n]

Explanation: It actually does not matter if the value is from 1 to n or otherwise, as long as they are sorted by some order. The logic is that for each particular value we choose, the list is divided into two parts: left list and right list. We just need to multiply the number in the left list and right list to get the total number of trees we have for this particular number. As for all the ordered list with the same length, they all have the same number of trees, hence we just need to start from the number of trees with one and zero, then gradually calculate from one to n and return the nth one in the list.