Blog Feed – Page 41 – 步步发财

LeetCode 14 – Python 3 (Week 05 – 06)

There are many ways to compare strings in strs. I just used vertical scanning and horizontal scanning, because I think the other methods are more complexity and harder to understand. Both solution 1 and solution 2 are vertical scanning. I found solution 2 online. “while true”, “try”, and “except” are use in solution 2.

Solution 1

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        
        for i in range(len(strs[0])):
            for string in strs[1:]:
                if len(string) <= i or strs[0][i] != string[i]:
                    return string[:i]
        #return "" is not right when the length of strs is 1.
        return strs[0]

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

Solution 2

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        ans = ""
        i = 0
        
        
        while True:
            try:
                s = set(string[i] for string in strs)
                if len(s) == 1:
                    ans += s.pop()
                    i += 1
                else: break
            except: break
                
        return ans

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

Solution 3

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        ans = strs[0]
    
        for i in range(1, len(strs)):

            for string in strs[1:]:
                if len(string) < len(ans):
                    ans = ans[:len(string)]
                j = 0
                while j < len(ans):
                    if string[j] == ans[j]:
                        j += 1
                    else:
                        ans = strs[0][:j]
                        break          
                                     
        return ans

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

LeetCode 26 – Python 3 (Week 5 – 05)

Solution 1

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        length = 0
        for i in range(len(nums)):
            if nums[length] != nums[i]:
                length += 1                
                nums[length] = nums[i]
                
        return length + 1

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

Solution 2

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums)-1:
            if nums[i] == nums[i+1]:
                nums.remove(nums[i+1])
            else: i += 1
                
        return len(nums)

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

LeetCode 13 – Python 3 (Week 5 – 04)

Solution 1

class Solution:
    def romanToInt(self, s: str) -> int:
        number_map, ans = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M': 1000}, 0
        
        for i in range(len(s)):
            if i > 0 and number_map[s[i]] > number_map[s[i-1]]:
                ans += number_map[s[i]] - 2*number_map[s[i-1]]
            else: ans += number_map[s[i]]
                
        return ans

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

LeetCode 7 – Python 3 (Week 5 – 03)

Solution 1

The integers within the 32-bit signed integer range: [−2³¹, 2³¹− 1].

class Solution:
    def reverse(self, x: int) -> int:
        
        ans = 0
        while x > 0:
            ans = ans * 10 + x % 10
            x = int(x / 10)
            
        if x < 0:
            x = - x
            while x:
                ans = ans * 10 + x % 10
                x = int(x / 10)
            ans = - ans
            
        return ans if -2**31<=ans<=2**31-1 else 0

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

LeetCode 617 – Python 3 (Week 5 – 02)

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 mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1: return t2
        if not t2: return t1
        
        ans = TreeNode(t1.val + t2.val)        
        ans.left = self.mergeTrees(t1.left, t2.left)
        ans.right = self.mergeTrees(t1.right, t2.right)
        
        return ans

Time complexity is O(n). Space complexity is O(m). n is the minimum number of nodes from the two given trees. m is the depth.

Solution 2

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

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1: return t2
        if not t2: return t1
        
        stack = []
        stack.append((t1, t2))
        while stack:
            t = stack.pop()
            if t[1]: t[0].val += t[1].val
            else: continue
            
            if t[0].left is None: t[0].left = t[1].left
            else: stack.append((t[0].left, t[1].left))
            
            if t[0].right is None: t[0].right = t[1].right
            else: stack.append((t[0].right, t[1].right))
            
        return t1

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

LeetCode 581 – Python 3 (Week 5 – 01)

Solution 1

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        
        snums = sorted(nums)
        right = 0 
        left = len(nums) - 1
        
        for i in range(len(nums)):
            if nums[i] != snums[i]:
                right = max(right, i)
                left = min(left, i)
                
        return 0 if right-left<=0 else right-left+1

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

Solution 2

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        
        maxnum = - float("inf")
        minnum = nums[len(nums) - 1]
        
        for i in range(1, len(nums) -1):
            if nums[i] < nums[i-1]:
                minnum = min(minnum, nums[i])
            
        i = len(nums) - 2    
        while i >= 0:
            if nums[i] > nums[i+1]:
                maxnum = max(maxnum, nums[i])
            i = i-1
        
        left = 0
        while left < len(nums):
            if nums[left] > minnum:
                break
            left = left + 1
         
        right = len(nums) - 1       
        while right >= 0:
            if nums[right] < maxnum:
                break
            right = right - 1
                
                
        return 0 if right-left<0 else right-left+1

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

LeetCode 595 – MySQL (Week 4 – 06)

Solution 1

SELECT
    name, population, area
FROM
    world
WHERE
    area > 3000000 OR population > 25000000;

Solution 2

We also can use UNION. I think it’s not necessary.

LeetCode 543 – Python 3 (Week 4 – 05)

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 diameterOfBinaryTree(self, root: TreeNode) -> int:
        
        self.ans = 0
        
        def depth(node):
            if not node: return 0
            L = depth(node.left)
            R = depth(node.right)
            self.ans = max(self.ans, L+R)
            return max(L, R) + 1
            
        depth(root)
        
        return self.ans

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

Convert BST to Greater Tree – Python 3 (Week 4 – 04)

The third solution is tricky and slow. But its space complexity is O(n).

Solution 1

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the new root
    """
    def convertBST(self, root):
        # write your code here
        self.sum = 0
        self.dfs(root)
        
        return root
    
        
    def dfs(self, root):
        if not root:
            return
        self.dfs(root.right)
        self.sum += root.val
        root.val = self.sum
        self.dfs(root.left)

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

class Solution:
    def __init__(self):
        self.total = 0
    
    def convertBST(self, root: TreeNode) -> TreeNode:
        
       #Recurision
        if root is not None:
            self.convertBST(root.right)
            self.total += root.val
            root.val = self.total
            self.convertBST(root.left)
        return root

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

Solution 2

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

class Solution:
  
    def convertBST(self, root: TreeNode) -> TreeNode:
        
        #Iteration
        total = 0
        stack = []
        node = root
        
        while node or stack: #"while stack or node is not None" "while stack or node"
            #"while node or stack is not None" is wrong****
            
            while node is not None:
                stack.append(node)
                node = node.right #add all node to the stack until none
                
            node = stack.pop()
            total += node.val
            node.val = total
            
            node = node.left
            
        return root

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

Solution 3

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

class Solution:
  
    def convertBST(self, root: TreeNode) -> TreeNode:
        
        node, total = root, 0
        while node:
            if not node.right:
                total += node.val
                node.val = total
                node = node.left
            else:
                pred = node.right
                while pred.left and pred.left is not node:
                    pred = pred.left
                if pred.left is node:
                    pred.left = None
                    total += node.val
                    node.val = total
                    node = node.left
                else:
                    pred.left = node
                    node = node.right
        return root

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

LeetCode 442 – Python 3 (Week 4 – 03)

Solution 1

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for num in nums:
            index = abs(num) - 1
            if nums[index] > 0:
                nums[index] = - nums[index]
            else:
                res.append(index+1)
        
        return res

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