Author: CongranLu

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.

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.

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.

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)

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.

The description of the question is in the following link:

https://leetcode.com/problems/climbing-stairs/

My Code:

class Solution:
    def climbStairs(self, n: int) -> int:
        Ladder = [1]*n;
        if n ==1: 
            return 1;
        else:
            Ladder[1] = 2;
            for LadNum in range(2,n):
                Ladder[LadNum] = Ladder[LadNum-1]+Ladder[LadNum -2]
            return Ladder[n-1]

Explanation:

The idea is clear: the only way to reach the nth ladder is that going from n-1th ladder with 1 step and n-2th ladder with 2 steps. So we just need to sum the number of steps to reach these two ladders to get the step to reach nth ladder. Just need to be very careful about some special situation and initialisation.