Tag Archives: Leetcode

Evaluate Division

Posted on by
Reply

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = dict()
        
        # Build graph
        for (a, b), value in zip(equations, values):                
            graph[a] = graph.get(a, []) + [(b, value)]
            graph[b] = graph.get(b, []) + [(a, 1/value)]

            
        def check(source, target):   
            # If there is any one number of the query didn't appear in the graph, answer certainly doesn't exist.
            if source not in graph or target not in graph:
                return -1.0
            
            visited = set()
            stack = collections.deque([(source, 1.0)])
            
            while stack:
                front, current = stack.popleft()
                
                if front == target:
                    return current
                
                visited.add(front)
                
                for back, value in graph[front]:
                    if back not in visited:
                        stack.append((back, current * value))
            
            return -1.0
        
        return [check(source, target) for (source, target) in queries]

Implement Trie (Prefix Tree)

Posted on by
Reply

我今天是打算去维妈买螃蟹的。

因为昨天自行车放在学校没有骑回家，所以今天是坐电车去学校的。上车的时候，算了一下边际成本，愉快的刷了卡。

到了州立图书馆之后，本来是说要去吃DonDon的，但是想到学校旁边的Don Tojo就突然想吃点别的了。于是找了一家网红店吃了一份鳗鱼饭。

吃完饭，捋了捋自己狂放不羁的头发，顺道去了一趟理发店。理完发，神清气爽的去了维妈。

发现没开门。

之后回学校坐定开始学校，打算随手水道题，于是瞄了一眼问题列表，选了Trie Tree。

以前写Trie都是要写好久的，但是这次居然五分钟不到就一次性Bug Free了，蛮开心的。

↓Code inside ↓

Continue reading →

Missing Ranges

Posted on by
Reply

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example:

Input:   nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]
class Solution:
    def findMissingRanges(self, nums, lower: int, upper: int):
        nums.insert(0, lower-1) # Left Bound
        nums.append(upper+1)    # Right Bound
       
        res = []

        for i in range(len(nums)-1):
            left, right = nums[i], nums[i + 1]

            if left != right:
                if right - left == 2:
                    res.append(str(left+1))
                elif right - left > 2:
                    res.append(str(left+1) + "->" + str(right-1))

        return res

Longest Consecutive Sequence

Posted on by
Reply

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        ans = 0
        
        for x in nums:
            # Find the first element in one segment
            if x-1 not in nums:
                y = x + 1
                # reach the last consecutive element in one element  
                while y in nums:
                    y += 1
                ans = max(ans, y - x)
             
        return ans
class Solution:
    def longestConsecutive(self, nums) -> int:
        UF = {}
        nums = set(nums)

        if not nums:
            return 0

        # for num in nums:
        #     UF[num] = num

        def find(x):
            if x != UF[x]:
                UF[x] = find(UF[x])
            return UF[x]

        def union(x, y):
            UF.setdefault(x, x)
            UF.setdefault(y, y)
            UF[find(x)] = find(y)

        for n in nums:
            if (n - 1) in nums:
                union(n - 1, n)
            if (n + 1) in nums:
                union(n, n + 1)

        ans = 1

        for num in nums:
            if num in UF:
                ans = max(ans, find(num) - num + 1)
        return ans

Most Stones Removed with Same Row or Column

Posted on by
Reply

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]

At very first I read this problem, the MOVE operation is described as confusing as heck. I read some explanations on the discussboard, and then finally got the actual meaning.

We can treat each coordinate as two parts (x and y), and can maintain an Union-Find in order to calculate how many groups in the entire field.

 class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        UF = {}
        
        def find(x):
            if x != UF[x]:
                UF[x] = find(UF[x])
            return UF[x]
        
        def union(x, y):
            UF.setdefault(x, x)
            UF.setdefault(y, y)
            UF[find(x)] = find(y)


        for i, j in stones:
            print(i, j, ~j)
            union(i, ~j)
            
        return len(stones) - len({find(x) for x in UF})

Brace Expansion

Posted on by
Reply

A string S represents a list of words.

Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.  If there is more than one option, then curly braces delimit the options.  For example, "{a,b,c}" represents options ["a", "b", "c"].

For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].

Return all words that can be formed in this manner, in lexicographical order.

Example 1:

Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

Example 2:

Input: "abcd"
Output: ["abcd"]

Note:

  1. 1 <= S.length <= 50
  2. There are no nested curly brackets.
  3. All characters inside a pair of consecutive opening and ending curly brackets are different.
class Solution:
    def expand(self, S):

        def func(remain, result, results):
            if not remain:
                results.append(result)

            else:
                # if a single character appear at the first of the remain string
                if remain[0] != "{":
                    func(remain[1:], result + remain[0], results)
                    return
                else:
                    temp = list()
                    i = 0

                    # find elements in the first brace of the remain string
                    while remain[i] != "}":
                        if remain[i].isalpha():
                            temp.append(remain[i])
                        i += 1

                    for t in temp:
                        func(remain[i + 1:], result + t, results)

        results = []

        func(S, "", results)

        return results

Delete Nodes And Return Forest

Posted on by
Reply

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest.  You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

  • The number of nodes in the given tree is at most 1000.
  • Each node has a distinct value between 1 and 1000.
  • to_delete.length <= 1000
  • to_delete contains distinct values between 1 and 1000.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        forest = []
        to_delete = set(to_delete)
        
        def buttom_up(root):
            if root:
                left, right = dfs(root.left), dfs(root.right)
                
                root.left, root.right = left, right
                
                if root.val in to_delete:
                    if left: forest.append(left)
                    if right: forest.append(right)
                else:
                    return root
        
        dfs(root)
        
        return ([] if root.val in to_delete else [root]) + forest
        
        #########################################################
        
        to_delete_set = set(to_delete)
        res = []

        def top_down(root, is_root):
            if not root: 
                return None
            
            root_deleted = root.val in to_delete_set
            
            if is_root and not root_deleted:
                res.append(root)
                
            root.left = helper(root.left, root_deleted)
            root.right = helper(root.right, root_deleted)
            
            return None if root_deleted else root
        
        top_down(root, True)
        
        return res

Decode String

Posted on by
Reply

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
class Solution:
    def decodeString(self, s: str) -> str:
        stack = list()
        times = list()

        for i, v in enumerate(s):
            if v.isdigit():
                # Single Digit, like 1,2,3...
                if not s[i-1].isdigit():
                    times.append(int(v))
                # Multiple digits, like 100, 200...
                else:
                    times[-1] = times[-1] * 10 + int(v)
            
            # push
            elif v != "]":
                stack.append(v)
            
            # reach "]"
            else:
                # Retrive string in cloest level square brackets
                b = ""
                t = stack.pop()
                while t != "[":
                    b = t + b
                    t = stack.pop()

                stack.append(b * times.pop())

        return "".join(stack)

Sentence Similarity II

Posted on by
Reply

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar, if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is transitive. For example, if “great” and “good” are similar, and “fine” and “good” are similar, then “great” and “fine” are similar.

Similarity is also symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Note:

  • The length of words1 and words2 will not exceed 1000.
  • The length of pairs will not exceed 2000.
  • The length of each pairs[i] will be 2.
  • The length of each words[i] and pairs[i][j] will be in the range [1, 20].
class Solution:
    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
        parent = {}
        
        if len(words1) != len(words2):
            return False
        
        def find(w):
            if w not in parent:
                return w
            if parent[w] != w:
                w = find(parent[w])
            return w
        
        
        def union(w1, w2):
            parent[w1] = w2
        
        
        for pair in pairs:
            union(find(pair[0]), find(pair[1]))
        
        
        for word_pair in zip(words1, words2):
            if word_pair[0] == word_pair[1]:
                continue
            else:
                leader1 = find(word_pair[0])
                leader2 = find(word_pair[1])
                if leader1 == leader2:
                    continue
                else:
                    return False
        return True

Campus Bikes II

Posted on by
Reply

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation: 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

  1. 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
  2. All worker and bike locations are distinct.
  3. 1 <= workers.length <= bikes.length <= 10
from functools import lru_cache

class Solution:
    def dis(self, a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
        
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        @lru_cache(None)
        def dfs(p, arr):
            return 0 if p == self.W else min([self.dis(bikes[i], workers[p]) + dfs(p + 1, arr + 2 ** i) for i in range(self.B) if not (arr>>i) & 1])

        self.W = len(workers)
        self.B = len(bikes)
        
        return dfs(0, 0)