处理交易列表的算法
Algorithms to process a list of transactions
这是我在为 Trading/Payment 服务公司做 SWE 实习 OA 时经常遇到的一类问题：给定“Action-Customer ID-Transaction ID-Amount”形式的交易列表，我们是要求处理它们，return 需要采取的行动列表或剩余金额。
这是一个具体的例子。输入是一个字符串列表，格式为“Action-Order ID-Price-Amount-Buy/Sell”，只有 2 个动作 SUB（提交）和 CXL（取消）。
- 对于买入，价格越高优先，对于卖出，价格越低优先。如果对于相同的买入或卖出类别，价格相似，则较早出现的字符串具有较高的优先级。
- 如果买单价格>=卖单价格，则两单匹配，Amount = min(Amount of Sell, Amount of Buy)，据此决定买入或卖出。
- 如果订单已经成交，则不会被取消。
- 如果 CXL 操作中的订单 ID 不存在，则不会有任何效果（无错误）。
我们被要求return要执行的操作列表，输出应该是具有以下格式的字符串列表：“Order ID-Buy/Sell-Amount to Buy/Sell”
输入输出示例：
输入：[“SUB-hghg-10-400-B”、“SUB-abab-15-500-B”、“SUB-abcd-10-400-S”]
输出：["abcd-S-400"]
解释：“abab”的买入价比“hghg”高，尽管它来得晚，所以它会被先处理。 abab 的数量 = 500，abcd 的数量 = 400 => 数量 = 400
输入：[“SUB-hghg-10-400-B”，“CXL-hghg”]
输出：[]
解释：什么都不做，因为订单在成交前被取消了。
我已经尝试使用散列映射来解决这个问题，但它对我来说太复杂了。之前我也遇到过类似的问题，但不同的是，无论订单是否成交，Cancel都会删除订单，此时我使用LinkedList来跟踪订单。
我想问问有没有通用的方法可以优化解决这类问题。逛了一段时间的LeetCode，练习了一些Medium题型，没遇到过这种题型。如果有什么典型的数据结构可以有效地存储每个订单的信息，我也想知道。我还在互联网上搜索了一些关键字，如算法交易、处理算法 payments/transactions，但我还没有找到任何有用的东西。非常感谢任何帮助！
非常感谢您阅读我冗长的 post。
那么您的输入是一系列提交的订单和取消，您的输出是订单匹配时发生的一系列交易，对吗？
我会按如下方式解决问题：创建一个订单簿数据结构，其中包含所有未结（不匹配）的订单，分别买卖，按价格排序。
Init: 订单簿当然初始化为空。也将结果交易列表初始化为空。
循环：然后将传入的请求（提交或取消）一一处理并应用到订单簿中。这会将订单添加到账簿中，或者订单与一个或多个其他订单相匹配，并生成新的交易。将生成的交易附加到您的交易列表。
基本上就是这样。但是，请注意，将新订单与图书相匹配并非易事。账簿中的一笔订单可能只被部分撮合而保留在账簿中，或者新的订单只会被部分撮合，剩余的金额必须添加到账簿中。我建议为单个步骤编写单元测试，以确保您的订单按预期排序和匹配。
这是我在为 Trading/Payment 服务公司做 SWE 实习 OA 时经常遇到的一类问题：给定“Action-Customer ID-Transaction ID-Amount”形式的交易列表，我们是要求处理它们，return 需要采取的行动列表或剩余金额。
这是一个具体的例子。输入是一个字符串列表，格式为“Action-Order ID-Price-Amount-Buy/Sell”，只有 2 个动作 SUB（提交）和 CXL（取消）。
- 对于买入，价格越高优先，对于卖出，价格越低优先。如果对于相同的买入或卖出类别，价格相似，则较早出现的字符串具有较高的优先级。
- 如果买单价格>=卖单价格，则两单匹配，Amount = min(Amount of Sell, Amount of Buy)，据此决定买入或卖出。
- 如果订单已经成交，则不会被取消。
- 如果 CXL 操作中的订单 ID 不存在，则不会有任何效果（无错误）。
我们被要求return要执行的操作列表，输出应该是具有以下格式的字符串列表：“Order ID-Buy/Sell-Amount to Buy/Sell”
输入输出示例：
输入：[“SUB-hghg-10-400-B”、“SUB-abab-15-500-B”、“SUB-abcd-10-400-S”]
输出：["abcd-S-400"]
解释：“abab”的买入价比“hghg”高，尽管它来得晚，所以它会被先处理。 abab 的数量 = 500，abcd 的数量 = 400 => 数量 = 400
输入：[“SUB-hghg-10-400-B”，“CXL-hghg”]
输出：[]
解释：什么都不做，因为订单在成交前被取消了。
我已经尝试使用散列映射来解决这个问题，但它对我来说太复杂了。之前我也遇到过类似的问题，但不同的是，无论订单是否成交，Cancel都会删除订单，此时我使用LinkedList来跟踪订单。
我想问问有没有通用的方法可以优化解决这类问题。逛了一段时间的LeetCode，练习了一些Medium题型，没遇到过这种题型。如果有什么典型的数据结构可以有效地存储每个订单的信息，我也想知道。我还在互联网上搜索了一些关键字，如算法交易、处理算法 payments/transactions，但我还没有找到任何有用的东西。非常感谢任何帮助！
非常感谢您阅读我冗长的 post。
那么您的输入是一系列提交的订单和取消，您的输出是订单匹配时发生的一系列交易，对吗？
我会按如下方式解决问题：创建一个订单簿数据结构，其中包含所有未结（不匹配）的订单，分别买卖，按价格排序。
Init: 订单簿当然初始化为空。也将结果交易列表初始化为空。
循环：然后将传入的请求（提交或取消）一一处理并应用到订单簿中。这会将订单添加到账簿中，或者订单与一个或多个其他订单相匹配，并生成新的交易。将生成的交易附加到您的交易列表。
基本上就是这样。但是，请注意，将新订单与图书相匹配并非易事。账簿中的一笔订单可能只被部分撮合而保留在账簿中，或者新的订单只会被部分撮合，剩余的金额必须添加到账簿中。我建议为单个步骤编写单元测试，以确保您的订单按预期排序和匹配。