Category: LeetCode

Link:

https://leetcode.com/problems/perfect-squares/

My Code:

class Solution:
    def numSquares(self, n: int) -> int:
        if n ==1:
            return 1
        else:
            NumList = [0]
            for Number in range(1,n+1):
                Min = 2**31
                SquareNum = math.floor(math.sqrt(Number))
                for j in range(1,(SquareNum+1)):
                    Min = min(Min,NumList[Number-j**2])
                NumList.append((Min+1))
            return NumList[n]

Explanation

It is clear that we for number a , we may check the number squares the a-k is made of and then take the minimum among them. A typical dynamic programming problem.

Link

https://leetcode.com/problems/minimum-falling-path-sum-ii/submissions/

My Code:

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if len(arr) ==1:
            return arr[0][0]
        else:
            Row = len(arr)
            Col = len(arr[0])
            ResultMat = [arr[0]] 
            for i in range(1,Row):
                ResultList = []
                for j in range(Col):
                    NewList= ResultMat[i-1]
                    NewList = NewList[0:j] + NewList[(j+1):len(NewList)]
                    Min = min(NewList)
                    Value = Min+arr[i][j]
                    ResultList.append(Value)
                ResultMat.append(ResultList)
            return min(ResultMat[Row-1])

Explanation: Similar with question 931, just check all the available value and choose the minimum value.

Link

https://leetcode.com/problems/minimum-falling-path-sum

My Code:

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        Row = len(A)
        Col = len(A[0])
        ResultMat = [A[0]]
        if Col ==1:
            Sum =0
            for i in range(Row):
                Sum+= A[i][0]
            return Sum
        else:
            for i in range(1,Row):
                RowIList = []
                for j in range(Col):
                    if j ==0:
                        Value = min(ResultMat[i-1][j],ResultMat[i-1][j+1])+A[i][j]
                        RowIList.append(Value)
                    elif j == (Col-1):
                        Value = min(ResultMat[i-1][j-1],ResultMat[i-1][j])+A[i][j]
                        RowIList.append(Value)
                    else:
                        Value = min(ResultMat[i-1][j-1],ResultMat[i-1][j],ResultMat[i-1][j+1])+ A[i][j]
                        RowIList.append(Value)
                ResultMat.append(RowIList)
            return min(ResultMat[Row-1])

Explanation:

The recursion we are using is a matrix. Mat[i][j] means the minimum value path we take going to the ith row and jth  col of the original matrix. The recursion is desinged as above: For each element, there are three choices ( except for two boundary elements). we then choose the minimum of them as the choice and then we add the value at the point, to get the minimum value up to this element. Based on this method, the value at each element is the minimum value path up to this element. Hence we just need to take out all the minimum value in the last row and then take the minimum value among them as the output.

Link:

https://leetcode.com/problems/subtract-the-product-and-sum-of-digits-of-an-integer/

My code:

class Solution:
    def subtractProductAndSum(self, n: int) -> int:
        IntLength = math.floor(math.log10(n))+1
        Sum = 0
        Prod =1
        Num = n
        for i in range(IntLength):
            Digit = Num %10
            Num = (Num-Digit)/10
            Sum += Digit
            Prod *= Digit
        Diff =int(Prod - Sum)
        return Diff

Explanation:

The idea is clear , just take out allthe digits and then calculate the result.

Link:

https://leetcode.com/problems/arithmetic-slices/

My code:

class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        if len(A)<3:
            return 0
        else:
            #Here the dynamic programming we use here dp[i] is the number of arithmetic list end up with ith element
            ArSeqList = [0,0]
            for i in range(2,len(A)):
                if A[i]-A[i-1] == A[i-1]-A[i-2]:
                    Num = ArSeqList[i-1] +1
                    ArSeqList.append(Num)
                else:
                    ArSeqList.append(0)
            return sum(ArSeqList)

The idea of the code:

The recursion follows the idea like this: the ith of the storage list is the number of the arithmetic sequence end up with ith element in the original list. Given the number of the ith element, the number of (i+1)the element is determined by following logic: we check if the difference between ith element and i-1 th element and i-1 and i-2 the element. If they are the same, then we know that for any arithmetic sequence end up with i-1th element, we put ith elment in the list it is also arithmetic as it is tested by the previous test. So the total number is the number of the arithmetic sequence end up with i-1th elment +1. If the difference are not the same, them there is no arithmetic sequence end up with ith element as if there is one, it must include at least three elements, however, the first possible choice if denied by this test. Hence with this recursion, we may figure out all the am sequence end up with ith element in the original list, the to get the total result, we just need to sum all the numbers in the result list.

Link:

https://leetcode.com/problems/counting-bits/

 

My Code:

class Solution:
    def countBits(self, num: int) -> List[int]:
        if num == 0:
            return [0]
        else:
            Exponent = math.floor(math.log2(num))+1
            OutPutList = [0]

            for i in range(Exponent):
                NewList = [x+1 for x in OutPutList]
                OutPutList = OutPutList + NewList
            OutPutList = OutPutList[:(num+1)]
            return OutPutList

Explanation:

Notice that the there are changes occur at indices 2^i. Here we notice that, for for the number between 2^i and 2^i-1, the binary representation is 1xxxx(i numbers after 1), the number of ones in this range is 1 + all the numbers for the list from 0 to 2^i-1. Hence for we just find out all the possible exponents, and we first plus one for all the elements in the previous list, then we concatenate this list in the original list to obtain the list up to 2^i. Here we take one more because the number might not be exact the power of two. For the Last line, we take out the list we need and return it.

 

Link

https://leetcode.com/problems/minimum-cost-for-tickets/

My code

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        if len(days) ==0:
            return 0
        else:
            CostList = [0] #Initialise for the day 0, the cost is always 0
            TotalNumberDays = days[-1]
            for i in range(1,TotalNumberDays+1):
                if i not in days:
                    CostList.append(CostList[i-1])
                else:
                    Index1 = max(i-1,0)
                    Index2 = max(i-7,0)
                    Index3 = max(i-30,0)
                    value1 = CostList[Index1]+costs[0]
                    value2 = CostList[Index2]+ costs[1]
                    value3 = CostList[Index3]+ costs[2]
                    Min1  = min(value1,value2)
                    Min2 = min(Min1,value3)
                    CostList.append(Min2)
        return CostList[TotalNumberDays]

Explanation:

The idea is this: On a specific day, we want to know if it is included in the specific ticket. There are two situations: if that day is not included in the travel days, then we just keep the value as it is yesterday ( i-1). The other situation is that it is in the travel days, then we want to know which ticket length does it take. To maximize the usage, we definitely want to make that day as the last day of the ticket. if that day is not the last day of the ticket, we can simply achieve a not worse result by purchasing the ticket one day before as the total cost of the ticket is non decreasing as the day increases. Hence we have three values, given by three length of the ticket. Then we take the minimum of these three as the minimum  value of the day on the year so far.

Link:

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

My Code:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) ==1:
            return nums[0]
        elif len(nums) ==2:
            return max(nums[0],nums[1])
        elif len(nums) ==3:
            return max(nums[0]+ nums[2], nums[1])
        else:
            Index = 3
            MaxList = [0]* (len(nums)+3)
            while Index < len(nums)+3:
                if nums[Index-3] ==0:
                    MaxList[Index] = max(MaxList[Index-1],MaxList[Index-2])
                    if Index == len(nums)+2 :
                        break
                    else:
                        Index+=1
                        MaxList[Index] = MaxList[Index-1]+nums[Index-3]
                else:
                    MaxList[Index] = max(MaxList[Index-2],MaxList[Index-3])+nums[Index-3]
                Index +=1
        return max(MaxList[len(MaxList)-1], MaxList[len(MaxList)-2])

Explanation: Two issues: if there is an zero in the list, there is definitely no need to rob that house, as that would eliminates the opportunities to rob the house next to it with no extra benefit. So the evaluate the list for the 0 zero value house as the maximum between the house one block before it and the house two blocks before it. We do not take the third house as if we choose to rob the three houses before the house we are facing now, it does no damage to rob the house one house before the house we are facing now, as the value is non negative. Similar for the situation when the value for the house is not zero. We just need to take the max between the house two blocks before it and three blocks before it, then add the value of the house we are facing now. So we just keep the calculation and take the maximum between the last one and the second last one in the list.

Description of the question:

https://leetcode.com/problems/range-sum-query-immutable/

My Code:

class NumArray:

    def __init__(self, nums: List[int]):
        self.sums = [0]*len(nums)
        
        Sum = 0
        
        for i, j in enumerate(nums):
            Sum += j
            self.sums[i] = Sum
            

    def sumRange(self, i: int, j: int) -> int:
        if i ==0 :
            return self.sums[j]
        else:
            return self.sums[j]-self.sums[i-1]

 

Explanation: we store each sum into the object function OO.sums, then whenever we need to use it, we may be able to call this function and use it. This extra space used may save time from repeated calculation.