Category: Uncategorized

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.

 

The description of the code is included in the following link.

class Solution:
    def reverse(self, x: int) -> int:
        if(x>=0):
            z = int(str(x)[::-1]);
            if (z>(2**31-1) ):
                return(0);
            else:
                return(z);
                
        else:
            z = abs(x);
            z = int(str(z)[::-1]);
            z = -z;
            if (z<-2**31):
                return(0);
            else:
                return(z);

Explain:

Turn integer into string and then take reverse of the string and then turn it back. Only thing that needs to be careful is if it exceeds the range proposed in the question.

 

The description of the question in the following link

https://leetcode.com/problems/longest-palindromic-substring/submissions/

My Code:

Explanation:

As we are looking for the substring, the idea is straightforward: writing a function that checks all the substring with possible length, from 1 to the length of whole string. The only thing that we need to be very careful is about the index of the substring. I have made several mistakes, and I want to summarize some useful situations here.

Assume z is a string, with length k;

1. z[j] : Take the j+1 th element in the string. (j < k)
2. z[j:j+i]: Take the substring from j to j+i-1
3. z[-j]: Take the jth last element of the string (starting from -1)
4. z[::-1]: Reverse the string
5. z[i:i] : Gives nothing (null)

Hence the first loop of the code initialize all the possible length, from 1 to total length.

The second loop gives all the possible starting checking point for each i given by the first loop indicator. Hence we may check all the possible substring and determine the longest palindromic substring.

P.S. When I am writing this review, I have an idea that may improve the speed of this code. 1. We may start from the longest substring to shortest. Whenever we find the longest one we do not need to continue the search.

2. Code by another submitter ；

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(l, r):
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1:r]
        pals = [check(i, i) for i in range(len(s))] + [check(i, i + 1) for i in range(len(s) - 1) if s[i] == s[i + 1]]
        return sorted(pals, key = len)[-1] if pals else ''

The idea of this code is to start from each element in the string and start the comparison between left and right expansion. The second last line first summand is to check when the centre of the palindromic substring is a single letter and the second summand is to check when the centre of the palindromic substring is two same letters. And the sum is a list with all the palindromic string.  The last line is to do the sort based on the length of the strings and return the last one which has the longest length.

The description of the question is in the following link.

The idea is really clear: For the longest substring, different from the longest subsequence, they must be continuous, hence if for the first time we meet a repeated character, we shall abandon all the character before and included the repeated one, because for any string starting before the repeated character, there will always be a repetition in the string. For each time, we take the maximum between the max we have already had and the maximum of sub string we have now.