ruby - Ruby 中的回溯和组合电子学问题
问题描述
所以我一直在尝试解决这个问题,并且有点坚持使用回溯来实现它,并且真的很想了解我在这里做错了什么。我怀疑我的问题与方法中通过引用传递的数组有关,但似乎无法解决。任何帮助表示赞赏。这是在采访中被问到的,我正在尝试自己解决。
这是问题:
卡片有套件和重复时间。给定一张卡片列表和输出大小,返回一个卡片列表
(所有相同的字母或所有不同的字母)&(所有相同的长度或所有不同的字母长度)。
exaple1:
input: ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
output: ['X', 'YY', 'ZZZ']
-------------
example2:
input: ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX'], 3
output: ['Y', 'Z', 'X']
-------------
example3:
input: ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
output: ['X', 'YY', 'ZZZ']
我的算法如下:
- 调用一个辅助方法,如果存在这样的组合,则返回该组合
- 辅助方法获取卡片列表和输出中所需的卡片数量
- 基本情况:如果 count 为 0,则返回 true 和空数组(意味着我们没有更多卡片可供选择)
- 遍历每张卡片
- 找到计数的组合 - 1 张牌,当前牌被选中(递归)
- 如果找到组合,请检查当前卡以确保可以将其添加到当前组合并返回
- 如果您遍历了所有卡片并且找不到组合,则返回 false 并返回空数组
def unique_cards(cards, count)
can, picked_cards = _unique_cards(cards, count)
puts can ? picked_cards : false
end
def _unique_cards(cards, count)
return [true, []] if count == 0
cards.each do |card|
card_length = card.length
card_type = card[0]
remaining_cards = cards - [card]
can, selected_cards = _unique_cards(remaining_cards, count - 1)
if can
can_be_added = (selected_cards.all? { |c1| c1.length == card_length } || selected_cards.all? { |c1| c1[0] == card_type }) && (selected_cards.all? { |c1| c1.length != card_length } || selected_cards.all? { |c1| c1[0] != card_type })
if can_be_added
selected_cards << card
return [true, selected_cards]
end
end
end
return [false, []]
end
解决方案
require 'set'
def find_em(arr, n)
arr.combination(n)
.select do |a|
[1, n].include?(a.map { |s| s[0] }.uniq.size) &&
[1, n].include?(a.map(&:size).uniq.size)
end.uniq(&:to_set)
end
find_em ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX', 'Y'], 3
#=> [["Y", "Y", "Y"], ["Y", "Z", "X"]]
find_em ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
#=> [["X", "YY", "ZZZ"]]
find_em ['X', 'Y', 'YY', 'ZZ', 'ZZ'], 3
#=> []
在第一个示例中,如果没有.uniq(&:to_set)
我们将获得
find_em ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX', 'Y'], 3
#=> [["Y", "Y", "Y"], ["Y", "Z", "X"], ["Y", "Z", "X"], ["Z", "X", "Y"]]
推荐阅读
- elasticsearch - 提示如何使用 Logstash 加速从 SQL Server 到 ElasticSearch Index 的数据流,仅给定 1 个工作人员
- swift - UICollectionView Swift中的对齐和两行水平滚动
- scala - 如何在 Akka-http 中动态设置请求大小限制
- jhipster - 使用 JHipster 的微前端架构
- php - Yii2:如何将默认动作设置到控制器中
- continuous-integration - 我可以在成功构建 travis CI 后运行脚本吗?
- javascript - 为反应中的每个单词添加背景
- javascript - 子类别不会显示为父类别
- database - 如何找到与 Neo4j 最相似的节点
- git - 如何更改 Jenkins 管道脚本中的默认超时以克隆 git repo