代码之家 › 专栏 › 技术社区 › Chubaka

广度优先搜索:如何获得货币兑换?

breadth-first-search numpy algorithm python-3.x python

Chubaka · 技术社区 · 5 年前

我正在做一些类似LeetCode的问题来练习,遇到了这个问题:

Given a list of currency pairs and the rates between these two currencies:
 
// USD = 6.4CNY, CNY = 0.13 EUR, EUR = 0.87 GBP, GBP = 89.4 INR
//
 
// Question: Input two currencies, return the rate

// Example: CNY, INR; return 10.1111
 
// Complexity?

想知道是否有Python 3的方法来解决这个问题?看起来像是广度优先的搜索问题。关于如何解决这个问题,有什么线索吗?谢谢!

评论:

我在这里看到了一个解决方案:

https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion

class Solution(object):
    
    def calcEquation(self, equations, values, queries):

        graph = {}
        
        def build_graph(equations, values):
            def add_edge(f, t, value):
                if f in graph:
                    graph[f].append((t, value))
                else:
                    graph[f] = [(t, value)]
            
            for vertices, value in zip(equations, values):
                f, t = vertices
                add_edge(f, t, value)
                add_edge(t, f, 1/value)
        
        def find_path(query):
            b, e = query
            
            if b not in graph or e not in graph:
                return -1.0
                
            q = collections.deque([(b, 1.0)])
            visited = set()
            
            while q:
                front, cur_product = q.popleft()
                if front == e:
                    return cur_product
                visited.add(front)
                for neighbor, value in graph[front]:
                    if neighbor not in visited:
                        q.append((neighbor, cur_product*value))
            
            return -1.0
        
        build_graph(equations, values)
        
        return [find_path(q) for q in queries]
    
s=Solution()

不知道如何测试此功能?

s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')

给我错误消息

Traceback (most recent call last):
  File "/home/coderpad/solution.py", line 45, in <module>
    s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')
  File "/home/coderpad/solution.py", line 39, in calcEquation
    build_graph(equations, values)
  File "/home/coderpad/solution.py", line 15, in build_graph
    f, t = vertices
ValueError: not enough values to unpack (expected 2, got 1)

0 回复 | 直到 5 年前

Emma 5 年前

我想这会奏效,但你不需要 values 变量在这里,因为它们已经在 equations .

在这里,我们使用 re.findall() 为了得到这三个所需的字符串(货币和比率),然后我们循环:

import collections
import re


class Solution:
    def calcEquation(self, equations, values, queries):
        memo = collections.defaultdict(dict)
        for equation in equations:
            num, val, den = re.findall(
                r'^\s*([A-Z]{3})\s*=\s*([0-9.]+)\s*([A-Z]{3})\s*$', equation)[0]

            val = float(val)
            memo[num][num] = memo[den][den] = 1.
            memo[num][den] = val
            memo[den][num] = 1 / val

        for key in memo:
            for val in memo[key]:
                for i in memo[key]:
                    memo[val][i] = memo[val][key] * memo[key][i]

        return [memo[num].get(den, -1.) for num, den in queries]


equations = ['USD = 6.4CNY', 'CNY = 0.13 EUR', 'EUR = 0.87 GBP', 'GBP = 89.4 INR']
values = [6.4, 0.13, 0.87, 89.4]
queries = [["USD", "CNY"], ["CNY", "EUR"], ["EUR", "GBP"], ["GBP", "INR"]]

print(Solution().calcEquation(equations, queries))

从技术上讲,您不必手动添加 价值观 ,如果你不想。我们可以安全地删除 价值观 变量:

import collections
import re


class Solution:
    def calcEquation(self, equations, queries):
        memo = collections.defaultdict(dict)
        for equation in equations:
            num, val, den = re.findall(
                r'^\s*([A-Z]{3})\s*=\s*([0-9.]+)\s*([A-Z]{3})\s*$', equation)[0]

            val = float(val)
            memo[num][num] = memo[den][den] = 1.
            memo[num][den] = val
            memo[den][num] = 1 / val

        for key in memo:
            for val in memo[key]:
                for i in memo[key]:
                    memo[val][i] = memo[val][key] * memo[key][i]

        return [memo[num].get(den, -1.) for num, den in queries]


equations = ['USD = 6.4CNY', 'CNY = 0.13 EUR', 'EUR = 0.87 GBP', 'GBP = 89.4 INR']
queries = [["USD", "CNY"], ["CNY", "EUR"], ["EUR", "GBP"], ["GBP", "INR"]]

print(Solution().calcEquation(equations, queries))

输出

[6.399999999999987, 0.12999999999999973, 0.8699999999999983, 89.39999999999993]

RegEx电路

jex.im 可视化正则表达式:

如果你想简化/更新/探索表达式,它在右上角的面板上进行了解释 regex101.com 。您可以查看匹配步骤或在中进行修改 this debugger link 如果你有兴趣的话。调试器演示了如何 a RegEx engine 可能会逐步消耗一些示例输入字符串,并执行匹配过程。