Blog Feed – Page 40 – 步步发财

LeetCode 171 – Python 3 (Week 05 – 16)

Solution 1

class Solution:
    def titleToNumber(self, s: str) -> int:
        dic = {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5, 'F': 6, 'G': 7,
			   'H': 8, 'I': 9, 'J': 10, 'K': 11, 'L': 12, 'M': 13, 'N': 14,
			   'O': 15, 'P': 16, 'Q': 17, 'R': 18, 'S': 19, 'T': 20, 'U': 21,
			   'V': 22, 'W': 23, 'X': 24, 'Y': 25, 'Z': 26}
        
        ans = 0
        for i in range(len(s)):
            ans = ans*26 + dic[s[i]]
            
        return ans

Time complexity is O(len(s)). Space complexity is O(1)

LeetCode 125 -Python 3 (Week 05 – 15)

Solution 1

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) == 0:
            return True
        l = 0
        r = len(s) - 1
        while 0 <= l < r < len(s):            
            while 0 <= l < r < len(s) and not s[l].isalnum() :
                l += 1
            while 0 <= l < r < len(s) and not s[r].isalnum():
                r -= 1
            
            if s[l].lower() != s[r].lower():
                return False
            
            l += 1
            r -= 1
            
        return True

Time complexity is O(n). Space complexity is O(1).

Solution 2

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = "".join(filter(lambda c: c.isalnum(), s.lower()))
        return s == s[::-1]

Time complexity is O(n). Space complexity is O(1).

LeetCode 122 -Python 3 (Week 05 – 14)

Solution 1

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2: 
            return 0
        
        ans = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                ans += prices[i] - prices[i-1]
        return ans

Time complexity is O(n). Space complexity is O(1).

LeetCode 118 -Python 3 (Week 05 – 13)

Solution 1

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0: return []
    
        ans = []
        
        for n in range(numRows):
            tmp = []
            for i in range(n+1):
                if i == 0 or i == n: tmp.append(1)
                else:
                    tmp.append(ans[n-1][i-1]+ans[n-1][i])
            ans.append(tmp)
            
        return ans

Time complexity is O(n^2). Space complexity is O(n^2).

LeetCode 108 – Python 3 (Week 05 – 12)

Solution 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums: return None
        
        mid = len(nums) // 2
        #mid = (len(nums)+1) // 2 not right
        
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        
        return root

Time complexity is O(n). Space complexity is O(n).

LeetCode 88 – Python 3 (Week 05 – 11)

Solution 1

 class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0:
            #nums1 = nums2
            for i in range(len(nums2)):
                nums1[i] = nums2[i]
            
            
        else:
            i = m -1
            j = n - 1
            while i >= 0 and j >= 0:
                if nums1[i] > nums2[j]:
                    nums1[i+j+1] = nums1[i]
                    i -= 1
                else:
                    nums1[i+j+1] = nums2[j]
                    j -= 1
          
            if i < 0: 
                nums1[0:j+1] = nums2[0:j+1]

Time complexity is O(n+m). Space complexity is O(1).

LeetCode 69 – Python 3 (Week 5 – 10)

Solution 1 is straightforward. Solution 2 uses binary search. Solution 3 uses Newton’s Iteration.

Solution 1

class Solution:
    def mySqrt(self, x: int) -> int:
        i = 0
        
        while x >= i*i:
            i += 1
            
        return i - 1

Time complexity is O(n). Space complexity is O(1).

Solution 2

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2: return x
        left, right = 1, x // 2
        
        while left <= right:
            mid = left + (right - left) // 2
            if x < mid*mid:
                right = mid - 1
            else: left = mid + 1
                
        return left - 1

Time complexity is O(logn). Space complexity is O(1).

Solution 3

class Solution:
     def mySqrt(self, x: int) -> int:
         return int(x**0.5)

Time complexity is O(1). Space complexity is O(1).

Solution 4

class Solution:
    def mySqrt(self, x: int) -> int:
        x_previous = x
        x_current = x / 2
        precision = 0.1
        while abs(x_previous - x_current) > precision:
            x_previous = x_current
            x_current = (1/2) * (x_current + x/x_current)
            
        return int(x_current)

Time complexity is O(logn). Space complexity is O(1).

LeetCode 66 – Python 3 (Week 5 – 09)

Solution 1

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        
        for i in reversed(range(len(digits))):
            if digits[i] == 9:
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
        
        digits[0] = 1
        digits.append(0)
        return digits

Time complexity is O(n). Space complexity is O(1).

LeetCode 38 – Python 3 (Week 05 – 08)

Solution 1

class Solution:
    def countAndSay(self, n: int) -> str:
        ans = '1' 
        for i in range(1, n):
            ans = self.getans(ans)
        return ans
    
    
    def getans(self, ans):
        i, next_ans = 0, ""
        while i < len(ans):
            count = 1
            while i < len(ans)-1 and ans[i] == ans[i+1]:
                count += 1
                i += 1
            next_ans += str(count) + ans[i]
            i += 1
        return next_ans

Time complexity is O(nk). Space complexity is O(1).